Complexity Papers

I am on vacation and off the internet for most of next week. Bill Gasarch will bring you his wit and wisdom in my absence.

A few of the accepted papers of the upcoming Computational Complexity Conference that caught my eye.

Extractors and Condensers from Univariate Polynomials, Venkatesan Guruswami, Christopher Umans, and Salil Vadhan.

Extracting nearly uniform random bits from weakly-random sources has been one of the solid lines of research in the past few years in complexity. This paper matches the best known bounds for extractors with a clever use of recently developed list-decodable codes.

On derandomizing probabilistic sublinear-time algorithms, Marius Zimand

I'm less excited by the title result than the tools Zimand develops, an extractor that produces bits that looks random even to circuits that can see part of the weakly random string.

Perfect Parallel Repetition Theorem for Quantum XOR Proof Systems, Richard Cleve, William Slofstra, Falk Unger, and Sarvagya Upadhyay

When running a multiple proof system in parallel, the provers can sometimes do better coordinating between runs than treating each run separately. This paper gives an example when classically the provers can take advantage of the parallelism but quantumly they cannot.

There were several very interesting titles whose authors have not put those papers online. Shame on them.