19 Ergebnisse.

Keine Beschreibung.

Keine Beschreibung.

This volume contains a collection of studies in the areas of complexity theory and property testing. The 21 pieces of scientific work included were conducted at different times, mostly during the last decade. Although most of these works have been cited in the literature, none of them was formally published before. Within complexity theory the topics include constant-depth Boolean circuits, explicit construction of expander graphs, interactive...

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, whereas ad hoc approaches and heuristics are a very dangerous way to go. These foundations were developed mostly in the 1980...

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, whereas ad hoc approaches and heuristics are a very dangerous way to go. These foundations were developed mostly in the 1980...

Surveys some of the known results regarding doubly-efficient interactive proof systems, which make the benefits of interactive proof system available for a wider range of applications.

Surveys the theory of pseudorandomness, starting with the general paradigm, and discussing various incarnations while emphasizing the case of general-purpose pseudorandom generators. The primer assumes basic familiarity with the notion of efficient algorithms and with elementary probability theory, but provides a basic introduction to all notions that are actually used.

Cryptography is one of the most active areas in current mathematics research and applications. This book focuses on cryptography along with two related areas: the study of probabilistic proof systems, and the theory of computational pseudorandomness. Following a common theme that explores the interplay between randomness and computation, the important notions in each field are covered, as well as novel ideas and insights.

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 car...

This volume commemorates Shimon Even, one of founding fathers of Computer Science in Israel, who passed away on May 1, 2004. This Festschrift contains research contributions, surveys and educational essays in theoretical computer science, written by former students and close collaborators of Shimon. The essays address natural computational problems and are accessible to most researchers in theoretical computer science.

Foundations of Cryptography surveys the main paradigms, approaches and techniques used to conceptualize, define and provide solutions to natural cryptographic problems. The author starts by presenting some of the central tools, that is, computational difficulty (in the form of one-way functions), pseudorandomness, and zero-knowledge proofs. Based on these tools, the emphasis is shifted to the treatment of basic applications such as encryption ...

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. This book presents a rigorous and systematic treatment of the foundational issues: defining cryptographic tasks and solving new cryptographic problems using existing tools. It focuses on the basic mathematical tools: computational difficulty...

A conceptual introduction to modern topics in complexity for advanced undergraduate and graduate students.

Starting from the basics of computability, this undergraduate introduction focuses on the P versus NP Question and the theory of NP-completeness.

A rigorous treatment of Encryption, Signatures, and General Cryptographic Protocols, emphasizing fundamental concepts.

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 ...

Cryptography is one of the most active areas in current mathematics research and applications. This book focuses on cryptography along with two related areas: the study of probabilistic proof systems, and the theory of computational pseudorandomness. Following a common theme that explores the interplay between randomness and computation, the important notions in each field are covered, as well as novel ideas and insights.

Starting from the basics of computability, this undergraduate introduction focuses on the P versus NP Question and the theory of NP-completeness.

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 state-of-the-art survey presents a collection of extended abstra...