Books and Lecture Notes by Oded Goldreich


Book listed in reverse chronological order and not including edited books.

Books

P, NP, and NP-Completeness: The Basics of Complexity Theory (2010)

The focus of this book is on the P-vs-NP Question, which is the most fundamental question of computer science, and on the theory of NP-completeness, which is its most influential theoretical discovery. The book also provides adequate preliminaries regarding computational problems and computational models. The P-vs-NP Question asks whether or not finding solutions is harder than checking the correctness of solutions. An alternative formulation asks whether or not discovering proofs is harder than verifying their correctness. Whilst the P-vs-NP Question remains unresolved, the theory of NP-completeness offers evidence to the intractability of specific problems in NP by showing that they are universal for the entire class. The current textbook is a significant revision of Chapter 2 and Section 1.2 of the author's book Computational Complexity: A Conceptual Perspective.

Computational Complexity: A Conceptual Perspective (2008)

Complexity Theory is a central field of the theoretical foundations of Computer Science, which is concerned with the general study of the intrinsic complexity of computational tasks. This book offers a conceptual perspective on complexity theory. It is intended to serve as an introduction to the field, and can be used either as a textbook or for self-study. The book is also useful to experts, since it provides expositions of various sub-areas of complexity theory. The exposition starts from the intuitive questions, as embodied in the concepts studies in each sub-area, and discusses the importance of these questions, definitional choices made in the actual formulation, and the approaches and ideas hat underly the answers.

Foundations of Cryptography: a two-volume textbook (2001 and 2004)

This work is aimed at presenting firm foundations for cryptography; that is, presenting the paradigms, approaches and techniques used to conceptualize, define and provide solutions to natural ``security concerns'' 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. See

Modern Cryptography, Probabilistic Proofs and Pseudorandomness (1998).

The interplay between randomness and computation is one of the most fascinating scientific phenomena uncovered in the last couple of decades. This interplay is at the heart of modern cryptography and plays a fundamental role in complexity theory at large. Specifically, the interplay of randomness and computation is pivotal to several intriguing notions of probabilistic proof systems and is the focal of the computational approach to randomness. This book provides an introduction to these three, somewhat interwoven domains (i.e., cryptography, proofs and randomness).


Lecture notes

Randomized Methods in Computation - Lecture Notes (2001).

A variety of randomized methods are being employed in the study of computation. The aim of the current course is to make the students familiar with some of these methods. We wish to stress three aspects regarding this course: this course focuses on methods (i.e., tools and techniques) and not on concepts, these methods are probabilistic and so the result is often not ``(fully) explicit'', and the focus is on applications to the study of computation. The lecture notes were taken by students attending my semester-long course given in Spring 2001 at the Weizmann Institute of Science.

Introduction to Complexity Theory - Lecture Notes (1999 and 2002).

The first set of lecture notes were taken by students attending my year-long introductory course on Complexity Theory, given in 1998--99 at the Weizmann Institute of Science. The second set of lecture notes were written by myself as preparation to a single-semester course given in 2002. Both lecture notes are mostly superseeded by the aforementioned book.


Back to Oded Goldreich's homepage