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