EE 477: Universal Schemes in Information Theory
# EE 477: Universal Schemes in Information Theory

### Stanford University

### Fall 2011-2012

### Contents:

### Announcements

- The first lecture is on Tue., Sep. 27th.

How can information be represented, processed, stored, transmitted,
decoded or predicted efficiently? How can noise be removed or reduced
from it? What is the minimum amount to be stored so that it can be
recovered within a specified fidelity? Recent decades have witnessed a
fruitful interplay of ideas from information theory, statistics,
probability and theoretical computer science, resulting in universal
schemes: algorithms that perform such tasks essentially optimally,
without knowledge of statistical properties of the data. Several of
these algorithms have practical and graceful implementations, and are
of wide current use. The course will focus on theoretical and
algorithmic aspects of universal schemes. Emphasis will be placed on
identifying common themes and on developing tools for constructing and
for analyzing the performance of such schemes in a unified framework.
These tools will be put to use and applied to a new problem in the
final project.
A tentative syllabus can be found here.

#### Prerequisites:

- Information theory EE376A

#### References:

Material will be drawn from the current literature, papers in Link 1,
Link 2
and Link 3,
and from the following textbooks:
- T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley, 1991.
- I. Csiszar and J. Korner, Information Theory: Coding Theorems for
Discrete Memoryless Systems, Akademiaki Kiado, 1981.
- R. Gallager, Information Theory and Reliable Communication, Wiley, 1968.
- T. Berger, Rate-Distortion Theory, Prentice-Hall, 1971.
- R. M. Gray, Source Coding Theory, Kluwer, 1990.
- R. M. Gray, Entropy and Information Theory, Springer-Verlag, 1990.
(Available online.)
- N. Cesa-Bianchi and G. Lugosi, Prediction, Learning, and Games,
Cambridge University Press, 2006
- G. Yona, Introduction to Computational Proteomics, Chapman and Hall/CRC, 2010.

Times and Location:
Gates 100, Tue&Th 11-12:15pm, 3 Units

Teaching staff:
- Instructor:
Tsachy Weissman
- Office: Packard 256
- Tel: 736-1418
- Email: tsachy *AT* stanford.edu
- Office hours: Thursday 1pm-2pm or by appointment.

- Teaching Assistant:
Vinith Misra
- Office: Packard 251
- Tel: 723-4544
- Email: vinith *AT* stanford.edu
- Office hours: Tuesday 1pm-2pm or by appointment

- Project Assistant:
Idoia Ochoa-Alvarez
- Office: Packard 251
- Tel: 723-4544
- Email: iochoa *AT* stanford.edu
- Office hours: Tuesday 4pm-6pm or by appointment

- Administrative Associate:
Kelly Yilmaz
- Office: Packard 259
- Tel: 723-4539
- Email: yilmaz *AT* stanford.edu

### Course Requirements

Grading will be based on homework sets(approximately biweekly),
a lecture scribe, and
a project. The weight of each part in determining the final grade will be announced
early in the quarter.

#### Restricted Access