Currently (for some time now), I am not teaching,
but I am willing to supervise *student-led reading group* on

- introduction to complexity theory, see extensive guidelines.
- foundations of cryptography, see tentative guidelines.
- introuction to property testing, see laconic guidelines (both for a full semester and half a semester).

**2017-18, 2018-19, 2020-21, 2021-22, and 2022-23:**Supervising (and occasionally attending) a two-semester student-led reading group on Introduction to Complexity Theory.**2012-13, 2014-15, and 2016-17:**A two-semester reading course on Introduction to Complexity Theory.**Fall 2015:**Introduction to Property Testing.**2010-11 and 2013-14:**A two-semester reading course on Foundations of Cryptography.**2005-06, 2007-08, and 2009-10:**A two-semester course on Introduction to Complexity Theory.**2004-05 and 2008-09:**A two-semester course on Foundations of Cryptography.**Spring 2001:**See lecture notes on Randomized Methods in Computation.**1998-9 and 2002:**See lecture notes on Introduction to Complexity Theory.

The (half-century) history of Complexity Theory has witnessed two main research efforts (or directions). The first direction is aimed towards actually establishing concrete lower bounds on the complexity of problems, via an analysis of the evolution of the process of computation. Thus, in a sense, the heart of this direction is a ``low-level'' analysis of computation. Most research in circuit complexity and in proof complexity falls within this category. In contrast, a second research effort is aimed at exploring the connections among computational problems and notions, without being able to provide absolute statements regarding the individual problems or notions. This effort may be viewed as a ``high-level'' study of computation, and the reading (see guidelines) will be confined to it. Specific topics will include:

- revisiting the P-vs-NP Question and NP-Completeness;
- separation results for time and space complexity;
- non-uniform complexity (e.g., P/poly);
- the Polynomial-time Hierarchy;
- space complexity (focus on log-space and NL);
- randomized computations (RP and BPP);
- counting problems and their approximation (the class #P and approximate-#P);
- hardness amplification (from worst-case and within average-case);
- pseudorandomness (generators and derandomization);
- probabilistic proof systems (IP, ZK, and PCP);
- approximation (optimization/search and property-testing/decision);
- average-case complexity;

In the first semester we will focus on basic tools such as
*one-way functions*,
*pseudorandomness* and *zero-knowledge proofs*.
These will be used, in the second semester, which will provide
a rigorous treatment of three basic applications:
*Encryption*, *Signatures*,
and *General Cryptographic Protocols*.
See guidelines for the reading.

This course has some overlap with the course introduction to complexity theory. Specifically, one-way functions, pseodorandom generators, and zero-knowledge proofs are covered in both courses, but the perspective and the actual contents are different.

- Introduction, motivation, and mind-frame (Sec 1.1-1.2);
- Main notions and general results (Sec 1.3.1, 1.3.3, and 1.3.5);
- Testing Linearity (Chap 2);
- Low Degree Tests (Sec 3.1 and 3.4) [background Sec 3.2-3.3];
- Testing monotonicity on the Boolean hypercube (Sec 4.2.1) and on the line (Sec 4.3.1) [and beyond Sec 4.4.0];
- Testing Dictatorship (Sec 5.2.1 and 5.2.3) and Juntas (Sec 5.3);
- Testing by Implicit Sampling (Sec 6.2);
- Lower Bounds Techniques (Sec 7.2 and 7.3);
- Testing Graph Properties in the Dense Graph Model (Sec 8.2 and 8.3 [and Sec 8.4]);
- Testing Graph Properties in the Bounded-Degree Graph Model (Sec 9.1, 9.2.3, 9.2.4, 9.3.1, and 9.4.1 [and Sec 9.5]);
- Testing Graph Properties in the General Graph Model (Sec 10.1, 10.2.2, and 10.3.2.1);
- Testing Properties of Distributions (Sec 11.1 and 11.2).

Back to homepage.