D. Achlioptas

MaRDI QIDQ1356725zbMATH OpenDBLPWikidataFDO

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

Publication	Date of Publication	Type
Beyond the Lovász local lemma: point to set correlations and their algorithmic applications	2025-08-12	Paper
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

Research outcomes over time

This page was built for person: D. Achlioptas