Course Identification

Student led reading of introduction to computational complexity 1
20184211

Lecturers and Teaching Assistants

Prof. Oded Goldreich
N/A

Course Schedule and Location

2018
First Semester
See comments,
31/10/2017

Field of Study, Course Type and Credit Points

Mathematics and Computer Science: Guided Reading Course; Elective; 2.00 points

Comments

The course will consist of 24-28 lectures, 12-14 in each semester, and students will be given 2 credit point for each semester.

Students will be expected to read 10-20 pages a week, and to participate in a weekly meeting (of 2 hours) organized by the students.

? A group led by Gal Arnon (email gal.arnon@weizmann.ac.il) will meet on Tuesdays (starting Oct-31) between 11 and 13, at room 108 (of Bldg II).
? A group led by Uri Ben-Levy (email uribla@gmail.com) will meet on Thursdays (starting Nov-2) between 12 and 14, *probably* at room 208 (of Bldg II).
Interested students should contact the group leader regarding details.

There are no formal prerequisites for the course, but comfortable familiarity with the notion of an algorithm is definitely assumed. Students who did not take a course in "computability" (or "theory of computation") or are not sure about it, should study Section 1.2 in the book. This section discusses the notion of computational tasks and algorithms, while emphasizing the importance of representation.



Prerequisites

No

Restrictions

20

Language of Instruction

English

Attendance and participation

Required in at least 80% of the lectures

Grade Type

Pass / Fail

Grade Breakdown (in %)

100%
A pass grade will be given subject to submitting (light-weight) homework assignments

Evaluation Type

No final exam or assignment

Scheduled date 1

N/A
N/A
-
N/A

Estimated Weekly Independent Workload (in hours)

4

Syllabus

Complexity Theory is concerned with the study of the intrinsic difficulty of computational tasks. This study tend to aim at generality:It focuses on natural computational resources, and the effect of limiting those on the class of problems that can be solved. 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 course 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;
  • the class #P and approximate-#P;
  • randomized computations (RP and BPP);
  • hardness amplification;
  • pseudorandomness (generators and derandomization);
  • probabilistic proof systesms (IP, PCP etc);

Learning Outcomes

Upon successful completion of this course students should be able to:

  1. Describe key notions and principles of the field of computational complexity theory.
  2. Demonstate familiarity with basic paradigms and techniques of the field of computational complexity theory.
  3. Apply notions, principles, paradigms and techniques of computational complexity theory to their own research.
  4. Discuss the meaning of the various notions and results of computational complexity theory.

Reading List

The course will be based on my book on Computational Complexity, and will cover approximately half the material in that book. (The students will get free access to an e-copy of the book.)

Website