Members of the CSAIL Theory of Computation (TOC) group will be taking home top honors from the 2014 Association for Computing Machinery (ACM) – Society for Industrial and Applied Mathematics (SIAM) Symposium on Discrete Algorithms (SODA). Students, faculty and postdoctoral associates from TOC have been named as winners of all three best paper awards.
Two groups from TOC were jointly awarded the Best Paper Award, which recognizes top-rated papers that introduce a strong new technique, provide a solution for a long-standing problem, or introduce or solve solution an interesting and important new problem. Professor Michael Goemans and postdoctoral fellow Thomas Rothvoss were honored with the Best Paper Award for their paper, “Polynomiality for Bin Packing with a Constant Number of Item Types.” Professor Jonathan Kelner, graduate student Yin Tat Lee, Dr. Lorenzo Orecchia and graduate student Aaron Sidford were recognized for their paper, “An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations.”
Graduate student Gregory T. Minton and former CSAIL graduate student Eric Price were honored with the Best Student Paper Award for their paper “Improved Concentration Bounds for Count-Sketch.” Winners of the Best Student Paper Award
Since its inception, the CSAIL TOC group has played a leadership role in the evolution of the theory of computation. Members have made such seminal research contributions as the RSA public-key cryptosystem, the pseudo randomness from hardness paradigm, the first super-polynomial size lower bound for a natural class of Boolean circuits, the impossibility of asynchronous consensus, zero-knowledge interactive proofs and more. For more information on the group, please visit: http://toc.csail.mit.edu/.