Students may choose lecture topics from the following list, or they may give a presentation on another topic they choose for themselves, with the intructor's permission. Each of the topics listed below is accompanied by one or more suggested papers. Generally, the presentation should be based on a single primary paper (or occasionally two papers); the highlighted paper on the list is the suggested primary paper. The others on the list provide supporting material which may enhance the lecture. For example, sometimes the primary paper is solving a problem raised in an earlier paper which is included elsewhere on the list of links.

All students in the class are responsible for reading the primary paper(s) before coming to class. You should at least read enough of the paper to learn the main contribution and the main technical ideas behind this contribution. Then write one or two paragraphs of comments on the paper and send it to cs783-2007fa@googlegroups.com. You may want to discuss some (not necessarily all) of the following points in your comments:

- What is the main contribution of the paper? Is it an important contribution? Why or why not?
- What was the main insight in getting the result?
- Propose an extension to the paper which would be interesting to consider. (You need not have any idea how to approach this extension.)
- Suggest a question arising from the paper that we should discuss in class.
- What are the applications of this work? Are the underlying assumptions appropriate for the applications?

Network Coding

- Multicast network coding.
- R. Koetter and M. Medard. An algebraic approach to network coding. IEEE/ACM Transactions on Networking 11(5):782-795, 2003.
- T. Ho, R. Koetter, M. Medard, M. Effros, J. Shi, and D. Karger. A random linear network coding approach to multicast. IEEE Trans. Information Theory 52 (10) : 4413-4430, 2006.
- A. Agarwal and M. Charikar. On the advantage of network coding for improving throughput. Information Theory Workshop, 2004.

- Multicommodity flow. Approximate max-flow/min-cut theorems.
- T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. JACM 46 (6) : 787-832, 1999.
- N. Garg, V. Vazirani, and M. Yannakakis. Approximate max-flow min-(multi)cut theorems and their applications. SIAM J. Computing 25 (2) : 235-251, 1996.
- D. Shmoys. Cut problems and their applications to divide and conquer. In: Approximation Algorithms for NP-Hard Problems, (D. S. Hochbaum, ed.) PWS, 1997, 192-235.

- Edge-cut constraints on network coding.
- N. J. A. Harvey, R. Kleinberg, and A. Rasala Lehman. On the capacity of information networks. IEEE Trans. Information Theory 52 (6) : 2345-2364, 2006.
- N. J. A. Harvey and R. Kleinberg.
Tighter cut-based bounds for
*k*-pairs communication problems. Allerton Conference on Communication, Control, and Computing, 2005. - N. J. A. Harvey, R. Kleinberg, C. Nair, and Y. Wu. A "chicken and egg" network coding problem. ISIT 2007.
- G. Kramer and S. A. Savari. Edge-cut bounds on network coding rate. Journal of Network and Systems Management 14 (1) : 49-67, 2006.

- Yeung's inner and outer bounds.
- L. Song and R. W. Yeung. Zero-error network coding for acyclic networks. IEEE Trans. Information Theory 49: 3129-3139, 2003.
- X. Yan, R. W. Yeung, and Z. Zhang. The capacity region for multi-source multi-sink network coding. ISIT 2007.

- Non-Shannon inequalities.
- Z. Zhang and R. W. Yeung. A non-Shannon-type conditional inequality of information quantities. IEEE Trans. Information Theory 43 : 1982-1985, 1997.
- Z. Zhang and R. W. Yeung. On characterization of entropy function by information inequalities. IEEE Trans. Information Theory 44 (4) : 1440-1452, 1998.
- T. H. Chan and R. W. Yeung. On a relation between information inequalities and group theory. IEEE Trans. Information Theory 48, 1992-1995, 2002.
- R. Dougherty, C. Freiling, and K. Zeger. Matroids, networks, and non-Shannon information inequalities. IEEE Trans. Information Theory 53 (6) : 1949-1969, 2007.

- Lower bounds on computational complexity and alphabet size
- A. Rasala Lehman and E. Lehman. Complexity classification of network information flow problems. SODA 2004.
- A. Rasala Lehman and E. Lehman. Network coding: does the model need tuning? SODA 2005.
- M. Adler, N. J. A. Harvey, K. Jain, R. Kleinberg, and A. Rasala Lehman. On the capacity of information networks. SODA 2006.

- Index coding
- Z. Bar-Yossef, Y. Birk, T. S. Jayram, and T. Kol. Index coding with side information. FOCS 2006.
- E. Lubetzky and U. Stav. Non-linear index coding outperforming the linear optimum. FOCS 2007.

- Network error correction
- R. W. Yeung and N. Cai. Network error correction, part I: Basic concepts and upper bounds. Communications in Information and Systems 6 (1): 19-36, 2006.
- N. Cai and R. W. Yeung. Network error correction, part II: Lower bounds. Communications in Information and Systems 6 (1): 37-54, 2006.

- Network coding in wireless networks
- S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft. XORs in The Air: Practical Wireless Network Coding. SIGCOMM 2006.
- S. Katti, S. Gollakotta, and D. Katabi. Embracing wireless interference: analog network coding. SIGCOMM 2007.

- Coding for correlated sources, sensor network applications.
- J. Barros and S. D. Servetto. Network information flow with correlated sources. IEEE Trans. Information Theory 52 (1) : 155-170, 2006.
- M. Adler. Collecting correlated information from a sensor network. SODA 2005.
- M. Adler, E. Demaine, N. J. A. Harvey, and M. Patrascu. Lower bounds for asymmetric communication channels and distributed source coding. SODA 2006.
- J. Liu, M. Adler, D. Towsley, and C. Zhang. On optimal communication cost for gathering correlated data through wireless sensor networks. MOBICOM 2006.

- Network coding in peer-to-peer networks
- K. Jain, L. Lovasz, and P. Chou. Building scalable and robust peer-to-peer overlay networks for broadcasting using network coding. PODC 2005.
- C. Gkantsidis, J. Miller, and P. Rodriguez. Comprehensive view of a live network coding P2P system. IMC 2006.

- Coding for delay tolerant networks
- J. Widmer and J.-Y. Le Boudec. Network coding for efficient communication in extreme networks. WDTN 2005.
- Y. Wang, S. Jain, M. Martonosi, and K. Fall. Erasure-coding based routing for opportunistic networks. WDTN 2005.

- Network coding for network management.
- T. Ho, M. Medard, and R. Koetter. An information-theoretic view of network management. IEEE Trans. Information Theory 51 (4) : 1295-1312, 2005.

- Compressed sensing

Sample papers:- E. Candes, M. Rudelson, T. Tao, and R. Vershynin. Error correction via linear programming. FOCS 2005.
- D. Donoho. Compressed sensing. IEEE Trans. Information Theory 52 (4) : 1289-1306, 2006.
- G. Cormode and S. Muthukrishnan. Combinatorial algorithms for compressed sensing. DIMACS Technical Report 2005-40.
- C. Dwork, F. McSherry, and K. Talwar. The price of privacy and the limits of LP decoding. STOC 2007.
- A. Gilbert, M. Strauss, J. Tropp, and R. Vershynin. One sketch for all: Fast algorithms for compressed sensing. STOC 2007.
- S. Muthukrishnan. Some algorithmic problems and results in compressed sensing. Allerton Conference on Communication, Control, and Computing, 2006.

- Error-correcting codes

Sample papers:- M. Sipser and D. Spielman. Expander codes. IEEE Transactions on Information Theory 42 (6):1710-1722, 1996.
- D. Spielman. Linear-time encodable and decodable error-correcting codes. IEEE Transactions on Information Theory 42 (6):1723-1732.
- M. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. Spielman. Efficient erasure correcting codes. IEEE Transactions on Information Theory 47 (2) : 569-584.
- V. Guruswami and A. Rudra. Explicit codes achieving list decoding capacity: Error-correction up to the Singleton bound. STOC 2006.
- S. Yekhanin. Towards 3-query locally decodable codes of subexponential length. STOC 2007.

- Deletion channels

Sample papers:- E. Drinea and M. Mitzenmacher. On lower bounds for the capacity of deletion channels. IEEE Transactions on Information Theory 52 (10): 4648-4657, 2006.
- E. Drinea and M. Mitzenmacher. A simple lower bound for the capacity of the deletion channel. IEEE Transactions on Information Theory 52 (10): 4657-4660, 2006.
- Improved lower bounds for the capacity of i.i.d. deletion and duplication channels. IEEE Transactions on Information Theory 53(8):2693-2714, 2007.
- S. Diggavi and M. Mitzenmacher and H. Pfister. Capacity upper bounds for deletion channels. ISIT 2007.

- Zero-error coding theory

Sample papers:- L. Lovasz. On the Shannon capacity of a graph. IEEE Transactions on Information Theory 25:1-7, 1979.
- J. Korner and A. Orlitsky. Zero-error information theory. IEEE Transactions on Information Theory 44 (6) : 2207-2229, 1998.
- T. Bohman and R. Holzman. A nontrivial lower bound on the Shannon capacities of the complements of odd cycles. IEEE Transactions on Information Theory 49 : 721-722, 2003.
- R. Calderbank, P. Frankl, R. L. Graham, W. Li, and L. Shepp. The Sperner capacity of the cyclic triangle for linear and nonlinear codes. J. Alg. Combinatorics 2 : 31-48, 1993.