| Publication | Date of Publication | Type |
|---|
| The Lov\'{a}sz Local Lemma is Not About Probability | 2021-11-16 | Paper |
Stochastic control via entropy compression
(available as arXiv preprint) | 2020-05-27 | Paper |
| The random 2-SAT partition function | 2020-02-10 | Paper |
Model counting with error-correcting codes
Constraints | 2019-11-27 | Paper |
A local lemma for focused stochastic algorithms
SIAM Journal on Computing | 2019-11-08 | Paper |
Rapid mixing for lattice colourings with fewer colours
Journal of Statistical Mechanics: Theory and Experiment | 2019-07-09 | Paper |
| Fast and flexible probabilistic model counting | 2018-08-10 | Paper |
| Fast sampling of perfectly uniform satisfying assignments | 2018-08-10 | Paper |
Random walks that find perfect objects and the Lovász local lemma
Journal of the ACM | 2018-08-02 | Paper |
Focused stochastic local search and the Lovász local lemma
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Symmetric graph properties have independent edges
Information and Computation | 2018-06-14 | Paper |
| Beyond the Lovasz Local Lemma: Point to Set Correlations and Their Algorithmic Applications | 2018-05-05 | Paper |
Competitive analysis of randomized paging algorithms
Algorithms — ESA '96 | 2017-12-05 | Paper |
Probabilistic model counting with short XORs
(available as arXiv preprint) | 2017-11-15 | Paper |
| Algorithmic improvements of the Lovász local lemma via cluster expansion | 2017-01-26 | Paper |
Navigability is a robust property
Lecture Notes in Computer Science | 2016-01-08 | Paper |
On the bias of traceroute sampling
Journal of the ACM | 2015-11-11 | Paper |
Symmetric graph properties have independent edges
Automata, Languages, and Programming | 2015-11-04 | Paper |
Fast computation of low rank matrix approximations
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
On the solution-space geometry of random constraint satisfaction problems
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
Unsatisfiability bounds for random CSPs from an energetic interpolation method
Automata, Languages, and Programming | 2013-08-12 | Paper |
Exponential lower bounds for DPLL algorithms on satisfiable random 3-CNF formulas
Theory and Applications of Satisfiability Testing – SAT 2012 | 2013-08-12 | Paper |
Explosive percolation in random networks
Science | 2011-11-30 | Paper |
On the solution-space geometry of random constraint satisfaction problems
Random Structures & Algorithms | 2011-05-11 | Paper |
On the bias of traceroute sampling
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
The threshold for random k-SAT is 2 k (ln 2 - O(k))
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
The two possible values of the chromatic number of a random graph
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
Almost all graphs with average degree 4 are 3-colorable
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Solution clustering in random satisfiability
The European Physical Journal B. Condensed Matter and Complex Systems | 2010-06-25 | Paper |
Random formulas have frozen variables
SIAM Journal on Computing | 2010-03-17 | Paper |
LATIN 2004: Theoretical Informatics
Lecture Notes in Computer Science | 2009-05-07 | Paper |
Fast computation of low-rank matrix approximations
Journal of the ACM | 2008-12-21 | Paper |
On the maximum satisfiability of random formulas
Journal of the ACM | 2008-12-21 | Paper |
Machine Learning: ECML 2004
Lecture Notes in Computer Science | 2008-03-14 | Paper |
| Algorithmic barriers from phase transitions | 2008-03-14 | Paper |
Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
SIAM Journal on Computing | 2007-06-26 | Paper |
Learning Theory
Lecture Notes in Computer Science | 2006-06-22 | Paper |
The two possible values of the chromatic number of a random graph
Annals of Mathematics. Second Series | 2006-06-19 | Paper |
| scientific article; zbMATH DE number 2243408 (Why is no real title available?) | 2006-01-04 | Paper |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2005-08-25 | Paper |
Almost all graphs with average degree 4 are 3-colorable
Journal of Computer and System Sciences | 2004-11-18 | Paper |
The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
Journal of the American Mathematical Society | 2004-10-07 | Paper |
| On the 2-colorability of random hypergraphs | 2003-12-17 | Paper |
On the 2-colorability of random hypergraphs
(available as arXiv preprint) | 2003-12-17 | Paper |
Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
Journal of Computer and System Sciences | 2003-08-19 | Paper |
Two‐coloring random hypergraphs
Random Structures & Algorithms | 2002-08-08 | Paper |
Lower bounds for random 3-SAT via differential equations
Theoretical Computer Science | 2002-03-03 | Paper |
Rigorous results for random (\(2+p)\)-SAT
Theoretical Computer Science | 2002-03-03 | Paper |
Random constraint satisfaction: A more accurate picture
Constraints | 2002-02-10 | Paper |
| The phase transition in 1-in-\(k\) SAT and NAE 3-SAT | 2002-01-30 | Paper |
| Balance and filtering in structured satisfiable problems. (Preliminary report) | 2001-09-24 | Paper |
Competitive analysis of randomized paging algorithms
Theoretical Computer Science | 2000-08-21 | Paper |
| scientific article; zbMATH DE number 1380613 (Why is no real title available?) | 1999-12-19 | Paper |
Tight Lower Bounds for st-Connectivity on the NNJAG Model
SIAM Journal on Computing | 1999-10-28 | Paper |
The complexity of \(G\)-free colourability
Discrete Mathematics | 1998-11-05 | Paper |
The existence of uniquely \(-G\) colourable graphs
Discrete Mathematics | 1998-03-24 | Paper |
