
Algorithms for Random 3SAT, extended version of chapter in Encyclopedia of Algorithms (2008) 742744.

A spectral technique for random satisfiable 3CNF formulas, Random Structures and Algorithms, 32 (4) (2008) 519534.

On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem, Combinatorics, Probability, and Computing 16 (2007) 713732.
[Coauthors: A. M. Frieze and J. Vera]
Slides from my talk at STOC 2005

The lower tail of the random minimum spanning tree, Electronic Journal of Combinatorics 14 (1) (2007) N3.

The diameter of a randomly perturbed digraph and some applications, Random Structures and Algorithms 30 (2007), 484504.
[Coauthor: A. Frieze]
Slides from RANDOM 2004 talk
[bibtex]

Firstpassage percolation on a width2 strip and the path cost in a VCG auction, Proc. of the 2nd International Workshop on Internet and Network Economics (WINE) (2006) 99111.
[Coauthors: D. Gamarnik and G. B. Sorkin]
Slides from talk at CanaDAM 2007
[bibtex]

Randomly coloring sparse random graphs with fewer colors than the maximum degree, Random Structures and Algorithms 29, (2006) 450465.
[Coauthors: M. Dyer, A. Frieze, and E. Vigoda]
[bibtex]

Averagecase analysis for combinatorial problems, Ph.D. Thesis, Dept. of Mathematical Sciences, Carnegie Mellon University (2006).

On the random 2stage minimum spanning tree, Random Structures and Algorithms, 28 (1) (2006) 2436.
[Coauthors: A. Freize and M. Krivelevich]
Slides from my postdoc job talk on medium density subset sum and random minimum spanning trees
[bibtex]

On the random 2stage minimum spanning tree, Proc. of the 16th Symposium on Discrete Algorithms (SODA) (2005) 287292 (see also journal version above).
[Coauthors: A. Freize and M. Krivelevich]
Slides from my postdoc job talk on medium density subset sum and random minimum spanning trees
[bibtex]

Solving medium density subset sum problems in expected polynomial time, Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS) (2005) 305314.
[Coauthor: B. Przydatek]
Slides from my postdoc job talk on medium density subset sum and random minimum spanning trees
[bibtex]

On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem, Proc. of the 37th Annual ACM Symposium on Theory of Computing (STOC) (2005) 441449 (see also journal version above).
[Coauthors: A. M. Frieze and J. Vera]
Slides from my talk at STOC 2005

Embracing the giant component, Random Structures and Algorithms 27 (3) (2005), 277289.
[Coauthors: D. Gamarnik and G. Sorkin]
[bibtex]

Embracing the giant component, Proc. of the 6th Conference of Latin American Theoretical Informatics (2004) 6979 (see also journal version above).
[Coauthors: D. Gamarnik and G. Sorkin]
[bibtex]

A sharp threshold for a random constraint satisfaction problem, Discrete Mathematics 285/13 (2004), 301305.
[bibtex]

The diameter of a randomly perturbed digraph and some applications, Proc. of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 8th International Workshop on Randomization and Computation (2004) 345356 (see also journal version above).
[Coauthor: A. Frieze]
Slides from RANDOM 2004 talk
[bibtex]

Efficient communication in an adhoc network, Journal of Algorithms 52 (1) (2004), 17.
[Coauthors: A. Frieze and E. Upfal]
[bibtex]

A spectral technique for random satisfiable 3CNF formulas, Proc. of the 14th Annual ACMSIAM Symposium on Discrete Algorithms, (2003), 357363.
[bibtex]