Gödel Prize 2015

Dear colleagues,

I am happy to inform you that the Gödel Prize 2015 is awarded to Daniel A. Spielman and Shang-Hua Teng for their series of

papers on nearly-linear-time Laplacian solvers:

  • 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 full citation for the award, which is presented jointly by ACM SIGACT and the EATCS,  is available at


This is the second time that Daniel A. Spielman and Shang-Hua Teng receive the Gödel Prize, which was presented to them at ICALP 2008 in Reykjavik for their work on smoothed analysis. Congratulations to Dan and Shang-Hua!

On behalf of the EATCS, I thank the 2015 Gödel Prize committee, which consisted of Krzysztof Apt (CWI Amsterdam),
Kurt Mehlhorn (Max Planck Institute), Joseph Mitchell (Stony Brook University), Andrew Pitts (University of Cambridge),
Madhu Sudan (Microsoft Research) and Éva Tardos, Chair (Cornell University), for their sterling work.

Best regards,

Luca Aceto

President of EATCS

e-max.it: your social media marketing partner
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.