[talks] N Heninger general exam

[Melissa M Lawson]

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.
-------------------------------------- 
Abstract:

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.

Reading list:

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