Applied Extremal Combinatorics

18.409 Topics in Theoretical Computer Science

Instructor: Dan Spielman.

This class meets TTh 2:30-4:00 in room 8-119.

Watch this page as the room may change.

(http://math.mit.edu/~spielman/AEC/)

Course Announcement

This course is designed for graduate students with experience in combinatorics, theoretical computer science, or coding theory. Some knowledge of group theory and linear algebra is necessary.

For each lecture, some student will produce a nice set of lecture notes (for example, see the notes from the last time I taught this class or from Advanced Complexity Theory). This task will be divided evenly among the students taking the class for credit.

The following is a list of the topics that I presently plan to discuss. We can adjust this list to satisfy the interests of those in the class.

• Eigenvalues of graphs
  • structures determined by eigenvalues
  • Second eigenvalue/mixing rate
    • Isoperimetric number, multicommodity flow, geometric embeddings and isoperimetry
    • Spectral partitioning, geometric embeddings and eigenvalues
  • Isomorphism testing
    • Cospectral graphs
    • Relation of eigenvalues to automorphisms and testing isomorphism of graphs of bounded eigenvalue multiplicity
  • Expander graphs
    • Random expanders
    • Explicit constructions (probably Gabber-Galil)
    • Application to re-using random bits
• Eigenvectors of graphs
  • Planar graphs
  • Regular polytopes
  • Cayley graphs
  • Strongly-regular graphs
    • Relation to spherical designs, extremal point sets, and density of sphere packings
    • Limits of regularity
• Error-correcting codes
  • Lower bounds
    • Capacity
    • Naive volume bound
    • Elias's bound
    • The JPL bound
  • Classical constructions
    • Random constructions
    • The Golay code and other great codes
    • Reed-Solomon codes
    • Justesen codes
    • Concatenated codes
    • Convolutional codes
  • Hot constructions
    • Low-density parity-check codes
    • Turbo codes
    • Codes from extremal graphs
  • Decoding and encoding algorithms
• A little extremal set theory
  • Erdos-Ko-Rado theorem
  • Ray-Chaudhuri--Wilson theorem