BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1583
DTSTAMP:20250715T052505Z
SUMMARY:A Theory for Computing with SAT Solvers: What's the Power of a Sati
 sfying Assignment?
DESCRIPTION:Speaker: Kuldeep Meel (Georgia Institute of Technology)\n\nAbst
 ract: \nThe past two decades have witnessed dramatic improvements in SAT s
 olving\, enabling today's solvers to handle problems involving millions of
  variables. Motivated by the power of SAT solvers\, there is a growing int
 erest in tackling problems that lie in higher classes of the polynomial hi
 erarchy\, wherein NP calls are to be replaced by SAT solvers in practice. 
 The complexity of such algorithms is measured in terms of calls to NP orac
 les. However\, SAT solvers are not mere decision oracles: they also provid
 e a satisfying assignment when the formula is satisfiable. Therefore\, a t
 heory based on NP oracles is limiting\, and there is a need for a theory t
 hat takes into account the power of SAT solvers. In this talk\, I will dis
 cuss how such consideration leads to new algorithms and new lower bounds i
 n the context of two fundamental problems: model counting and sampling.\nB
 ased on joint work (LICS-22 and ICALP-23) with Diptarka Chakaraborty\, Sou
 rav Chakraborty\, Remi Delannoy\, and Gunjan Kumar.\nShort Bio:Kuldeep Mee
 l holds Stephen Fleming Early-Career Associate Professorship in the School
  of Computer Science at GeorgiaTech\, and an Associate Professor at the Un
 iversity of Toronto (on leave). His research interests lie at the intersec
 tion of Formal Methods and Artificial Intelligence. He is a recipient of t
 he 2022 ACP Early Career Researcher Award\, the 2019 NRF Fellowship for AI
 \, and was named AI's 10 to Watch by IEEE Intelligent Systems in 2020. His
  research program's recent recognitions include the 2023 CACM Research Hig
 hlight Award\, 2022 ACM SIGMOD Research Highlight\, IJCAI-22 Early Career 
 Spotlight\, Distinguished Paper Award at CAV-23\, "Best Papers of CAV" (20
 20 and 2022) special issue in FMSD journal\, Best Paper Award nominations 
 at ICCAD-21 and DATE-23\, 1st Place in Model Counting Competition (2020 an
 d 2022). He is passionate about teaching\, and most proud of being recipie
 nt of university-level Annual Teaching Excellence Awards in 2022 and 2023.
 \n
URL:https://www.tcs.tifr.res.in/web/events/1583
DTSTART;TZID=Asia/Kolkata:20250717T110000
DTEND;TZID=Asia/Kolkata:20250717T120000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR