Publications

---

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.

---