## Recent Work

- Sufficient conditions for stochastic local
search

- Probabilistic models of network formation (Quanta Magazine article, July 2015)
- Applications of coding theory in machine learning

## 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.*

## Preprints

- A New
Perspective on Stochastic Local Search and the
Lovasz Local Lemma (with F. Iliopoulos, A.
Sinclair),

FOCS'19, to appear.

## 2019

- 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)
*,*24(2): 162-182, 2019.

Constraints,

## 2018

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

SAT'18, - Fastand
Flexible Probabilistic Model Counting (with Z.
Hammoudeh, P. Theodoropoulos),

SAT'18,*.* - Product
Measure Approximation of Symmetric Graph Properties
(with P. Siminelakis)
*,*261 (2): 446-463

Information & Computation,*.*

## 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
Perfomance & 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 2
^{k}log2 - 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-98

- 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.*