Sunday, January 03, 2016

Predictions for 2016

This is the first post of 2016! (that is not a factorial). Hence I will make some predictions and at the end of the year I'll see how I did

1)  The USA Prez election will have two main candidates: Hillary Clinton and Ted Cruz. Clinton will win by floating rumors that Cruz was born in a foreign country.

2) There will be a proof that  there exists a constant c such that the methods that got a lower bound of (3+1/86)n on an explicit function cannot be extended to cn.

3) P vs NP will not be solved. But see next point.

4) I will be asked to look at at least two resolutions of P vs NP. This year I was asked to look at two
proofs that P=NP. Neither was correct.

5) GI will still not be in known to be in P.

6) There will be a proof that Babai's techniques cannot get GI into P.

7) The fact that 2016=25327 will be useful in a math competition.

8) Posting a video of a talk (as Babai did) will become an acceptable way to claim a result, rather than having a paper on arXiv. Getting a paper in a Journal will become less and less relevant for big results.
(This is a topic for a later blog post.)

9) The Unique Game conjecture... When it was first stated it seemed like maybe it could be proven or disproven. The longer it stays open the harder it seems. Clyde Kruskal tells me that a good method for guessing how long a problem will stay open is how long its been open.  So I'll predict it won't be resolved this year. However, by that reasoning, I will always predict it will not be resolved in the following year.

10) There will be a big data breach. The security protocols used were never proven secure, though that won't be what caused the breach.  Nor was it caused because of a really fast factoring or DL algorithm.

11) Comp Sci enrollment will continue to rise.

12) Leave your predictions in the comments!


  1. There will be a huge breakthrough in the topic of pseudorandomness

  2. 2) are you referring to an explicit one way function? an outsider.

  3. Prediction In 2016, the arxiv will host 189 preprints, broadly relating to quantum simulation, whose abstracts specifically mention 'matrix product state' (MPS) and/or 'tensor network' (TN).

    Rationale  The years 2004-2015 inclusive have witnessed a sustained doubling interval of 38 months for the number of MPS/TN arxiv preprints (in 2015 there were 142 of them).

    Student-friendly references  Particularly commended is Roman Orus' "A Practical Introduction to Tensor Networks" (arXiv:1306.2164, 2013), as illuminated by Ilya Kapovich's broader discussion "Musings on generic-case complexity" (arXiv:1505.03218, 2015); see in particular Orus' discussion in "Section 3.4 Hilbert space is far too large".

    Open questions  Thought-provoking too are Orus' references to the literature of AdS/CFT correspondences and quantum holographic principles, which connect concrete topics in MPS/TN research to fundamental questions in quantum physics.

    Career opportunities  Sustained growth is a sine qua non of academic research careers; one further decade of sustained growth in MPS/TN research will generate a article stream sufficient enough to sustain on the order of one hundred academic research groups. Researchers who channel their creative energies into this area may benefit from these opportunities.

    Further observations  The Arora/Belenzon/Patacconi white paper "Killing the Golden Goose? The Decline of Science in Corporate R&D" (NBER Working Paper No. 20902, 2015) provides considerable evidence that research opportunities comparable those associated to MPS/TN studies may be becoming relatively less abundant than previous generations of researchers have enjoyed.

  4. "Clyde Kruskal tells me that a good method for guessing how long a problem will stay open is how long its been open."

    That's called The Lindy Effect: