## Selected Papers

- Random Walks that Find Perfect Objects and the Lovasz Local Lemma

J. ACM, 22:1-22:29 (2016). - Explosive Percolation in Random Networks

Science 2009, 323, 1453 – 1455 - The Two Possible Values of the Chromatic Number of a Random Graph

Annals of Mathematics, 162 (3), (2005), 1333-1349. - Rigorous Location of Phase Transitions in Hard Optimization Problems

Nature, 435 (2005), 759-764.

### 2019

- A New Perspective on Stochastic Local Search and the Lovasz Local Lemma (with F. Iliopoulos, A. Sinclair), FOCS’19, to appear.
- Bad Global Minima Exist and SGD Can Reach Them (with S. Liu, D. Papailiopoulos),

ICML Workshop on Identifying and Understanding Deep Learning Phenomena. - Model Counting with Error-Correcting Codes (with P. Theodoropoulos),

Constraints, 24(2): 162-182, 2019.

### 2018

- Fast Sampling of Perfectly Uniform Satisfying Assignments (with Z. Hammoudeh, P. Theodoropoulos),

SAT’18, 135-147. - Fast and Flexible Probabilistic Model Counting (with Z. Hammoudeh, P. Theodoropoulos),

SAT’18, 148-164. - Product Measure Approximation of Symmetric Graph Properties (with P. Siminelakis),

Information & Computation, 261 (2): 446-463.

### 2017

- SkipGram – Zipf + Uniform = Vector Additivity (with A. Gittens, M.W. Mahoney)

ACL’17: 69-76. - Stochastic Control via Entropy Compression (with F. Iliopoulos, N. Vlassis)

ICALP’17, 469-479. - Time-invariantLDPC convolutional codes (with S. Hassani, W. Liu, R. Urbanke)

ISIT’17, 366-370. - ProbabilisticModel Counting with Short XORs (with P. Theodoropoulos)

SAT’17, 3-19.

### 2016

- Random Walks that Find Perfect Objects and the Lovasz Local Lemma (with F. Iliopoulos)

J. ACM, 63 (3): 22:1-22:29. - Bounds for Random Constraint Satisfaction Problems via Spatial Coupling (with H. Hassani, N. Macris, R. Urbanke)

SODA’16, 469-479. - Focused Local Search and the Lovasz Local Lemma (with F. Iliopoulos)

SODA’16, 2024-2038.

### 2015

- Symmetric Graph Properties have Independent Edges (with P. Siminelakis)

ICALP’15, 467-478. - StochasticIntegration via Error-Correcting Codes (with P. Jiang)

UAI’15, 22-31. - Navigability is a Robust Property (with P. Siminelakis)

WAW’15, 78-91.

### 2014

- Random Walks that Find Perfect Objects and the Lovasz Local Lemma (with F. Iliopoulos)

FOCS’14, 494-503. - Erasure Coding & Read/Write Separation in Flash Storage (with D. Skourits, N. Watkins, C. Maltzahn, S. Brandt)

INFLOW’14. - Flashon Rails: Consistent Flash Performance through Redundancy (with D. Skourtis, N. Watkins, C. Maltzahn, S. Brandt)

USENIX ATC’14, 463-474.

### 2013

- Near-Optimal Entrywise Sampling for Data Matrices (with Z. Karnin, E. Liberty)

NIPS’13, 1565-1573. - High Performance & Low Latency in Solid-State Drives through Redundancy (with D. Skourtis, C. Maltzahn, S. Brandt)

INFLOW@SOSP’13, 6:1-6:9

### 2012

- Unsatisfiability Lower Bounds for Random CSPs from an Energetic Interpolation Method (with R. Menchaca-Mendez)

ICALP’12, pp. 1-12. - Exponential Lower Bounds for DPLL Algorithms on Satisfiable Random 3-CNF Formulas (with R. Menchaca-Mendez)

SAT’12, pp. 327-340. - Algorithmic Improvements of the Lovasz Local Lemma via Cluster Expansion (with T. Gouleakis)

FSTTCS’12, pp. 16-23.

### 2011

- The Solution Space Geometry of Random Linear Equations (with M. Molloy)

Random Structures & Algorithms, 46, 197-231.

### 2010

- On the solution-space geometry of random constraint satisfaction problems (with A. Coja-Oghlan, F. Ricci-Tersenghi)

Random Structures & Algorithms, 38, 251-268.

### 2009

- Explosive Percolation in Random Networks (with R. D’Souza, J. Spencer) Report in New Scientist

Science 2009, 323, 1453 – 1455 - Random Satisfiability

Handbook of Satisfiability, Eds. A. Biere et al., IOS Press, 243-268 (2009) - On the Bias of Traceroute Sampling (with A. Clauset, D.Kempe, C. Moore)

Journal of ACM, 56 (4), Article 21 (June 2009). - Random Formulas have Frozen Variables (with F. Ricci-Tersenghi)

SIAM Journal of Computing, 39 (2009), 260-280.

### 2008

- Algorithmic Barriers from Phase Transitions (with A. Coja-Oghlan)

FOCS’08, pp. 793–802. - Solution Clustering in Random Satisfiability

European Physics Journal B, 64, (2008), 395-402.

### 2007

- On the maximum satisfiability of random formulas (with A. Naor, Y. Peres)

Journal of ACM, 54 (2), Article 9, (2007). - Fast Computation of Low-Rank Approximations (with F. McSherry)

Journal of ACM, 54 (2), Article 10, (2007).

### 2006

- Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold (with C. Moore)

SIAM Journal of Computing, 36, (2006), 740-762. - On the Solution-Space Geometry of Random Constrain Satisfaction Problems (with F. Ricci-Tersenghi)

STOC’06, pp. 130-139.

### 2005

- The Two Possible Values of the Chromatic Number of a Random Graph (with A. Naor)

Annals of Mathematics, 162 (3), (2005), 1333-1349. - Rigorous Location of Phase Transitions in Hard Optimization Problems (with A. Naor, Y. Peres)

Nature, 435 (2005), 759-764. - Hiding Truth Assignments: Two are Better Than One (with H. Jia, C. Moore)

Journal of Artifical Intelligence Research, 24, (2005), 623-639. - Rapid Mixing for Lattice Colourings with Fewer Colours (with M. Molloy, C. Moore, F. van Bussell)

Journal of Statistical Mechanics: Theory and Experiment, 2005, P10012.

### 2004

- The Threshold for Random k-SAT is 2klog2 – O(k) (with Y. Peres)

J.AMS, 17, (2004), 947-973. - A Sharp Threshold in Proof Complexity Yields a Lower Bound for Satisfiability Search (with P. Beame, M. Molloy)

Journal of Comp. & Sys. Sci., 68 (2), (2004), 238-268. - Random Matrices in Data Analysis

ECML’04, pp. 1-8. - The Chromatic Number of Random Regular Graphs (with C. Moore)

RANDOM’04, pp.219-228. - Exponential Bounds for DPLL Below the Satisfiability Threshold (with P. Beame, M. Molloy)

SODA’04, pp. 132-133.

### 2003

- Almost all Graphs with Average Degree 4 are 3-colorable (with C. Moore)

Journal of Comp. & Sys. Sci., 67 (2), (2003), p.441-471, special issue of invited papers from STOC’02. - Database-friendly Random Projections: Johnson-Lindenstrauss with Binary Coins

Journal of Comp. & Sys. Sci.,, 66 (4), (2003), p.671-687, special issue of invited papers from PODS’01. - The Fraction of Satisfiable Clauses in a Typical Formula (with A. Naor, Y.Peres)

FOCS’03, pp. 362-370.

### 2002

- On the 2-colorability of Random Hypergraphs (with C. Moore)

RANDOM’02. - Sampling Techniques for Kernel Methods (with F. McSherry, B. Schölkopf)

NIPS’02. - Two-Coloring Random Hypergraphs (with J.H. Kim, M. Krivelevich, P.Tetali)

Random Structures & Algorithms, 20 (2), (2002), p.249-259.

### 2001

- Web Search via Hub Synthesis (with A. Fiat, A. Karlin, F. McSherry)

FOCS’01, pp.611-618. - Balance and Filtering in Structured Satisfiable Problems

IJCAI’01, p.351-358. (with H. Kautz, Y. Ruan, C. Gomes, B. Selman, M. Stickel) - The Phase Transition in NAESAT and 1-in-k SAT (with A. Chtcherba, G. Istrate, C. Moore)

SODA’01, pp.721-722. - Lower Bounds for Random 3-SAT via Differential Equations

Theoretical Computer Science, 265 (1-2), (2001), pp.159-185. - Random Constraint Satisfaction: A More Accurate Picture

Constraints, 6 (4), (2001), p. 329-344. (with L.M. Kirousis, E. Kranakis, D. Krizanc, M.Molloy, Y. Stamatiou) - Rigorous Results for (2+p)-SAT (with L.M. Kirousis, E. Kranakis, D. Krizanc)

Theoretical Computer Science, 265 (1-2), (2001), p.109-129.

### 2000

- Optimal Myopic Algorithms for Random 3-SAT (with G.B. Sorkin)

FOCS’00, pp.590-600. - Generating Satisfiable Problem Instances (with C. Gomes, H. Kautz, B. Selman)

AAAI’00. - Setting Two Variables at a Time Yields a New Lower Bound for Random 3-SAT

STOC’00, pp.28-37. - Competitive Analysis of Randomized Paging Algorithms (with M. Chrobak, J. Noga)

Theoretical Computer Science, 234, (2000), p.203-218.

### 1999

- A Sharp Threshold for k-Colorability (with E. Friedgut)

Random Structures & Algorithms, 14 (1), (1999), p.63-70. - Almost All Graphs with 2.522n Edges are not 3-Colorable (with M. Molloy)

Electronic Journal of Combinatorics, 6 (1), (1999), R29 - Tight Lower Bounds on st-Connectivity on the NNJAG model (with J. Edmonds, C.K. Poon)

SIAM Journal on Computing, 28 (6), (1999), p.2257-2284.

### 1997 – 1998

- The Existence of Uniquely G-free Colourable Graphs (with J.I. Brown, D. Corneil, M. Molloy)

Discrete Mathematics, 179, (1998), p.1-11. - Analysis of a List-Coloring Algorithm on a Random Graph (with M. Molloy)

FOCS’97, p.204-212. - The Complexity of G-free Colorability

Discrete Mathematics, 165/166, (1997), p.21-30.