This course covers codes for the “modern age,” going well beyond their highly successful use in communication systems over the past few decades. Topic areas covered centers around the use of codes for (i) large-scale distributed storage systems that form the core of today’s massive data centers; (ii) learning and computing for settings like graph sketching, decision trees, and reducing the latency of parallel machine learning; and (iii) fast computation and inference that are designed to exploit sparsity in a variety of settings including for compressed sensing, massive sparse FFT computation, compressive phase-retrieval, quantum state tomography, and group-testing for a wide variety of applications such as imaging (MRI and optical), astronomy, wide-band spectrum sensing, scientific computing, and fast neighbor discovery for large-scale Internet-of-Things applications.
The prerequisites for the course are basic undergraduate linear algebra, basic probability (EE 126 or equivalent) and basic familiarity with signals and systems (though this is less important). The class will emphasize breadth and should be accessible to motivated undergraduates who are interested in research, as well as incoming graduate students. There will be no exams, but students are expected to read papers and give presentations of selected literature. There will be a final project that can feature either existing literature or new research, and can be theoretical, algorithmic, and/or experimental in focus.
Time and place: Tuesdays & Thursdays: 11-12:30, 293 Cory Hall
Instructor: Kannan Ramchandran (kannanr at eecs dot berkeley dot edu)
Point of contact: Orhan Ocal (ocal at eecs dot berkeley dot edu)
Office Hours: Tuesdays from 1:00 pm to 2:00 pm at 258 Cory Hall
Important communication will be made through bCourses. There is also a Piazza for the course that you can enroll.
Each student needs to complete a course project, and give an oral and written presentation.
You need to sign up to scribe a lecture using the google doc sent to your email. You can download the scribe template here.
Students have to present selected reading material at the end of each module.
Attendance and contribution to the lecture.
We will have a few assignments. These are for your benefit only, and they will not be graded. To incentivize you to provide solutions, we will give bonus points for those providing elegant solutions.
October 6th: Project proposals are due
Overview of channel capacity and Shannon's random coding philosophy
Binary erasure channel (BEC)
Overview of algebraic codes
Overview of network codes
Introduction to regenerating codes
Code constructions for minimum bandwidth regenerating (MBR) and minimum storage regenerating (MSR) operating points
Interference alignment for exact-repair MSR codes
Locally repairable codes, piggyback codes, and systems aspects
Fast access of hot data, and redundant requests
Overview of parallel computing in today's platforms
Codes for parallel machine learning: coded matrix computations, and coded shuffling
Student presentations
Introduction to sparse recovery and compressed sensing
Sparse-graph codes for the BEC, inference over trees, density evolution
Sublinear-time algorithms for sparse Fourier transform and its applications
Fast Walsh-Hadamard transform, boolean function learning, and graph sketching
Compressed sensing based on sparse-graph codes
Compressive phase retrieval
Group testing
Student presentations
Elements of Information Theory, Chapters 2 and 7, Cover and Thomas
Information Theory, Inference, and Learning Algorithms, Mackay
Modern Coding Theory, Chapter 3, Richardson and Urbanke
Essential Coding Theory, Venkatesan Guruswami, Atri Rudra and Madhu Sudan
A Survey on Network Codes for Distributed Storage, Dimakis et al.
Network coding for distributed storage systems, Dimakis et al.
More resources will be added as needed.