Ever since the fundamental work of Cook from 1971, satisfiability has been recognized as a central problem in computational complexity. It is widely believed to be intractable, and yet till recently even a linear-time, logarithmic-space algorithm for satisfiability was not ruled out. In 1997 Fortnow, building on earlier work by ... more >>>

For Boolean functions that are $\epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted $\textsc{rej}(\epsilon)$) of the linearity test suggested by Blum, Luby and Rubinfeld. The interest in this problem is partly due to its relation to PCP constructions and hardness of ... more >>>

We describe a public-key cryptosystem with worst-case/average case
equivalence. The cryptosystem has an amortized plaintext to
ciphertext expansion of $O(n)$, relies on the hardness of the
$\tilde O(n^2)$-unique shortest vector problem for lattices, and
requires a public key of size at most $O(n^4)$ bits. The new
cryptosystem generalizes a conceptually ... more >>>