Friday, February 09, 2007

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.

4 comments:

  1. Some of us are waiting for the reviewer comments, its almost been a week now.

    ReplyDelete
  2. Bill Gasarch will bring you his wit and wisdom in my absence.

    1. DON'T BELIEVE IT
    2. NOT FOR ONE SECOND
    3. NO WAY THIS IS THE REAL BILL GASARCH

    ReplyDelete
  3. The [GUV] paper is the first paper that gives extractors that are optimal up to constant factors in all parameters (output length, seed length and error).

    Saying that it "matches the best known bounds" is not making this paper justice.

    ReplyDelete