We show that Yao's XOR Lemma, and its essentially equivalent
rephrasing as a Direct Product Lemma, can be
re-interpreted as a way of obtaining error-correcting
codes with good list-decoding algorithms from error-correcting
codes having weak unique-decoding algorithms. To get codes
with good rate and efficient list decoding algorithms
one needs ... more >>>

We study the Chv\'atal rank of polytopes as a complexity measure of
unsatisfiable sets of clauses. Our first result establishes a
connection between the Chv\'atal rank and the minimum refutation
length in the cutting planes proof system. The result implies that
length lower bounds for cutting planes, or even for ... more >>>

We use recent results on the hardness of resource-bounded
Kolmogorov random strings, to prove that RP is small in SUBEXP
else ZPP=PSPACE and NP=EXP.
We also prove that if NP is not small in SUBEXP, then
NP=AM, improving a former result which held for the measure ... more >>>