Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] All I Want for Christmas is a Proof that P≠NP

Expand Messages
  • Lance
    For the first time in my lifetime, Christmas and Chanukah land on the same day. So to all my readers, Happy Holidays! And what do we find under our theory
    Message 1 of 1 , Dec 23, 2005
    • 0 Attachment
      For the first time in my lifetime, Christmas and Chanukah land on the same day. So to all my readers, Happy Holidays!

      And what do we find under our theory Christmas tree? Our first present is a new randomized polynomial-time algorithm for linear programming from Kelner and Spielman. The card reads

      In this paper, we present the first randomized polynomial-time simplex method. Like the other known polynomial-time algorithms for linear programming, the running time of our algorithm depends polynomially on the bit-length of the input. We do not prove an upper bound on the diameter of polytopes. Rather we reduce the linear programming problem to the problem of determining whether a set of linear constraints defines an unbounded polyhedron. We then randomly perturb the right-hand sides of these constraints, observing that this does not change the answer, and use a shadow-vertex simplex method to try solve the perturbed problem. When the shadow-vertex method fails, it suggests a way to alter the distributions of the perturbations, after which we apply the method again. We prove that the number of iterations of this loop is polynomial with high probability.
      Our next present is a list-decodable code from Guruswami and Rudra. Back in October I posted about the Parvaresh-Vardy code that list decode a 1-ε fraction of errors using a code of rate O(ε/log(1/ε)). Guruswami and Rudra, for any constant δ>0, create a code with rate ε-δ.

      Many more presents under the tree, presumably many STOC and Complexity submissions. No proofs (at least correct ones) that P≠NP this year but maybe Santa will come through for us in time for next Christmas.

      --
      Posted by Lance to Computational Complexity at 12/23/2005 08:47:00 AM

    Your message has been successfully submitted and would be delivered to recipients shortly.