
Dimitris AchlioptasDepartment of Computer Science UC Santa Cruz1156 High Street MS: SOE3 Santa Cruz, CA 95064 U.S.A. Office: E2 343 

last five letters of last
name@cs.ucsc.edu 
Recent Work
Selected Papers
Random
Walks that Find Perfect Objects and the Lovasz Local
Lemma
FOCS'14, to
appear in JACM.
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.
Random
Walks that Find Perfect Objects and the Lovasz Local
Lemma (with F. Iliopoulos)
J. ACM,
to appear.
Symmetric
Graph Properties have Independent Edges (with P.
Siminelakis)
Information
& Computation, to appear.
2015
Focused Local
Search and the Lovasz Local Lemma (with F. Iliopoulos)
Submitted.
Navigability is a
Robust Property (with P. Siminelakis)
Submitted.
HighDimensional
Stochastic Integration via ErrorCorrecting Codes (with P. Jiang)
UAI'15
Symmetric
Graph Properties have Independent Edges (with P.
Siminelakis)
ICALP'15,
467478.
Random
Walks that Find Perfect Objects and the Lovasz Local
Lemma (with F. Iliopoulos)
FOCS'14,
494503.
Random
Flash on Rails: Consistent Flash Performance through
Redundancy (with D. Skourtis, N. Watkins, C. Maltzahn, S. Brandt)
USENIX ATC'14,
463474.
Erasure
Coding & Read/Write Separation in Flash Storage (with D. Skourits, N. Watkins, C. Maltzahn, S. Brandt)
INFLOW'14.
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
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.
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} log 2  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.