Recent Work

• Convergence conditions for stochastic local search
  
• Probabilistic models of network formation (Quanta Magazine article, July 2015)
• Applications of error-correcting codes in machine learning

Selected Papers

• Random Walks that Find Perfect Objects and the Lovász 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

• Bad Global Minima Exist and SGD Can Reach Them
  S. Liu, D. Papailiopoulos, D. Achlioptas,
  NeurIPS'20, to appear.
  
• The Random 2-SAT Partition Function
  D. Achlioptas, A. Coja-Oghlan, M. Hahn-Klimroth, J. Lee, N. Muller, M. Penschuck, G. Zhou,
  Random Structures & Algorithms, to appear.
  

2020

• Simple Local Computation Algorithms for the General Lovász Local Lemma
  D. Achlioptas, T. Gouleakis, F. Iliopoulos,
  SPAA'20, 1-10
  

2019

• Beyond the Lovász Local Lemma: Point to Set Correlations and Their Algorithmic Applications
  D. Achlioptas, F. Iliopoulos, A. Sinclair,
  FOCS'19, 725-744.
• A Local Lemma for Focused Stochastic Algorithms
  D. Achlioptas, F. Iliopoulos, V. Kolmogorov,
  SIAM J. Computing, 48 (5), 1583-1602 (2019)
  
• Model Counting with Error-Correcting Codes
  D. Achlioptas, P. Theodoropoulos,
  Constraints, 24(2): 162-182 (2019).

2018

• Symmetric Graph Properties Have Independent Edges
  D. Achlioptas, P. Siminelakis,
  Information & Computation, 261 (2), 446-463 (2018).
• Fast Sampling of Perfectly Uniform Satisfying Assignments
  D. Achlioptas, Z. Hammoudeh, P. Theodoropoulos,
  SAT'18, 135-147.
• Fastand Flexible Probabilistic Model Counting
  D. Achlioptas, Z. Hammoudeh, P. Theodoropoulos,
  SAT'18, 148-164.

2017

• SkipGram- Zipf + Uniform = Vector Additivity
  A. Gittens, M.W. Mahoney, D. Achlioptas
  ACL'17: 69-76.
• Stochastic Control via Entropy Compression
  D. Achlioptas, F. Iliopoulos, N. Vlassis
  ICALP'17, 469-479.
• Time-invariant LDPC convolutional codes
  D. Achlioptas, S. Hassani, W. Liu, R. Urbanke
  ISIT'17, 366-370.
• Probabilistic Model Counting with Short XORs
  D. Achlioptas, P. Theodoropoulos
  SAT'17, 3-19.

2016

• Random Walks that Find Perfect Objects and the Lovasz Local Lemma
  D. Achlioptas, F. Iliopoulos
  Journal of ACM, 63 (3): 22:1-22:29 (2016).

• Bounds for Random Constraint Satisfaction Problems via Spatial Coupling
  D. Achlioptas, H. Hassani, N. Macris, R. Urbanke
  SODA'16, 469-479.
• Focused Local Search and the Lovasz Local Lemma
  D. Achlioptas, F. Iliopoulos
  SODA'16, 2024-2038.
  

2015

• Symmetric Graph Properties have Independent Edges
  D. Achlioptas, P. Siminelakis
  ICALP'15, 467-478.
• Stochastic Integration via Error-Correcting Codes
  D. Achlioptas, P. Jiang
  UAI'15, 22-31.
• Navigability is a Robust Property
  D. Achlioptas, P. Siminelakis
  WAW'15, 78-91.

2014

• Random Walks that Find Perfect Objects and the Lovász Local Lemma
  D. Achlioptas, F. Iliopoulos
  FOCS'14, 494-503.
• Erasure Coding & Read/Write Separation in Flash Storage
  D. Skourtis, D. Achlioptas, N. Watkins, C. Maltzahn, S. Brandt
  INFLOW'14.
• Flash on Rails: Consistent Flash Performance through Redundancy
  D. Skourtis, D. Achlioptas, N. Watkins, C. Maltzahn, S. Brandt
  USENIX ATC'14, 463-474.

2013

• Near-Optimal Entrywise Sampling for Data Matrices
  D. Achlioptas, Z. Karnin, E. Liberty
  NIPS'13, 1565-1573.
• High Perfomance & Low Latency in Solid-State Drives through Redundancy
  D. Skourtis, D. Achlioptas, C. Maltzahn, S. Brandt
  INFLOW@SOSP'13, 6:1-6:9

2012

• Unsatisfiability Lower Bounds for Random CSPs from an Energetic Interpolation Method
  D. Achlioptas, R. Menchaca-Mendez
  ICALP'12,  1-12.
• Exponential Lower Bounds for DPLL Algorithms on Satisfiable Random 3-CNF Formulas
  D. Achlioptas, R. Menchaca-Mendez
  SAT'12,  327-340.
• Algorithmic Improvements of the Lovasz Local Lemma via Cluster Expansion
  D. Achlioptas, T. Gouleakis 
  FSTTCS'12,  16-23.

2011

• The Solution Space Geometry of Random Linear Equations
  D. Achlioptas, M. Molloy 
  Random Structures & Algorithms, 46, 197-231 (2011).

2010

• On the solution-space geometry of random constraint satisfaction problems
  D. Achlioptas, A. Coja-Oghlan, F. Ricci-Tersenghi
  Random Structures & Algorithms, 38, 251-268 (2010).

2009

• Explosive Percolation in Random Networks                 Report in New Scientist
  D. Achlioptas, R. D'Souza, J. Spencer 
  Science, 323, 1453-1455 (2009).
• Random Satisfiability
  Handbook of Satisfiability, Eds. A. Biere et al., IOS Press, 243-268 (2009)
• On the Bias of Traceroute Sampling
  D. Achlioptas, A. Clauset, D.Kempe, C. Moore
  Journal of ACM, 56 (4), Article 21 (June 2009).
• Random Formulas have Frozen Variables
  D. Achlioptas, F. Ricci-Tersenghi 
  SIAM Journal of Computing, 39, 260-280 (2009).

2008

• Algorithmic Barriers from Phase Transitions
  D. Achlioptas, A. Coja-Oghlan 
  FOCS'08,  793–802.
• Solution Clustering in Random Satisfiability
  European Physics Journal B, 64, 395-402 (2008).

2007

• On the maximum satisfiability of random formulas
  D. Achlioptas, A. Naor, Y. Peres
  Journal of ACM, 54 (2), Article 9, (2007).
• Fast Computation of Low-Rank Approximations
  D. Achlioptas, F. McSherry
  Journal of ACM, 54 (2), Article 10 (2007).

2006

• Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold
  D. Achlioptas, C. Moore
  SIAM Journal of Computing, 36, 740-762 (2006).
• On the Solution-Space Geometry of Random Constrain Satisfaction Problems
  D. Achlioptas, F. Ricci-Tersenghi
  STOC'06,  130-139.

2005

• The Two Possible Values of the Chromatic Number of a Random Graph
  D. Achlioptas, A. Naor
  Annals of Mathematics, 162 (3), 1333-1349 (2005).
• Rigorous Location of Phase Transitions in Hard Optimization Problems
  D. Achlioptas, A. Naor, Y. Peres
  Nature, 435, 759-764 (2005).
• Hiding Truth Assignments: Two are Better Than One
  D. Achlioptas, H. Jia, C. Moore 
  Journal of Artifical Intelligence Research, 24, 623-639 (2005).
• Rapid Mixing for Lattice Colourings with Fewer Colours
  D. Achlioptas, 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^klog2 - O(k)
  D. Achlioptas, Y. Peres
  Journal of the American Mathematical Society, 17, 947-973 (2004).
• A Sharp Threshold in Proof Complexity Yields a Lower Bound for Satisfiability Search
  D. Achlioptas, P. Beame, M. Molloy
  Journal of Computer & System Sciences, 68 (2), 238-268 (2004).
• Random Matrices in Data Analysis
  ECML'04,  1-8.
• The Chromatic Number of Random Regular Graphs
  D. Achlioptas, C. Moore
  RANDOM'04, 219-228.
• Exponential Bounds for DPLL Below the Satisfiability Threshold
  D. Achlioptas, P. Beame, M. Molloy
  SODA'04,  132-133.

2003

• Almost all Graphs with Average Degree 4 are 3-colorable
  D. Achlioptas, C. Moore 
  Journal of Computer & System Sciences 67 (2), 441-471 (2003).
• Database-friendly Random Projections: Johnson-Lindenstrauss with Binary Coins
  Journal of Computer & System Sciences, 66 (4), 671-687 (2003).
• The Fraction of Satisfiable Clauses in a Typical Formula
  D. Achlioptas, A. Naor, Y.Peres
  FOCS'03,  362-370.

2002

• On the 2-colorability of Random Hypergraphs
  D. Achlioptas, C. Moore
  RANDOM'02.
• Sampling Techniques for Kernel Methods
  D. Achlioptas, F. McSherry, B. Schölkopf
  NIPS'02.
• Two-Coloring Random Hypergraphs
  D. Achlioptas, J.H. Kim, M. Krivelevich, P.Tetali
  Random Structures & Algorithms, 20 (2), 249-259 (2002).

2001

• Web Search via Hub Synthesis
  D. Achlioptas, A. Fiat, A. Karlin, F. McSherry
  FOCS'01, 611-618.
• Balance and Filtering in Structured Satisfiable Problems
  H. Kautz, Y. Ruan, D. Achlioptas, B. Selman, C. Gomes, M. Stickel 
  IJCAI'01, 351-358. 
• The Phase Transition in NAESAT and 1-in-k SAT
  D. Achlioptas, A. Chtcherba, G. Istrate, C. Moore
  SODA'01, 721-722.
• Lower Bounds for Random 3-SAT via Differential Equations
  Theoretical Computer Science, 265 (1-2), 159-185 (2001).
• Random Constraint Satisfaction: A More Accurate Picture
  D. Achlioptas, L.M. Kirousis, E. Kranakis, D. Krizanc, M.Molloy, Y. Stamatiou
  Constraints, 6 (4), 329-344, (2001).
  
• Rigorous Results for (2+p)-SAT
  D. Achlioptas, L.M. Kirousis, E. Kranakis, D. Krizanc
  Theoretical Computer Science, 265 (1-2), 109-129 (2001). 

2000

• Optimal Myopic Algorithms for Random 3-SAT
  D. Achlioptas, G.B. Sorkin
  FOCS'00, 590-600.
• Generating Satisfiable Problem Instances
  D. Achlioptas 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, 28-37.
• Competitive Analysis of Randomized Paging Algorithms
  D. Achlioptas, M. Chrobak, J. Noga
  Theoretical Computer Science, 234, 203-218 (2000).

1999

• A Sharp Threshold for k-Colorability
  D. Achlioptas, E. Friedgut
  Random Structures & Algorithms, 14 (1), 63-70 (1999).
• Almost All Graphs with 2.522n Edges are not 3-Colorable
  D. Achlioptas, M. Molloy
  Electronic Journal of Combinatorics, 6 (1), R29 (1999).
• Tight Lower Bounds on st-Connectivity on the NNJAG model
  J. Edmonds, C.K. Poon, D. Achlioptas
  SIAM Journal on Computing, 28 (6), 2257-2284 (1999).

1997-98

• The Existence of Uniquely G-free Colourable Graphs
  D. Achlioptas, J.I. Brown, D. Corneil, M. Molloy
  Discrete Mathematics, 179, 1-11 (1998).
• The Analysis of a List-Coloring Algorithm on a Random Graph
  D. Achlioptas, M. Molloy
  FOCS'97, 204-212.
• The Complexity of G-free Colorability
  Discrete Mathematics, 165/166, 21-30 (1997).