<html><body><div style="font-family: garamond,new york,times,serif; font-size: 12pt; color: #000000"><div>Sumegha Garg will present her General Exam on Monday, May 22, 2017 at 2pm in CS 302.</div><div><br data-mce-bogus="1"></div><div>The members of her committee are: Mark Braverman (adviser), Ran Raz, and Kyle Jamieson.</div><div><br>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.<br></div><div data-marker="__QUOTED_TEXT__"><div dir="ltr"><div><div><div><br></div>----------<br><b>Reading List</b><br>1. On the Capacity of Information Networks - Nicholas J. A. Harvey, Robert Kleinberg, April Rasala Lehman<br><br>2. Derandomized Squaring of Graphs - Eyal Rozenman, Salil Vadhan<br><br>3. Symbol-level Network Coding for Wireless Mesh Networks - Sachin Katti, Dina Katabi, Hari Balakrishnan, and Muriel Medard<br><br>4.&nbsp;

 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)<br>-------------<br><br><b>Book</b><br>Computational Complexity: A Modern Approach by Arora and Barak<br>-------------<br><br><b>Abstract</b><br>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.<br><br>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 &lt; 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.<br><br>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.<br><br>Joint work with Mark Braverman and Ariel Schvartzman<br><br></div></div></div></div></div></body></html>