Dimitris Achlioptas

Recent work has included:

• Threshold phenomena in random graphs and random formulas
• Applications of embeddings and spectral techniques in machine learning
• Algorithmic analysis of massive networks.

Recently, I was on the Program Committee for FOCS'07 in Providence, SODA'06 in Miami, and RANDOM'06 in Barcelona.

Papers
in Reverse Chronological Order

2008-Preprints

• On the Bias of Traceroute Sampling (with A. Clauset, D.Kempe, C. Moore)
  To appear in Journal of ACM.

• Random Formulas have Frozen Variables (with F. Ricci-Tersenghi)
  To appear in SIAM Journal of Computing.

• Solution Clustering in Random Satisfiability
  To appear in European Physics Journal.

• On Spectral Learning of Mixtures of Distributions (with F. McSherry)
   To appear in Journal of Machine Learning Research.
  

2007

• The Fraction of Satisfiable Clauses in a Random Formula (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)
  in Proceedings of 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 log 2 - 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
  in Proceedings of ECML'04, pp. 1-8.

• The Chromatic Number of Random Regular Graphs (with C. Moore)
  in Proceedings of RANDOM'04, pp.219-228.

• Exponential Bounds for DPLL Below the Satisfiability Threshold (with P. Beame, M. Molloy)
  in Proceedings of 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)
  in Proceedings of FOCS'03, pp. 362-370.

2002

• On the 2-colorability of Random Hypergraphs (with C. Moore)
  in Proceedings of RANDOM'02.

• Sampling Techniques for Kernel Methods (with F. McSherry, B. Schölkopf)
  in Proceedings of 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)
  in Proceedings of FOCS'01, pp.611-618.

• Balance and Filtering in Structured Satisfiable Problems
  in Proceedings of 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)
  in Proceedings of 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)
  in Proceedings of FOCS'00, pp.590-600.

• Generating Satisfiable Problem Instances (with C. Gomes, H. Kautz, B. Selman)
  in Proceedings of AAAI'00.

• Setting Two Variables at a Time Yields a New Lower Bound for Random 3-SAT
  in Proceedings of 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)
  in Proceedings of FOCS'97, p.204-212.

• The Complexity of G-free Colorability
  Discrete Mathematics, 165/166, (1997), p.21-30.