Oded Goldreich, Avi Wigderson

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

Oded Goldreich, Rafail Ostrovsky, Erez Petrank

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

Mihir Bellare, Oded Goldreich, Madhu Sudan

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

Martin Dietzfelbinger

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

Martin Sauerhoff

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

Madhu Sudan, Luca Trevisan, Salil Vadhan

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

Martin Sauerhoff

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

Prahladh Harsha, Madhu Sudan

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

Philippe Moser

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

more >>>

Philippe Moser

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

Philippe Moser

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

Philippe Moser

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

Zeev Dvir, Amir Shpilka

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

Oded Goldreich, Dana Ron

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

Xin Li

We study the problem of constructing affine extractors over $\mathsf{GF(2)}$. Previously the only known construction that can handle sources with arbitrarily linear entropy is due to Bourgain (and a slight modification by Yehudayoff), which relies heavily on the technique of Van der Corput differencing and a careful choice of a ... more >>>

Xin Li

We study the problem of constructing extractors for independent weak random sources. The probabilistic method shows that there exists an extractor for two independent weak random sources on $n$ bits with only logarithmic min-entropy. However, previously the best known explicit two source extractor only achieves min-entropy $0.499n$ \cite{Bourgain05}, and the ... more >>>

Xin Li

We study the problem of constructing explicit extractors for independent general weak random sources. For weak sources on $n$ bits with min-entropy $k$, perviously the best known extractor needs to use at least $\frac{\log n}{\log k}$ independent sources \cite{Rao06, BarakRSW06}. In this paper we give a new extractor that only ... more >>>

Xin Li

We study the problem of constructing explicit extractors for independent general weak random sources. Given weak sources on $n$ bits, the probabilistic method shows that there exists a deterministic extractor for two independent sources with min-entropy as small as $\log n+O(1)$. However, even to extract from a constant number of ... more >>>

Jack H. Lutz, Neil Lutz

This paper proves that there is, in every direction in Euclidean space, a line that misses every computably random point. Our proof of this fact shows that a famous set constructed by Besicovitch in 1964 has computable measure 0.

more >>>Eshan Chattopadhyay, David Zuckerman

Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs \cite{DPW10} as an elegant generalization of the classical notions of error detection, where the corruption of a codeword is viewed as a tampering function acting on it. Informally, a non-malleable code with respect to a family of tampering functions $\mathcal{F}$ consists ... more >>>

Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan

The communication complexity of many fundamental problems reduces greatly

when the communicating parties share randomness that is independent of the

inputs to the communication task. Natural communication processes (say between

humans) however often involve large amounts of shared correlations among the

communicating players, but rarely allow for perfect sharing of ...
more >>>

Xin Li

We continue the study of constructing explicit extractors for independent

general weak random sources. The ultimate goal is to give a construction that matches what is given by the probabilistic method --- an extractor for two independent $n$-bit weak random sources with min-entropy as small as $\log n+O(1)$. Previously, the ...
more >>>

Badih Ghazi, Madhu Sudan

In a recent work (Ghazi et al., SODA 2016), the authors with Komargodski and Kothari initiated the study of communication with contextual uncertainty, a setup aiming to understand how efficient communication is possible when the communicating parties imperfectly share a huge context. In this setting, Alice is given a function ... more >>>

Jayadev Acharya, Clement Canonne, Yanjun Han, Ziteng Sun, Himanshu Tyagi

We study goodness-of-fit of discrete distributions in the distributed setting, where samples are divided between multiple users who can only release a limited amount of information about their samples due to various information constraints. Recently, a subset of the authors showed that having access to a common random seed (i.e., ... more >>>

Huacheng Yu, Wei Zhan

We prove the first polynomial separation between randomized and deterministic time-space tradeoffs of multi-output functions. In particular, we present a total function that on the input of $n$ elements in $[n]$, outputs $O(n)$ elements, such that:

- There exists a randomized oblivious algorithm with space $O(\log n)$, time $O(n\log n)$ ... more >>>