----------
Reading List1. 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)
-------------
BookComputational Complexity: A Modern Approach by Arora and Barak
-------------
AbstractThe 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