CS 860 Fall 2025 Topics in Coding Theory

Hamming and Shannon built the mathematical foundations of modern communication theory in the late 1940s, showing how to overcome noise in data transmission. Since their discovery, error-correcting codes have been widely applied in technology, were found to occur naturally in DNA, and have inspired deep mathematical and algorithmic advances that continue to drive progress across many scientific fields.

In this course we'll study error-correcting codes from the perspective of theoretical computer science, and cover a selection of classical topics, as well as some of modern interest. We will describe combinatorial and algebraic facets of codes, error models, as well as algorithmic advances and limitations.

Prerequisites: Mathematical maturity, and CS341 or equivalent.

Grading

2-4 homework sets: 40%

Semester-long research/survey project:  45%

Scribe notes for 1-3 lectures (+ peer homework grading): 10%. Use this latex template.

Class participation 5%

The project

The project may be either a research project, or survey of a topic of your choice that involves error-correcting codes.

Along the way, you would submit the chosen topic, partial progress reports, and a final report for which you would give an in-class presentation. I will be guiding you through all of these stages. The project can be done in groups of at most 2 people. To get started, pick a relatively recent paper related to the class, from a theoretical CS conferenc (FOCS, STOC, SODA, CCC, APPROX-RANDOM, ICALP, ICS) or journal. Follow the timeline (TBD) to keep up with the partial progress.

Timeline:

Sept:  start brainstorming for project ideas, possibly with your collaborators.

By Sep 30th: run your ideas by me and I'll help you choose a topic.

Oct 30: submit a 1-2 paragraph proposal

Nov ??: project outcomes presentation

Nov ??: report submission

A tentative list of topics includes:

• Basic parameters, constructions and limitations
• Algebraic constructions of codes: polynomial codes, folding, multiplicity
• Decoding Reed-Solomon codes
• List decoding
• Code concatenation
• Combinatorial constructions: codes from expander graphs
• Linear-time decoding: Sipser-Spielman codes
• Codes against insertion-deletion error: Schulman-Zuckerman codes
• Locality in coding theory: Locally Testable/Decodable/Correctable Codes
• Quantum codes

Essential coding theory: Venkat Guruswami, Atri Rudra and Madhu Sudan

Other courses on codes out there.

Mental Health: At the University of Waterloo, we are dedicated to supporting your mental and emotional well-being. Our Counselling Services offer confidential support, including individual counselling, workshops, and crisis intervention.
If you're struggling, please reach out for help at 519-888-4096 or visit their website for more information.

Academic integrity: In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility. [Check the Office of Academic Integrity for more information.]

Grievance: A student who believes that a decision affecting some aspect of their university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70, Student Petitions and Grievances, Section 4. When in doubt, please be certain to contact the department's administrative assistant who will provide further assistance.

Discipline: A student is expected to know what constitutes academic integrity to avoid committing an academic offence, and to take responsibility for their actions. [Check the Office of Academic Integrity for more information.] A student who is unsure whether an action constitutes an offence, or who needs help in learning how to avoid offences (e.g., plagiarism, cheating) or about rules for group work/collaboration should seek guidance from the course instructor, academic advisor, or the undergraduate associate dean. For information on categories of offences and types of penalties, students should refer to Policy 71, Student Discipline. For typical penalties, check Guidelines for the Assessment of Penalties.

Appeals: A decision made or penalty imposed under Policy 70, Student Petitions and Grievances (other than a petition) or Policy 71, Student Discipline may be appealed if there is a ground. A student who believes they have a ground for an appeal should refer to Policy 72, Student Appeals.

Note for students with disabilities and disabling conditions: The University of Waterloo recognizes its obligations under the Ontario Human Rights Code to accommodate students with known or suspected disabilities and disabling conditions (e.g. medical conditions, injuries, impacts of trauma such as from violence or discrimination) to the point of undue hardship. To support this obligation, AccessAbility Services (AAS) collaborates with all academic departments and schools to facilitate academic accommodations for students with disabilities and disabling conditions without compromising the academic integrity of the curriculum. If you believe you may require academic accommodations (e.g., testing accommodations, classroom accommodations), register with AAS as early in the term as possible by completing the online application. Students already registered with AAS must activate their accommodations for each of their courses at the beginning of each term using AAS' online system. If you require assistance, contact AAS by phone (519-888-4567 ext. 35082), email (access@uwaterloo.ca) or in-person (Needles Hall North, 1st Floor, Room 1401). 

Turnitin.com: Text matching software (Turnitin®) may be used to screen assignments in this course. Turnitin® is used to verify that all materials and sources in assignments are documented. Students' submissions are stored on a U.S. server, therefore students must be given an alternative (e.g., scaffolded assignment or annotated bibliography), if they are concerned about their privacy and/or security. Students will be given due notice, in the first week of the term and/or at the time assignment details are provided, about arrangements and alternatives for the use of Turnitin in this course.

It is the responsibility of the student to notify the instructor if they, in the first week of term or at the time assignment details are provided, wish to submit alternate assignment.