ColloquiaTalk by Dieter van Melkebeek, Institute for Advanced Study, April 5th

[Margery Ishmael]

Thursday, April 5th at 2:30 p.m. in Ryerson 251

Speaker: Dieter van Melkebeek, Institute for Advanced Study

Title: Time-Space Tradeoffs for Satisfiability

Abstract:  Satisfiability is the problem of deciding whether a given
propositional formula has a satisfying assignment. It is the seminal
NP-complete problem and is of major practical importance. Although we
expect satisfiability to take exponential time in the worst case, we
do not know how to prove that no linear-time algorithm exists on a
general-purpose random-access machine. The same situation holds for
Boolean circuits deciding satisfiability.

In recent years we have seen a new approach to establish
superlinear time lower bounds for machines that only use a small
amount of space. We will survey the underlying ideas and present the
strongest result of this type so far: Satisfiability cannot be solved
on general-purpose random-access machines running in n^{1.618}
time and subpolynomial space. In general, for any constant c less
than the golden ratio, we prove that satisfiability cannot be solved
in n^c time and n^d space for some positive constant d depending on c.

We obtain these results by establishing time-space tradeoffs for
nondeterministic linear time. The same techniques yield new lower
bounds on conondeterministic versus nondeterministic computation,
as well as on circuits deciding satisfiability.

Joint work with Lance Fortnow.
http://medan.math.ias.edu/~dieter/

*The talk will be followed by refreshments in Ryerson 255*
If you'd like to meet the speaker, please send e-mail to marge at cs.uchicago.edu
-- 
Margery Ishmael
Department of Computer Science
The University of Chicago
1100 E. 58th Street
Chicago, IL. 60637

Tel. 773-834-8977  Fax. 773-702-8487