Oded Goldreich

An interactive proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier’s strategy can be implemented in almost-linear time. Such proof systems make the benefits of interactive proof system available to real-life agents who are restricted to polynomial-time computation. This book surveys some of the known results regarding doubly-efficient interactive proof systems. It starts by presenting two simple constructions for t-no-CLIQUE, where the first construction offers the benefit of being generalized to any “locally characterizable” set, and the second construction offers the benefit of preserving the combinatorial flavor of the problem.It then turns to two more general constructions of doubly-efficient interactive proof system: the proof system for sets having (uniform) bounded-depth circuits and the proof system for sets that are recognized in polynomial-time and small space. The presentation of the GKR construction is complete and is somewhat different from the original presentation. A brief overview is provided for the RRR construction.

Property testing is concerned with the design of super-fast algorithms for the structural analysis of large quantities of data. The aim is to unveil global features of the data, such as determining whether the data has a particular property or estimating global parameters. Remarkably, it is possible for decisions to be made by accessing only a small portion of the data. Property testing focuses on properties and parameters that go beyond simple statistics. This book provides an extensive and authoritative introduction to property testing. It provides a wide range of algorithmic techniques for the design and analysis of tests for algebraic properties, properties of Boolean functions, graph properties, and properties of distributions.

This book presents a collection of 36 pieces of scientific work in the areas of complexity theory and foundations of cryptography: 20 research contributions, 13 survey articles, and 3 programmatic and reflective viewpoint statements. These so far formally unpublished pieces were written by Oded Goldreich, some in collaboration with other scientists. The articles included in this book essentially reflect the topical scope of the scientific career of Oded Goldreich now spanning three decades. In particular the topics dealt with include average-case complexity, complexity of approximation, derandomization, expander graphs, hashing functions, locally testable codes, machines that take advice, NP-completeness, one-way functions, probabilistically checkable proofs, proofs of knowledge, property testing, pseudorandomness, randomness extractors, sampling, trapdoor permutations, zero-knowledge, and non-iterative zero-knowledge.All in all, this potpourri of studies in complexity and cryptography constitutes a most valuable contribution to the field of theoretical computer science centered around the personal achievements and views of one of its outstanding representatives.

You can start by putting the DO NOT DISTURB sign. Cay, in Desert Hearts (1985). The interplay between randomness and computation is one of the most fas­ cinating 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). Modern Cryptography. Whereas classical cryptography was confined to the art of designing and breaking encryption schemes (or "secrecy codes"), Modern Cryptography is concerned with the rigorous analysis of any system which should withstand malicious attempts to abuse it. We emphasize two aspects of the transition from classical to modern cryptography: ( 1) the wide­ ning of scope from one specific task to an utmost wide general class of tasks; and (2) the move from an engineering-art which strives on ad-hoc tricks to a scientific discipline based on rigorous approaches and techniques.

The focus of this book is the P versus NP Question and the theory of NP-completeness. It also provides adequate preliminaries regarding computational problems and computational models. The P versus 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. It is widely believed that the answer to these equivalent formulations is positive, and this is captured by saying that P is different from NP. Although the P versus NP Question remains unresolved, the theory of NP-completeness offers evidence for the intractability of specific problems in NP by showing that they are universal for the entire class. Amazingly enough, NP-complete problems exist, and furthermore hundreds of natural computational problems arising in many different areas of mathematics and science are NP-complete.

The focus of this book is the P versus NP Question and the theory of NP-completeness. It also provides adequate preliminaries regarding computational problems and computational models. The P versus 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. It is widely believed that the answer to these equivalent formulations is positive, and this is captured by saying that P is different from NP. Although the P versus NP Question remains unresolved, the theory of NP-completeness offers evidence for the intractability of specific problems in NP by showing that they are universal for the entire class. Amazingly enough, NP-complete problems exist, and furthermore hundreds of natural computational problems arising in many different areas of mathematics and science are NP-complete.

Cryptography is concerned with the conceptualization, definition and construction of computing systems that address security concerns. The design of cryptographic systems must be based on firm foundations. Foundations of Cryptography presents a rigorous and systematic treatment of foundational issues, defining cryptographic tasks and solving cryptographic problems. The emphasis is on the clarification of fundamental concepts and on demonstrating the feasibility of solving several central cryptographic problems, as opposed to describing ad-hoc approaches. This second volume contains a thorough treatment of three basic applications: Encryption, Signatures, and General Cryptographic Protocols. It builds on the previous volume, which provided a treatment of one-way functions, pseudorandomness, and zero-knowledge proofs. It is suitable for use in a graduate course on cryptography and as a reference book for experts. The author assumes basic familiarity with the design and analysis of algorithms; some knowledge of complexity theory and probability is also useful.

Various types of probabilistic proof systems have played a central role in the development of computer science in the last couple of decades. These proof systems deviate from the traditional concept of a proof by introducing randomization and interaction into the verification process. Probabilistic proof systems carry an error probability (which is explicitly bounded and can be decreased by repetitions), but they offer various advantages over deterministic proof systems.This primer concentrates on three types of probabilistic proof systems: interactive proofs, zero-knowledge proofs, and probabilistically checkable proofs (PCP). Surveying the basic results regarding these proof systems, the primer stresses the essential role of randomness in each of them.

Complexity theory is a central field of the theoretical foundations of computer science. It is concerned with the general study of the intrinsic complexity of computational tasks; that is, it addresses the question of what can be achieved within limited time (and/or with other limited natural computational resources). This book offers a conceptual perspective on complexity theory. It is intended to serve as an introduction for advanced undergraduate and graduate students, either as a textbook or for self-study. The book will also be useful to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness and probabilistic proof systems. In each case, the author starts by posing the intuitive questions that are addressed by the sub-area and then discusses the choices made in the actual formulation of these questions, the approaches that lead to the answers, and the ideas that are embedded in these answers.

You can start by putting the DO NOT DISTURB sign. Cay, in Desert Hearts (1985). The interplay between randomness and computation is one of the most fas­ cinating 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). Modern Cryptography. Whereas classical cryptography was confined to the art of designing and breaking encryption schemes (or "secrecy codes"), Modern Cryptography is concerned with the rigorous analysis of any system which should withstand malicious attempts to abuse it. We emphasize two aspects of the transition from classical to modern cryptography: ( 1) the wide­ ning of scope from one specific task to an utmost wide general class of tasks; and (2) the move from an engineering-art which strives on ad-hoc tricks to a scientific discipline based on rigorous approaches and techniques.