BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/481
DTSTAMP:20230914T125926Z
SUMMARY:Beating Brute Force Search for QBF Satisfiability\, and Implication
 s for Formula Size Lower Bounds
DESCRIPTION:Speaker: Rahul Santhanam (University of Edinburgh\nSchool of In
 formatics\n10\, Crichton Street\nEdinburgh - EH8 9AB\nUnited Kingdom)\n\nA
 bstract: \nAbstract: We give the first algorithms for the QBF Satisfiabili
 ty problem beating brute force search. We show that the QBF satisfiability
  question for CNF instances with $n$ variables\, $q$ quantifier blocks and
  size $poly(n)$ can be solved in time $2^{n-\\Omega(n^{1/(q+1)})}$\, and t
 hat the QBF satisfiability question for circuit instances with $n$ variabl
 es\, $q$ quantifier blocks and size $poly(n)$ can be solved in time $2^{n-
 \\Omega(q)}$. We also show that improvements on these algorithms would lea
 d to super-polynomial formula size lower bounds for NEXP (this is joint wo
 rk with Ryan Williams).\n
URL:https://www.tcs.tifr.res.in/web/events/481
DTSTART;TZID=Asia/Kolkata:20140417T160000
DTEND;TZID=Asia/Kolkata:20140417T170000
LOCATION:AG-80
END:VEVENT
END:VCALENDAR