| 2023 | WG | Bounds on Functionality and Symmetric Difference - Two Intriguing Graph Parameters. | Pavel Dvork, Luks Folwarczn, Michal Opler, Pavel Pudlk, Robert Smal, Tung Anh Vu |
| 2018 | SODA | Beating Brute Force for (Quantified) Satisfiability of Circuits of Bounded Treewidth. | Daniel Lokshtanov, Ivan Mikhailin, Ramamohan Paturi, Pavel Pudlk |
| 2017 | FOCS | Random Formulas, Monotone Circuits, and Interpolation. | Pavel Hrubes, Pavel Pudlk |
| 2017 | ICALP | Tighter Hard Instances for PPSZ. | Pavel Pudlk, Dominik Scheder, Navid Talebanfard |
| 2014 | STACS | Partition Expanders. | Dmitry Gavinsky, Pavel Pudlk |
| 2013 | ICALP | The Complexity of Proving That a Graph Is Ramsey. | Massimo Lauria, Pavel Pudlk, Vojtech Rdl, Neil Thapen |
| 2013 | MFCS | Parity Games and Propositional Proofs. | Arnold Beckmann, Pavel Pudlk, Neil Thapen |
| 2012 | STOC | Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. | Anna Gl, Kristoffer Arnsfelt Hansen, Michal Kouck, Pavel Pudlk, Emanuele Viola |
| 2011 | STOC | Pseudorandom generators for group products: extended abstract. | Michal Kouck, Prajakta Nimbhorkar, Pavel Pudlk |
| 2010 | STOC | On the complexity of circuit satisfiability. | Ramamohan Paturi, Pavel Pudlk |
| 2008 | CSR | Twelve Problems in Proof Complexity. | Pavel Pudlk |
| 2006 | CIAC | On Search Problems in Complexity Theory and in Logic (Abstract). | Pavel Pudlk |
| 2006 | FOCS | Lower bounds for circuits with MOD_m gates. | Arkadev Chattopadhyay, Navin Goyal, Pavel Pudlk, Denis Thrien |
| 2005 | STOC | Bounded-depth circuits: separating wires from gates. | Michal Kouck, Pavel Pudlk, Denis Thrien |
| 2001 | MFCS | On Reducibility and Symmetry of Disjoint NP-Pairs. | Pavel Pudlk |
| 2000 | SODA | A lower bound for DLL algorithms for | Pavel Pudlk, Russell Impagliazzo |
| 1998 | FOCS | An Improved Exponential-Time Algorithm for | Ramamohan Paturi, Pavel Pudlk, Michael E. Saks, Francis Zane |
| 1998 | MFCS | Satisfiability - Algorithms and Logic. | Pavel Pudlk |
| 1997 | FOCS | Satisfiability Coding Lemma. | Ramamohan Paturi, Pavel Pudlk, Francis Zane |
| 1996 | COCOON | On Sparse Parity Chack Matrices (Extended Abstract). | Hanno Lefmann, Pavel Pudlk, Petr Savick |
| 1995 | FOCS | On Computing Boolean Functions by Sparse Real Polynomials. | Matthias Krause, Pavel Pudlk |
| 1994 | CSL | How to Lie Without Being (Easily) Convicted and the Length of Proofs in Propositional Calculus. | Pavel Pudlk, Samuel R. Buss |
| 1994 | FOCS | Lower Bound on Hilbert's Nullstellensatz and propositional proofs | Paul Beame, Russell Impagliazzo, Jan Krajcek, Toniann Pitassi, Pavel Pudlk |
| 1994 | ICALP | Unexpected Upper Bounds on the Complexity of Some Communication Games. | Pavel Pudlk |
| 1994 | STOC | On the computational power of depth 2 circuits with threshold and modulo gates. | Matthias Krause, Pavel Pudlk |
| 1993 | FCT | AC | Pavel Pudlk |
| 1993 | FOCS | Top-Down Lower Bounds for Depth 3 Circuits | Johan Hstad, Stasys Jukna, Pavel Pudlk |
| 1993 | STOC | Modified ranks of tensors and the size of circuits. | Pavel Pudlk, Vojtech Rdl |
| 1992 | STOC | Exponential Lower Bounds for the Pigeonhole Principle | Paul Beame, Russell Impagliazzo, Jan Krajcek, Toniann Pitassi, Pavel Pudlk, Alan R. Woods |
| 1990 | CSL | Ramsey's Theorem in Bounded Arithmetic. | Pavel Pudlk |
| 1990 | MFCS | Interactive Computations of Optimal Solutions. | Jan Krajcek, Pavel Pudlk, Jir Sgall |
| 1989 | CSL | Propositional Provability and Models of Weak Arithmetic. | Jan Krajcek, Pavel Pudlk |
| 1989 | FCT | On the Communication Complexity of Planarity. | Pavol Duris, Pavel Pudlk |
| 1987 | FOCS | Threshold circuits of bounded depth | Andrs Hajnal, Wolfgang Maass, Pavel Pudlk, Mario Szegedy, Gyrgy Turn |
| 1986 | STOC | Two lower bounds for branching programs | Mikls Ajtai, Lszl Babai, Pter Hajnal, Jnos Komls, Pavel Pudlk, Vojtech Rdl, Endre Szemerdi, Gyrgy Turn |
| 1984 | MFCS | New Lower Bound for Polyhedral Membership Problem with an Application to Linear Programming. | Jaroslav Morvek, Pavel Pudlk |
| 1984 | MFCS | A Lower Bound on Complexity of Branching Programs (Extended Abstract). | Pavel Pudlk |
| 1975 | MFCS | Polynomially Complete Problems in the Logic of Automated Discovery. | Pavel Pudlk |