This volume commemorates Shimon Even, one of founding fathers of Computer Science in Israel, who passed away on May 1, 2004. The volume contains research contributions, surveys and educational essays in theoretical computer science, written by former students and close collaborators of Shimon. In accordance with Shimon's style and principles, the essays address natural computational problems and are intended to be accessible to most researchers in theoretical computer science.
Property Testing is the study of super-fast (randomized) algorithms for approximate decision making. These algorithms are given direct access to items of a huge data set, and determine whether this data set has some predetermined (global) property or is far from having this property. Remarkably, this approximate decision is made by accessing a small portion of the data set. This volume provides a collection of extended abstracts and surveys that reflect the program of a mini-workshop on Property Testing, which took place as part of the 1st ITCS (in Jan 2010).
Cryptography is concerned with the construction of schemes that withstand any abuse: A cryptographic scheme is constructed so as to maintain a desired functionality, even under malicious attempts aimed at making it deviate from its prescribed behavior. The design of cryptographic systems must be based on firm foundations, which were developed mostly in the 1980's, in works that are all co-authored by Shafi Goldwasser and/or Silvio Micali. The current book celebrates these works, which were the basis for bestowing the 2012 Turing Award upon Shafi Goldwasser and Silvio Micali. These works have transformed Cryptography from an engineering discipline, lacking sound theoretical foundations, into a scientific field possessing a well-founded theory, which influences practice as well as contributes to other areas of Theoretical Computer Science. A significant portion of this book reproduces some of these works, and another portion consists of scientific perspectives by some of their former students. The highlight of the book is provided by a few texts that allow for the readers to meet Shafi and Silvio in person. These include their biographies, interviews with them, and their Turing Award lectures.
Also edited the Proceedings of the 2nd Israel Symposium on the Theory of Computing and Systems (ISTCS), 1993.
Also edited a volume of collected works, titled Studies in Complexity and Cryptography, appear as LNCS 6650, 2011.
Back to Oded Goldreich's homepage