We present a new boolean function for which any Ordered Binary Decision Diagram (OBDD) computing it has an exponential number of nodes. This boolean function is obtained from Nisan's pseudorandom generator to derandomize space bounded randomized algorithms. Though the relation between hardness and randomness for computational models is well known, ... more >>>

Cryan and Miltersen recently considered the question of whether there can be a pseudorandom generator in NC0, that is, a pseudorandom generator such that every bit of the output depends on a constant number k of bits of the seed. They show that for k=3 there is always a distinguisher; ... more >>>

Cryan and Miltersen recently considered the question of whether there can be a pseudorandom generator in NC0, that is, a pseudorandom generator such that every bit of the output depends on a constant number k of bits of the seed. They show that for k=3 there is always a distinguisher; ... more >>>

The language compression problem asks for succinct descriptions of the strings in a language A such that the strings can be efficiently recovered from their description when given a membership oracle for A. We study randomized and nondeterministic decompression schemes and investigate how close we can get to the information ... more >>>

We study several properties of sets that are complete for NP. We prove that if $L$ is an NP-complete set and $S \not\supseteq L$ is a p-selective sparse set, then $L - S$ is many-one-hard for NP. We demonstrate existence of a sparse set $S \in \mathrm{DTIME}(2^{2^{n}})$ such that for ... more >>>

We show new lower bounds and impossibility results for general (possibly non-black-box) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions:

1. There does not exist a two-round zero-knowledge proof system with perfect completeness for an NP-complete language. The previous impossibility result for two-round zero ... more >>>

We study the compression of polynomially samplable sources. In particular, we give efficient prefix-free compression and decompression algorithms for three classes of such sources (whose support is a subset of {0,1}^n). 1. We show how to compress sources X samplable by logspace machines to expected length H(X)+O(1). Our next results ... more >>>

We introduce a "derandomized" analogue of graph squaring. This operation increases the connectivity of the graph (as measured by the second eigenvalue) almost as well as squaring the graph does, yet only increases the degree of the graph by a constant factor, instead of squaring the degree. One application of ... more >>>

We give two applications of Nisan--Wigderson-type ("non-cryptographic") pseudorandom generators in cryptography. Specifically, assuming the existence of an appropriate NW-type generator, we construct: A one-message witness-indistinguishable proof system for every language in NP, based on any trapdoor permutation. This proof system does not assume a shared random string or any setup ... more >>>

We consider two of the most fundamental theorems in Cryptography. The first, due to Haastad et. al. [HILL99], is that pseudorandom generators can be constructed from any one-way function. The second due to Yao [Yao82] states that the existence of weak one-way functions (i.e. functions on which every efficient algorithm ... more >>>

We consider a general approach to the hoary problem of (im)proving circuit lower bounds. We define notions of hardness condensing and hardness extraction, in analogy to the corresponding notions from the computational theory of randomness. A hardness condenser is a procedure that takes in a Boolean function as input, as ... more >>>

We give an explicit construction of pseudorandom generators against low degree polynomials over finite fields. We show that the sum of $2^d$ small-biased generators with error $\epsilon^{2^{O(d)}}$ is a pseudorandom generator against degree $d$ polynomials with error $\epsilon$. This gives a generator with seed length $2^{O(d)} \log{(n/\epsilon)}$. Our construction follows ... more >>>

We consider (uniform) reductions from computing a function f to the task of distinguishing the output of some pseudorandom generator G from uniform. Impagliazzo and Wigderson (FOCS `98, JCSS `01) and Trevisan and Vadhan (CCC `02, CC `07) exhibited such reductions for every function f in PSPACE. Moreover, their reductions ... more >>>

Let $X$ be randomly chosen from $\{-1,1\}^n$, and let $Y$ be randomly chosen from the standard spherical Gaussian on $\R^n$. For any (possibly unbounded) polytope $P$ formed by the intersection of $k$ halfspaces, we prove that $$\left|\Pr\left[X \in P\right] - \Pr\left[Y \in P\right]\right| \leq \log^{8/5}k \cdot \Delta,$$ where $\Delta$ is ... more >>>