2 citations · 4 across the 7 of their papers we have counts for
5 papers · 1 filter
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 + ε)…
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…
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…