Pavel Pudlák
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Pavel Pudlák has a total of 64 co-authors. Here are the top co-authors by number of shared publications:
- Sam Buss
Department of Mathematics University of California San Diego
4 shared publications - Jiří Sgall
Computer Science Institute Faculty of Mathematics and Physics of Charles University Prague Czech Republic
3 shared publications Petr Hájek
3 shared publications- Ramamohan Paturi
University of California
2 shared publications - Russell Impagliazzo
Department of Computer Science, University of California San Diego, La Jolla, USA
2 shared publications - Alexander Razborov
Steklov Mathematical Institute
1 shared publication
Latest Publications
- 23 September 2023
- Published by Springer Nature
- p. 305-318
Bounds on Functionality and Symmetric Difference – Two Intriguing Graph Parameters
- 23 September 2023
- Published by Springer Nature
- p. 305-318
Bounds on Functionality and Symmetric Difference – Two Intriguing Graph Parameters
- Open Access
- 1 June 2023
- Published by Cambridge University Press (CUP) in The Bulletin of Symbolic Logic
- Vol. 29 (4) , 657-660
Logic, Automata, and Computational Complexity: The Works Of Stephen A. Cook. Edited by Bruce M. Kapron, ACM Books, vol. 43. Association for Computing Machinery, New York, xxvi + 398 pp.—therein: - Michelle Waitzman. Stephen Cook: Complexity’s Humble Hero, pp. 3–28. - Bruce M. Kapron and Stephen A. Cook, ACM Interview of Stephen A. Cook by Bruce M. Kapron, pp. 29–44. - Stephen A. Cook, Overview of Computational Complexity, pp. 47–70. - Christos H. Papadimitriou, Cook’s NP-Completeness Paper and the Dawn of the New Theory, pp. 73–82. - Jan Krajíček, The Cook–Reckhow Definition, pp. 83–94. - Sam Buss, Polynomially Verifiable Arithmetic, pp. 95–106. - Paul Beame and Pierre McKenzie, Towards a Complexity Theory of Parallel Computation, pp. 107–126. - Nicholas Pippenger, Computation with Limited Space, pp. 127–140. - Stephen A. Cook, The Complexity of Theorem-Proving Procedures, pp. 143–152. - Stephen A. Cook, Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, pp. 153–172. - Stephen A. Cook and Robert A. Reckhow, The Relative Efficiency of Propositional Proof Systems, pp. 173–192. - Stephen A. Cook, Feasibly Constructive Proofs and the Propositional Calculus (Preliminary Version), pp. 193–218. - Stephen A. Cook, Towards a Complexity Theory of Synchronous Parallel Computation, pp. 219–244. - Allan Borodin and Stephen A. Cook, A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation, pp. 245–260. - Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, and Rahul Santhanam, Pebbles and Branching Programs for Tree Evaluation, pp. 261–318. - Bruce M. Kapron, Cook’s Berkeley Notes, pp. 321–324. - Stephen A. Cook, A Survey of Classes of Primitive Recursive Functions, pp. 325–336.
Theorem (Steel). There is a normal tree T of length Θ + 1 on M below its least Woodin cardinal such that the last model of T is M∞ and T Θ ∈ L(R). Normalizing iteration trees also plays a role in the author's efforts to analyze HOD in larger models of determinacy. Another major contribution of HOD as a Core Model is an adaptation of this direct limit argument to identify HOD L[x,G] for a real x such that L[x] "OD-determinacy" and G which is L[x]-generic for Col (, < κ), where κ is the least inaccessible cardinal of L[x]. The authors show HOD L[x,G] = L[M∞, Λ], where M∞ is the direct limit of all iterates of M 1 which are countable in L[x, G] and Λ is a portion of the iteration strategy for M∞. The generic G ensures that the last model of a coiteration of a pair of countable, M 1-like mice in L[x] is countable in L[x, G]. The inability to prove the last model of this coiteration is countable in L[x] inhibits the authors from resolving the more natural goal of characterizing HOD L[x]. The analysis of HOD L(R) required the property of mouse capturing (MC): If x and y are countable, transitive sets, x ⊆ y, and x is ordinal definable from parameters in y ∪ {y}, then there is a y-premouse M with an 1-iteration strategy such that x ∈ M. The last chapter of the paper considers the problem of analyzing HOD from the axiom AD +. It is open whether AD + alone implies MC , but it does under certain smallness assumptions. For example, Sargsyan proves MC in the minimal model of AD R + "Θ is regular" in Hod Mice and the Mouse Set Conjecture, Memoirs of the American Mathematical Society, vol. 236 (2015). In this context, HOD can be constructed as a fine structural model in which extenders are added while simultaneously coding iteration strategies for initial segments of the model built so far. Models of this form are now referred to as hod mice. The study of HOD below the minimal model of AD R + "Θ is regular" proceeds inductively by associating each pointclass Γ of Wadge rank equal to some level Θα in the Solovay sequence to a hod mouse with an iteration strategy in this pointclass, and identifying HOD|Θα as a direct limit of this hod mouse. A different technique is needed if Θα is the largest Suslin cardinal below Θ α+1. In this case, a set of Wadge rank Θα cannot code a new iteration strategy for a hod mouse, but Sargsyan and Trang showed a strategy restricted to short trees can have Wadge rank Θα and characterized HOD in the minimal model of AD + + "The largest Suslin cardinal exists and is in the Solovay sequence." Performing an analysis of HOD from AD + without any smallness assumption is a central question of descriptive inner model theory. Towards this goal, Steel proves a comparison lemma for hod mice in A Comparison Process for Mouse Pairs, Lecture Notes in Logic, vol. 51 (2022).
- 1 June 2023
- Published by Cambridge University Press (CUP) in The Bulletin of Symbolic Logic
- Vol. 29 (4) , 657-660
Open AccessLogic, Automata, and Computational Complexity: The Works Of Stephen A. Cook. Edited by Bruce M. Kapron, ACM Books, vol. 43. Association for Computing Machinery, New York, xxvi + 398 pp.—therein: - Michelle Waitzman. Stephen Cook: Complexity’s Humble Hero, pp. 3–28. - Bruce M. Kapron and Stephen A. Cook, ACM Interview of Stephen A. Cook by Bruce M. Kapron, pp. 29–44. - Stephen A. Cook, Overview of Computational Complexity, pp. 47–70. - Christos H. Papadimitriou, Cook’s NP-Completeness Paper and the Dawn of the New Theory, pp. 73–82. - Jan Krajíček, The Cook–Reckhow Definition, pp. 83–94. - Sam Buss, Polynomially Verifiable Arithmetic, pp. 95–106. - Paul Beame and Pierre McKenzie, Towards a Complexity Theory of Parallel Computation, pp. 107–126. - Nicholas Pippenger, Computation with Limited Space, pp. 127–140. - Stephen A. Cook, The Complexity of Theorem-Proving Procedures, pp. 143–152. - Stephen A. Cook, Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, pp. 153–172. - Stephen A. Cook and Robert A. Reckhow, The Relative Efficiency of Propositional Proof Systems, pp. 173–192. - Stephen A. Cook, Feasibly Constructive Proofs and the Propositional Calculus (Preliminary Version), pp. 193–218. - Stephen A. Cook, Towards a Complexity Theory of Synchronous Parallel Computation, pp. 219–244. - Allan Borodin and Stephen A. Cook, A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation, pp. 245–260. - Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, and Rahul Santhanam, Pebbles and Branching Programs for Tree Evaluation, pp. 261–318. - Bruce M. Kapron, Cook’s Berkeley Notes, pp. 321–324. - Stephen A. Cook, A Survey of Classes of Primitive Recursive Functions, pp. 325–336.
Theorem (Steel). There is a normal tree T of length Θ + 1 on M below its least Woodin cardinal such that the last model of T is M∞ and T Θ ∈ L(R). Normalizing iteration trees also plays a role in the author's efforts to analyze HOD in larger models of determinacy. Another major contribution of HOD as a Core Model is an adaptation of this direct limit argument to identify HOD L[x,G] for a real x such that L[x] "OD-determinacy" and G which is L[x]-generic for Col (, < κ), where κ is the least inaccessible cardinal of L[x]. The authors show HOD L[x,G] = L[M∞, Λ], where M∞ is the direct limit of all iterates of M 1 which are countable in L[x, G] and Λ is a portion of the iteration strategy for M∞. The generic G ensures that the last model of a coiteration of a pair of countable, M 1-like mice in L[x] is countable in L[x, G]. The inability to prove the last model of this coiteration is countable in L[x] inhibits the authors from resolving the more natural goal of characterizing HOD L[x]. The analysis of HOD L(R) required the property of mouse capturing (MC): If x and y are countable, transitive sets, x ⊆ y, and x is ordinal definable from parameters in y ∪ {y}, then there is a y-premouse M with an 1-iteration strategy such that x ∈ M. The last chapter of the paper considers the problem of analyzing HOD from the axiom AD +. It is open whether AD + alone implies MC , but it does under certain smallness assumptions. For example, Sargsyan proves MC in the minimal model of AD R + "Θ is regular" in Hod Mice and the Mouse Set Conjecture, Memoirs of the American Mathematical Society, vol. 236 (2015). In this context, HOD can be constructed as a fine structural model in which extenders are added while simultaneously coding iteration strategies for initial segments of the model built so far. Models of this form are now referred to as hod mice. The study of HOD below the minimal model of AD R + "Θ is regular" proceeds inductively by associating each pointclass Γ of Wadge rank equal to some level Θα in the Solovay sequence to a hod mouse with an iteration strategy in this pointclass, and identifying HOD|Θα as a direct limit of this hod mouse. A different technique is needed if Θα is the largest Suslin cardinal below Θ α+1. In this case, a set of Wadge rank Θα cannot code a new iteration strategy for a hod mouse, but Sargsyan and Trang showed a strategy restricted to short trees can have Wadge rank Θα and characterized HOD in the minimal model of AD + + "The largest Suslin cardinal exists and is in the Solovay sequence." Performing an analysis of HOD from AD + without any smallness assumption is a central question of descriptive inner model theory. Towards this goal, Steel proves a comparison lemma for hod mice in A Comparison Process for Mouse Pairs, Lecture Notes in Logic, vol. 51 (2022).
- Open Access
On the Ramsey number of daisies I
Daisies are a special type of hypergraphs introduced by Bollob\'{a}s, Leader and Malvenuto. An $r$-daisy determined by a pair of disjoint sets $K$ and $M$ is the $(r+|K|)$-uniform hypergraph $\{K\cup P:\: P\in M^{(r)}\}$. In [Combin. Probab. Comput. 20, no. 5, 743-747, 2011] the authors studied Tur\'{a}n type density problems for daisies. This paper deals with Ramsey numbers of Daisies, which are natural generalizations of classical Ramsey numbers. We discuss upper and lower bounds for the Ramsey number of $r$-daisies and also for special cases where the size of the kernel is bounded.Open AccessOn the Ramsey number of daisies I
Daisies are a special type of hypergraphs introduced by Bollob\'{a}s, Leader and Malvenuto. An $r$-daisy determined by a pair of disjoint sets $K$ and $M$ is the $(r+|K|)$-uniform hypergraph $\{K\cup P:\: P\in M^{(r)}\}$. In [Combin. Probab. Comput. 20, no. 5, 743-747, 2011] the authors studied Tur\'{a}n type density problems for daisies. This paper deals with Ramsey numbers of Daisies, which are natural generalizations of classical Ramsey numbers. We discuss upper and lower bounds for the Ramsey number of $r$-daisies and also for special cases where the size of the kernel is bounded. - Open Access
- 14 March 2022
- Published by Springer Nature in Combinatorica
- Vol. 42 (4) , 1-30
Extractors for Small Zero-Fixing Sources
- 14 March 2022
- Published by Springer Nature in Combinatorica
- Vol. 42 (4) , 1-30
Open AccessExtractors for Small Zero-Fixing Sources
- 10 August 2021
- Published by Elsevier in Information Processing Letters
- Vol. 174, 106180
On matrices potentially useful for tree codes
- 10 August 2021
- Published by Elsevier in Information Processing Letters
- Vol. 174, 106180
On matrices potentially useful for tree codes
- 22 April 2019
- Published by Springer Nature in computational complexity
- Vol. 28 (2) , 185-239
Random resolution refutations
- 22 April 2019
- Published by Springer Nature in computational complexity
- Vol. 28 (2) , 185-239
Random resolution refutations
- 1 March 2018
- Published by Elsevier in Information Processing Letters
- Vol. 131, 15-19
A note on monotone real circuits
- 1 March 2018
- Published by Elsevier in Information Processing Letters
- Vol. 131, 15-19
A note on monotone real circuits
- 1 December 2017
- Published by Cambridge University Press (CUP) in The Bulletin of Symbolic Logic
- Vol. 23 (4) , 405-441
INCOMPLETENESS IN THE FINITE DOMAIN
Motivated by the problem of finding finite versions of classical incompleteness theorems, we present some conjectures that go beyondNP≠coNP. These conjectures formally connect computational complexity with the difficulty of proving some sentences, which means that high computational complexity of a problem associated with a sentence implies that the sentence is not provable in a weak theory, or requires a long proof. Another reason for putting forward these conjectures is that some results in proof complexity seem to be special cases of such general statements and we want to formalize and fully understand these statements. Roughly speaking, we are trying to connect syntactic complexity, by which we mean the complexity of sentences and strengths of the theories in which they are provable, with the semantic concept of complexity of the computational problems represented by these sentences.We have introduced the most fundamental conjectures in our earlier works [27, 33–35]. Our aim in this article is to present them in a more systematic way, along with several new conjectures, and prove new connections between them and some other statements studied before.
- 1 December 2017
- Published by Cambridge University Press (CUP) in The Bulletin of Symbolic Logic
- Vol. 23 (4) , 405-441
INCOMPLETENESS IN THE FINITE DOMAIN
Motivated by the problem of finding finite versions of classical incompleteness theorems, we present some conjectures that go beyondNP≠coNP. These conjectures formally connect computational complexity with the difficulty of proving some sentences, which means that high computational complexity of a problem associated with a sentence implies that the sentence is not provable in a weak theory, or requires a long proof. Another reason for putting forward these conjectures is that some results in proof complexity seem to be special cases of such general statements and we want to formalize and fully understand these statements. Roughly speaking, we are trying to connect syntactic complexity, by which we mean the complexity of sentences and strengths of the theories in which they are provable, with the semantic concept of complexity of the computational problems represented by these sentences.We have introduced the most fundamental conjectures in our earlier works [27, 33–35]. Our aim in this article is to present them in a more systematic way, along with several new conjectures, and prove new connections between them and some other statements studied before.
- 31 March 2017
- Published by Cambridge University Press (CUP)
Opening speech of Petr Vopěnka
- 31 March 2017
- Published by Cambridge University Press (CUP)
Logic Colloquium '98
Since their inception, the Perspectives in Logic and Lecture Notes in Logic series have published seminal works by leading logicians. Many of the original books in the series have been unavailable for years, but they are now in print once again. This volume, the thirteenth publication in the Lecture Notes in Logic series, collects the proceedings of the European Summer Meeting of the Association for Symbolic Logic held at the University of Economics in Prague, August 9–15, 1988. It includes surveys and research from preeminent logicians. The papers in this volume range over all areas of mathematical logic, including proof theory, set theory, model theory, computability theory and philosophy. This book will be of interest to all students and researchers in mathematical logic.
- 31 March 2017
- Published by Cambridge University Press (CUP)
Logic Colloquium '98
Since their inception, the Perspectives in Logic and Lecture Notes in Logic series have published seminal works by leading logicians. Many of the original books in the series have been unavailable for years, but they are now in print once again. This volume, the thirteenth publication in the Lecture Notes in Logic series, collects the proceedings of the European Summer Meeting of the Association for Symbolic Logic held at the University of Economics in Prague, August 9–15, 1988. It includes surveys and research from preeminent logicians. The papers in this volume range over all areas of mathematical logic, including proof theory, set theory, model theory, computability theory and philosophy. This book will be of interest to all students and researchers in mathematical logic.