We present three explicit constructions of hash functions, which exhibit a trade-off between the size of the family (and hence the number of random bits needed to generate a member of the family), and the quality (or error parameter) of the pseudo-random property it achieves. Unlike previous constructions, most notably ... more >>>

We study the computational complexity of languages which have interactive proofs of logarithmic knowledge complexity. We show that all such languages can be recognized in ${\cal BPP}^{\cal NP}$. Prior to this work, for languages with greater-than-zero knowledge complexity (and specifically, even for knowledge complexity 1) only trivial computational complexity bounds ... more >>>

This paper continues the investigation of the connection between proof systems and approximation. The emphasis is on proving ``tight'' non-approximability results via consideration of measures like the ``free bit complexity'' and the ``amortized free bit complexity'' of proof systems. The first part of the paper presents a collection of new ... more >>>

Tiwari (1987) considered the following scenario: k+1 processors P_0,...,P_k, connected by k links to form a linear array, compute a function f(x,y), for inputs (x,y) from a finite domain X x Y, where x is only known to P_0 and y is only known to P_k; the intermediate processors P_1,...,P_{k-1} ... more >>>

Randomized branching programs are a probabilistic model of computation defined in analogy to the well-known probabilistic Turing machines. In this paper, we present complexity theoretic results for randomized read-once branching programs. Our main result shows that nondeterminism can be more powerful than randomness for read-once branching programs. We present a ... more >>>

Impagliazzo and Wigderson have recently shown that if there exists a decision problem solvable in time $2^{O(n)}$ and having circuit complexity $2^{\Omega(n)}$ (for all but finitely many $n$) then $\p=\bpp$. This result is a culmination of a series of works showing connections between the existence of hard predicates and the ... more >>>

This paper deals with the number of monochromatic combinatorial rectangles required to approximate a Boolean function on a constant fraction of all inputs, where each rectangle may be defined with respect to its own partition of the input variables. The main result of the paper is that the number of ... more >>>

Most known constructions of probabilistically checkable proofs (PCPs) either blow up the proof size by a large polynomial, or have a high (though constant) query complexity. In this paper we give a transformation with slightly-super-cubic blowup in proof size, with a low query complexity. Specifically, the verifier probes the proof ... more >>>

We show that for determinictic polynomial time computation, oracle access to $\mathbf{APP}$, the class of real functions approximable by probabilistic Turing machines, is the same as having oracle access to promise-$\mathbf{BPP}$. First we construct a mapping that maps every function in $\mathbf{APP}$ to a promise problem in $\mathbf{prBPP}$, and that ... more >>>

We construct a nondeterministic analogue to \textbf{APP}, denoted \textbf{NAPP}; which is the set of all real valued functions $f: \{ 0,1 \}^{*} \rightarrow [0,1]$, that are approximable within 1/$k$, by a probabilistic nondeterministic transducer, in time poly($n,1^{k}$). We show that the subset of all Boolean functions in $\mbf{NAPP}$ is exactly ... more >>>

We use Lutz's resource bounded measure theory to prove that either \tbf{RP} is small or \tbf{ZPP} is hard. More precisely we prove that if \tbf{RP} has not p-measure zero, then \tbf{EXP} is contained in $\mbf{ZPP}/n$. We also show that if \tbf{RP} has not p-measure zero, \tbf{EXP} equals \tbf{ZPP} on infinitely ... more >>>

We introduce a new measure notion on small complexity classes (called F-measure), based on martingale families, that get rid of some drawbacks of previous measure notions: martingale families can make money on all strings, and yield random sequences with an equal frequency of 0's and 1's. As applications to F-measure, ... more >>>

Mergers are functions that transform k (possibly dependent) random sources into a single random source, in a way that ensures that if one of the input sources has min-entropy rate $\delta$ then the output has min-entropy rate close to $\delta$. Mergers have proven to be a very useful tool in ... more >>>

Inspired by Feige ({\em 36th STOC}, 2004), we initiate a study of sublinear randomized algorithms for approximating average parameters of a graph. Specifically, we consider the average degree of a graph and the average distance between pairs of vertices in a graph. Since our focus is on sublinear algorithms, these ... more >>>