Monday, December 28, 2015

Complexity Year in Review 2015

We had an incredible year for theorems in 2015, the strongest year in computational complexity in the last decade. Topping the list as the theorem of the year is László Babai's quasipolynomial-time algorithm for graph isomorphism. A little risky because nobody, including Babai himself, has fully verified the proof but given Babai's reputation and the warm reception of his lectures, I have little doubt it will all work out. Again I strongly recommend watching the video of Babai's first lecture. Not only is Babai a great researcher but he's an excellent speaker as well. For the those up to the challenge, the paper is now available as well.

Beyond Babai's result we had a great year including random oracles separating the polynomial-time hierarchy, the (3+1/86)n size lower bound for general circuits, Terry Tao's solution to the Erdős discrepancy problem, explicit constructions of Ramsey Graphs and new bounds on threshold circuits.

We celebrated 50 years of computational complexity and Moore's law, the centenary of Hamming and the bicentenaries of Ada Lovelace and George Boole, the latter giving us the Boolean algebra. In 2016 we will celebrate the centenary of the person who used those bits to describe information.

We thank our guest posters Dylan McKay and Thomas Zeume. Dylan's metric group problem is still open if anyone wants to try and crack it.

In 2015 we continue to see CS departments struggle to meet the demand of students and industry. US universities faced many difficult challenges including dealing with race relations, freedom of speech and safety issues. Too much tragedy in the US and abroad, and a far too divisive political campaign. Here's hoping for reason to prevail in 2016.

We remember Gene Amdahl, Alberto Apostolico, Barry Cooper, George Cox, Jiří Matoušek, John NashLeonard Nimoy, Hartley Rogers Jr., Donald Rose, Karsten Schwan and Joe Traub.

Wishing everyone a Happy New Year and a successful 2016.


  1. Also QMA(2) is contained in EXP and edit distance-SETH connection.

  2. On QMA(2) in EXP: my proof is currently considered incomplete. I'm working on an updated version of the argument.

  3. Happy New Year!

    Can you also write a post about more practical theory results of interest to people outside theory? Is there any major problem that we can not solve faster in practice? etc.

  4. What about the interesting but easier non-trivial theorems proved in 2015, like The common generalization of Alon-Furedi, Schwartz-Zippel, and DeMillo-Lipton? Having sharp bounds for the number of zeros of a polynomial in a finite grid can be quite useful in a variety of contexts.

    1. Thank you for showing interest in my work and for your nice comment. I hope these results end up being useful to the community.

  5. Dear Professor Lance,

    We pretend to show the answer of the P versus NP problem. We start assuming the hypothesis of P = NP that will lead us to a contradiction. The argument is supported by a Theorem that states if P = NP, then the problem SUCCINCT HAMILTON PATH would be in P.

    In this Theorem, we take an arbitrary succinct representation C of a graph G_{C} with n nodes, where n = 2^{b} is a power of two and C will be a Boolean circuit of 2 * b input gates. Interestingly, if C is a ``yes" instance of SUCCINCT HAMILTON PATH, then there will be a linear order Q on the nodes of G_{C}, that is, a binary relationship isomorphic to "<" on the nodes of G_{C}, such that consecutive nodes are connected in G_{C}.

    This linear order Q must require several things:

    * All distinct nodes of G_{C} are comparable by Q,
    * next, Q must be transitive but not reflexive,
    * and finally, any two consecutive nodes in Q must be adjacent in G_{C}.

    Any binary relationship Q that has these properties must be a linear order, any two consecutive elements of which are adjacent in G_{C}, that is, it must be a Hamilton path.

    On the other hand, the linear order Q can be actually represented as a graph G_{Q}. In this way, the succinct representation C_{Q} of the graph G_{Q} will represent the linear order Q too. We can define a polynomially balanced relation R_{Q}, where for all succinct representation C of a graph: There is another Boolean circuit C_{Q} that will represent a linear order Q on the nodes of G_{C} such that (C, C_{Q}) is in R_{Q} if and only if C is in SUCCINCT HAMILTON PATH.

    We finally show R_{Q} would be polynomially decidable if P = NP. For this purpose, we use the existential second-order logic expressions, used to express this graph-theoretic property (the existence of a Hamilton path), that are described in Computational Complexity book of Papadimitriou: Chapter "5.7 SECOND-ORDER LOGIC" in Example "5.12" from page "115". Indeed, we just simply replace those expressions with Universal quantifiers into equivalent Boolean tautologies formulas.

    Certainly, a language L is in class NP if there is a polynomially decidable and polynomially balanced relation R such that L = {x: (x, y) in R for some y}. In this way, we show that SUCCINCT HAMILTON PATH would be in NP if we assume our hypothesis, because the relation R_{Q} would be polynomially decidable and polynomially balanced when P = NP. Moreover, since P would be equal to NP, we obtain that SUCCINCT HAMILTON PATH would be in P too.

    But, we already know if P = NP, then EXP = NEXP. Since SUCCINCT HAMILTON PATH is in NEXP–complete, then it would be in EXP–complete, because the completeness of both classes uses the polynomial-time reduction. But, if some EXP–complete problem is in P, then P should be equal to EXP, because P and EXP are closed under reductions and P is a subset of EXP. However, as result of the Hierarchy Theorem the class P cannot be equal to EXP. To sum up, we obtain a contradiction under the assumption that P = NP, and thus, we can claim that P is not equal to NP as a direct consequence of applying the Reductio ad absurdum rule.

    You could see the details in: