2 citations · 4 across the 7 of their papers we have counts for
14 papers
Herbrand Game Complexity
Sam Buss, Pavel Pudlák
The Student-Teacher game is an extension of Herbrand's theorem. In the game, Student and Teacher take turns giving values for existentially and universally quantified variables, an…
The canonical pairs of bounded depth Frege systems
Pavel Pudlak
The canonical pair of a proof system is the pair of disjoint NP sets where one set is the set of all satisfiable CNF formulas and the other is the set of CNF formulas that have…
Santha-Vazirani sources, deterministic condensers and very strong extractors
Dmytro Gavinsky, Pavel Pudlák
The notion of semi-random sources, also known as Santha-Vazirani (SV) sources, stands for a sequence of n bits, where the dependence of the i'th bit on the previous i-1 bits is lim…
Extractors for small zero-fixing sources
Pavel Pudlák, Vojtech Rödl
A random variable is an -zero-fixing source if for some subset , is the uniform distribution on the strings that are zero on every coordin…
Tighter Hard Instances for PPSZ
Pavel Pudlák, Dominik Scheder, Navid Talebanfard
We construct uniquely satisfiable -CNF formulas that are hard for the algorithm PPSZ. Firstly, we construct graph-instances on which "weak PPSZ" has savings of at most $(2 + ε)…
A wild model of linear arithmetic and discretely ordered modules
Petr Glivický, Pavel Pudlák
Linear arithmetics are extensions of Presburger arithmetic (Pr) by one or more unary functions, each intended as multiplication by a fixed element (scalar), and containing the full…
Incompleteness in the finite domain
Pavel Pudlak
Motivated by the problem of finding finite versions of classical incompleteness theorems, we present some conjectures that go beyond . These conjectures formall…
On the Joint Entropy of -Wise-Independent Variables
Dmytro Gavinsky, Pavel Pudlák
How low can the joint entropy of -wise independent (for ) discrete random variables be, subject to given constraints on the individual distributions (say, no value ma…
On the complexity of finding falsifying assignments for Herbrand disjunctions
Pavel Pudlak
Suppose that is a consistent sentence. Then there is no Herbrand proof of , which means that any Herbrand disjunction made from the prenex form of is falsifiab…
Partition Expanders
Dmytro Gavinsky, Pavel Pudlák
We introduce a new concept, which we call partition expanders. The basic idea is to study quantitative properties of graphs in a slightly different way than it is in the standard d…
Linear tree codes and the problem of explicit constructions
Pavel Pudlák
We reduce the problem of constructing asymptotically good tree codes to the construction of triangular totally nonsingular matrices over fields with polynomially many elements. We…
The complexity of proving that a graph is Ramsey
Massimo Lauria, Pavel Pudlák, Vojtěch Rödl +1
We say that a graph with vertices is -Ramsey if it does not contain either a clique or an independent set of size . We define a CNF formula which expresses this pr…
Randomness, pseudorandomness and models of arithmetic
Pavel Pudlak
Pseudorandmness plays an important role in number theory, complexity theory and cryptography. Our aim is to use models of arithmetic to explain pseudorandomness by randomness. To t…
Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity
Dmytro Gavinsky, Pavel Pudlák
We give the first exponential separation between quantum and classical multi-party communication complexity in the (non-interactive) one-way and simultaneous message passing settin…