For 2014, that is

 Cropped from Guardian article.

Isaac Asimov was one of the most prolific writers of all times—he wrote or edited over 500 books. In his Foundation series a mathematician finds out that the future can be predicted based on equations.

Today Ken and I wish to make several predictions about the new year, without using any equations.

In previous years we tried to make serious predictions, well we thought they were serious. So this year we plan on making less serious ones. Perhaps, based on Murphy’s Law, these will all come to pass. Some jokes on this blog do run parallel to serious research ideas, as we sometimes say if our own second thoughts haven’t shot them down already.

In this spirit, Asimov wrote a joke paper, “The Endochronic Properties of Resublimated Thiotimoline,” at the time he was finishing his own PhD in biochemistry. He intended it to help him transit from the style of his already-successful fiction to serious academic writing. It was supposed to appear in the magazine Astounding Science Fiction under a pseudonym, but appeared under his real name. One of his examiners noticed it, and queried how his time-reversing molecule squared with the laws of thermodynamics. Happily there was hilarity all around and Asimov earned his “Dr.”

Of course, as Kurt Gödel remarked at the end of our last interview with him, we need a new time-reversal mechanism to re-contact him. The system could also enable us to make perfect predictions. So let us proceed to last year’s and next year’s business.

## Last Year’s Predictions

Another hitch with serious predictions is that sometimes it is seriously hard to verify them, especially when there is difference of opinion. Probably we should crowdsource the results. At least we began with a slam dunk.

1. No circuit lower bound of ${ 1000n}$ or better will be proved for SAT. True.
2. A Computer Scientist will win a Nobel Prize. As usual, close but no. The Chemistry Nobel centered on computerized models of chemical systems, but none of the three winners has an official CS affiliation.
3. An important advance will be made on understanding barriers either to proving ${\mathsf{P = NP}}$ or proving the opposite, ${\mathsf{P \neq NP}}$. Depends. The improved “chasm” results for arithmetical complexity are certainly relevant, but it is not clear which way the support goes. There was ongoing significant work on polytopes for TSP and other problems, but they merely speak against one approach to ${\mathsf{P = NP}}$.
4. A new simple group will be discovered. By the classification theorem, such a group must be infinite. Apparently no, nor have we heard about a new result about finitely generated ones.
5. Another gap will be found in Shinichi Mochizuki’s claimed proof of the ABC Conjecture. (Note that Mochizuki released updates to his papers on Dec. 16th, including acknowledgments to Vesselin Dimitrov and Akshay Venkatesh who had found a gap in two of them.) We claim half-credit: all five “Inter-universal Teichmüller Theory” papers at the bottom of his papers page have 2013 modification dates, with two updates just recently on Dec. 18th.
6. The ABC claimed proof will be found to be correct. Not yet.
7. Experiments scaling up boson sampling from ${3 \times 3}$ to ${4 \times 4}$ permanents will be published by year’s end. Apparently yes; indeed per this Jan 8, 2013 item, ${4 \times 4}$ may already have been done as we wrote. However, according to Scott Aaronson’s Nov. 8 post on his blog, “…so far, BosonSampling has only been demonstrated with 3-4 photons,” amid proposals for larger-scale computation of permanent-related quantities. We should stress that computing the permanent itself, or anything NP-hard, is not the object. The latest news we find is this Nov. 17 paper on techniques for verifying experiments that may put 25–30 photons in reach, pushing the limit of brute-force classical simulation, and that furthers interesting issues of matrix and polynomial symmetry. Scott has just posted notes of 5 lectures he gave in Rio de Janeiro.
8. A new conditional relation will be found tying the difficulty of scaling up boson sampling to that of scaling up full universal quantum computation. Not that we see. Closest we find is this paper giving an elementary argument against classical methods scaling up to simulate boson sampling.
9. A best seller will be published by a noted blogger on the ${\mathsf{P = NP}}$ question.

Does Top-14,000 count? Lance Fortnow’s book The Golden Ticket made Amazon’s 2013 Best Books in Science list. Congratulations, Lance.

10. Work will begin on a major motion picture whose plot is based on finding a polynomial time algorithm for factoring. It will audition Angelina Jolie as the brilliant mathematician who solves the problem and Tom Hanks as the villain. Our script is still looking for a buyer, while Jolie and Hanks are tied up with Disney.
11. Noted progress toward solving another Clay Problem will be released on the ArXiv this year. Maybe. Closest we find is this paper showing a sense in which a positive fraction of elliptic curves over the rationals have an analytic rank of ${0}$, and hence meet a long-known criterion for satisfying the Birch/Swinnerton-Dyer conjecture.

12. A planet no more than twice Earth’s size will be detected orbiting within the habitable zone of its single star. Apparently still no. Major headlines were made by a study released last month giving what appears to be an overwhelming probabilistic proof of their existence, but the best that stories about it such as this one seem to give are planets that are still too big or too hot. Update (thanks to this comment): If “twice in size” means in radii—as used for the probabilistic argument—then Kepler 62e (1.61 Earth radii) and 62f (1.41 Earth radii) count (April 27, 2013 paper). If “twice” means volume, then it needs to be within 1.26 radii (1.2599…).

## A New Kind-Of Prediction

We have only 8 this year, about all we could manage with the new formulation. Usually predictions have some intermediate truth value—that’s why they are called predictions—but at least our first one pushes the boundary.

${\bullet }$ Two integers ${p/q}$ of over one million digits each, in decimal, will be discovered so that

$\displaystyle p/q = \sqrt{2}.$

The New York Times will report, “Numbers All Askew in the Heavens.” In the article written by Gina Kolata, she will quote a prominent number theorist as saying: This is very disturbing. I really thought that the proof of Pythagoras was correct. I am at a loss…

${\bullet }$ Trading in Bitcoins will be stopped when an anonymous team posts an algorithm that breaks the scheme. Social media will be abuzz with the question: why did they post it? They could have made billions in real dollars.

${\bullet }$ A new field of computer science called computational football will be one of the hottest areas of research. At least one university president will be quoted by the New York Times as saying: Finally a research area I can understand and get behind. As a result MIT will create a college football team in the NCAA Division I Football Bowl Subdivision. Their team will win no games their first season under coach Mike Shanahan. The MIT president will say, jokingly, “next year we will win twice as many games.” MIT students will love the quote, and it will appear on t-shirts all over campus.

${\bullet }$ A proof that there is a proof that there is a proof that there is no proof that there is a proof that there is a proof in Peano Arithmetic of ${\mathsf{P} \neq \mathsf{NP}}$ will be found. No one will be able to referee the proof. The author, who is famous, will appeal to the formal proof checking community to get involved, but they will demur.

${\bullet }$ Computer scientists will sweep the all the Nobel Prizes except Peace and Literature. The Nobel committee will say in a press release: Computing is now a lens for all of science, so we had little choice. When the board of ACM’s SIGNOBEL group is interviewed by the New York Times on why computer scientists missed out on the Literature prize, they will say: “Surely your joking.”

${\bullet }$ A company called Braincloud LLC will announce a competitor for Google Glass that is controlled directly by brain pulses. The first release will include apps for cryptographically secured remembering of your passwords and phone numbers, hands-free texting, playing chess, visualizing GPS directions, and (for panicky new parents) having Dr. Spock’s Baby Guides fed right to the brain. It will be worn in the ears not the eyes, using vulcanized rubber ear tips.

${\bullet}$ A new massively-multiplayer online role-playing computer game called “DoS Survivor” will take the world by storm. Each player connects a pair of computers to the game. One runs a licensed simulation of a famous online server, while the other is used to generate Denial-of-Service attacks on other players’ servers. Survivors progress to higher levels and are enabled to run more advanced servers. The two finalists square off with one running healthcare.gov and the other running Silk Road. Results of field tests this week indicate that the game is close to alpha release.

${\bullet }$ MOOCs will adopt a “human-centered support structure.” This will involve geographically localized cells of up-close instruction at regularly spaced time intervals, with generous time in-between for absorbing material and practicing non-bubble exercises. Advanced-intelligence scanning of exercise submissions for quality points will be an implementable option. Accompanying each course will be a device predicted 40 years ago by Isaac Asimov himself in his essay, “The Ancient and the Ultimate”:

“[It] can go anywhere, and is totally portable. Something that can be started and stopped at will along its data stream, allowing the user to access the information in an effective, easy manner … and requir[ing] no electrical energy to operate … minimum technology for maximum interaction.”

Ken and I have been extra-busy with Asimov’s devices, as we will shortly reveal.

## Open Problems

Our final prediction is that 2014 will be another great year for mathematical research, and another fun year for all of us at GLL. We thank you again for your support and wish you all a joyous new year.

January 2, 2014 12:02 am

Hi

That was a wonderful post.. as usual though. This one especially brought many smiles:-) A good start of the new year 2014…

January 2, 2014 11:17 am

Ms. Megha Kollehekar,

You are very kind. Thanks.

2. Last year's no more than twice earth-sized planet prediction permalink
January 2, 2014 4:23 am

lastyear #12

According to Wikipedia: http://en.wikipedia.org/wiki/Exoplanet

“The count, from April 2013, of detected Earth-like planets in a habitable zone are two: Kepler-62e and Kepler-62f which have 1.61 and 1.41 Earth radii respectively.”

• Last year's no more than twice earth-sized planet prediction permalink
January 2, 2014 4:49 am

Edited. That should read: “The most Earth-like planets in a habitable zone to have been discovered, as of April 2013, are Kepler-62e and Kepler-62f which have 1.61 and 1.41 Earth radii respectively”.

• January 2, 2014 10:33 am

Thanks!—forgot to check that on Wikipedia. Added an update—this actually plays in to the “difference of opinion” issue we already noted.

January 2, 2014 5:37 am

First of all, I wish a happy new year to GLL and its readers! 🙂

A Computer Scientist will win a Nobel Prize.

I think it’s only a significant progress in P?NP that might award the Nobel Prize to a computer scientist. The solution of any of the other longstanding conjectures in complexity theory might result in a Fields Medal or a Turing Award, depending on their respective importance…

But I have one more prediction for 2014:

A computer will make an amazing conjecture that looks true but nobody can prove – even a computer!

• January 2, 2014 11:17 am

Protein folding would likely merit a Nobel Prize, and it could well come from a researcher at a CS department or even before that Gene Myers might be awarded one.

Also do not forget that Herbert Simon already won one, Shapley could be argued to be a computer scientist, and people doing mechanism design and economic game theory could well walk away with a Nobel Prize one of these days.

January 2, 2014 11:18 am

Serge

Could be great algorithm of some kind. Or quantum based insight?

January 2, 2014 11:58 am

Hi Dick!

That would maybe require some quantum device embedded within the core of the machine, together with a larger classical part…

But the insight itself comes from a brillant movie I’ve seen recently – “How I came to hate maths” by Olivier Peyon – where the mathematician Rocco Servedio discusses his opinion that sooner or later, computers will not only be able to prove theorems but to discover them – and to do do it better than humans. I guess his intuition basically originates from the game of chess, or from the most recent advances in automated theorem proving…

January 2, 2014 5:55 am

my prediction is that GLL will be my favorite scientific blog in 2014 🙂 Happy New Year 🙂

January 2, 2014 11:19 am

Istvan,

Very kind. Happy new year to you and all.

5. January 2, 2014 1:41 pm

If only the first one could be true, the rest would probably fall right in line.

• January 3, 2014 4:09 am

jolie as mathematician? that shows dr.lipton never went to the grad dept in math programs.

January 2, 2014 11:03 pm

1) There was an episode of Elementary (the Sherlock Holmes in modern day) series that centered around P=NP and crypto. Not quite what you predicted. Close? Depends on how you define close.

2) I predict that a book of blog posts by a pair of prominent theorists who jointly run a blog who are not Fortnow/Gasarch. will come out and be awesome. (Coming out in Dec 27, 2013 is, in my mind, coming out in 2014.)

7. January 4, 2014 5:10 pm

Lovely post! I have one comment on this year’s prediction and one on last year’s. Mathematical football is already an important area of (solitary) activity. This post http://gilkalai.wordpress.com/2009/04/20/the-intermediate-value-theorem-applied-to-football/
proposes a new mathematical way to revolutionize football (aka soccer). Some theoretical difficulties were raised by Weinberger and resolved by Gowers in the comment section. Szemeredi, known himself as an excellent football player was also very pleased with this direction. Another way to revolutionize football is proposed here http://gilkalai.wordpress.com/2011/06/09/another-way-to-revolutionize-football/

Yet another way to revolutionize table-football (fussball), was invented and implemented by me with Oded, Tselil, and Pele Schramm around 2000. The idea is to play as ususal but the two teams are the four right hands of the four players against the four left hands of the four players. (I don’t remember which team won although this is apparently the most important thing if not the only.)

While BosonSampling is indeed quite exciting, prediction 8) of last year seems very reasonable. The post http://gilkalai.wordpress.com/2013/08/01/bosonsampling-and-bks-noise-sensitivity/ is relevant as well some updates from the same time for my older post on the matter: http://gilkalai.wordpress.com/2010/11/17/aaronson-and-arkhipovs-result-on-hierarchy-collapse/

January 7, 2014 11:02 am

Gil, please let me expression the thanks and appreciation (of me and many) for your wonderful 2013 debate with Aram Harrow. Hopefully this debate will continue into 2014 (and beyond)!

In regard to the Kalai/Harrow debate, our Soldier Healing Seminar’s SHS notes for 2013 essays the following cautious prediction:

“Varietal dynamical systems provide formal models for (Kalai-type) quantum postulates that seemingly can’t support scalable quantum computing … unless they can, depending on the scaling that is postulated for the state-space variety’s tensor rank, resolution of singularities, and symplectomorphic monodromy (of thermodynamic cycles).

Similarly, varietal systems (seemingly) can’t simulate BosonSampling in PTIME … unless they can, depending upon the scaling that is postulated for the Lindblad/Carmichael unravelling of finite-noise BosonSampling experiments.”

Here the main point is that the three notions in-question:

(1) the Kalai non-scaling postulates, and
(2) scalable quantum computing, and
(3) scalable BosonSampling observations,

are individually so wonderful, and collectively bear so directly upon urgent human concerns, that a prediction born-of-hope is that the Kalai-Harrow debate will in future years establish the mutual consistency of all three postulates. In short, the SHS notes foresees the eventual verdict of history in regard to the Kalai-Harrow debate as “You’re all absolutely right.”

Meanwhile, everyone (including me) appreciates you and Aram — and appreciates too Dick’s and Ken’s GLL&P=NP weblog, and also Scott Aaronson and Alex Arkhipov — for gifting us with a 2013 that has been full of marvelous ideas.

• January 8, 2014 1:04 pm

Dear John, you may be interested to watch lectures from our winter school on Frontiers of quantum information. http://www.as.huji.ac.il/schools/phys31 In particular part of Frank’s Verstraete’s lecture III discusses non-linear Schrodinger-like equations on low dimensional non-flat submanifolds of huge Hilbert spaces which is a topic you like.

8. January 5, 2014 12:18 pm

Happy New Year!
I think some of the questions to be tackled in quantum computing this year will be a look at the scaling problem in terms of what we can say about the “free-will” of such devices. Schemes for quantum correction algorithms will be begin being viewed as how to restrict the free-will of systems.

http://thefurloff.com/2014/01/05/i-have-free-will-even-if-you-dont-but-maybe-you-do/

9. January 5, 2014 12:27 pm

Sorry for the double tap,
Just in case the other comment got eaten, I have a prediction that questions to be tackled in quantum computing this year will addressed by looking at the scaling problem in terms of what we can say about the “free-will” of such devices. Schemes for quantum correction algorithms will be begin being viewed as how to restrict the free-will of systems.

http://thefurloff.com/2014/01/05/i-have-free-will-even-if-you-dont-but-maybe-you-do/

10. January 6, 2014 8:28 am

Very important!
Open problem solution!!!

Nobel Prize to CS is open problem. But just here is its solution. Someone from very rich people (Bill Gates or Sergey Brin, for example) would be able to fix his name in history as Nobel-2. For that he have to make Nobel-2 Prize (like Nobel Prize) for CS. As for me, I hope to be the first winner of this Prize for the idea 😉

— Michael Trofimov,
another open problem solved by me is GI problem:

http://arxiv.org/abs/1004.1808

(some bugs were found, so, please, wait for new version soon!)

PS Google and MS read this blog, so I am sure that Bill Gates and Sergey Brin will be informed. To help their search I add following keywords:
* Very important for Microsoft
* Very important for Bill Gates
* Very important for Sergey Brin
(I think this one is quite enough: MS is interested in “very important for Google” and visa versa, others are interested in “very important for Google or/and MS” 😉

PPS What do you think: is it joke only? 😉