Instructor: Sruthi Sekar (sruthi [at] cse [dot] iitb [dot] ac [dot] in)
Course Timing and Location (CS 785): 11:05-12:30 AM Wed/Fri, CC105
Teaching Assistants: Nilabha Saha, Maathangi S
Contact Hours: After class, or fix appointment by emailing
Important Dates:
- QUIZ 1: 28th Jan, 2026, 8:30-9:30 AM, CC103
- QUIZ 2: 11th Feb 2026, 8:30-9:30 AM, CC103
- MID SEM EXAM: 26th Feb 2026, 11:00- 13:00, CC101/105
- QUIZ 3: 27th Mar 2026, 8:30-9:30 AM, CC103
Course Description (CS 785) –tentative
This course is meant to introduce some advanced mathematical tools that are commonly used in theoretical computer science. The pre-requisite is some discrete structures course, and basic mathematical maturity. The course will follow the broad structure of Ryan O’Donnell’s course on CS Theory Toolkit.
- Basics of Linear Algebra, Asymptotics and Probability: Vector spaces, linear dependence and independence, eigenvalues/ eigenvectors, Bounds and estimation, Stirling, binomial coefficients, Chernoff bounds.
- Fourier Transforms: Properties of Discrete Fourier Transforms (DFTs), integer multiplication, Analysis of Boolean functions, other applications.
- Algebra and applications: Number theory, fields and polynomials, schwartz-Zippel Lemma, error correcting codes.
- Graph Theory and applications: Random walks in graphs, Markov chains, expander graphs and its applications to codes and derandomization.
- Information Theory and property testing: Basics of communication complexity, entropy, mutual information, information complexity.
- Hardness in Cryptography: Lattice assumptions, other alternative assumptions, average case hardness vs worst case hardness, PCP theorem.
Background
The pre-requisites are basic discrete mathematics, basic linear algebra, basic probability and mathematical maturity
Grading
- Seminar talk: Attend online talks or in-person talks on topics related to TCS, and email me to set a time to meet and explain what you understood from the talk. Additionally submit a short report summarizing the key takeaways from the talk. I will post plenty of resources. You can pick your favorite talk for this. Your score depends on how well you explain your understanding both while explaining and in the report.
- Scribe: Deadline is 2 weeks from the lecture day. After you submit, we will give you comments. You will have 1 week post receiving the comments to fix and re-submit. You can scribe multiple lectures and I will consider the best. Template: link
- Class Participation: Attending >=50% for 1%, Ask meaningful questions in person or through email for 2%, and answer questions/provide ideas in class for 2%.
- Audit Grade: Class Participation score >=3/5, Scribe atleast one lecture, Seminar talk component must complete.
References
- Mathematics and Computation, A theory revolutionizing technology and science, Avi Wigderson, Princeton University Press, 2019
- A Theorist’s Toolkit, Sanjeev Arora, 2005
- The Nature of Computation, Christopher Moore and Stephen Martens, OUP Oxford, 2011
- Pseudorandomness, Salil Vadhan, Foundations and Trends in Theoretical Computer Science
- Ryan O’Donnell’s course on CS Theory Toolkit.
- Concrete Mathematics, A Foundation for Computer Science, Graham, Knuth and Patashnik (Second edition)
Assignments
- Assignment 0 (Practice set: Basic probability and Linear Algebra recap)
- Assignment 1 (Module I: Asymptotics and Probability)
- Assignment 2 (Module II: Discrete Fourier Analysis)
- Assignment 3 (Module III: Coding Theory)
- Assignment 4 (Module IV: Spectral Graph Theory)
- Assignment 5 (Module V: Randomness Extractors)
Lectures
Scribe Template: scribe template.zip
See per-lecture references on the first page of the handwritten lecture notes below.
| Number/Date | Topics | Slide/Notes |
| Lecture 1 (7th Jan) | Introduction/Course Logistics, Some motivation for the course | [Lec 1 slides] |
| Lecture 2 (9th Jan) | Asymptotic Notations, Coupon Collector Problem, The Birthday Problem [Ref: Concrete Mathematics, Knuth and Patashnik] | [Lec 2 slides] Scribes: Bhavadharini V [link], Ramsundar A [link] |
| Lecture 3 (14th Jan) | Probability: Gaussian Distribution, Convolution of R.V.s, Central Limit Theorem [Ref: Intro to Probability, Feller] | [Lec 3 slides] [Lec 3 notes] Scribes: Shan Muhammed [link], Udit Sarkar [link] |
| Lecture 4 (16th Jan) | Probability: Chernoff and other tail bounds [Ref: Probability and Computing, Mitzenmacher-Upfal] | [Lec 4 notes] Scribes: Udit Sarkar [link], Aditya Sanapala [link] |
| Lecture 5 (21st Jan) | Probability: Sampling theorem, McDiarmid’s inequality Discrete Fourier Transform: Fast integer multiplication, FFT [Ref: Probability and Computing, Mitzenmacher-Upfal] | [Lec 5 notes] Scribes: Bharat Chandra Mukkavalli [link], Akepati Sriya [link] |
| Lecture 6 (23rd Jan) | Fourier Analysis of Boolean Functions: Introduction, the Fourier exansion of a boolean function, some combinatorial properties, the linear algebra view [Ref: Analysis of Boolean Functions, O’Donnell] | [Lec 6 notes] Scribes: Aditya Sanapala [link], Bharat Chandra Mukkavalli [link] |
| (28th Jan) | Quiz 1 | [Q paper][Sol Sketch] |
| Lecture 7 (28th Jan) | Applications of Fourier Analysis: Probability Densities, BLR Test, Social Choice Theory [Ref: Analysis of Boolean Functions, O’Donnell] | [Lec 7 notes] Scribe: John Joseph Dayyala [link], Swatej I [link] |
| Lecture 8 (30th Jan) | Application: Some quantum basics, Grover’s algorithm Guest Lecture: Dr. Pavithran Iyer, Xanadu Tech. [Ref: Quantum Computation and Quantum Information, Nielsen and Chuang] | [Lec 8 notes] (by Pavi) No scribe |
| Lecture 9 (4th Feb) | Introduction to Coding Theory (motivation, basic codes) [Ref: Essential Coding Theory, Guruswami, Rudra, Sudan] | [Lec 9 notes] Scribes: Dhruv Sanjay Jain [link], Akepati Sriya [link], Chidvilas Reddy Vavilala [link] |
| Lecture 10 (6th Feb) | Coding Theory Continued, Linear Codes and their properties, Family of Codes [Ref: Essential Coding Theory, Guruswami, Rudra, Sudan] | [Lec 10 notes] Scribe: Uday Darade [link], Tejas Shinde [link] |
| (11th Feb) | Quiz 2 | [Q paper][Sol sketch] |
| Lecture 11 (11th Feb) | Polynomial Based Codes: Reed Solomon Codes and Welch-Berlekamp Decoder Guest lecture: Prof. Vishwas, CSE IITB [Ref: Essential Coding Theory, Guruswami, Rudra, Sudan] | [Lec 11 notes] Scribe: Tejas Shinde [link], Srikar Ayyagari [link], Chidvilas Reddy Vavilala [link] |
| Lecture 12 (13th Feb) | Polynomial Based Codes: Reed Muller Codes Guest lecture: Prof. Vishwas, CSE IITB [Ref: Essential Coding Theory, Guruswami, Rudra, Sudan] | [Lec 12 (partial notes + plan)] Scribe: Priyanshu Kumar [link], Ragav R [link] |
| Lecture 13 (18th Feb) | Asymptotically Good Binary Codes: Concatenation Codes [Ref: Essential Coding Theory, Guruswami, Rudra, Sudan] | [Lec 13 notes] Scribe: Mounisha Naidu [link] |
| (20th Feb) | Tutorial Class/Recitation | Assignments 2/3 |
| (26th Feb) | Mid Sem Exam | [Q paper] |
| Lecture 14 (6th Mar) | Spectral Graph Theory: Introduction and motivation, Dirichlet form, random walk, mean, global variance [Ref: Spectral and Algebraic Graph Theory, Speilman] | [Lec 14 notes] Scribe: Kabir S Prakash [link], Ragav R [link] |
| Lecture 15 (11th Mar) | Spectral Graph Theory: Transition and Laplacian Operators, Conductance [Ref: Spectral and Algebraic Graph Theory, Speilman] | [Lec 15 notes] Scribe: Uday Darade [link], Arihant Bedagkar [link] |
| Lecture 16 (13th Mar) | Spectral Graph Theory: Eigenvalues, eigenvectors, spectral theorem, convergence of random walk [Ref: Cheeger’s inequality notes, Speilman’s lecture notes] | [Lec 16 notes] Scribe: Swatej I [link] |
| Lecture 17 (18th Mar) | Spectral Graph Theory: Examples and Application of Random Walks | [Lec 17 notes] Scribe: Ujjawal Kumar Singh [link], Arihant Bedagkar [link] |
| Lecture 18 (20th Mar) | Expander Graphs: definitions, Expander mixing lemma, some constructions, graph-based codes [Refs: survey (Hoory, Linial, Wigderson), monograph (Vadhan), survey video (Wigderson)] | [Lec 18 notes] Scribe: Vavilala Chidvilas [link] |
| Lecture 19 (25th Mar) | Expander Codes: Bipartite Expanders, Factor graph, [Sipser-Spielman95]-asymptotically good (binary) codes with linear time decoder [Refs: survey (Hoory, Linial, Wigderson), Essential Coding Theory (Guruswami, Rudra, Sudan), survey video (Wigderson)] | [Lec 19 notes] Scribe: Bhavadharini V [link] |
| (27th Mar) | Quiz 3 | [Q.paper] |
| Lecture 20 (27th Mar) | Expander Codes (continued): Distance and decoder of Sipser Spielman; Module 5 introduction: deterministic randomness extractors, weak sources. [Ref: monograph (Vadhan)] | [Lec 20 notes] Scribe (Module 5 part merged with next lecture and Expanders will be part of previous scribe) |
| Lecture 21 (1st Apr) | Randomness Extractors: Entropy notions (Shannon, Min entropy), k-sources, impossibility of deterministic extraction. [Ref: monograph (Vadhan)] | [Lec 21 notes] Scribe: Mihir Vasave [link], Vaibhav Gera [link], Dhruv Sanjay Jain [link] |
| Lecture 22 (8th Apr) | Seeded Randomness Extractors: Definition and existence, application to randomized algorithms [Ref: monograph (Vadhan)] | [Lec 22 notes] Scribe: Ramsundar A [link], Dhruv Sanjay Jain [link] |
| Lecture 23 (10th Apr) | Extractors vs Expanders: Dispersers and Vertex Expanders (combinatorial view), Expander Mixing and Extractors (spectral view), explicit seeded extractors. [Ref: monograph (Vadhan)] | [Lec 23 notes] Scribe: Chandrakant Pradhan [link], Nimish Manware [link] |
| Lecture 24 (15th Apr) | Extractors: Left Over Hash Lemma, Pairwise independent hash family, Course Summary! [Ref: monograph (Vadhan)] | [Lec 24 notes] Scribe: Jalajakshi Palli [link] |
| (17th Apr) | Tutorial Class | Assignment 4/5 (+ doubts) |
| (29th Apr, 13:00-16:00) | End Sem Exam |