Papers

(With U. Feige & E. Ofek) Witnesses for non-satisfiability of dense random 3CNF formulas, to appear in Proceedings of the 47th Annual Symposium on Foundations of Computer Science (FOCS), 2006.

Finding cores of random 2-SAT formulae via Poisson cloning (revised on July 28, 2006), Preprint.

Poisson Cloning Model for Random Graphs, (revised on Jan. 2006, Presentation Slides), Preprint.

(With V. Vu) Generating Random Regular Graphs, To appear in Combinatorica.

(With M. Hajiaghayi) Tight Bounds For Random MAX 2-SAT, Preprint.

(With B. Bollobás, J. Verstraëte) Regular Subgraphs of Random Graph, Random Structures and Algorithms, 29 (2006), 1-13.

(With T. Bohman) A phase transition for avoiding a giant component, Random Structures & Algorithms, 28 (2006), 195-214.

(With J. Matouvsek, V. Vu) Discrepancy after adding a single set, Combinatorica, 25 (2005), 499-501.

(With Sung-Soon Choi(최성순), Kyomin Jung(정교민)) , Phase transition in a random NK landscape model, Genetic and Evolutionary Computation Conference (GECCO), 2005, 1241-1248, Conference Paper.

(With M. Hajiaghayi, T. Leighton, H. Räcke) Oblivious routing in directed graphs with random demands, ACM Symposium on Theory of Computing (STOC), 2005, 193-201, Conference Paper.

(With O. Pikhurko, J. Spencer, O. Verbitsky) How complex are random graphs in first order logic?, Random Structures and Algorithms, 26 (2005), 119-145.

(With V. Vu) Sandwiching random graphs, Advances in Mathematics, 188(2004), 444-469.

(With C. Greenhill & N. Wormald) Hamiltonian decompositions of random bipartite regular graphs, 90(2004), 195-222.

(With V. Vu) Divide and Conquer martingales and the number of triangles in a random graph, Random Structures and Algorithms, 24 (2004), 166-174.

(With Sungchul Lee) Tail bound for the minimal spanning tree of a complete graph, Statistics & Probability Letters, 64(2003), 425-430.

Perfect matchings in random uniform hypergraphs, Random Structures and Algorithms, 23 (2003), 111-132.

( with V. Vu) On complete arcs in projective planes, Combinatorica, 23(2003), 311-363.

(With N. Alon, B. Bollobás & V. Vu) Economical covers with geometric applications, Proceedings of the London Mathematical Society, 86 (2003), 273-301.

(With B. Sudakov & V. Vu) On the asymmetry of random graphs and random regular graphs, Random Structures & Algorithms, 21 (2002), 216-224.

(With S. Janson, C. Greenhill & N. Wormald) Permutation pseudographs and contiguity, Combinatorics, Probability and Computing, 11(2002), 273-298.

(With D. Achlioptas, M. Krivelevich & P. Tetali) Two-coloring Random Hypergraphs, Random Structures & Algorithms, 20 (2002), 249-259

(With B. Bollobás, C. Borgs, J. Chayes & D. Wilson) The scaling window of the 2-SAT transition, Random Structures & Algorithms, 18 (2001), 201-256.

(with M. Mandjes) Large deviations for small buffers: an insensitivity result, Queueing Systems, 37 (2001), 349-362.

(With M. Mandjes) An analysis of the phase transition phenomenon in packet networks, Advances in Applied Probability, 33 (2001), 260-280.

(with N. Wormald) Random matchings which induce Hamilton cycles, and Hamiltonian decompositions of random regular graphs, J. Combinatorial Theory, Series B, 81 (2001), 20-44.

(with Boris Pittel) Confirming Kleitman-Winston conjecture on the largest coefficient in a q-Catalan number, J. Combinatorial Theory Series A, 92 (2000), 197-206.

(with J. Kahn, L. Lovász & V. Vu) The cover time, the blanket time, and the Matthews bound, 41st Annual Symposium on Foundations of Computer Science (FOCS), (2000).

(with Boris Pittel) On tail distribution of interpost distance, J. Combin. Theory Ser. B 80 (2000), 49-56.

(with V. Vu) Concentration of multivariate polynomials and its applications, Combinatorica 20 (2000), 417-434.

(with D. Simon and P. Tetali) Limits on the Efficiency of One-Way Permutation-Based Hash Functions, 40th Annual Symposium on Foundations of Computer Science (FOCS), (1999).

(C. Borgs, J. Chayes, A, Frieze, P. Tetali E. Vigoda and V.Vu) Torpid mixing of some MCMC algorithms in Statistical Physics, 40th Annual Symposium on Foundations of Computer Science (FOCS), (1999).

(with D. Du, B. Gao, and F. K. Hwang) On Multirate Rearrangeable Clos Networks,

SIAM

J. Comput. 28 (1999), 464-471.

(with J. Kahn) Random Matchings in Regular Graphs, Combinatorica 8 (1998), 201-226.

(with J. Roche) Covering cubes by random half cubes, with applications to binary neural networks. J. Comput. System Sci. 56 (1998), no. 2, 223--252. Also appeared in Eighth Annual Workshop on Computational Learning Theory (COLT) (Santa Cruz, CA, 1995).

(with P. Fishburn, J. Lagarias and P. Wright) Interference-Minimizing Colorings of Regular Graphs,

SIAM

J. Discrete Math. 11 (1998), 15-40.

(with N. Alon and J. Spencer) Nearly Perfect Matchings in Regular Simple Hypergraphs.

Israel

J. of Math. 100 (1997), 171-187.

(With N. Alon) On the Degree, Size and Chromatic Index of a Uniform Hypergraph, J. of Combi. Th. (A), 77 (1997), 164-170.

(with P. C. Fishburn and P. Tetali) Score Certificates for Tournaments, J. of Graph Theory 24 (1997), 117-138.

On Increasing Subsequences of Random Permutations, J. of Comb. Th. A 76 (1996), 148-155.

The Ramsey Number R(3,t) has Order of Magnitude t^2/ \log t, Random Structures & Algorithms 7 (1995), 173-207.

(with P. C. Fishburn and P. Tetali) Tournament Certificates, Dimacs Tech. Report 94-06, (1994).

On Brooks' Theorem For Sparse Graphs, Combi. Prob. & Comp. 4 (1995), 97-132.

(with J. Kahn) Entropy and Sorting, J. of Computer and System Sciences 51 (1995), 390-399. Also appeared in 24th Annual ACM Symposium on the Theory of Computing (STOC), (Victoria, BC, 1992).

On 3-Colorings of E(Kn), Discrete Mathematics 118 (1993), 269-273.

Full List of Publications