P. Pudlák

activity

20122019

most citedRandomness, pseudorandomness and models of arithmetic

2 citations · 2 across the 2 of their papers we have counts for

collaborators

Showing cs.CCShow all

2 papers · 1 filter

cs.CC2019

Extractors for small zero-fixing sources

Pavel Pudlák, Vojtech Rödl

A random variable $X$ is an $(n, k)$ -zero-fixing source if for some subset $V \subseteq [n]$ , $X$ is the uniform distribution on the strings ${0, 1}^{n}$ that are zero on every coordin…

cs.CC2013

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 $n$ vertices is $c$ -Ramsey if it does not contain either a clique or an independent set of size $c lo g n$ . We define a CNF formula which expresses this pr…