In 2017-18, I will supervise a (year long) reading group on Introduction to Complexity Theory. The first meeting will take place on Tuesday, 31-Oct-17, at 14:15-16:00, in Room B of FGS building.

This is a full-year student-led reading group in Introduction to Complexity Theory. It is intended for a small group of highly motivated students, who wish to learn the subject in depth as well as experiment with reading material by themselves and brainstorming with other students.

A general suggested outline for the reading will be provided by me (see HERE), but the actual implementation will be up to the students.

My suggestion, which was implemented in past years, is that the students will read 10-20 pages a week, and participate in a weekly meeting (of 2 hours). In the meeting the students will discuss the material they read, focusing on resolving difficulties by themselves. I will be happy to attend some of the meetings, and answer various questions or present some material, all at the students' choice.

Participating students will be credited 2 points for each semester.

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 book is focused on it. Specific topics 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);
- the class #P and approximate-#P;
- randomized computations (RP and BPP);
- probabilistic proof systesms (IP, ZK, and PCP);
- pseudorandomness (generators and derandomization);
- approximation (optimization/search and property-testing/decision);
- average-case complexity;

**2012-13, 2014-15, and 2016-17:**A two-semester reading course on 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 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.

Back to homepage.