Fetching the paper…
Reading the bibliography…
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$.
Problems and results on 3-chromatic hypergraphs and some related questions
Paul Erdős and László Lovász · 1975
Earlier work this paper cites.
Asymptotic lower bounds for Ramsey functions
Joel Spencer · 1977
Earlier work this paper cites.
Component structure in the evolution of random hypergraphs
Jeanette Schmidt-Pruzan and Eli Shamir · 1985
Earlier work this paper cites.
A parallel algorithmic version of the Local Lemma
Noga Alon · 1991
Earlier work this paper cites.
Approximating the unsatisfiability threshold of random formulas
Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, and Yannis C. Stamatiou · 1998
Earlier work this paper cites.
Sharp thresholds of graph properties, and the k k -sat problem
Ehud Friedgut · 1999
Earlier work this paper cites.
The asymptotic order of the random k k -SAT threshold
Dimitris Achlioptas and Cristopher Moore · 2002
Earlier work this paper cites.
Analytic and algorithmic solution of random satisfiability problems
Marc Mézard, Giorgio Parisi, and Riccardo Zecchina · 2002
Earlier work this paper cites.
The threshold for random k k -SAT is 2 k ( ln 2 − o ( k ) ) 2^{k}(\ln 2-o(k))
Dimitris Achlioptas and Yuval Peres · 2003
Earlier work this paper cites.
Clustering of solutions in the random satisfiability problem
Marc Mézard, Thierry Mora, and Riccardo Zecchina · 2005
Earlier work this paper cites.
Probability and Computing: Randomized Algorithms and Probabilistic Analysis
Michael Mitzenmacher and Eli Upfal · 2005
Earlier work this paper cites.
Counting good truth assignments of random k k -SAT formulae
Andrea Montanari and Devavrat Shah · 2007
Earlier work this paper cites.
Algorithmic barriers from phase transitions
Dimitris Achlioptas and Amin Coja-Oghlan · 2008
Earlier work this paper cites.
A better algorithm for random k k -SAT
Amin Coja-Oghlan · 2010
Earlier work this paper cites.
A constructive proof of the general Lovász local lemma
Robin A. Moser and Gábor Tardos · 2010
Cited alongside, same era.
New constructive aspects of the Lovász local lemma
Bernhard Haeupler, Barna Saha, and Aravind Srinivasan · 2011
Cited alongside, same era.
Deterministic algorithms for the Lovász local lemma
Karthekeyan Chandrasekaran, Navin Goyal, and Bernhard Haeupler · 2013
Cited alongside, same era.
Sharp thresholds and the partition function
Amin Coja-Oghlan and Daniel Reichman · 2013
Cited alongside, same era.
Exact thresholds for Ising-Gibbs samplers on general graphs
Elchanan Mossel and Allan Sly · 2013
Cited alongside, same era.
On the concentration of the number of solutions of random satisfiability formulas
Emmanuel Abbe and Andrea Montanari · 2014
Cited alongside, same era.
The number of satisfying assignments of random regular k k -SAT formulas
Amin Coja-Oghlan and Nick Wormald · 2018
Later among the works it cites.
Sampling random colorings of sparse random graphs
Charilaos Efthymiou, Thomas P. Hayes, Daniel Štefankovič, and Eric Vigoda · 2018
Later among the works it cites.
Approximation via correlation decay when strong spatial mixing fails
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Daniel Štefankovič · 2019
Closest in time.
Uniform sampling through the Lovász local lemma
Heng Guo, Mark Jerrum, and Jingcheng Liu · 2019
Closest in time.
Counting hypergraph colorings in the local lemma regime
Heng Guo, Chao Liao, Pinyan Lu, and Chihao Zhang · 2019
Closest in time.
Rapid mixing of hypergraph independent sets
Jonathan Hermon, Allan Sly, and Yumeng Zhang · 2019
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Analyzing Walksat on random formulas
Amin Coja-Oghlan and Alan Frieze · 2014
Cited alongside, same era.
Proof of the satisfiability conjecture for large k k
Jian Ding, Allan Sly, and Nike Sun · 2015
Cited alongside, same era.
The asymptotic k k -SAT threshold
Amin Coja-Oghlan and Konstantinos Panagiotou · 2016
Cited alongside, same era.
A simple algorithm for sampling colorings of G ( n , d / n ) {G}(n,d/n) up to the Gibbs uniqueness threshold
Charilaos Efthymiou · 2016
Cited alongside, same era.
Analysing survey propagation guided decimationon random formulas
Samuel Hetterich · 2016
Cited alongside, same era.
The number of solutions for random regular NAE-SAT
Allan Sly, Nike Sun, and Yumeng Zhang · 2016
Cited alongside, same era.
Counting independent sets and colorings on random regular bipartite graphs
Chao Liao, Jiabao Lin, Pinyan Lu, and Zhenyu Mao · 2019
Closest in time.
Approximate counting, the Lovász local lemma, and inference in graphical models
Ankur Moitra · 2019
Closest in time.
The random 2-SAT partition function
Dimitris Achlioptas, Amin Coja-Oghlan, Max Hahn-Klimroth, Joon Lee, Noela Müller, Manuel Penschuck, and Guangyan Zhou · 2020
Closest in time.
Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, Daniel Štefankovič, Eric Vigoda, and Kuan Yang · 2020
Closest in time.
Belief propagation on the random k-sat model
Amin Coja-Oghlan, Noëla Müller, and Jean B. Ravelomanana · 2020
Closest in time.
Fast sampling and counting k k -SAT solutions in the local lemma regime
Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang · 2020
Closest in time.
On the sampling Lovász local lemma for atomic constraint satisfaction problems
Vishesh Jain, Huy Tuan Pham, and Thuy Duong Vuong · 2021
Closest in time.