Sergio Servetto

ECE 662: Network Information Theory

Announcements

11/17, 2am: Homework #3 posted, and syllabus updated.

Older announcements:

9/28, midnight: Homework #2 posted, and syllabus updated.
9/16, 8:50pm: On Thu 10/14 we will have a guest lecture by Professor Venu Veeravalli (of UIUC). I would like to schedule his guest lecture for 2pm: if you have a conflict and you cannot attend at this time, please let me know asap, as I am trying to work out his schedule for that day.
9:16, 8:50pm: Addition to your scribe assignment. The notes you turn in next Tuesday must include as well the extra material I presented last Tuesday on the proof of the rate/distortion theorem based on types.
9/16, 1:50pm: New time schedule:

Tuesdays, 2:55-4:10pm, 407 Phillips
Thursdays, 2:55-4:10pm, 312 Hollister
9/09, 10pm: Homework #1 and scribe instructions posted.
9/02, 1am: Time for office hours on Thu 9/02: 2-5pm.

Syllabus

This is a second course in information theory, focused on the study of problems involving discrete distributed sources and channels. Such systems are of great interest these days in the context of new applications such as sensor networks. Our goal in this course is to understand what is known about some classical network problems, and to read some papers and book chapters on interesting related research topics.

Tentative Date	Lectures on	Related readings	Problems to start working on
8/31	Course presentation	Yeung: 2,3,4,5,8,9; Cover&Thomas: 2,3,4,5,8,13.	Review of ECE 562.
9/07, 9/09, 9/14	The method of types. Capacity and rate/distortion for two terminals.	Cover&Thomas: 12.1, 12.2; Yeung: 8, 9; Csiszar&Koerner: 1.1, 1.2, 2.1, 2.2. Csiszar's tutorial.	Homework #1
9/16, 9/21	Broadcast channels.	Cover&Thomas: 14.6. Papers: Cover 1998, Marton 1979, El Gamal and van der Meulen 1981, Prof. El Gamal's class notes.	Homework #2
9/23, 9/28	Relay channels.	Cover&Thomas: 14.7. Papers: Cover and El Gamal 1979, Dabora and Servetto 2004 (draft handed out), Prof. El Gamal's class notes.	Homework #2
9/30, 10/05, 10/07, 10/12	No lecture: 9/30 visa renewal, 10/05-07 attending the AEW4 Workshop, 10/12 is fall break.	No reading assignments.	No homework.
10/14	*Capacity of MIMO Channels: a guest lecture by Professor Venu Veeravalli*.	No reading assignments.	No homework.
10/19	Multiple access channels.	Cover&Thomas: 14.3. Prof. El Gamal's class notes.	Homework #3, Supplement
10/21	Distributed correlated sources.	Cover&Thomas: 14.4. Papers: Slepian and Wolf 1973, Cover 1975, Prof. El Gamal's class notes.	Homework #3, Supplement
10/26	Multiple access channels with correlated inputs.	Papers: Cover, El Gamal and Salehi 1980, Dueck 1981, Ahlswede and Han 1983, Prof. El Gamal's class notes.	Homework #3, Supplement
10/28	No lecture: attending the IT Workshop in San Antonio, TX.	Start reading Yeung, Chapter 11.	No homework.
11/02	The Wyner-Ziv problem.	Cover&Thomas: 14.9. Papers: Prof. Berger's 1978 notes. Wyner and Ziv 1976.	Homework #3, Supplement
11/04	Network coding -- elements of network flows.	Cormen, Leiserson, Rivest and Stein, 2001.	TBA
11/09, 11/11	*Multiterminal rate/distortion problems: two guest lectures by Professor Toby Berger*.	Cover&Thomas: 14.9. Papers: Prof. Berger's 1978 notes. Wyner and Ziv 1976.	Homework #3, Supplement
11/16	The multiterminal source coding problem.	Papers: Prof. Berger's 1978 notes. Barros and Servetto 2005 (draft handed out).	Homework #3, Supplement
11/18, 11/23	Network coding.	Yeung, Ch. 11 and 15. Papers: Ahlswede, Cai, Li and Yeung 2000, Koetter and Medard 2003.	TBA
11/25	No lecture, thanksgiving break.	Assignment of research challenge problems during this week.	No homework.
11/30, 12/02	Course wrap-up.	No new reading assignments.	Take home final exam handed out.

Two topics I would have liked to cover in this course, but that now, after 3 weeks of classes, I am quite sure there is no way we will be able to get to:

A collection of papers on the topic of measure concentration, starting with Talagrand's paper, and with Csiszar's discussions on the relevance of those ideas in information theory.
Statistical inference in an information theoretic setting, working backwards from Han and Amari's 1998 paper.

About the course

Course staff:

Instructor: Sergio Servetto

Meeting times and place, and office hours:

Class: T 2:55-4:10pm 407 PH, R 2:55-4:10 312 HO.

Office hours: by appointment.

Prerequisites:

Highly recommended: ECE 562, or else at least some probability (e.g., ORIE 651).

Might be of some use: CS 482, MATH 611.

Grading:

75% homework.

25% take home final exam.

Extra credit research challenge.

By default, homeworks should be turned in a week after they are assigned, unless either I tell you otherwise or you talk to me and we make arrangements otherwise.

Scribe Instructions:

Jeff Erickson's style file for producing scribe notes.

A sample file using Jeff's style file.

Please note: use Latex only to typeset text. For including figures, just leave a blank space in the file, draw the figures by hand, and scan them. And if you do not have a scanner, just give me a printout and I will take care of scanning them. This will take you far less time to do than using a package like xfig or similar to generate graphics.

Reading materials

Main reference material:

R. W. Yeung. A First Course in Information Theory. Kluwer, 2002.
T. M. Cover, J. A. Thomas. Elements of Information Theory. Wiley, 1991.
I. Csiszar, J. Koerner. Information Theory: Coding Theorems For Discrete Memoryless Systems. Academic Press, 1981.
Prof. Berger's 1978 lecture notes on Multiterminal Source Coding.
Prof. El Gamal's class notes for his course taught at Stanford during Spring 2004.

Some other reference material:

T. Berger. Rate Distortion Theory: A Mathematical Basis for Data Compression. Prentice Hall, 1971.
R. G. Gallager. Information Theory and Reliable Communication. Wiley, 1968.
J. M. Wozencraft, I. M. Jacobs. Principles of Communication Engineering. Wiley, 1965.
R. Graham, D. Knuth, O. Patashnik. Concrete Mathematics: A Foundation for Computer Science (2nd. ed). Addison-Wesley, 1994.
R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.