In case you are using a slow connection, you may prefer fetching the textonly page.
Book listed in reverse chronological order and not including edited books.
The focus of this book is on the PvsNP Question,
which is the most fundamental question of computer science,
and on the theory of NPcompleteness,
which is its most influential theoretical discovery.
The book also provides adequate preliminaries regarding
computational problems and computational models.
The PvsNP 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 PvsNP Question remains unresolved,
the theory of NPcompleteness 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. 
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 selfstudy.
The book is also useful to experts, since it provides
expositions of various subareas of complexity theory.
The exposition starts from the intuitive questions,
as embodied in the concepts studies in each subarea,
and discusses the importance of these questions,
definitional choices made in the actual formulation,
and the approaches and ideas hat underly the answers.
See also related texts on Computational Complexity (including surveys of the area). 

This twovolume 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.
Volume 1 focuses on basic tools (OneWay Functions, Pseudorandomness and ZeroKnowledge), whereas Volume 2 focuses on basic applications (Encryption, Signatures and General Secure Protocols). See also related texts (including surveys of the area). 
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).
See related texts on Foundations of Cryptography, Probabilistic Proof Systems, Pseudorandomness, and Computational Complexity (at large). 
Back to Oded Goldreich's homepage