[Colloquium] TTI-C Talk: Mikhail Alekhnovitch Tomorrow @ 3:00pm

[Katherine Cumming]

TOYOTA TECHNOLOGICAL INSTITUTE TALK
 
Thursday, March 3rd, 3:00pm
TTI-C Conference Room (1427 E. 60th St. - 2nd Floor) 
Refreshments provided
 
 
Speaker: Mikhail Alekhnovitch; Institute for Advanced Study, School of
Mathematics
Speaker's homepage: http://www.math.ias.edu/~misha/
 
Title: Hard Satisfiable Instances for DPLL Algorithms and Other Weak
Models of Computation
Abstract:
DPLL (for Davis, Putnam, Logemann, and Loveland) algorithms form the
largest family of contemporary algorithms for SAT (the propositional
satisfiability problem) and are widely used in applications. While the
behavior of DPLL algorithms on unsatisfiable formulas has been
extensively investigated (by studying the refutation size in Resolution
proof system), little research was done towards proving lower bounds on
satisfiable instances. We fill this gap by constructing satisfiable
formulas which are provably difficult for a wide class of DPLL
algorithms.

In the second part of the talk I will survey some lower bounds on other
restricted computational models, which include a generalization of our
results for backtrack SAT algorithms and proving integrality gaps for
Lovasz-Schrijver hierarchy for the linear relaxations of a (hypergraph)
vertex cover.

The talk is based on the joint work with: Edward Hirsch, Dmitry
Itsykson, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo,
Avner Magen, Toniann Pitassi Sanjeev Arora, Iannis Tourlakis 
If you have questions, or would like to meet the speaker, please contact
Katherine at 4-1994 or kcumming at tti-c.org. For information on future
TTI-C talks or events, please go to the TTI-C Events
<http://ttic.uchicago.edu/events/events_dyn.php>  page. 
 
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20050302/6072a5fc/attachment.htm