CSE 590VG: Codes and Pseudorandom
Objects, Winter 2003
- Venkatesan Guruswami
- Office: 414 Sieg Hall; Phone: 685-1959
- Office hours: Drop in any time or email to make appointment.
- Mondays and Wednesdays, 2:00-3:20 PM, EE1-042
Needless to say, we will not have a textbook for this course. Some of
the following books might be useful (you can borrow and refer to them
if needed, they are by no means required for the course).
For coding theory basics, I also recommend browsing the notes/slides
of the first few lectures (numbers 1, 4, 5 should suffice) of Madhu
Sudan's recent course at
MIT. When we discuss expander codes, notes for Lectures 16, 17
and 19 on that page will also be useful. In general, it is a good page
to bookmark. Here are also some useful notes
on algebra, by Madhu Sudan.
- The Probabilistic Method (by Alon and Spencer), Chapter 9
(for portion on expanders)
- Introduction to Coding Theory,
by J. H. van Lint, Springer Verlag, Berlin, 1999. Good, compact
textbook on coding theory. Also Section 1.1 can be used to brush up on
the necessary algebra topics (linear algebra, finite fields, etc.)
- The Theory of Error Correcting Codes. F.J. MacWilliams and
N.J.A. Sloane. North-Holland, Amsterdam, 1981.
The main topics discussed in lectures will be subsets from a subset of
the following papers.
Note: These links point to actual location of papers at
authors' webpages and the papers are not reposted locally.
codes, by M. Sipser and D. Spielman. Also the survey
by Dan Spielman.
- On expander codes, by G. Zemor, IEEE Trans. on Information Theory,
IT-47 No 2, (2001) pp. 835--837.
(Somewhat simpler analysis than [Sipser-Spielman])
- Linear time encodable/decodable codes with
near-optimal rate, by V. Guruswami and P. Indyk.
Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders
and Extractors, by O. Reingold, S. Vadhan and A. Wigderson.
- Random Cayley graphs and expanders, by N. Alon and
Y. Roichman. Random Structures Algorithms, 5 (1994), pages
67659: Expander graphs and their applications : Webpage of course
offered by N. Linial and A. Wigderson, maintained by B. Barak. Very neat
- Extractors from
Reed-Muller Codes, by A. Ta-Shma, D. Zuckerman, and S. Safra.
Extractors for All Min-Entropies and a New Pseudo-Random
Generator, by R. Shaltiel and C. Umans.
Developments in Extractors, Survey article by Ronen
Shaltiel. (I highly recommend that you at least browse through
this when we begin the extractors part.)
codes, by A. Ta-Shma and D. Zuckerman.
extractors and their many guises, Slides of FOCS 2002 Tutorial
given by Salil Vadhan.
Department of Computer Science & Engineering|
University of Washington
Seattle, WA 98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX