2 citations · 4 across the 7 of their papers we have counts for
Showing 2019Show all
3 papers · 1 filter
math.LO2019
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…
cs.CC2019
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…
cs.CC2019
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…