BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/629
DTSTAMP:20230914T125932Z
SUMMARY:Phase Transitions in Random k-satisfiability Problems
DESCRIPTION:Speaker: Sumedha (NISER\nPO: Sainik School\nKhorda District\nBh
 ubaneswar\nOdisha)\n\nAbstract: \nAbstract: k-satisfiability is a constrai
 nt satisfaction problem where one wants to find the assignments of Boolean
  variables that satisfies a given set of constraints(or clauses). The prob
 lem is known to undergo phase transitions as a function of the ratio of co
 nstraints and variables. Phase transitions in random k-satisfiability prob
 lems are believed to be connected to their computational complexity. While
  polynomial time algorithms are known to solve the problem for k = 2\, for
  k ≥ 3 the problem is known to be NP-complete. In this talk\, we will di
 scuss random k-satisfiability and many of its variants on regular trees. T
 he solvability threshold for k = 2 matches the exact value of the threshol
 d on regular random graphs. For higher k\, the values are very close to th
 ose predicted using other techniques like the cavity method.\n \n
URL:https://www.tcs.tifr.res.in/web/events/629
DTSTART;TZID=Asia/Kolkata:20151012T160000
DTEND;TZID=Asia/Kolkata:20151012T170000
LOCATION:A-304 (Theoretical Physics Seminar Room)
END:VEVENT
END:VCALENDAR