Seminars

View all Seminars  |  Download ICal for this event

Counting and Sampling random k-SAT near the satisfiability threshold 

Series: Bangalore Theory Seminars

Speaker: Aditya Lonkar, Georgia Tech

Date/Time: Jan 09 11:00:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

Abstract:
We present efficient counting and sampling algorithms for random k -SAT when the clause density satisfies α ? 2^k /poly(k) . In particular, the exponential term 2^k matches the satisfiability threshold ?(2^k) for the existence of a solution and the (conjectured) algorithmic threshold 2^k.(ln k)/k for efficiently finding a solution.

Previously, the best-known counting and sampling algorithms required far more restricted densities α ? 2^{k/3} [He, Wu, Yang 23]. Notably, our result goes beyond the lower bound d ? 2^{k/2} for worst-case k -SAT with bounded-degree d [Bezakova, Galanis, Goldberg, Guo, Stefankovic 19], showing that for counting and sampling, the average-case random k -SAT model is computationally much easier than the worst-case model.

At the heart of our approach is a new refined analysis of the recent novel coupling procedure by [Wang, Yin 24], utilizing the structural properties of random constraint satisfaction problems (CSPs). Crucially, our analysis avoids reliance on the 2-tree structure used in prior works, which cannot extend beyond the worst-case threshold 2^{k/2} . Instead, we employ a witness tree similar to that used in the analysis of the Moser-Tardos algorithm for the Lovasz Local lemma, which may be of independent interest. Our new analysis provides a universal framework for efficient counting and sampling for random atomic CSPs, including, for example, random hypergraph colorings. At the same time, it immediately implies as corollaries several structural and probabilistic properties of random CSPs that have been widely studied but rarely justified, including replica symmetry and non-reconstruction.

Microsoft Teams link:

Link


We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series


Hosts: Rameesh Paul, Nirjhar Das, KVN Sreenivas, Debajyoti Kar, Rahul Madhavan