everything.study
6.895

Essential Coding Theory

Graduate · Historical course

Fall 2004

Topics

  • Decoding Reed-Solomon Codes - The Welch-Berlekamp Algorithm
  • List Decoding of Reed-Solomon Codes
  • Achieving Shannon Capacity in Polytime with Concatenated Codes
  • List Decoding versus Rate versus Distance
  • The Gap between Constructive and Existential Results in Coding Theory
  • Algebraic Geometry Codes
  • Linear-time Decodable Codes
  • Linear-time Encodable and Decodable Codes
  • Expander Codes - the ABNNR Construction
  • Computation and Randomness: Pseudo-randomness, Limited Independence, Small-bias Spaces
  • Extraction of Randomness, Min-entropy, Statistical Difference, Extractors and Codes
  • Trevisan’s Extractor
  • Ta-Shma-Zuckerman-Safra Extractor, Guruswami-codes
  • Ta-Shma-Zuckerman-Safra Extractor (cont.)
  • Expanders, Eigenvalues and the Zig-Zag Product
  • TBA

Readings

  • Blahut, R. E. Theory and Practice of Error-Control Codes . Reading, MA: Addison-Wesley, 1983. ISBN: 0201101025.
    Listed reading
  • MacWilliams, F. J., and N. J. A. Sloane. The Theory of Error Correcting Codes . Amsterdam, Netherlands: North-Holland, 1978. ISBN: 0444851933.
    Listed reading
  • Van Lint, J. H. Introduction to Coding Theory . 3rd ed. Berlin, Germany: Springer-Verlag, 1999. ISBN: 3540641335.
    Listed reading
Fall 2003 · Theory of Parallel Systems (SMA 5509)

Topics

  • Dynamic Multithreading
  • Cilk, Matrix Multiplication, and Sorting
  • Serial Performance and Caching
  • Determinacy Detection and Race Detection
  • Consistency of the Memory Sub-System
  • Analyzing Space Bounds
  • Memory Contention
  • Cilk Scheduler
  • Analysis of Cilk Scheduler
  • Cilk Implementation
  • Project Presentations 1
  • Project Presentations 2
  • Implementation of Memory Consistency
  • Competitive Snoopy Caching
  • Snoopy Caching and Spin-Block Problem
  • Hypercubic Networks 1
  • Hypercubic Networks 2
  • Hypercubic Networks 3
  • Squish Routing
  • Permuting Data on Parallel Disks
  • Sorting and Permuting
  • Pick a Winner
  • Final Project Presentations
  • Final Project Presentations (cont.)
  • Final Project Presentations (cont.) Final Papers Due

Readings

  • Cache-Oblivious Algorithms
    Listed reading
  • Feng, Mingdong, and Charles E. Leiserson. Efficient Detection of Determinacy Races in Cilk Programs.
    Listed reading
  • Cheng, Guang-Ien, Mingdong Feng, Charles E. Leiserson, Keith H. Randall, and Andrew F. Stark. “Detecting Data Races in Cilk Programs that Use Locks.” In Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures (1998): 298-309.
    Listed reading
  • Goodman, James R. Using Cache Memory To Reduce Processor-Memory Traffic . Department of Computer Sciences, University of Wisconsin-Madison Madison, WI: 19883, pp. 255-262.
    Listed reading
  • Lamport, Leslie. “How to Make a Correct Multiprocess Program Execute Correctly on a Multiprocessor.” IEEE Trans. Computers 46 (February 14, 1993).
    Listed reading
  • Frigo, Matteo, and Victor Luchangco. “Computation-Centric Memory Models.” To appear in Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms And Architectures (SPAA). MIT Laboratory for Computer Science, Massachusetts Institute of Technology. June 28-July 2, 1998.
    Listed reading
  • Herlihy and Moss. Transactional Memory: Architectural Support for Lock-Free Data Structures. ( PDF ) (Courtesy of Maurice Herlihy and J. Eliot Moss. Used with permission.) ↗
    Listed reading
  • Huang, Kai. Data-Race Detection In Transaction Everywhere Parallel Programming. ( PDF ) ↗
    Listed reading
  • Blumofe, Robert D., Charles E. Leiserson. “Space-Efficient Scheduling of Multithreaded Computations.” SIAM Journal on Computing 27, 1: 202-229. MIT Laboratory for Computer Science, Massachusetts.
    Listed reading
  • Berger, Emery D., Kathryn S. McKinley, Robert D. Blumofe, and Paul R. Wilson. “Hoard: A Scalable Memory Allocator for Multithreaded Applications.” In Proceedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems . Cambridge, MA: November 2000. Department of Computer Sciences, The University of Texas at Austin Austin, Texas. Department of Computer Science, University of Massachusetts Amherst, Massachusetts.
    Listed reading
  • Blumofe, Robert D., Matteo Frigo, Christopher F. Joerg, Charles E. Leiserson, and Keith H. Randall. “An Analysis of Dag-Consistent Distributed Shared-Memory Algorithms.” In Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA). Department of Computer Sciences, The University of Texas at Austin, Texas. MIT Laboratory for Computer Science, Massachusetts.
    Listed reading
  • Narlikar, Girija J., and Guy E. Blelloch. “Space-Efficient Scheduling of Nested Parallelism.” ACM Transactions on Programming Languages and Systems (TOPLAS) 21, 1 (January 1999): 138-173. Carnegie Mellon University.
    Listed reading
  • LEC #: 8 · TOPICS: Cilk Scheduler · READINGS: Executing Multithreaded Programs Efficiently
    Reading assignment
  • Karlin, Anna R., Mark S. Manasse, Larry Rudolph, and Daniel D. Sleator. “Competitive Snoopy Caching.” Algorithmica 3 . Springer-Verlag, New York Inc., 1988, pp. 79-119.
    Listed reading
  • Karlin, Anna R., Mark S. Manasse, Lyle A. McGeochj, and Susan Owicki. “Competitive Randomized Algorithms for Non-Uniform Problems” In Proceedings, Symposium on Discrete Algorithms. 1990, chapter 33, pp. 301-309.
    Listed reading
  • LEC #: 22 · TOPICS: Pick a Winner · READINGS: Awerbuch, Baruch, Yossi Azar, Amos Fiat, and Tom Leighton. “Making Commitments in the Face of Uncertainty: How to Pick a Winner Almost Every Time.” In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (1996): 519-530.
    Reading assignment
Sources