Giovedì 15 maggio alle ore 14.30 Zongchen Chen (Georgia Institute of Technology) terrà il seminario
Title: *Counting Random k-SAT Near the Satisfiability Threshold*.
Abstract: We present efficient counting and sampling algorithms for random k-SAT when the clause density is at most 2^k/poly(k). In particular, the exponential term 2^k matches the satisfiability threshold O(2^k) for the existence of a solution and the (conjectured) algorithmic threshold 2^k (\ln k)/k for efficiently finding a solution. At the heart of our approach is a refined analysis of the recent novel coupling procedure introduced by Wang and Yin. Our new analysis utilizes the structural properties of random constraint satisfaction problems (CSPs). It provides a universal framework for efficient counting and sampling for random atomic CSPs, including, for example, random hypergraph colorings. At the same time, we obtain as immediate corollaries several important probabilistic properties of random CSPs that have been widely studied but rarely justified, including replica symmetry and non-reconstruction. Joint work with Aditya Lonkar, Chunyang Wang, Kuan Yang, and Yitong Yin.
Il seminario si svolgerà presso il Dipartimento di Matematica e Fisica di Roma Tre, Via della Vasca Navale 84, Aula A.