EATCS-IPEC Nerode Prize 2013 - Laudatio
On the Exact Complexity of Evaluating Quantified k-CNF
Chris Calabro, Russell Impagliazzo, Ramamohan Paturi, Algorithmica 2013
The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs
Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan, Paturi, Journal of Computer and System Sciences 2008
On the Complexity of k-SAT
Russell Impagliazzo, Ramamohan Paturi, Journal of Computer and System Sciences 2001
Which Problems Have Strongly Exponential Complexity?
Russell Impagliazzo, Ramamohan Paturi, Francis Zane, Journal of Computer and System Sciences 2001
The Nerode Prize 2013 Committee, consisting of Georg Gottlob (University of Oxford, UK), Rolf Niedermeier (TU Berlin, Germany; chair), and Peter Widmayer (ETH Zurich, Switzerland), has unanimously decided to award Chris Calabro (Google Inc., Mountain View, USA), Russell Impagliazzo (UC San Diego, USA), Valentine Kabanets (Simon Fraser University, Canada), Ramamohan Paturi (UC San Diego, USA), and Francis Zane (Alcatel Lucent, Murray Hill, USA) the 2013 EATCS-IPEC Nerode Prize for outstanding papers in the area of multivariate algorithmics.
Their series of papers elaborates on what is known as the Exponential Time Hypothesis (ETH), and its stronger variant, the Strong Exponential Time Hypothesis (SETH). These complexity assumptions state lower bounds on how fast Boolean Satis ability problems can be solved. A key result of the corresponding theory is the Sparsi cation Lemma, a core tool in the area of developing relative lower bounds for NP-hard problems, which lends credence to the ETH. Altogether, the papers open an avenue for proving exponential lower bounds (assuming ETH or SETH) for a multitude of diverse computational problems, helping to derive tight parameterized computational complexity results. This has led to numerous recent advances in the eld of multivariate algorithmics, thus adding a central tool to the repertoire of worst-case complexity analysis. The obtained insights also have a strong impact on elds such as structural and communication complexity theory. The knowledge of the (S)ETH now belongs into the standard toolkit of every researcher in multivariate algorithmics.
 |
