By topic: random graphs, economics, average case analysis, operations research
Preprints
- The frugality of a VCG path auction in a sparse random graph.
[Co-author: B. Reed]
Slides from my presentation at UBC Discrete Math Seminar, 1/31/2008 - Algorithms for Random 3-SAT, extended version of chapter to appear in Encyclopedia of Algorithms.
2008
- Trust-based recommendation systems: an axiomatic approach, to appear in WWW (2008).
[Co-authors: R. Andersen, C. Borgs, J. Chayes, U. Feige, A. Kalai, V. Mirrokni, and M. Tennenholtz] - Structured procurement auctions, Proc. of the 19th Symposium on Discrete Algorithms (SODA) (2008).
[Co-authors: M. Cary, J. Hartline, and A. Karlin]
Slides for my 20 minute talk at SODA 2008
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.
[Co-authors: A. Frieze and J. Vera]
Slides for my 25 minute talk at WAW 2007 - Identifying entitlement to share in a class action settlement, 2007 Harvey Mudd College Mathematics Conference on Public Sector Operations Research (Poster).
[Co-author: S. E. Pav] - The lower tail of the random minimum spanning tree, Electronic Journal of Combinatorics 14 (1) (2007) N3.
- Maximum matchings in regular graphs of high girth, Electronic Journal of Combinatorics 14 (1) (2007) N1.
[Co-author: S. Hoory] - 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 - 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] - A geometric preferential attachment model of networks, Internet Mathematics 3 (2) (2007) 187-205.
[Co-authors: A. Frieze and J. Vera]
[bibtex] - 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]
2006
- 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] - Expansion and lack thereof in randomly perturbed graphs, Microsoft Research Technical Report TR-2006-118, presented at Web Algorithms Workshop (2006), to appear in Internet Mathematics.
Slides from DIMACS workshop, spring 2007 - 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] - Defending against Sybil attacks via social networks, ACM SIGCOMM (2006) 267-278.
[Co-authors: Haifeng Yu, M. Kaminsky, P. Gibbons]
[bibtex] - On permutation sums, unpublished manuscript.
[Co-authors: D. Coppersmith and C. Smythe] - Average-case analysis for combinatorial problems, Ph.D. Thesis, Dept. of Mathematical Sciences, Carnegie Mellon University (2006).
- On the random 2-stage minimum spanning tree, Random Structures and Algorithms, 28 (1) (2006) 24-36.
[Co-authors: A. Freize and M. Krivelevich]
Slides from my post-doc job talk on medium density subset sum and random minimum spanning trees
[bibtex]
2005
- On the competitive ratio of the random sampling auction, Proc. of the 1st International Workshop on Internet and Network Economics (WINE) (2005) 878-886.
[Co-authors: U. Feige, J. D. Hartline, R. Kleinberg]
Slides from a one hour talk - 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 - Solving medium density subset sum problems in expected polynomial time, Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS) (2005) 305-314.
[Co-author: B. Przydatek]
Slides from my post-doc job talk on medium density subset sum and random minimum spanning trees
[bibtex] - Online convex optimization in the bandit setting: gradient descent without a gradient, Proc. of the 16th Symposium on Discrete Algorithms (SODA) (2005) 385-394.
[Co-authors: A. Kalai and B. McMahan]
Slides from a talk at INTERFACE workshop
[bibtex] - 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] - On the random 2-stage minimum spanning tree, Proc. of the 16th Symposium on Discrete Algorithms (SODA) (2005) 287-292 (see also journal version above).
[Co-authors: A. Freize and M. Krivelevich]
Slides from my post-doc job talk on medium density subset sum and random minimum spanning trees
[bibtex] - Embracing the giant component, Random Structures and Algorithms 27 (3) (2005), 277-289.
[Co-authors: D. Gamarnik and G. Sorkin]
[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]
2004
- 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] - 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] - A sharp threshold for a random constraint satisfaction problem, Discrete Mathematics 285/1-3 (2004), 301-305.
[bibtex] - Efficient communication in an ad-hoc network, Journal of Algorithms 52 (1) (2004), 1-7.
[Co-authors: A. Frieze and E. Upfal]
[bibtex] - Strings with maximum numbers of distinct subsequences and substrings, Electronic Journal of Combinatorics 11 (1) (2004), R8.
[Co-authors: A. Harrow and G. Sorkin]
[bibtex]
2003
- 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] - A spectral technique for random satisfiable 3CNF formulas, Proc. of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, (2003), 357-363 (to appear in Random Structures and Algorithms).
[bibtex]