
Dimitris AchlioptasEmail: <last five letters of last name> @ cs.ucsc.edu 
Department of Computer Science
UC Santa Cruz 1156 High Street MS: SOE3 Santa Cruz, CA 95064 U.S.A. 

Phone: +1 (831) 459 1081 
Office: E2 343A 
Recent work has included:
Recently, I was on the Program Committee for ICALP'10 in Bordeaux, SAT'10 in Edinburgh,
and RANDOM'10
in
Barcelona.
Papers
in Reverse Chronological Order
2010
On the solutionspace geometry of random constraint
satisfaction problems (with A. CojaOghlan, F. RicciTersenghi)
Random Structures & Algorithms,
appeared online March 2010.
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)
In Proceedinds of 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
in Proceedings of ECML'04, pp.
18.
The Chromatic
Number of Random Regular Graphs (with C. Moore)
in Proceedings of RANDOM'04, pp.219228.
Exponential
Bounds
for DPLL Below the Satisfiability Threshold (with P. Beame, M.
Molloy)
in Proceedings of 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)
in Proceedings of FOCS'03,
pp. 362370.
2002
On the
2colorability 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.
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)
in Proceedings of FOCS'01, pp.611618.
Balance
and Filtering in Structured Satisfiable Problems
in Proceedings of 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)
in Proceedings of 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)
in Proceedings of FOCS'00, pp.590600.
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 3SAT
in Proceedings of 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)
in Proceedings of FOCS'97, p.204212.
The
Complexity of Gfree Colorability
Discrete Mathematics, 165/166, (1997), p.2130.