Possible Lecture Topics
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.
- Multicommodity flow. Approximate max-flow/min-cut theorems.
- 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.
- 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
- Index coding
- Network error correction
- Network coding in wireless networks
- Coding for correlated sources, sensor network applications.
- Network coding in peer-to-peer networks
- Coding for delay tolerant networks
- Network coding for network management.
Potential additional topics
- 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:
- Deletion channels
Sample papers:
- 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.