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:
Back to homepage.