Instructor: Sruthi Sekar (sruthi [at] cse [dot] iitb [dot] ac [dot] in)
Course Timing and Location (CS 785): 14:00-15:25 AM Tue/Fri, CC105
Teaching Assistants: Nilabha Saha, Krishna N Agaram
Contact Hours: After class, or fix appointment by emailing
Important Dates:
- QUIZ 1: 24th January, 8:30-9:30 AM, CC103
- QUIZ 2: 14th February, 8:30-9:30 AM, CC103
- QUIZ 3: 26th March, 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 probability and mathematical maturity
Grading
- Final Exam – 30%
- MidSem Exam – 25%
- Quizzes/Assignments -20%
- Presentations -15%
- Scribe -5% (see template below)
- Class Participation (2%) + Attending seminar talks (3%) -5%
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 (to help you with basic probability)
- Assignment 1 (Asymptotics and Probability)
- Quiz 1 paper [solution sketch]
- Assignment 2 (to help you refresh basic linear algebra)
- Assignment 3 (DFT)
- Quiz 2 paper [solution sketch]
- Assignment 4 (Algebra and error correction) [solution for problem 4]
- Assignment 5 (Spectral Graph Theory)
- Quiz 3 paper [solution sketch]
- Assignment 6 (Communication Complexity and Information Theory)
Lectures
Scribe Template: 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 | [slides] |
| Lecture 2 (10th Jan) | Asymptotics: Basic notations and definitions, Approximation of Harmonic Number and application to Coupon Collector Problem | [lecture 2 notes] Scribes: Srijan Das [link], Priyanshu Singh [link] |
| Lecture 3 (14th Jan) | Asymptotics: Stirling’s Approximation, Binomial Coefficients | [lecture 3 notes] Scribes: Samipa Samanta [link], Abhimanyu Basu [link] |
| Lecture 4 (17th Jan) | Probability: Gaussian, Central Limit Theorem | [lecture 4 notes] Scribes: Abhishek Gupta [link], Priyanshu Singh [link] |
| Lecture 5 (21st Jan) | Probability: Chernoff and other tail bounds | [lecture 5 notes] Scribe: Mayank Yadav [link], Abhishek Kumar [link] |
| Lecture 6 (24th Jan) | Spill over from lecture 5 (Hoeffding, some other common concentration inequalities) Discrete Fourier Transform: Fast integer Multiplication, Fast polynomial multiplication via FFT | [lecture 6 notes] Scribe: Ravi B Prakash [link] [video resource for FFT] |
| Lecture 7 (28th Jan) | Fourier Analysis of Boolean Functions | [lecture 7 notes] Scribe: Siddhi Pevekar [link] |
| Lecture 8 (31st Jan) | Some properties of Fourier coefficients, Applications of Boolean Function Analysis: Property Testing (BLR Test) | [lecture 8 notes] Scribe: Nidhi Jha [link] |
| Lecture 9 (4th Feb) (Candidate for the Seminar talk component of your grade) | Guest Lecture (by Dr. Pavithran Iyer): Quantum Computing, Grover’s Algorithm | [lecture 9 notes] (references in the notes) No scribe (if interested, you can write a report and submit it for the 3% grade towards attending the seminar talk) |
| Lecture 10 (7th Feb) | Algebra Module: Finite fields (prime fields, extension fields), polynomials, application to communication complexity of equality | [lecture 10 notes] Scribe: Advay Sant [link], Suryansh Pal [link] |
| Lecture 11 (11th Feb) | Multivariate polynomials, Schwartz Zippel, Error Correcting Codes: basic definitions, notations, linear codes and their properties | [lecture 11 notes] Scribe: Rishit Shrivastava [link], Pratham Garg [link] |
| Lecture 12 (14th Feb) | Error Correcting Codes: Hamming Code, Hadamard Code, Reed Solomon Code, some bounds | [lecture 12 notes] Scribe: Siddharth Patil [link] |
| 18th & 21st Feb | Chalk and Talk Presentations | |
| 22nd Feb-2nd March | Mid-Sem Exam Week | |
| Lecture 13 (4th March) | Spectral Graph Theory: basic definitions and properties, random walks, stationary distribution | [lecture 13 notes] Scribe: Pragya Verma [link], Pranav Kandwal [link] |
| Lecture 14 (7th March) | Spectral Graph Theory: Inner product, Normalized Adjacency operator/Transition Matrix, Properties of the transition matrix, Normalized Laplacian operator, Conductance | [lecture 14 notes] Scribe: Yash Sadhwan [link] |
| Lecture 15 (11th March) | Spectral Graph Theory: Eigenvalues, Eigenvectors, Spectral theorem, Convergence of random walk to stationary distribution | [lecture 15 notes] Scribe: Durgam Latha [link] |
| Lecture 16 (18th March) | Spectral Graph Theory: Distance between probability distributions, Proving the convergence of random walk | [lecture 16 notes] Scribe: Maathangi S [link] |
| Lecture 17 (21st March) (Candidate for the Seminar talk component of your grade) | Guest Lecture (by Prof. Akash Kumar): Lovasz Simonovits technique to find sparse cuts | [lecture notes] No scribe (if interested, you can write a report and submit it for the 3% grade towards attending the seminar talk) |
| Lecture 18 (25th March) | Expander Graphs, Expander Mixing Lemma, Properties, discussion on constructions and applications [Reference: talk, survey, book] | [lecture 18 notes] Scribe: Srijan Das [link] |
| Lecture 19 (28th March) | Communication Complexity: basic definitions, deterministic communication complexity bounds | [lecture 19 notes] Scribe: Abhinav Vinod [link] |
| Lecture 20 (1st April) | Communication complexity continued: randomized communication commplexity | [lecture 20 notes] Scribe: Sagar Verma [link], Patil Vipul Sudhir [link] |
| Lecture 21 (4th April) | Information theory basics | [lecture 21 notes] Scribe: Geetesh Kini [link], Aakarsh Chaudhary [link] |
| Lecture 22 (8th April) | Information complexity, applying information theory to communication complexity | [lecture 22 notes] Scribe: Soni Naman Nirmal [link] |
Chalk and Talk
Reports for the presentations before mid-sem will be due one week after the mid-sem week!
| Chalk and Talk Topic | Group | Report |
| #1 An Elementary Proof of Stirling’s Formula [Reference: link] | Srijan Das, Abhimanyu Basu | Present on 18th Feb [Report] |
| #2 A Simple and Combinatorial Approach to proving Chernoff Bounds [Reference: paper] | Priyanshu Singh, Siddhi Pevekar | Present on 18th Feb [Report] |
| #3 Faster Walsh Hadamard Transform [Reference: paper, section 6] | Siddharth Patil, Yash Sadhwan | Present on 11th April |
| #4 Application of Boolean Function Analysis to Social Choice Theory: May’s Theorem and Arrow’s Theorem [Reference: Chapter 2, book] | Maathangi S, Durgam Latha | Present on 21st Feb [Report] |
| #5 Shor’s Algorithm (Quantum Computing) [Reference: Quantum Computation and Quantum Information by Nielsen and Chuang] | Samipa Samantha, Ravi B Prakash | Present on 21st Feb [Report] |
| #6 Justesen’s Code (the concatenation code, decoder, rate, min distance) [Reference: Section 10.3 from Essential Coding Theory by Guruswami, Rudra, Sudan] | Abhinav Vinod, Geetesh Kini | 11th April, in class |
| #7 Reed-Muller Code (The code, decoder, rate, min distance) [Reference: Chapter 9 (you can explain sub-parts from this, we can discuss) from Essential Coding Theory by Guruswami, Rudra, Sudan] | Advay Sant, Suryansh Pal | 9th April, 2 PM, CC109 |
| #8 List Decodable Codes: Parvaresh-Vardy Codes [Reference: Pseudorandomness by Salil Vadhan (ch-5)] | Group of 2 | Unclaimed |
| #9 Cheeger’s Inequality [References: link1, link2, video] | Pragya Verma, Abhishek Gupta | 4th April, 3:30 PM, CC105 |
| #10 Expander Codes [Reference: link] | Pranav Kandwal, Abhishek Kumar | 11th April, in class |
| #11 An Entropy Proof of Bregman’s Theorem (bound on the number of perfect matchings in a bipartite graph) [Reference: link, paper] | Nidhi Jha, Sagar Varma | 11th April, 12 PM, CC109 |
| #12 Pairwise and k-wise Independence, Hash tables (the definitions and constructions of the pairwise and k-wise independent family with a motivating application to hash tables) [Reference: Section 3.5, Pseudorandomness by Salil Vadhan] | Group of 2 | Unclaimed |
| #13 Shannon’s Source Coding Theorem [Reference: link] | Vipul Sudhir, Aakarsh Chaudhary | 15th April, in class |
| #14 The Randomized Communication Complexity of Set Disjointness [Reference: link] | Soni Naman Nirmal, Terli TulsiRam | 15th April, in class |
| #15 Fingerprinting and Freivalds’ Algorithm [Reference: link, section 2.1-2.3 of book] | Pratham Garg, Rishit Srivastava | 15th April, in class |
