BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1578
DTSTAMP:20250703T094715Z
SUMMARY:Supercritical Tradeoffs in Resolution
DESCRIPTION:Speaker: Sreejata Kishor  Bhattacharya (TIFR)\n\nAbstract: \nTr
 adeoffs in propositional proof complexity typically involve two parameters
  (e.g.\, size\, width\, depth) and exhibit a CNF for which both of these p
 arameters can be made small separately\, but keeping one parameter small n
 ecessarily makes the other parameter big. Typically\, the lower bound on t
 he other parameter is close to the trivial upper bound on that parameter.\
 nIn a supercritical tradeoff\, keeping one parameter small implies a lower
  bound on the other parameter which is significantly larger than the trivi
 al upper bound. The first such supercritical tradeoff for resolution was e
 xhibited by Razborov\, for the parameters width and tree-size. Since then 
 there has been active research on finding more supercritical tradeoffs.\nW
 e shall describe the first supercritical tradeoff found by Razborov: there
  exists a CNF which has a refutation of width k\, but any tree-like refuta
 tion of width $n^{1-epsilon}/k$ must have size $exp(n^k)$. (The trivial up
 per bound for tree-like size is $exp(n)$)\n
URL:https://www.tcs.tifr.res.in/web/events/1578
DTSTART;TZID=Asia/Kolkata:20250704T160000
DTEND;TZID=Asia/Kolkata:20250704T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR