Assistant Professor Jonathan Kelner has been named one of the winners of the Best Paper Award for the annual Association for Computing Machinery (ACM) Symposium on Theory of Computing (STOC), to be held in June.
The paper, “Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs,” was written by Kelner, MIT EECS graduate student Aleksander Madry, MIT undergraduate student Paul Christiano, Yale Professor Daniel Spielman and USC Professor Shang-Hua Teng. The paper offers a new, and the fastest-known, approach to computing an approximately maximum s-t flow.
Bernhard Haeupler, a PhD student in CSAIL’s Theory of Computation group and one of Kelner’s advisees, has been awarded the Danny Lewin Best Student Paper Award at STOC. Haeupler was honored for his paper “Analyzing Network Coding Gossip Made Easy.”
Haeupler’s work presents a new technique for analyzing the stopping time of gossip protocols based on random linear network coding (RLNC).
The Danny Lewin Best Student Paper Award is presented to one student each year at STOC. The prize comes with a $500 award for the author. Previous recipients include CSAIL Associate Professor Scott Aaronson and Kelner.
For more on Kelner’s work, visit http://math.mit.edu/~kelner/index.html, and for more on Haeupler’s work, visit http://people.csail.mit.edu/haeupler/.