View article

We trace three major directions of research in complexity theory to their origins in the foundations of cryptography. Specifically, we refer to the theory of pseudorandomness (including the various incarnations of this concept), to the study of various forms of probabilistic proof system (including interactive proofs, zero-knowledge proofs, and probabilistically checkable proofs), and to the finer study of reductions (including random self-reducibility, worst-case to average-case reductions, averagecase preserving reductions, and black-box reductions).