Babai did seminal research on interactive proofs, communication complexity, group algorithms and much more. One cannot count the number of PhD theses in mathematics and computer science that can trace themselves back to some initial work by Babai. I was lucky to have Laci Babai as a colleague, mentor and friend during my years at the University of Chicago.
- Spectral sparsification of graphs. SIAM J. Computing 40:981-1025, 2011.
- A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM J. Computing 42:1-26, 2013.
- Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM J. Matrix Anal. Appl. 35:835-885, 2014.
The ACM Awards ceremony later this month will have a number of theory related prizes.
- Dan Boneh is the recipient of the ACM-Infosys Foundation Award in the Computing Sciences for the development of pairing-based cryptography and its application in identity-based encryption.
- James Demmel is the recipient of the Paris Kanellakis Theory and Practice Award for his work on numerical linear algebra libraries, including LAPACK.
- Charles Leiserson will receive the ACM-IEEE CS Ken Kennedy award for his work on parallel computing.
- Jon Kleinberg is the 2014 recipient of the ACM – AAAI Allen Newell Award for social and information networks, information retrieval, and data science, and for bridging computing, economics and the social sciences.
- New ACM Fellows include Al Borodin, Faith Ellen, Michael Kearns, Valerie King, Yishay Mansour, Michael Mitzenmacher, Omer Reingold, Ronitt Rubinfeld and Aravind Srinivasan.