[talks] N Heninger general exam
Melissa M Lawson
mml at CS.Princeton.EDU
Fri May 11 16:06:15 EDT 2007
Nadia Heninger will present her research seminar/general exam on Thursday May 17
at 2PM in Room 402. The members of her committee are; Bernard Chazelle (advisor),
Boaz Barak, and Moses Charikar. Everyone is invited to attend her talk, and those
faculty wishing to remain for the oral exam following are welcome to do so. Her
abstract and reading list follow below.
In 2004, Goemans and Vondrak showed that there is a sparse set of edges which covers the
minimum spanning tree of a random subgraph of vertices or edges chosen independently with
probability p. I improve the bounds for the case where edges can be chosen with arbitrary
different probabilities and show that this result does not generalize to the case when
vertices are chosen non-independently. I will also explain how their main lemma is
actually an intriguing fact about reliability polynomials, which represent the probability
that a network is connected under failure, a well-known #P-complete problem. I will
discuss some natural open problems connected to this work.
N. Ailon, B. Chazelle, S. Comandur, and D. Liu Self-Improving Algorithms. SODA 2006
Holm, J., de Lichtenberg, K., and Thorup, M. Poly-logarithmic deterministic fully-dynamic
algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. STOC '98.
Charikar, M. S. Similarity estimation techniques from rounding algorithms. STOC '02.
Indyk, P. 2006. Stable distributions, pseudorandom generators, embeddings, and data stream
computation. J. ACM 53, 3 (May. 2006), 307-323.
M. Luby and A. Wigderson, "Pairwise independence and derandomization,"
Tech. Rep. 95-035, International Computer Science Institute (ICSI), Berkeley, 1995.
A. Z. Broder, M. Charikar, A. Frieze, and M. Mitzenmacher. Min-wise independent
permutations. STOC '98
S. Albers and J. Westbrook. Self-organizing data structures. In Online
Algorithms: The State of the Art, Fiat-Woeginger, Springer, 1998.
Motwani & Raghavan Randomized Algorithms Ch 5, 6, 8, 10
Mitzenmacher & Upfal Probability and Computing Ch 2, 3, 4, 5, 6, 7, 9
Vazirani Approximation Algorithms Ch 12, 13, 14, 15
More information about the talks