Pavel Pudlák

Bull. Symb. Log., December, 2023

Bounds on Functionality and Symmetric Difference - Two Intriguing Graph Parameters.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2023

2022

On matrices potentially useful for tree codes.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2022

Extractors for Small Zero-Fixing Sources.

[BibT_eX]

[DOI]

Comb., 2022

Linear Branching Programs and Directional Affine Extractors.

[BibT_eX]

[DOI]

Svyatoslav Gryaznov

Navid Talebanfard

Proceedings of the 37th Computational Complexity Conference, 2022

2021

The canonical pairs of bounded depth Frege systems.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2021

2020

Santha-Vazirani sources, deterministic condensers and very strong extractors.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2020

2019

Random resolution refutations.

[BibT_eX]

[DOI]

Comput. Complex., 2019

2018

A note on monotone real circuits.

[BibT_eX]

[DOI]

Pavel Hrubes

Inf. Process. Lett., 2018

Proof Complexity (Dagstuhl Seminar 18051).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2018

Beating Brute Force for (Quantified) Satisfiability of Circuits of Bounded Treewidth.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

A wild model of linear arithmetic and discretely ordered modules.

[BibT_eX]

[DOI]

Petr Glivický

Mateus de Oliveira Oliveira

Math. Log. Q., 2017

Representations of Monotone Boolean Functions by Linear Programs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Random formulas, monotone circuits, and interpolation.

[BibT_eX]

[DOI]

Pavel Hrubes

Electron. Colloquium Comput. Complex., 2017

Petr Hajek, 1940-2016.

[BibT_eX]

[DOI]

Bull. EATCS, 2017

The complexity of proving that a graph is Ramsey.

[BibT_eX]

[DOI]

Comb., 2017

Incompleteness in the finite Domain.

[BibT_eX]

[DOI]

Bull. Symb. Log., 2017

Tighter Hard Instances for PPSZ.

[BibT_eX]

[DOI]

Dominik Scheder

Navid Talebanfard

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Backtracking Based k-SAT Algorithms.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

2015

On the Entropy of Locally-Independent Bernoulli Trials.

[BibT_eX]

[DOI]

CoRR, 2015

On the complexity of finding falsifying assignments for Herbrand disjunctions.

[BibT_eX]

[DOI]

Arch. Math. Log., 2015

2014

Parity Games and Propositional Proofs.

[BibT_eX]

[DOI]

Arnold Beckmann

ACM Trans. Comput. Log., 2014

Partition Expanders.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

The space complexity of cutting planes refutations.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

2013

Linear tree codes and the problem of explicit constructions.

[BibT_eX]

[DOI]

CoRR, 2013

An Upper Bound for a Communication Game Related to Time-Space Tradeoffs.

[BibT_eX]

[DOI]

Proceedings of the Mathematics of Paul Erdős I, 2013

Logical Foundations of Mathematics and Computational Complexity - A Gentle Introduction.

[BibT_eX]

[DOI]

Springer monographs in mathematics, Springer, ISBN: 978-3-319-00118-0, 2013

2012

A lower bound on the size of resolution proofs of the Ramsey theorem.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2012

Alternating minima and maxima, Nash equilibria and Bounded Arithmetic.

[BibT_eX]

[DOI]

Kristoffer Arnsfelt Hansen

Ann. Pure Appl. Log., 2012

2011

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates.

[BibT_eX]

[DOI]

Anna Gál

Emanuele Viola

Electron. Colloquium Comput. Complex., 2011

Pseudorandom generators for group products: extended abstract.

[BibT_eX]

[DOI]

Prajakta Nimbhorkar

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010

On convex complexity measures.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2010

Some constructive bounds on Ramsey numbers.

[BibT_eX]

[DOI]

Alexandr V. Kostochka

J. Comb. Theory, Ser. B, 2010

Pseudorandom Generators for Group Products.

[BibT_eX]

[DOI]

Prajakta Nimbhorkar

Electron. Colloquium Comput. Complex., 2010

On the complexity of circuit satisfiability.

[BibT_eX]

[DOI]

Ramamohan Paturi

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

On extracting computations from propositional proofs (a survey).

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

2008

Backtracking Based k-SAT Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Fragments of bounded arithmetic and the lengths of proofs.

[BibT_eX]

[DOI]

J. Symb. Log., 2008

Twelve Problems in Proof Complexity.

[BibT_eX]

[DOI]

Proceedings of the Computer Science, 2008

2007

Quantum deduction rules.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

2006

Gödel and computations: a 100th anniversary retrospective.

[BibT_eX]

[DOI]

SIGACT News, 2006

Lower bounds for circuits with MOD_m gates.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

Navin Goyal

Denis Thérien

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

06111 Abstracts Collection -- Complexity of Boolean Functions.

[BibT_eX]

[DOI]

Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

06111 Executive Summary -- Complexity of Boolean Functions.

[BibT_eX]

[DOI]

Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

Godel and Computations (Abstract).

[BibT_eX]

[DOI]

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

On Search Problems in Complexity Theory and in Logic (Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity, 6th Italian Conference, 2006

2005

An improved exponential-time algorithm for k-SAT.

[BibT_eX]

[DOI]

J. ACM, 2005

A nonlinear bound on the number of wires in bounded depth circuits

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Bounded-depth circuits: separating wires from gates.

[BibT_eX]

[DOI]

Denis Thérien

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

2004

Circuit lower bounds and linear codes

[BibT_eX]

[DOI]

Ramamohan Paturi

Electron. Colloquium Comput. Complex., 2004

2003

On reducibility and symmetry of disjoint NP pairs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

Parallel strategies.

[BibT_eX]

[DOI]

J. Symb. Log., 2003

Erratum to: "A note on monotone complexity and the rank of matrices": [Information Processing Letters 87 (2003) 321-326].

[BibT_eX]

[DOI]

Anna Gál

Inf. Process. Lett., 2003

A note on monotone complexity and the rank of matrices.

[BibT_eX]

[DOI]

Anna Gál

Inf. Process. Lett., 2003

An Application of Hindman's Theorem to a Problem on Communication Complexity.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2003

2002

Monotone simulations of non-monotone proofs.

[BibT_eX]

[DOI]

Albert Atserias

J. Comput. Syst. Sci., 2002

Monotone complexity and the rank of matrices

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2002

Cycles of Nonzero Elements in Low Rank Matrices.

[BibT_eX]

[DOI]

Comb., 2002

2001

Gust Editor's Foreword.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2001

Complexity Theory and Genetics: The Computational Power of Crossing Over.

[BibT_eX]

[DOI]

Inf. Comput., 2001

On the computational content of intuitionistic propositional proofs.

[BibT_eX]

[DOI]

Samuel R. Buss

Ann. Pure Appl. Log., 2001

Monotone Simulations of Nonmonotone Proofs.

[BibT_eX]

[DOI]

Albert Atserias

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

Some structural properties of low-rank matrices related to computational complexity.

[BibT_eX]

[DOI]

Bruno Codenotti

Giovanni Resta

Theor. Comput. Sci., 2000

Proofs as Games.

[BibT_eX]

[DOI]

Am. Math. Mon., 2000

A note on the use of determinant for proving lower bounds on the size of linear circuits.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2000

Monotone simulations of nonmonotone propositional proofs

[BibT_eX]

[DOI]

Albert Atserias

Electron. Colloquium Comput. Complex., 2000

A lower bound for DLL algorithms for k-SAT (preliminary version).

[BibT_eX]

[DOI]

Russell Impagliazzo

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1999

Satisfiability Coding Lemma.

[BibT_eX]

[DOI]

Ramamohan Paturi

Francis Zane

Chic. J. Theor. Comput. Sci., 1999

Lower Bounds for the Polynomial Calculus and the Gröbner Basis Algorithm.

[BibT_eX]

[DOI]

Russell Impagliazzo

Comput. Complex., 1999

A Note on Applicability of the Incompleteness Theorem to Human Mind.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 1999

1998

Some Consequences of Cryptographical Conjectures for S12 and EF.

[BibT_eX]

[DOI]

Inf. Comput., 1998

Computing Boolean Functions by Polynomials and Threshold Circuits.

[BibT_eX]

[DOI]

Matthias Krause

Comput. Complex., 1998

Satisfiability - Algorithms and Logic.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

1997

On the Computational Power of Depth-2 Circuits with Threshold and Modulo Gates.

[BibT_eX]

[DOI]

Matthias Krause

Theor. Comput. Sci., 1997

Boolean Circuits, Tensor Ranks, and Communication Complexity.

[BibT_eX]

[DOI]

SIAM J. Comput., 1997

Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations.

[BibT_eX]

[DOI]

J. Symb. Log., 1997

Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm

[BibT_eX]

[DOI]

Russell Impagliazzo

Electron. Colloquium Comput. Complex., 1997

On Sparse Parity Check Matrices.

[BibT_eX]

[DOI]

Hanno Lefmann

Des. Codes Cryptogr., 1997

Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting.

[BibT_eX]

[DOI]

Alexander A. Razborov

Comput. Complex., 1997

1996

Algebraic models of computation and interpolation for algebraic proof systems.

[BibT_eX]

[DOI]

Proceedings of the Proof Complexity and Feasible Arithmetics, 1996

On Sparse Parity Chack Matrices (Extended Abstract).

[BibT_eX]

[DOI]

Hanno Lefmann

Proceedings of the Computing and Combinatorics, Second Annual International Conference, 1996

1995

An Exponenetioal Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle.

[BibT_eX]

[DOI]

Alan R. Woods

Random Struct. Algorithms, 1995

An Upper Bound for a Communication Game Related to Time-Space Tradeoffs

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1995

Top-Down Lower Bounds for Depth-Three Circuits.

[BibT_eX]

[DOI]

Johan Håstad

Stasys Jukna

Comput. Complex., 1995

On Computing Boolean Functions by Sparse Real Polynomials.

[BibT_eX]

[DOI]

Matthias Krause

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994

Superconcentrators of Depths 2 and 3; Odd Levels Help (Rarely).

[BibT_eX]

[DOI]

Noga Alon

J. Comput. Syst. Sci., 1994

An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle

[BibT_eX]

[DOI]

Alan R. Woods

Electron. Colloquium Comput. Complex., 1994

Complexity Theory and Genetics (extended abstract)

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1994

Some combinatorial-algebraic problems from complexity theory.

[BibT_eX]

[DOI]

Discret. Math., 1994

Communication in Bounded Depth Circuits.

[BibT_eX]

[DOI]

Comb., 1994

Some Consequences of Cryptographical Conjectures for S_2^1 and EF.

[BibT_eX]

[DOI]

Proceedings of the Logical and Computational Complexity. Selected Papers. Logic and Computational Complexity, 1994

Unexpected Upper Bounds on the Complexity of Some Communication Games.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

Lower Bound on Hilbert's Nullstellensatz and propositional proofs

[BibT_eX]

[DOI]

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

How to Lie Without Being (Easily) Convicted and the Length of Proofs in Propositional Calculus.

[BibT_eX]

[DOI]

Samuel R. Buss

Proceedings of the Computer Science Logic, 8th International Workshop, 1994

Complexity Theory and Genetics.

[BibT_eX]

[DOI]

Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1993

On shifting networks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1993

Threshold Circuits of Bounded Depth.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1993

Modified ranks of tensors and the size of circuits.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Top-Down Lower Bounds for Depth 3 Circuits

[BibT_eX]

[DOI]

Johan Håstad

Stasys Jukna

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

AC0 Circuit Complexity.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 9th International Symposium, 1993

Metamathematics of First-Order Arithmetic.

[BibT_eX]

[DOI]

Petr Hájek

Perspectives in mathematical logic, Springer, ISBN: 978-3-540-63648-9, 1993

1992

A combinatorial approach to complexity.

[BibT_eX]

[DOI]

Comb., 1992

Exponential Lower Bounds for the Pigeonhole Principle

[BibT_eX]

[DOI]

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

1991

Bounded Arithmetic and the Polynomial Hierarchy.

[BibT_eX]

[DOI]

Gaisi Takeuti

Ann. Pure Appl. Log., 1991

1990

Lower Bounds to the Complexity of Symmetric Boolean Functions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1990

Quantified propositional calculi and fragments of bounded arithmetic.

[BibT_eX]

[DOI]

Math. Log. Q., 1990

Interactive Computations of Optimal Solutions.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

Ramsey's Theorem in Bounded Arithmetic.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 4th Workshop, 1990

1989

Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations.

[BibT_eX]

[DOI]

J. Symb. Log., 1989

On the structure of initial segments of models of arithmetic.

[BibT_eX]

[DOI]

Arch. Math. Log., 1989

On the Communication Complexity of Planarity.

[BibT_eX]

[DOI]

Pavol Duris

Proceedings of the Fundamentals of Computation Theory, 1989

Propositional Provability and Models of Weak Arithmetic.

[BibT_eX]

[DOI]

Proceedings of the CSL '89, 1989

1988

The number of proof lines and the size of proofs in first order logic.

[BibT_eX]

[DOI]

Arch. Math. Log., 1988

Graph Complexity.

[BibT_eX]

[DOI]

Acta Informatica, 1988

1986

Two lower bounds for branching programs

[BibT_eX]

[DOI]

Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

1985

Elementary Extensions of Models of the Alternative Set Theory.

[BibT_eX]

[DOI]

Antonín Sochor

Math. Log. Q., 1985

Cuts, Consistency Statements and Interpretations.

[BibT_eX]

[DOI]

J. Symb. Log., 1985

1984

Models of the Alternative Set Theory.

[BibT_eX]

[DOI]

Antonín Sochor

J. Symb. Log., 1984

A Lower Bound on Complexity of Branching Programs (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1984, 1984

New Lower Bound for Polyhedral Membership Problem with an Application to Linear Programming.

[BibT_eX]

[DOI]

Jaroslav Morávek

Proceedings of the Mathematical Foundations of Computer Science 1984, 1984

1983

Bounds for Hodes-Specker theorem.

[BibT_eX]

[DOI]

Proceedings of the Logic and Machines: Decision Problems and Complexity, 1983

1982

Partition theorems for systems of finite subsets of integers.

[BibT_eX]

[DOI]

Discret. Math., 1982

1979

Complexity in Mechanized Hypothesis Formation.

[BibT_eX]

[DOI]

Frederick N. Springsteel

Theor. Comput. Sci., 1979

1975

Polynomially Complete Problems in the Logic of Automated Discovery.

[BibT_eX]

[DOI]