Monday, June 17, 2019

Why does the Nevalina Prize (now Abacus) got to Algorithms/Complexity people

In my post about the Nevanlinna prize  name change (see here) one of my readers raised a different question about the prize:


So there's one of my main questions about the prize answered (or at least resolved). The second remains. The IMU's website(which still refers to the Nevanlinna Prize) says that it is awarded "for outstanding contributions in Mathematical Aspects of Information Sciences including:"

1)All mathematical aspects of computer science, including complexity theory, logic of programming languages, analysis of algorithms, cryptography, computer vision, pattern recognition, information processing and modelling of intelligence.

2)Scientific computing and numerical analysis. Computational aspects of optimization and control theory. Computer algebra.

Correct me if I'm wrong, but it seems that the recognized work of the ten winners of the award all fits into two or three of the possible research areas for which the prize may be rewarded. Why do people think that this is the case?


First off, lets see if this is true. Here is a list of all the winners:

Tarjan, Valiant, Razborov, Wigderson, Shor, Sudan, Kleinberg, Spielman, Khot, Daskalakis 

Yup, they all seem to be in Algorithms or Complexity.

Speculation as to why:

1) Algorithms and Complexity have problems with short descriptions that can easily be understood: Tarjan proved Planarity was in O(n) time. Valiant defined Sharp-P and showed the Permanent was Sharp-P complete. Hence it is easy to see what they have done. In many of the fields listed, while people have done great work, it may be harder to tell since the questions are not as clean.  If my way to do Vision is better than your way to do Vision, that may be hard to prove. And the proof  may need to be non-rigorous.

2) If someone does great work in (for example) Logic of Programming Languages, it may not be recognized until she is past 40 years old. 

3) This one I am less sure of (frankly I'm not that sure of any of these and invite polite commentary): areas that are more practical may take longer to build and get to work.

But there is still a problem with this. Numerical Analysis and Cryptography would seem to not have these problems. 

I invite the reader to speculate


  1. Because the US has a big weight in CS research, and in the US algorithms and complexity has a big weight in CS theory.
    Also in algorithms and complexity there are precisely defined open problems with (sometimes) precise mathematical solutions. That's a good fit with a prize awarded during a math congress.


  2. I disagree with the characterization of the winners. While you can count Jon Kleinberg among algorithms researchers that is too limiting, his biggest contributions for the prize were conceptual, extending the reach of the methods of discrete mathematics and TCS to a social context, not solving specific open problems.

    At every ICM there is a prize short-list that is essentially public - just look at the TCS invited plenary speakers under the age of 40.

    Cryptography has been represented in that group of invitees. In general, cryptographers do have the problem that their theorems mostly involve reductions to unproven conjectures.

    On the more logical side, Andrei Bulatov was an invited speaker in 2014 and so clearly was a finalist.

    I also don't think that the list of winners/invitees is very related to the US-Europe differences in the style of research. I was trying to see who would be natural candidates with a different scope of research. EATCS has its own prize for specific papers/series of papers by young scientists, the Presburger Award, so I thought I would look among the winners of that award. Most of the winners would be winners on either side of the Atlantic. Each of the TCS winners at the ICM has had multiple major contributions to the field.

  3. An even more tantalizing question is, why doesn't the prize go to female computer scientists? Is it because of the ridiculous cutoff at 40 years of age? That is definitely a big contributing factor due to the impact that having children has on women, and also since as some would argue, it takes much longer for women's contributions to be recognized. It is not the whole story of course. I hope that the prize committee at least considers having some sort of clause to help women, such as extending the 40 year clause for people who have had kids. The Sloan fellowship has such a clause for instance. Anyway, I thought I'd say something, as these things are on my mind.

  4. In reply to Anonymous: The committee that chooses the Nevanlinna Prize finalists and the committee that chooses the invited speakers are different, and I don't believe that they talk to each other. Not all Fields Medalists are invited speakers (although if they're not, they get their own Fields Medalist talks where their names aren't announced ahead of time. Thus, saying that Andrei Bulatov was "clearly a finalist" is wrong.

    On the other hand, both the invited speakers and the Nevanlinna Prize winners are chosen by mathematicians, so the criteria should be similar.