Email: <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,
in Reverse Chronological Order
On the solution-space geometry of random constraint
satisfaction problems (with A. Coja-Oghlan, F. Ricci-Tersenghi)
Random Structures & Algorithms, appeared online March 2010.
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. Ricci-Tersenghi)
SIAM Journal of Computing, 39 (2009), 260-280.
Algorithmic Barriers from
Phase Transitions (with A. Coja-Oghlan)
In Proceedinds of FOCS'08, pp. 793–802.
Solution Clustering in Random Satisfiability
European Physics Journal B, 64, (2008), 395-402.
On the maximum satisfiability of random formulas
(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.
Rapid 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.
The Fraction of
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.