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:122: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), 13331349. 
Rigorous Location of Phase Transitions in Hard
Optimization Problems
Nature, 435 (2005), 759764.
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 ErrorCorrecting Codes
(with P. Theodoropoulos),
Constraints, 24(2): 162182, 2019.
2018
 Fast Sampling of Perfectly Uniform Satisfying
Assignments (with Z. Hammoudeh, P.
Theodoropoulos),
SAT'18, 135147.  Fastand Flexible Probabilistic Model Counting (with
Z. Hammoudeh, P. Theodoropoulos),
SAT'18, 148164.  Product
Measure Approximation of Symmetric Graph Properties
(with P. Siminelakis),
Information & Computation, 261 (2): 446463.
2017
 SkipGram Zipf + Uniform = Vector Additivity (with A.
Gittens, M.W. Mahoney)
ACL'17: 6976.
 Stochastic
Control via Entropy Compression (with F.
Iliopoulos, N. Vlassis)
ICALP'17, 469479.  TimeinvariantLDPC convolutional codes (with S. Hassani, W.
Liu, R. Urbanke)
ISIT'17, 366370.  ProbabilisticModel Counting with Short XORs (with P.
Theodoropoulos)
SAT'17, 319.
2016
 Random Walks
that Find Perfect Objects and the Lovasz Local Lemma
(with F. Iliopoulos)
J. ACM, 63 (3): 22:122:29.
 Bounds
for Random Constraint Satisfaction Problems via
Spatial Coupling (with H. Hassani, N. Macris, R.
Urbanke)
SODA'16, 469479.  Focused Local
Search and the Lovasz Local Lemma (with F.
Iliopoulos)
SODA'16, 20242038.
2015
 Symmetric
Graph Properties have Independent Edges (with P.
Siminelakis)
ICALP'15, 467478.  StochasticIntegration via ErrorCorrecting Codes (with P.
Jiang)
UAI'15, 2231.  Navigability
is a Robust Property (with P. Siminelakis)
WAW'15, 7891.
2014
 Random
Walks that Find Perfect Objects and the Lovasz Local
Lemma (with F. Iliopoulos)
FOCS'14, 494503.  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, 463474.
2013
 NearOptimal
Entrywise Sampling for Data Matrices (with Z.
Karnin, E. Liberty)
NIPS'13, 15651573.  High
Perfomance & Low Latency in SolidState Drives
through Redundancy(with D. Skourtis, C.
Maltzahn, S. Brandt)
INFLOW@SOSP'13, 6:16:9
2012
 Unsatisfiability
Lower Bounds for Random CSPs from an Energetic
Interpolation Method (with R. MenchacaMendez)
ICALP'12, pp. 112.  Exponential
Lower Bounds for DPLL Algorithms on Satisfiable
Random 3CNF Formulas (with R. MenchacaMendez)
SAT'12, pp. 327340.  Algorithmic
Improvements of the Lovasz Local Lemma via Cluster
Expansion (with T. Gouleakis)
FSTTCS'12, pp. 1623.
2011
 The
Solution Space Geometry of Random Linear Equations
(with M. Molloy)
Random Structures & Algorithms, 46, 197231.
2010
 On
the solutionspace geometry of random constraint
satisfaction problems (with A. CojaOghlan, F.
RicciTersenghi)
Random Structures & Algorithms, 38, 251268.
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, 243268 (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.
RicciTersenghi)
SIAM Journal of Computing, 39 (2009), 260280.
2008
 Algorithmic
Barriers from Phase Transitions (with A.
CojaOghlan)
FOCS'08, pp. 793–802.  Solution
Clustering in Random Satisfiability
European Physics Journal B, 64, (2008), 395402.
2007
 On
the maximum satisfiability of random formulas
(with A. Naor, Y. Peres)
Journal of ACM, 54 (2), Article 9, (2007).  Fast
Computation of LowRank Approximations (with F.
McSherry)
Journal of ACM, 54 (2), Article 10, (2007).
2006
 Random
kSAT: Two Moments Suffice to Cross a Sharp
Threshold (with C. Moore)
SIAM Journal of Computing, 36, (2006), 740762.  On
the SolutionSpace Geometry of Random Constrain
Satisfaction Problems (with F. RicciTersenghi)
STOC'06, pp. 130139.
2005
 The
Two Possible Values of the Chromatic Number of a
Random Graph (with A. Naor)
Annals of Mathematics, 162 (3), (2005), 13331349.  Rigorous
Location of Phase Transitions in Hard Optimization
Problems (with A. Naor, Y. Peres)
Nature, 435 (2005), 759764.  Hiding
Truth Assignments: Two are Better Than One (with
H. Jia, C. Moore)
Journal of Artifical Intelligence Research, 24, (2005), 623639.  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 kSAT is 2^{k}log2 
O(k) (with Y. Peres)
J.AMS, 17, (2004), 947973.  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), 238268.  Random
Matrices in Data Analysis
ECML'04, pp. 18.  The
Chromatic Number of Random Regular Graphs (with
C. Moore)
RANDOM'04, pp.219228.  Exponential
Bounds for DPLL Below the Satisfiability Threshold (with P. Beame, M. Molloy)
SODA'04, pp. 132133.
2003
 Almost
all Graphs with Average Degree 4 are 3colorable
(with C. Moore)
Journal of Comp. & Sys. Sci., 67 (2), (2003), p.441471, special issue of invited papers from STOC'02.  Databasefriendly
Random Projections: JohnsonLindenstrauss with
Binary Coins
Journal of Comp. & Sys. Sci.,, 66 (4), (2003), p.671687, 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. 362370.
2002
 On
the 2colorability of Random Hypergraphs (with
C. Moore)
RANDOM'02.  Sampling
Techniques for Kernel Methods (with F.
McSherry, B. Schölkopf)
NIPS'02.  TwoColoring
Random Hypergraphs (with J.H. Kim, M.
Krivelevich, P.Tetali)
Random Structures & Algorithms, 20 (2), (2002), p.249259.
2001
 Web
Search via Hub Synthesis (with A. Fiat, A.
Karlin, F. McSherry)
FOCS'01, pp.611618.  Balance
and Filtering in Structured Satisfiable Problems
IJCAI'01, p.351358. (with H. Kautz, Y. Ruan, C. Gomes, B. Selman, M. Stickel)  The
Phase Transition in NAESAT and 1ink SAT (with
A. Chtcherba, G. Istrate, C. Moore)
SODA'01, pp.721722.  Lower
Bounds for Random 3SAT via Differential Equations
Theoretical Computer Science, 265 (12), (2001), pp.159185.  Random
Constraint Satisfaction: A More Accurate Picture
Constraints, 6 (4), (2001), p. 329344. (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 (12), (2001), p.109129.
2000
 Optimal
Myopic Algorithms for Random 3SAT (with G.B.
Sorkin)
FOCS'00, pp.590600.  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 3SAT
STOC'00, pp.2837.  Competitive
Analysis of Randomized Paging Algorithms (with
M. Chrobak, J. Noga)
Theoretical Computer Science, 234, (2000), p.203218.
1999
 A
Sharp Threshold for kColorability (with E.
Friedgut)
Random Structures & Algorithms, 14 (1), (1999), p.6370.  Almost
All Graphs with 2.522n Edges are not 3Colorable
(with M. Molloy)
Electronic Journal of Combinatorics, 6 (1), (1999), R29  Tight
Lower Bounds on stConnectivity on the NNJAG model
(with J. Edmonds, C.K. Poon)
SIAM Journal on Computing, 28 (6), (1999), p.22572284.
199798
 The
Existence of Uniquely Gfree Colourable Graphs
(with J.I. Brown, D. Corneil, M. Molloy)
Discrete Mathematics, 179, (1998), p.111.  Analysis
of a ListColoring Algorithm on a Random Graph
(with M. Molloy)
FOCS'97, p.204212.  The
Complexity of Gfree Colorability
Discrete Mathematics, 165/166, (1997), p.2130.