Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > RANDOMNESS:
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
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

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

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

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

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