Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Randomness:
TR94-002 | 12th December 1994
Oded Goldreich, Avi Wigderson

Tiny Families of Functions with Random Properties: A Quality--Size Trade--off for Hashing

Revisions: 2

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

TR94-007 | 12th December 1994
Oded Goldreich, Rafail Ostrovsky, Erez Petrank

Computational Complexity and Knowledge Complexity

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

TR95-024 | 23rd May 1995
Mihir Bellare, Oded Goldreich, Madhu Sudan

Free bits, PCP and Non-Approximability - Towards tight results

Revisions: 4

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

TR96-063 | 6th November 1996
Martin Dietzfelbinger

The Linear-Array Problem in Communication Complexity Resolved

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

TR97-030 | 25th August 1997
Martin Sauerhoff

On Nondeterminism versus Randomness for Read-Once Branching Programs

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

TR98-074 | 16th December 1998
Madhu Sudan, Luca Trevisan, Salil Vadhan

Pseudorandom generators without the XOR Lemma

Revisions: 2

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

TR00-058 | 1st August 2000
Martin Sauerhoff

Approximation of Boolean Functions by Combinatorial Rectangles

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

TR00-061 | 14th August 2000
Prahladh Harsha, Madhu Sudan

Small PCPs with low query complexity

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

TR01-068 | 19th September 2001
Philippe Moser

Relative to P, APP and promise-BPP are the same

Revisions: 1

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

TR02-006 | 8th November 2001
Philippe Moser

Random nondeterministic real functions and Arthur Merlin games

Revisions: 1

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

TR02-015 | 13th February 2002
Philippe Moser

ZPP is hard unless RP is small

Revisions: 1

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

TR05-045 | 12th April 2005
Philippe Moser

Martingale Families and Dimension in P

Revisions: 1

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

TR05-067 | 28th June 2005
Zeev Dvir, Amir Shpilka

An Improved Analysis of Mergers

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

TR05-073 | 14th July 2005
Oded Goldreich, Dana Ron

Approximating Average Parameters of Graphs.

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

TR10-064 | 13th April 2010
Xin Li

A New Approach to Affine Extractors and Dispersers

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

TR10-190 | 9th December 2010
Xin Li

Improved Constructions of Three Source Extractors

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

TR12-147 | 7th November 2012
Xin Li

New Independent Source Extractors with Exponential Improvement

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

TR13-025 | 6th February 2013
Xin Li

Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy

Revisions: 1

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

TR14-015 | 24th January 2014
Jack H. Lutz, Neil Lutz

Lines Missing Every Random Point

Revisions: 1

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

TR14-102 | 4th August 2014
Eshan Chattopadhyay, David Zuckerman

Non-Malleable Codes Against Constant Split-State Tampering

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

TR14-153 | 14th November 2014
Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan

Communication with Imperfectly Shared Randomness

Revisions: 2

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

TR15-034 | 8th March 2015
Xin Li

Three-Source Extractors for Polylogarithmic Min-Entropy

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

TR17-081 | 2nd May 2017
Badih Ghazi, Madhu Sudan

The Power of Shared Randomness in Uncertain Communication

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

TR19-098 | 20th July 2019
Jayadev Acharya, Clement Canonne, Yanjun Han, Ziteng Sun, Himanshu Tyagi

Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit

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

TR23-096 | 28th June 2023
Huacheng Yu, Wei Zhan

Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions

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

ISSN 1433-8092 | Imprint