Tata Institute of Fundamental Research
Phase Transitions in Random k-satisfiability Problems
Special Random Interactions
Speaker:
Sumedha (NISER
PO: Sainik School
Khorda District
Bhubaneswar
Odisha)
Date:
Monday, 12 Oct 2015, 16:00 to 17:00
Venue:
A-304 (Theoretical Physics Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: k-satisfiability is a constraint satisfaction problem where one wants to find the assignments of Boolean variables that satisfies a given set of constraints(or clauses). The problem is known to undergo phase transitions as a function of the ratio of constraints and variables. Phase transitions in random k-satisfiability problems 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 discuss random k-satisfiability and many of its variants on regular trees. The solvability threshold for k = 2 matches the exact value of the threshold on regular random graphs. For higher k, the values are very close to those predicted using other techniques like the cavity method.
| Speaker: | Sumedha (NISER PO: Sainik School Khorda District Bhubaneswar Odisha) |
| Date: | Monday, 12 Oct 2015, 16:00 to 17:00 |
| Venue: | A-304 (Theoretical Physics Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: k-satisfiability is a constraint satisfaction problem where one wants to find the assignments of Boolean variables that satisfies a given set of constraints(or clauses). The problem is known to undergo phase transitions as a function of the ratio of constraints and variables. Phase transitions in random k-satisfiability problems 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 discuss random k-satisfiability and many of its variants on regular trees. The solvability threshold for k = 2 matches the exact value of the threshold on regular random graphs. For higher k, the values are very close to those predicted using other techniques like the cavity method.