Mark Braverman has achieved fundamental results in complexity theory, the theory of computation over the reals, approximation algorithms, computational learning theory, information theory, algorithmic economics, pseudorandomness and communication complexity. In 2009, using a surprisingly simple argument from harmonic analysis, he completely settled the Linial-Nisan conjecture that any k-wise independent distribution will look completely random to a bounded depth boolean circuit. He and his collaborators cast new light on the computability and computational complexity of Julia sets and disproved a long-standing conjecture of Krivine on the value of Grothendieck’s constant. Through his many seminal results, he has become a leader in extending information theory to an interactive setting, developing the theory of information complexity, a thriving subfield at the boundary of theoretical computer science and electrical engineering. On this topic, he is currently co-organizing a semester on the Nexus of Information and Computation Theories at the Institut Henri PoincarĂ© in Paris, January-April 2016. For more information see here.
The Presburger Award is given to a young scientist (in exceptional cases to several young scientists) for outstanding contributions in theoretical computer science, documented by a published paper or a series of published papers. The list of the previous recipients of the Presburger Award is available at
http://eatcs.org/index.php/
The Presburger Award carries a prize money of 1000 Euros and will be delivered at ICALP 2016, which will take place in Rome (Italy) from the 12th till the 15th of July 2016.
The 2016 Presburger Award Committee consisted of Zoltan Esik (University of Szeged, Hungary), Marta Kwiatkowska (University of Oxford, UK) and Claire Mathieu (ENS Paris, France; chair).
No comments:
Post a Comment