Email: <last five letters of last name> @di.uoa.gr
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
in Reverse Chronological Order
Bias of Traceroute Sampling
(with A. Clauset, D.Kempe, C. Moore)
To appear in Journal of ACM.
Formulas have Frozen Variables
(with F. Ricci-Tersenghi)
To appear in SIAM Journal of Computing.
Phase Transitions (with A. Coja-Oghlan)
In Proceedinds of FOCS'08, pp.
Clustering in Random Satisfiability
European Physics Journal B, 64, (2008), 395-402.
Satisfiable Clauses in a Random Formula (with A. Naor, Y. Peres)
Journal of ACM, 54 (2), Article 9, (2007).
Computation of Low-Rank Approximations (with F. McSherry)
Journal of ACM, 54 (2), Article 10, (2007).
Two Moments Suffice to Cross a Sharp Threshold (with C. Moore)
SIAM Journal of Computing, 36, (2006), 740-762.
Possible Values of the Chromatic Number of a Random Graph (with A.
Annals of Mathematics, 162 (3), (2005), 1333-1349.
Location of Phase Transitions in Hard Optimization Problems (with
A. Naor, Y. Peres)
Nature, 435 (2005), 759-764.
Assignments: Two are Better Than One (with H. Jia, C. Moore)
Journal of Artifical Intelligence Research, 24, (2005), 623-639.
Mixing for Lattice Colourings with
Fewer Colours (with M. Molloy, C. Moore, F. van
Journal of Statistical Mechanics: Theory and Experiment, 2005, P10012.
Threshold for Random k-SAT is 2k log 2 - O(k)
(with Y. Peres)
J.AMS, 17, (2004), 947-973.
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.
Matrices in Data Analysis
in Proceedings of ECML'04, pp. 1-8.
Number of Random Regular Graphs (with C. Moore)
in Proceedings of RANDOM'04, pp.219-228.
for DPLL Below the Satisfiability Threshold (with P. Beame, M.
in Proceedings of SODA'04, pp. 132-133.
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.
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.
Satisfiable Clauses in a Typical Formula (with A. Naor, Y.Peres)
in Proceedings of FOCS'03, pp. 362-370.
2-colorability of Random Hypergraphs (with C. Moore)
in Proceedings of RANDOM'02.
Techniques for Kernel Methods (with F. McSherry, B.
in Proceedings of NIPS'02.
Random Hypergraphs (with J.H. Kim, M. Krivelevich,
Random Structures & Algorithms, 20 (2), (2002), p.249-259.
Hub Synthesis (with A. Fiat, A. Karlin, F. McSherry)
in Proceedings of FOCS'01, pp.611-618.
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)
Transition in NAESAT and 1-in-k SAT (with A. Chtcherba, G. Istrate,
in Proceedings of SODA'01, pp.721-722.
for Random 3-SAT via Differential Equations
Theoretical Computer Science, 265 (1-2), (2001), pp.159-185.
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)
Results for (2+p)-SAT (with L.M. Kirousis, E. Kranakis, D. Krizanc)
Theoretical Computer Science, 265 (1-2), (2001), p.109-129.
Algorithms for Random 3-SAT (with G.B. Sorkin)
in Proceedings of FOCS'00, pp.590-600.
Satisfiable Problem Instances (with C. Gomes, H. Kautz,
in Proceedings of AAAI'00.
Variables at a Time Yields a New Lower Bound for Random 3-SAT
in Proceedings of STOC'00, pp.28-37.
Analysis of Randomized Paging Algorithms (with M.
Chrobak, J. Noga)
Theoretical Computer Science, 234, (2000), p.203-218.
Sharp Threshold for k-Colorability (with E. Friedgut)
Random Structures & Algorithms, 14 (1), (1999), p.63-70.
All Graphs with 2.522n Edges are not 3-Colorable (with M.
Electronic Journal of Combinatorics, 6 (1), (1999), R29
Bounds on st-Connectivity on the NNJAG model (with J. Edmonds, C.K.
SIAM Journal on Computing, 28 (6), (1999), p.2257-2284.
Existence of Uniquely G-free Colourable Graphs (with J.I. Brown, D.
Corneil, M. Molloy)
Discrete Mathematics, 179, (1998), p.1-11.
of a List-Coloring Algorithm on a Random Graph (with M.
in Proceedings of FOCS'97, p.204-212.
Complexity of G-free Colorability
Discrete Mathematics, 165/166, (1997), p.21-30.