BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Parameterized Complexity of DPLL Search Procedures - Beyerdorff\, 
 O (Universit degli Studi di Roma La Sapienza)
DTSTART:20120326T140000Z
DTEND:20120326T143000Z
UID:TALK37093@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:We study the performance of DPLL algorithms on parameterized p
 roblems. In particular\, we investigate how difficult it is to decide whet
 her small solutions exist for satisfiability and other combinatorial probl
 ems. For this purpose we develop a Prover-Delayer game which models the ru
 nning time of DPLL procedures and we establish an information-theoretic me
 thod to obtain lower bounds to the running time of parameterized DPLL proc
 edures. We illustrate this technique by showing lower bounds to the parame
 terized pigeonhole principle and to the ordering principle. As our main ap
 plication we study the DPLL procedure for the problem of deciding whether 
 a graph has a small clique. We show that proving the absence of a k-clique
  requires $n^{Omega(k)}$ steps for a non-trivial distribution of graphs cl
 ose to the critical threshold. For the restricted case of tree-like Parame
 terized Resolution\, this result answers a question asked in [BGLR11] of u
 nderstanding the Resolution complexity of this family of formulas.\n\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR