Course Announcement: Toolkit for Theoretical Computer Science - Winter/Summer Semester (2022-23)


Time: TuTh 9:30-11:00
Location: A201
Instructor: and
Homepage: http://tifr.res.in/~prahladh/teaching/2022-23/toolkit


CSS.205.1: Toolkit for Theoretical Computer Science

Course Outline

This course will be an selection of topics from the literature in computer science, probability, and mathematics. The goal is to cover a broad spectrum of techniques underlying various areas of research in theoretical computer science.
  1. Basic probability inequalities. Applications to sketching and streaming. The role of pseudorandomness.
  2. Basic Matrix analysis: properties of semi-denite matrices, concentration for matrix values random variables.
  3. Linear and Semi-denite programming. Rounding. Duality. Algorithmic and analytic applications.
  4. The multiplicative weight update method and its applications.
  5. Spectral methods.
  6. “Polynomial methods” in combinatorics.
  7. VC Dimension
  8. Introduction to oracle models of optimization.
  9. Concentration of measure and applications. (Tentative)
  10. Lattice problems in algorithms and complexity. (Tentative)

Earlier versions of this course were offered in the Monsoon, 2018 and Winter 2021 semesters. Webpages can be accessed at https://www.tifr.res.in/~piyush.srivastava/teaching/mon-2018-toolkit/ and https://www.tifr.res.in/~prahladh/teaching/2020-21/toolkit/. We expect to cover the following topics (we expect the course to be roughly similar to the Winter 2021 offering).

Grading

There will be a final exam (likely to be in class), and 2-4 homework assignments. There might also be a couple of graded/ungraded quizzes.

Prerequisites

In addition to undergraduate algorithms and discrete mathematics, we expect the only other prerequisites to be some familiarity with linear algebra (the notions of eigenvalues, eigenvectors and eigenvalue and singular value decompositions) and analysis (notions of convergence, norms, Hölder’s inequality etc.).

Instructor: and


Prahladh Harsha