New Insights into Computational Intractability
September 30 - October 4, 2013
Clay Mathematics Institute
Mathematical Institute
University of Oxford
Computational complexity theory deals with the central mystery of computation: What is feasible to compute, and what computational tasks will forever remain out of reach? Although the main open questions (such as the Millennium Problem of P versus NP) continue to elude us, exciting progress has been reported on a number of fronts recently. This workshop will bring together many leading researchers in the field of computational complexity theory, and provide a forum where they can share their perspectives on the new insights that have been obtained.
This workshop will take place in the new Mathematical Institute building during the week of its opening.
Participation in the workshop is by invitation. A limited number of additional places is available. Please register your interest here.
Schedule
Monday, September 30
| 9:00-9:45 | Ketan Mulmuley The GCT Chasm |
| 9:45-10:30 | Peter Bürgisser Prospects for Geometric Complexity Theory |
| 10:30-11:15 | Break |
| 11:15-12:00 | Peter Bro Miltersen Real Algebraic Geometry and Computational Complexity |
| 12:00-2:00 | Lunch |
| 2:00-2:45 | Russell Impagliazzo Meta-Computational Problems as a Link between Algorithms and Lower Bounds |
| 2:45-3:30 | Rahul Santhanam QBF Algorithms and Circuit Lower Bounds |
| 3:30-4:15 | Break |
| 4:15-5:00 | Ryan Williams Algorithms for Circuits and Circuits for Algorithms |
Tuesday, October 1
| 9:00-9:45 | Martin Dyer The #CSP Dichotomy |
| 9:45-10:30 | Leslie Ann Goldberg The Complexity of Approximate Counting |
| 10:30-11:15 | Break |
| 11:15-12:00 | Mark Jerrum Phase Transitions and Computational Intractability |
| 12:00-2:00 | Lunch |
| 2:00-2:45 | Irit Dinur PCPs and Direct Products |
| 2:45-3:30 | Peter Jeavons Structure in Satisfiability |
| 3:30-4:15 | Break |
| 4:15-5:00 | Stephen Cook The Complexity of the Comparator Circuit Value Problem |
Thursday, October 3
| 9:00-9:45 | Scott Aaronson Computational Complexity and Physics |
| 9:45-10:30 | Elias Koutsoupias Monotone Computation and Economics |
| 10:30-11:15 | Break |
| 11:15-12:00 | Salil Vadhan Computational Intractability in Data Privacy |
Friday, October 4
| 9:00-9:45 | Manindra Agrawal Polynomial Identity Testing for Small Depth Circuits |
| 9:45-10:30 | Paul Goldberg The Complexity of Computing the Solution Obtained by a Specific Algorithm |
| 10:30-11:15 | Break |
| 11:15-12:00 | Georg Gottlob The Monotone Duality Problem |
| 12:00-2:00 | Lunch |
| 2:00-2:45 | Toniann Pitassi Topics in Communication Complexity and Information Complexity |
| 2:45-3:30 | Harry Buhrman Reverse Newman's Theorem in Interactive Information Complexity |
| 3:30-4:15 | Break |
| 4:15-5:00 | Eric Allender Complexity Classes via Algorithmic Information Theory |
Return to top