Oded Goldreich - Current Teaching

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

These reading groups are intended for small groups 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. No group should contain more than six students, and the recommended size is 3-5. The general suggested outline for the reading is provided by me (see above), but the actual implementation will be up to the students.

Record of past teaching (partial)

Syllabi of reading groups

Introduction to complexity theory

Complexity Theory is concerned with the study of the intrinsic difficulty of computational tasks. This study tends 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 reading (see guidelines) will be confined to it. Specific topics will include:

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

Foundations of Cryptography

The foundations of cryptography are the paradigms, approaches and techniques used to conceptualize, define and provide solutions to natural security concerns. The reading will present some of these conceptual tools as well as some of the fundamental results obtained using them. The emphasis is on the clarification of fundamental concepts and on demonstrating the feasibility of solving several central cryptographic problems.

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 to property testing

Property Testing is concerned with approximate decisions, where the task is distinguishing between objects having a predetermined property and objects that are ``far'' from having this property. Typically, objects are modeled by functions, and distance between functions is measured as the fraction of the domain on which the functions differ. We consider (randomized) algorithms that may query the function at arguments of their choice, and seek algorithms of very low complexity (i.e., much lower than the size of the function's domain). This reading provides a taste of the area. Specific topics include: Material is square brackets is optional.

Back to homepage.