Sumegha Garg will present her General Exam on Monday, May 22, 2017 at 2pm in CS 302. The members of her committee are: Mark Braverman (adviser), Ran Raz, and Kyle Jamieson. 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. ---------- Reading List 1. On the Capacity of Information Networks - Nicholas J. A. Harvey, Robert Kleinberg, April Rasala Lehman 2. Derandomized Squaring of Graphs - Eyal Rozenman, Salil Vadhan 3. Symbol-level Network Coding for Wireless Mesh Networks - Sachin Katti, Dina Katabi, Hari Balakrishnan, and Muriel Medard 4. Optimization-Based Linear Network Coding for General Connections of Continuous Flows - Ying Cui, Muriel M ́edard, Edmund Yeh, Douglas Leith, Ken Duffy 5. Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning - Ran Raz 6. A Time-Space Lower Bound for a Large Class of Learning Problems - Ran Raz 7. Information Equals Amortized Communication - Mark Braverman, Anup Rao 8. Fast polynomial factorization and modular composition - Kiran S. Kedlaya, Christopher Umans 9. Query-to-Communication Lifting for BPP - Mika Goos, Toniann Pitassi, Thomas Watson 10. Deterministic Communication vs. Partition Number - Mika Goos, Toniann Pitassi, Thomas Watson (Query-lifting for deterministic case) ------------- Book Computational Complexity: A Modern Approach by Arora and Barak ------------- Abstract The area of network coding addresses the following basic problem: in a distributed communication scenario, can one use coding to outperform packet routing-based solutions? While it is known that using network coding can significantly improve the throughput of directed networks, it is a notorious open problem whether coding yields any advantage over the multicommodity flow (MCF) rate in undirected networks. It was conjectured that the answer is ‘no’. In this talk, I will present our result that even a small advantage over MCF can be amplified to yield a near-maximum possible gap. We prove that any undirected network with k source-sink pairs that exhibits a (1 + ε) gap between its MCF rate and its network coding rate can be used to construct a family of graphs G′ whose gap is log(|G′|)^c for some constant c < 1. The resulting gap is close to the best currently known upper bound, log(|G′|), which follows from the connection between MCF and sparsest cuts. Our construction relies on a gap-amplifying graph tensor product that, given two graphs G1,G2 with small gaps, creates another graph G with a gap that is equal to the product of the previous two, at the cost of increasing the size of the graph. We iterate this process to obtain a gap of log(|G′|)^c from any initial gap. Joint work with Mark Braverman and Ariel Schvartzman