This book is rooted in the thesis that complexity theory is extremely rich in conceptual
content, and that this contents should be explicitly communicated in expositions and courses …

Cryptography is concerned with the conceptualization, definition, and construction of
computing systems that address security concerns. The design of cryptographic systems …

We study the satisfiability of random Boolean expressions built from many clauses with K
variables per clause (K-satisfiability). Expressions with a ratio α of clauses to variables less …

This book is intended as a text for a course on cryptography with emphasis on algebraic
methods. It is written so as to be accessible to graduate or advanced undergraduate …

The structural theory of average-case complexity, introduced by Levin (1986), gives a formal
setting for discussing the types of inputs for which a problem is difficult. This is vital to …

We study the problem of satisfiability of randomly chosen clauses, each with K Boolean
variables. Using the cavity method at zero temperature, we find the phase diagram for the K …

We introduce and investigate a new model of learning probability distributions from
independent draws. Our model is inspired by the popular Probably Approximately Correct …

The satis ability (SAT) problem is a core problem in mathematical logic and computing
theory. In practice, SAT is fundamental in solving many problems in automated reasoning …

In several cryptographic systems, a fixed element g of a group (generally Z/q Z) is repeatedly
raised to many different powers. In this paper we present a practical method of speeding up …

Finding sets of hard instances of propositional satis ability is of interest for understanding the
complexity of SAT, and for experimentally evaluating SAT algorithms. In discussing this we …