Pavel Pudlák

According to our database1, Pavel Pudlák
  • authored at least 142 papers between 1975 and 2017.
  • has a "Dijkstra number"2 of four.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

2017
Partition Expanders.
Theory Comput. Syst., 2017

Representations of Monotone Boolean Functions by Linear Programs.
Electronic Colloquium on Computational Complexity (ECCC), 2017

A note on monotone real circuits.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Random formulas, monotone circuits, and interpolation.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Petr Hajek, 1940-2016.
Bulletin of the EATCS, 2017

The complexity of proving that a graph is Ramsey.
Combinatorica, 2017

Tighter Hard Instances for PPSZ.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Random Resolution Refutations.
Proceedings of the 32nd Computational Complexity Conference, 2017

Representations of Monotone Boolean Functions by Linear Programs.
Proceedings of the 32nd Computational Complexity Conference, 2017

2016
Backtracking Based k-SAT Algorithms.
Encyclopedia of Algorithms, 2016

Random resolution refutations.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Tighter Hard Instances for PPSZ.
CoRR, 2016

2015
On the Entropy of Locally-Independent Bernoulli Trials.
CoRR, 2015

On the complexity of finding falsifying assignments for Herbrand disjunctions.
Arch. Math. Log., 2015

The Space Complexity of Cutting Planes Refutations.
Proceedings of the 30th Conference on Computational Complexity, 2015

2014
Parity Games and Propositional Proofs.
ACM Trans. Comput. Log., 2014

Partition Expanders.
Electronic Colloquium on Computational Complexity (ECCC), 2014

The space complexity of cutting planes refutations.
Electronic Colloquium on Computational Complexity (ECCC), 2014

On the complexity of finding falsifying assignments for Herbrand disjunctions.
CoRR, 2014

Partition Expanders.
CoRR, 2014

Partition Expanders.
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

2013
Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates.
IEEE Trans. Information Theory, 2013

Parity Games and Propositional Proofs.
Electronic Colloquium on Computational Complexity (ECCC), 2013

The complexity of proving that a graph is Ramsey.
Electronic Colloquium on Computational Complexity (ECCC), 2013

The complexity of proving that a graph is Ramsey
CoRR, 2013

Linear tree codes and the problem of explicit constructions.
CoRR, 2013

Parity Games and Propositional Proofs.
Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

The Complexity of Proving That a Graph Is Ramsey.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

An Upper Bound for a Communication Game Related to Time-Space Tradeoffs.
Proceedings of the Mathematics of Paul Erdős I, 2013

Logical Foundations of Mathematics and Computational Complexity - A Gentle Introduction.
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.
Inf. Process. Lett., 2012

Alternating minima and maxima, Nash equilibria and Bounded Arithmetic.
Ann. Pure Appl. Logic, 2012

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011
A lower bound on the size of resolution proofs of the Ramsey theorem.
Electronic Colloquium on Computational Complexity (ECCC), 2011

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates.
Electronic Colloquium on Computational Complexity (ECCC), 2011

Pseudorandom generators for group products: extended abstract.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010
On convex complexity measures.
Theor. Comput. Sci., 2010

Some constructive bounds on Ramsey numbers.
J. Comb. Theory, Ser. B, 2010

Pseudorandom Generators for Group Products.
Electronic Colloquium on Computational Complexity (ECCC), 2010

On the complexity of circuit satisfiability.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

On extracting computations from propositional proofs (a survey).
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

2009
On convex complexity measures.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Quantum deduction rules.
Ann. Pure Appl. Logic, 2009

2008
Backtracking Based k-SAT Algorithms.
Proceedings of the Encyclopedia of Algorithms, 2008

Fragments of bounded arithmetic and the lengths of proofs.
J. Symb. Log., 2008

Twelve Problems in Proof Complexity.
Proceedings of the Computer Science, 2008

Exponential Separation of Quantum and Classical Non-interactive Multi-party Communication Complexity.
Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007
Quantum deduction rules.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity.
Electronic Colloquium on Computational Complexity (ECCC), 2007

2006
Gödel and computations: a 100th anniversary retrospective.
SIGACT News, 2006

Lower bounds for circuits with MOD_m gates.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

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

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

Godel and Computations (Abstract).
Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

On Search Problems in Complexity Theory and in Logic (Abstract).
Proceedings of the Algorithms and Complexity, 6th Italian Conference, 2006

2005
An improved exponential-time algorithm for k-SAT.
J. ACM, 2005

A nonlinear bound on the number of wires in bounded depth circuits
Electronic Colloquium on Computational Complexity (ECCC), 2005

Bounded-depth circuits: separating wires from gates.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

2004
Circuit lower bounds and linear codes
Electronic Colloquium on Computational Complexity (ECCC), 2004

2003
On reducibility and symmetry of disjoint NP pairs.
Theor. Comput. Sci., 2003

Parallel strategies.
J. Symb. Log., 2003

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

A note on monotone complexity and the rank of matrices.
Inf. Process. Lett., 2003

An Application of Hindman's Theorem to a Problem on Communication Complexity.
Combinatorics, Probability & Computing, 2003

2002
Monotone simulations of non-monotone proofs.
J. Comput. Syst. Sci., 2002

Monotone complexity and the rank of matrices
Electronic Colloquium on Computational Complexity (ECCC), 2002

Cycles of Nonzero Elements in Low Rank Matrices.
Combinatorica, 2002

2001
Gust Editor's Foreword.
J. Comput. Syst. Sci., 2001

Complexity Theory and Genetics: The Computational Power of Crossing Over.
Inf. Comput., 2001

On reducibility and symmetry of disjoint NP-pairs
Electronic Colloquium on Computational Complexity (ECCC), 2001

On the computational content of intuitionistic propositional proofs.
Ann. Pure Appl. Logic, 2001

On Reducibility and Symmetry of Disjoint NP-Pairs.
Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

Monotone Simulations of Nonmonotone Proofs.
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000
Some structural properties of low-rank matrices related to computational complexity.
Theor. Comput. Sci., 2000

Proofs as Games.
The American Mathematical Monthly, 2000

A note on the use of determinant for proving lower bounds on the size of linear circuits.
Inf. Process. Lett., 2000

Monotone simulations of nonmonotone propositional proofs
Electronic Colloquium on Computational Complexity (ECCC), 2000

A lower bound for DLL algorithms for k-SAT (preliminary version).
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1999
Satisfiability Coding Lemma.
Chicago J. Theor. Comput. Sci., 1999

Lower Bounds for the Polynomial Calculus and the Gröbner Basis Algorithm.
Computational Complexity, 1999

A Note on Applicability of the Incompleteness Theorem to Human Mind.
Ann. Pure Appl. Logic, 1999

1998
Some Consequences of Cryptographical Conjectures for S12 and EF.
Inf. Comput., 1998

A Note On the Use of Determinant for Proving Lower Bounds on the Size of Linear Circuits
Electronic Colloquium on Computational Complexity (ECCC), 1998

Computing Boolean Functions by Polynomials and Threshold Circuits.
Computational Complexity, 1998

Satisfiability - Algorithms and Logic.
Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

An Improved Exponential-Time Algorithm for k-SAT.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997
On the Computational Power of Depth-2 Circuits with Threshold and Modulo Gates.
Theor. Comput. Sci., 1997

Boolean Circuits, Tensor Ranks, and Communication Complexity.
SIAM J. Comput., 1997

Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations.
J. Symb. Log., 1997

Some structural properties of low rank matrices related to computational complexity
Electronic Colloquium on Computational Complexity (ECCC), 1997

Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm
Electronic Colloquium on Computational Complexity (ECCC), 1997

On Sparse Parity Check Matrices.
Des. Codes Cryptography, 1997

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

Satisfiability Coding Lemma.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996
Algebraic models of computation and interpolation for algebraic proof systems.
Proceedings of the Proof Complexity and Feasible Arithmetics, 1996

On Sparse Parity Chack Matrices (Extended Abstract).
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.
Random Struct. Algorithms, 1995

An Upper Bound for a Communication Game Related to Time-Space Tradeoffs
Electronic Colloquium on Computational Complexity (ECCC), 1995

Top-Down Lower Bounds for Depth-Three Circuits.
Computational Complexity, 1995

On Computing Boolean Functions by Sparse Real Polynomials.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994
Superconcentrators of Depths 2 and 3; Odd Levels Help (Rarely).
J. Comput. Syst. Sci., 1994

On the Computational Power of Depth 2 Circuits with Threshold and Modulo Gates
Electronic Colloquium on Computational Complexity (ECCC), 1994

An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle
Electronic Colloquium on Computational Complexity (ECCC), 1994

Complexity Theory and Genetics (extended abstract)
Electronic Colloquium on Computational Complexity (ECCC), 1994

Some combinatorial-algebraic problems from complexity theory.
Discrete Mathematics, 1994

Communication in Bounded Depth Circuits.
Combinatorica, 1994

On the computational power of depth 2 circuits with threshold and modulo gates.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Some Consequences of Cryptographical Conjectures for S_2^1 and EF.
Proceedings of the Logical and Computational Complexity. Selected Papers. Logic and Computational Complexity, 1994

Unexpected Upper Bounds on the Complexity of Some Communication Games.
Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

Lower Bound on Hilbert's Nullstellensatz and propositional proofs
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.
Proceedings of the Computer Science Logic, 8th International Workshop, 1994

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

1993
On shifting networks.
Theor. Comput. Sci., 1993

Threshold Circuits of Bounded Depth.
J. Comput. Syst. Sci., 1993

Modified ranks of tensors and the size of circuits.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Top-Down Lower Bounds for Depth 3 Circuits
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

AC0 Circuit Complexity.
Proceedings of the Fundamentals of Computation Theory, 9th International Symposium, 1993

Metamathematics of First-Order Arithmetic.
Perspectives in mathematical logic, Springer, ISBN: 978-3-540-63648-9, 1993

1992
A combinatorial approach to complexity.
Combinatorica, 1992

Exponential Lower Bounds for the Pigeonhole Principle
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

1991
Bounded Arithmetic and the Polynomial Hierarchy.
Ann. Pure Appl. Logic, 1991

1990
Lower Bounds to the Complexity of Symmetric Boolean Functions.
Theor. Comput. Sci., 1990

Quantified propositional calculi and fragments of bounded arithmetic.
Math. Log. Q., 1990

Interactive Computations of Optimal Solutions.
Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

Ramsey's Theorem in Bounded Arithmetic.
Proceedings of the Computer Science Logic, 4th Workshop, 1990

1989
Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations.
J. Symb. Log., 1989

On the structure of initial segments of models of arithmetic.
Arch. Math. Log., 1989

On the Communication Complexity of Planarity.
Proceedings of the Fundamentals of Computation Theory, 1989

Propositional Provability and Models of Weak Arithmetic.
Proceedings of the CSL '89, 1989

1988
The number of proof lines and the size of proofs in first order logic.
Arch. Math. Log., 1988

Graph Complexity.
Acta Inf., 1988

1987
Threshold circuits of bounded depth
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

1986
Two lower bounds for branching programs
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

1985
Elementary Extensions of Models of the Alternative Set Theory.
Math. Log. Q., 1985

Cuts, Consistency Statements and Interpretations.
J. Symb. Log., 1985

1984
Models of the Alternative Set Theory.
J. Symb. Log., 1984

A Lower Bound on Complexity of Branching Programs (Extended Abstract).
Proceedings of the Mathematical Foundations of Computer Science 1984, 1984

New Lower Bound for Polyhedral Membership Problem with an Application to Linear Programming.
Proceedings of the Mathematical Foundations of Computer Science 1984, 1984

1983
Bounds for Hodes-Specker theorem.
Proceedings of the Logic and Machines: Decision Problems and Complexity, 1983

1982
Partition theorems for systems of finite subsets of integers.
Discrete Mathematics, 1982

1979
Complexity in Mechanized Hypothesis Formation.
Theor. Comput. Sci., 1979

1975
Polynomially Complete Problems in the Logic of Automated Discovery.
Proceedings of the Mathematical Foundations of Computer Science 1975, 1975


  Loading...