[Colloquium] TTI-C Talk: Ryan Williams, Carnegie Mellon University

[Julia MacGlashan]

When:             Tue, Mar 11, 2008 @ 2:00 pm

 

Where:            TTI-C Conference Room

 

Who:               Ryan Williams, Carnegie Mellon University 

 

Topic:             Applying Practice to Theory: Time Lower Bounds for
Fundamental Problems

 

 

A fertile area of recent research has demonstrated concrete polynomial time
lower bounds for solving natural hard problems on restricted computational
models. Among these problems are Satisfiability, Vertex Cover, Hamilton
Path, MOD6-SAT, Majority-of-Majority-SAT, and Tautologies, to name a few.
These lower bound proofs all follow a certain diagonalization-based
proof-by-contradiction strategy. A pressing open problem has been to
determine how powerful such proofs can possibly be.

 

I will survey some of my work in this area, with an emphasis on simplicity.
After a brief overview of the proof techniques used, I will propose an
automated search strategy for studying the limits of these proof techniques.
In particular, I will demonstrate how the search for better lower bounds can
often be turned into a problem of solving a large series of linear
programming instances. This mathematical work has in turn led to a new
methodology for proving time lower bounds, where prospective lower-bounders
formulate their proof rules, write programs to generate optimal short
proofs, then study the empirical results and extrapolate new proofs on
paper.

 

In some settings, our programs provide strong evidence that the best known
lower bound proofs are already optimal for the current framework,
contradicting the consensus intuition; in other settings, we are guided to
improved lower bounds where no further progress had been made for some time.

 

Contact:          Lance Fortnow         fortnow at eecs.northwestern.edu
834-9873

 

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20080310/29770440/attachment.html