Demetrios Achlioptas

Available identifiers

zbMath Open achlioptas.dimitrisWikidataQ102232798 ScholiaQ102232798MaRDI QIDQ1356725

List of research outcomes

Publication	Date of Publication	Type
The Lov\'{a}sz Local Lemma is Not About Probability	2021-11-16	Paper
Stochastic Control via Entropy Compression	2020-05-27	Paper
The random 2-SAT partition function	2020-02-10	Paper
Model counting with error-correcting codes	2019-11-27	Paper
A Local Lemma for Focused Stochastic Algorithms	2019-11-08	Paper
Rapid mixing for lattice colourings with fewer colours	2019-07-09	Paper
Fast sampling of perfectly uniform satisfying assignments	2018-08-10	Paper
Fast and flexible probabilistic model counting	2018-08-10	Paper
Random Walks That Find Perfect Objects and the Lovász Local Lemma	2018-08-02	Paper
Focused Stochastic Local Search and the Lovász Local Lemma	2018-07-16	Paper
Symmetric graph properties have independent edges	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	2017-12-05	Paper
Probabilistic model counting with short XORs	2017-11-15	Paper
Algorithmic Improvements of the Lovász Local Lemma via Cluster Expansion	2017-01-26	Paper
Navigability is a Robust Property	2016-01-08	Paper
On the bias of traceroute sampling	2015-11-11	Paper
Symmetric Graph Properties Have Independent Edges	2015-11-04	Paper
Fast computation of low rank matrix approximations	2015-02-27	Paper
On the solution-space geometry of random constraint satisfaction problems	2014-11-25	Paper
Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)	2014-09-26	Paper
Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method	2013-08-12	Paper
Exponential Lower Bounds for DPLL Algorithms on Satisfiable Random 3-CNF Formulas	2013-08-12	Paper
Explosive Percolation in Random Networks	2011-11-30	Paper
On the solution‐space geometry of random constraint satisfaction problems	2011-05-11	Paper
The threshold for random k-SAT is 2 k (ln 2 - O(k))	2010-08-16	Paper
On the bias of traceroute sampling	2010-08-16	Paper
The two possible values of the chromatic number of a random graph	2010-08-15	Paper
Almost all graphs with average degree 4 are 3-colorable	2010-08-05	Paper
Solution clustering in random satisfiability	2010-06-25	Paper
Random Formulas Have Frozen Variables	2010-03-17	Paper
LATIN 2004: Theoretical Informatics	2009-05-07	Paper
Fast computation of low-rank matrix approximations	2008-12-21	Paper
On the maximum satisfiability of random formulas	2008-12-21	Paper
Machine Learning: ECML 2004	2008-03-14	Paper
Algorithmic barriers from phase transitions	2008-03-14	Paper
Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold	2007-06-26	Paper
Learning Theory	2006-06-22	Paper
The two possible values of the chromatic number of a random graph	2006-06-19	Paper
https://portal.mardi4nfdi.de/entity/Q5715725	2006-01-04	Paper
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques	2005-08-25	Paper
Almost all graphs with average degree 4 are 3-colorable	2004-11-18	Paper
The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)	2004-10-07	Paper
On the 2-colorability of random hypergraphs	2003-12-17	Paper
Database-friendly random projections: Johnson-Lindenstrauss with binary coins.	2003-08-19	Paper
Two‐coloring random hypergraphs	2002-08-08	Paper
Rigorous results for random (\(2+p)\)-SAT	2002-03-03	Paper
Lower bounds for random 3-SAT via differential equations	2002-03-03	Paper
Random constraint satisfaction: A more accurate picture	2002-02-10	Paper
https://portal.mardi4nfdi.de/entity/Q2768371	2002-01-30	Paper
https://portal.mardi4nfdi.de/entity/Q2741510	2001-09-24	Paper
Competitive analysis of randomized paging algorithms	2000-08-21	Paper
https://portal.mardi4nfdi.de/entity/Q4705349	1999-12-19	Paper
Tight Lower Bounds for st-Connectivity on the NNJAG Model	1999-10-28	Paper
The complexity of \(G\)-free colourability	1998-11-05	Paper
The existence of uniquely \(-G\) colourable graphs	1998-03-24	Paper

Research outcomes over time

Doctoral students

No records found.

Known relations from the MaRDI Knowledge Graph

Property	Value
MaRDI profile type	MaRDI person profile
instance of	human

This page was built for person: Demetrios Achlioptas