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.