
Dimitris AchlioptasEmail: <last five letters of last name> @di.uoa.gr 

Office: B24 Fax: +30 210 727 5114
Department of Computer Science 

Recent work has included:
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
2009Preprints
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)
To appear in Journal of ACM.
Random
Formulas have Frozen Variables
(with F. RicciTersenghi)
To appear in SIAM Journal of Computing.
2008
Algorithmic
Barriers from
Phase Transitions (with A. CojaOghlan)
In Proceedinds of FOCS'08, pp.
Solution
Clustering in Random Satisfiability
European Physics Journal B, 64, (2008), 395402.
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 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.