Random Graphs Papers

A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks, Combinatorica 2012, 1-33.
[Co-authors: O. Angel and D. Wilson]
On the diameter of the set of satisfying assignments in random satisfiable k-CNF formulas, SIAM Journal on Discrete Mathematics. 2011; 25 (2) 736-749.
[Co-authors: U. Feige and D. Vilenchik]
Algorithms for Random 3-SAT, extended version of chapter in Encyclopedia of Algorithms (2008) 742-744.
Defending against Sybil attacks via social networks, IEEE/ACM Transactions on Networking 16 (3) (2008) 576-589.
[Co-authors: Haifeng Yu, M. Kaminsky, P. Gibbons]
A spectral technique for random satisfiable 3CNF formulas, Random Structures and Algorithms, 32 (4) (2008) 519-534.
A geometric preferential attachment model of networks II, Internet Mathematics 4 (1) (2007) 87-111.
[Co-authors: A. Frieze and J. Vera]
Slides for my 25 minute talk at WAW 2007
The lower tail of the random minimum spanning tree, Electronic Journal of Combinatorics 14 (1) (2007) N3.
A geometric preferential attachment model of networks, Internet Mathematics 3 (2) (2007) 187-205.
[Co-authors: A. Frieze and J. Vera]
[bibtex]
Expansion and lack thereof in randomly perturbed graphs, Internet Mathematics 4 (2) (2007) 131-147.
Slides from DIMACS workshop, spring 2007
Bias reduction in traceroute sampling: towards a more accurate map of the Internet, Proc. of the 5th International Workshop on Algorithms and Models for the Web-Graph (WAW), (2007), 1-15.
[Co-author: J. Vera]
Slides for my 25 minute talk at WAW 2007
A geometric preferential attachment model of networks II, Proc. of the 5th International Workshop on Algorithms and Models for the Web-Graph (WAW), (2007), 41-55 (see also journal version above).
[Co-authors: A. Frieze and J. Vera]
Slides for my 25 minute talk at WAW 2007
On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem, Combinatorics, Probability, and Computing 16 (2007) 713-732.
[Co-authors: A. M. Frieze and J. Vera]
Slides from my talk at STOC 2005
The diameter of a randomly perturbed digraph and some applications, Random Structures and Algorithms 30 (2007), 484-504.
[Co-author: A. Frieze]
Slides from RANDOM 2004 talk
[bibtex]
Adversarial deletions in a scale free random graph process, Combinatorics, Probability and Computing, 16 (2007) 261-270.
[Co-authors: A. Frieze and J. Vera]
[bibtex]
Randomly coloring sparse random graphs with fewer colors than the maximum degree, Random Structures and Algorithms 29, (2006) 450-465.
[Co-authors: M. Dyer, A. Frieze, and E. Vigoda]
[bibtex]
First-passage percolation on a width-2 strip and the path cost in a VCG auction, Proc. of the 2nd International Workshop on Internet and Network Economics (WINE) (2006) 99-111.
[Co-authors: D. Gamarnik and G. B. Sorkin]
Slides from talk at CanaDAM 2007
[bibtex]
Defending against Sybil attacks via social networks, ACM SIGCOMM (2006) 267-278 (see also journal version above).
[Co-authors: Haifeng Yu, M. Kaminsky, P. Gibbons]
[bibtex]
Average-case analysis for combinatorial problems, Ph.D. Thesis, Dept. of Mathematical Sciences, Carnegie Mellon University (2006).
Adversarial deletions in a scale free random graph process, Proc. of the 16th Symposium on Discrete Algorithms (SODA) (2005) 287-292 (see also journal version above).
[Co-authors: A. Frieze and J. Vera]
[bibtex]
High degree vertices and eigenvalues in the preferential attachment graph, Internet Mathematics, 2 (2005) no. 1, 1-19.
[Co-authors: T. Fenner and A. Frieze]
[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) 441-449 (see also journal version above).
[Co-authors: A. M. Frieze and J. Vera]
Slides from my talk at STOC 2005
Embracing the giant component, Random Structures and Algorithms 27 (3) (2005), 277-289.
[Co-authors: D. Gamarnik and G. Sorkin]
[bibtex]
A sharp threshold for a random constraint satisfaction problem, Discrete Mathematics 285/1-3 (2004), 301-305.
[bibtex]
Embracing the giant component, Proc. of the 6th Conference of Latin American Theoretical Informatics (2004) 69-79 (see also journal version above).
[Co-authors: D. Gamarnik and G. Sorkin]
[bibtex]
Efficient communication in an ad-hoc network, Journal of Algorithms 52 (1) (2004), 1-7.
[Co-authors: A. Frieze and E. Upfal]
[bibtex]
A geometric preferential attachment model of networks, Proc. of 3rd International Workshop on Algorithms and Models for the Web-Graph (2004) 44-55 (see also journal version above).
[Co-authors: A. Frieze and J. Vera]
[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) 345-356 (see also journal version above).
[Co-author: A. Frieze]
Slides from RANDOM 2004 talk
[bibtex]
A spectral technique for random satisfiable 3CNF formulas, Proc. of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, (2003), 357-363.
[bibtex]
High degree vertices and eigenvalues in the preferential attachment graph, Proc. 7th International Workshop on Randomization and Approximation Techniques in Computer Science (2003) 264-274 (see also journal version above).
[Co-authors: T. Fenner and A. Frieze]
[bibtex]