University of Birmingham > Talks@bham > Combinatorics and Probability Seminar > Counting solutions in the random k-SAT model

## Counting solutions in the random k-SAT modelAdd to your list(s) Download to your calendar using vCal - Andreas Galanis (University of Oxford)
- Thursday 03 December 2020, 16:00-17:00
- Venue to be confirmed.
If you have a question about this talk, please contact M.Jenssen. We give the first efficient algorithm to approximately count the number of solutions in the random k-SAT model when the density of the formula scales exponentially with k. The best previous counting algorithm was due to Montanari and Shah and was based on the correlation decay method, which works up to densities (1+o_k(1))2logk/k, the Gibbs uniqueness threshold for the model. Instead, our algorithm harnesses a recent technique by Moitra to work for random formulas. The main challenge in our setting is to account for the presence of high-degree variables whose marginal distributions are hard to control and which cause significant correlations within the formula. This is joint work with Leslie Ann Goldberg, Heng Guo, and Kuan Yang. This talk is part of the Combinatorics and Probability Seminar series. ## This talk is included in these lists:Note that ex-directory lists are not shown. |
## Other listsMedical Imaging Research Seminars Lab Lunch Beverley Glover## Other talksMachine learning for coarse-graining molecular systems Title tbc Open Problem Workshop Title tbc Title tbc Title tbc |