BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1314
DTSTAMP:20230914T125959Z
SUMMARY:Majority-3SAT in Polynomial Time
DESCRIPTION:Speaker: Ratnakar Medepalli\n\nAbstract: \nMajority-SAT is the 
 problem of determining whether a boolean formula evaluates to true on more
  than half of its assignments. Majority-SAT is known to be PP-hard. In thi
 s talk\, we will see a polynomial time algorithm for Majority-3SAT\, which
  is the problem of determining whether a 3-CNF formula evaluates to true o
 n more than half of its assignments. The result is surprising because most
  SAT-related problems remain hard when restricted to their corresponding 3
 -CNF variant.\nThis is a result of Shyan Akmal and Ryan Williams from FOCS
  2021.\n
URL:https://www.tcs.tifr.res.in/web/events/1314
DTSTART;TZID=Asia/Kolkata:20230714T140000
DTEND;TZID=Asia/Kolkata:20230714T150000
LOCATION:A201
END:VEVENT
END:VCALENDAR