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!
There will be a huge breakthrough in the topic of pseudorandomness
ReplyDelete2) are you referring to an explicit one way function? an outsider.
ReplyDeleteI think Donald Trump was reading your blog:
ReplyDeleteTrump Says Cruz's Canadian Birth Could Be Very Precarious For GOP
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).
ReplyDeleteRationale 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.
"Clyde Kruskal tells me that a good method for guessing how long a problem will stay open is how long its been open."
ReplyDeleteThat's called The Lindy Effect: https://en.wikipedia.org/wiki/Lindy_effect