(This is a revised version of work that was posted on arXiv in July 2010.)

We present sublinear-time (randomized) algorithms for finding simple cycles of length at least $k\geq3$ and tree-minors in bounded-degree graphs.
The complexity of these algorithms is related to the distance
of the graph from being ... more >>>

Loosely speaking, a proximity-oblivious (property) tester is a randomized algorithm that makes a constant number of queries to a tested object and distinguishes objects that have a predetermined property from those that lack it. Specifically, for some threshold probability $c$, objects having the property are accepted with probability at least ... more >>>

This note refers to the effect of the proximity parameter on the operation of (standard) property testers. Its bottom-line is that, except in pathological cases, the effect of the proximity parameter is restricted to determining the query complexity of the tester. The point is that, in non-pathological cases, the mapping ... more >>>

We take a closer look at several enhancements of the notion of trapdoor permutations. Specifically, we consider the notions of enhanced trapdoor permutation (Goldreich 2004) and doubly enhanced trapdoor permutation (Goldreich 2008) as well as intermediate notions (Rothblum 2010). These enhancements arose in the study of Oblivious Transfer and NIZK, ... more >>>

We study the computability of one-way functions and pseudorandom generators
by monotone circuits, showing a substantial gap between the two:
On one hand, there exist one-way functions that are computable
by (uniform) polynomial-size monotone functions, provided (of course)
that one-way functions exist at all.
On the other hand, ... more >>>

We revisit the notion of a {\em targeted canonical derandomizer},
introduced in our recent ECCC Report (TR10-135) as a uniform notion of
a pseudorandom generator that suffices for yielding BPP=P.
The original notion was derived (as a variant of the standard notion
of a canonical derandomizer) by providing both ... more >>>

We initiate a study of input-oblivious proof systems, and present a few preliminary results regarding such systems.
Our results offer a perspective on the intersection of the non-uniform complexity class P/poly with uniform complexity classes such as NP and IP.
In particular, we provide a uniform complexity formulation of the ... more >>>

We consider two basic computational problems
regarding discrete probability distributions:
(1) approximating the statistical difference (aka variation distance)
between two given distributions,
and (2) approximating the entropy of a given distribution.
Both problems are considered in two different settings.
In the first setting the approximation algorithm
more >>>

We show that proving results such as BPP=P essentially
necessitate the construction of suitable pseudorandom generators
(i.e., generators that suffice for such derandomization results).
In particular, the main incarnation of this equivalence
refers to the standard notion of uniform derandomization
and to the corresponding pseudorandom generators
(i.e., the standard uniform ... more >>>

The aim of this article is to introduce the reader to the study
of testing graph properties, while focusing on the main models
and issues involved. No attempt is made to provide a
comprehensive survey of this study, and specific results
are often mentioned merely as illustrations of general ... more >>>

We take another step in the study of the testability
of small-width OBDDs, initiated by Ron and Tsur (Random'09).
That is, we consider algorithms that,
given oracle access to a function $f:\{0,1\}^n\to\{0,1\}$,
need to determine whether $f$ can be implemented
by some restricted class of OBDDs or is far from
more >>>

We present a general notion of properties that
are characterized by local conditions that are invariant
under a sufficiently rich class of symmetries.
Our framework generalizes two popular models of
testing graph properties as well as the algebraic
invariances studied by Kaufman and Sudan (STOC'08).

We show that, in the ... more >>>

We put forward a general theory of goal-oriented communication, where communication is not an end in itself, but rather a means to achieving some goals of the communicating parties. The goals can vary from setting to setting, and we provide a general framework for describing any such goal. In this ... more >>>

We study methods of converting algorithms that distinguish pairs
of distributions with a gap that has an absolute value that is noticeable
into corresponding algorithms in which the gap is always positive.
Our focus is on designing algorithms that, in addition to the tested string,
obtain a fixed ... more >>>

We present a candidate counterexample to the
easy cylinders conjecture, which was recently suggested
by Manindra Agrawal and Osamu Watanabe (ECCC, TR09-019).
Loosely speaking, the conjecture asserts that any 1-1 function
in $P/poly$ can be decomposed into ``cylinders'' of sub-exponential
size that can each be inverted by some polynomial-size circuit.
more >>>

Referring to the query complexity of property testing,
we prove the existence of a rich hierarchy of corresponding
complexity classes. That is, for any relevant function $q$,
we prove the existence of properties that have testing
complexity Theta(q).
Such results are proven in three standard
domains often considered in property ... more >>>

We initiate a systematic study of a special type of property testers.
These testers consist of repeating a basic test
for a number of times that depends on the proximity parameters,
whereas the basic test is oblivious of the proximity parameter.
We refer to such basic tests ... more >>>

In this paper we consider two refined questions regarding
the query complexity of testing graph properties
in the adjacency matrix model.
The first question refers to the relation between adaptive
and non-adaptive testers, whereas the second question refers to
testability within complexity that
is inversely proportional to ... more >>>

Given two codes R,C, their tensor product $R \otimes C$ consists of all matrices whose rows are codewords of R and whose columns are codewords of C. The product $R \otimes C$ is said to be robust if for every matrix M that is far from $R \otimes C$ it ... more >>>

Motivated by a recent study of Zimand (22nd CCC, 2007),
we consider the average-case complexity of property testing
(focusing, for clarity, on testing properties of Boolean strings).
We make two observations:

1) In the context of average-case analysis with respect to
the uniform distribution (on all strings of ... more >>>

We initiate a general study of the randomness complexity of
property testing, aimed at reducing the randomness complexity of
testers without (significantly) increasing their query complexity.
One concrete motovation for this study is provided by the
observation that the product of the randomness and query complexity
of a tester determine ... more >>>

This note points out a gap between two natural formulations of
the concept of a proof of knowledge, and shows that in all
natural cases (e.g., NP-statements) this gap can be closed.
The aforementioned formulations differ by whether they refer to
(all possible) probabilistic or deterministic prover strategies.
Unlike ... more >>>

This paper concerns the possibility of developing a coherent
theory of security when feasibility is associated
with expected probabilistic polynomial-time (expected PPT).
The source of difficulty is that
the known definitions of expected PPT strategies
(i.e., expected PPT interactive machines)
do not support natural results of the ... more >>>

We highlight a common theme in four relatively recent works
that establish remarkable results by an iterative approach.
Starting from a trivial construct,
each of these works applies an ingeniously designed
sequence of iterations that yields the desired result,
which is highly non-trivial. Furthermore, in each iteration,
the ... 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 >>>

The notion of promise problems was introduced and initially studied
by Even, Selman and Yacobi
(Information and Control, Vol.~61, pages 159-173, 1984).
In this article we survey some of the applications that this
notion has found in the twenty years that elapsed.
These include the notion of ... more >>>

We survey known results regarding locally testable codes
and locally testable proofs (known as PCPs),
with emphasis on the length of these constructs.
Locally testability refers to approximately testing
large objects based on a very small number of probes,
each retrieving a single bit in the representation ... more >>>

Building on Barak's work (Random'02),
Fortnow and Santhanam (FOCS'04) proved a time hierarchy
for probabilistic machines with one bit of advice.
Their argument is based on an implicit translation technique,
which allow to translate separation results for short (say logarithmic)
advice (as shown by Barak) into separations for ... more >>>

We continue the study of the trade-off between the length of PCPs
and their query complexity, establishing the following main results
(which refer to proofs of satisfiability of circuits of size $n$):
We present PCPs of length $\exp(\tildeO(\log\log n)^2)\cdot n$
that can be verified by making $o(\log\log n)$ Boolean queries.
more >>>

Following Feige, we consider the problem of
estimating the average degree of a graph.
Using ``neighbor queries'' as well as ``degree queries'',
we show that the average degree can be approximated
arbitrarily well in sublinear time, unless the graph is extremely sparse
(e.g., unless the graph has a sublinear ... more >>>

We initiate a general study of pseudo-random implementations
of huge random objects, and apply it to a few areas
in which random objects occur naturally.
For example, a random object being considered may be
a random connected graph, a random bounded-degree graph,
or a random error-correcting code with good distance.
more >>>

We present upper bounds on the size of codes that are locally
testable by querying only two input symbols. For linear codes, we
show that any $2$-locally testable code with minimal distance
$\delta n$ over a finite field $F$ cannot have more than
$|F|^{3/\delta}$ codewords. This result holds even for ... more >>>

Zero-knowledge proofs are proofs that are both convincing and yet
yield nothing beyond the validity of the assertion being proven.
Since their introduction about twenty years ago,
zero-knowledge proofs have attracted a lot of attention
and have, in turn, contributed to the development of other
areas of cryptography and complexity ... more >>>

Locally testable codes are error-correcting codes that admit
very efficient codeword tests. Specifically, using a constant
number of (random) queries, non-codewords are rejected with
probability proportional to their distance from the code.

Locally testable codes are believed to be the combinatorial
core of PCPs. However, the relation is less ... more >>>

Assuming the inractability of factoring, we show that
the output of the exponentiation modulo a composite function
$f_{N,g}(x)=g^x\bmod N$ (where $N=P\cdot Q$) is pseudorandom,
even when its input is restricted to be half the size.
This result is equivalent to the simultaneous hardness of the upper
half of the bits ... more >>>

We say that a distribution over $\{0,1\}^n$
is almost $k$-wise independent
if its restriction to every $k$ coordinates results in a
distribution that is close to the uniform distribution.
A natural question regarding almost $k$-wise independent
distributions is how close they are to some $k$-wise
independent distribution. We show that ... more >>>

We consider the function ensembles emerging from the
construction of Goldreich, Goldwasser and Micali (GGM),
when applied to an arbitrary pseudoramdon generator.
We show that, in general, such functions
fail to yield correlation intractable ensembles.
Specifically, it may happen that, given a description of such a function,
more >>>

For every $\epsilon>0$,
we present a {\em deterministic}\/ log-space algorithm
that correctly decides undirected graph connectivity
on all but at most $2^{n^\epsilon}$ of the $n$-vertex graphs.
The same holds for every problem in Symmetric Log-space (i.e., $\SL$).

Making no assumptions (and in particular not assuming the ... more >>>

Using known results regarding PCP,
we present simple proofs of the inapproximability
of vertex cover for hypergraphs.
Specifically, we show that

(1) Approximating the size of the minimum vertex cover
in $O(1)$-regular hypergraphs to within a factor of~1.99999 is NP-hard.
(2) Approximating the size of ... more >>>

We put forward a new type of
computationally-sound proof systems, called universal-arguments,
which are related but different from both CS-proofs (as defined
by Micali) and arguments (as defined by Brassard, Chaum and
Crepeau). In particular, we adopt the instance-based
prover-efficiency paradigm of CS-proofs, but follow the
computational-soundness condition of argument ... more >>>

Following Dwork, Naor, and Sahai (30th STOC, 1998),
we consider concurrent execution of protocols in a
semi-synchronized network. Specifically, we assume that each party
holds a local clock such that a constant bound on the relative rates
of these clocks is a-priori known, and consider protocols that
employ ... more >>>

We prove that if a linear error correcting code
$\C:\{0,1\}^n\to\{0,1\}^m$ is such that a bit of the message can
be probabilistically reconstructed by looking at two entries of a
corrupted codeword, then $m = 2^{\Omega(n)}$. We also present
several extensions of this result.

We show a reduction from the complexity ... more >>>

Informally, an <i>obfuscator</i> <b>O</b> is an (efficient, probabilistic)
"compiler" that takes as input a program (or circuit) <b>P</b> and
produces a new program <b>O(P)</b> that has the same functionality as <b>P</b>
yet is "unintelligible" in some sense. Obfuscators, if they exist,
would have a wide variety of cryptographic ... more >>>

We continue the investigation of interactive proofs with bounded
communication, as initiated by Goldreich and Hastad (IPL 1998).
Let $L$ be a language that has an interactive proof in which the prover
sends few (say $b$) bits to the verifier.
We prove that the complement $\bar L$ has a ... more >>>

Property testing is a relaxation of decision problems
in which it is required to distinguish {\sc yes}-instances
(i.e., objects having a predetermined property) from instances
that are far from any {\sc yes}-instance.
We presents three theorems regarding testing graph
properties in the adjacency matrix representation.
more >>>

We suggest a candidate one-way function using combinatorial
constructs such as expander graphs. These graphs are used to
determine a sequence of small overlapping subsets of input bits,
to which a hard-wired random predicate is applied.
Thus, the function is extremely easy to evaluate:
all that is needed ... more >>>

In the theory of pseudorandomness, potential (uniform) observers
are modeled as probabilistic polynomial-time machines.
In fact many of the central results in
that theory are proven via probabilistic polynomial-time reductions.
In this paper we show that analogous deterministic reductions
are unlikely to hold. We conclude that randomness ... more >>>

We consider testing graph expansion in the bounded-degree graph model.
Specifically, we refer to algorithms for testing whether the graph
has a second eigenvalue bounded above by a given threshold
or is far from any graph with such (or related) property.

We present a natural algorithm aimed towards ... more >>>

A hitting-set generator is a deterministic
algorithm which generates a set of strings that intersects
every dense set recognizable by a small circuit.
A polynomial time hitting-set generator readily implies $RP=P$.
Andreev \etal\/ (ICALP'96, and JACM 1998)
showed that if polynomial-time hitting-set
generator in fact implies the ... more >>>

We introduce the notion of Resettable Zero-Knowledge (rZK),
a new security measure for cryptographic protocols
which strengthens the classical notion of zero-knowledge.
In essence, an rZK protocol is one that remains zero knowledge
even if an adeversary can interact with the prover many times, each
time resetting ... more >>>

We introduce the notion of Interleaved Zero-Knowledge (iZK),
a new security measure for cryptographic protocols which strengthens
the classical notion of zero-knowledge, in a way suitable for multiple
concurrent executions in an asynchronous environment like the internet.
We prove that iZK protocols are robust: they are ``parallelizable'',
and ... more >>>

We present improved algorithms for testing monotonicity of functions.
Namely, given the ability to query an unknown function $f$, where
$\Sigma$ and $\Xi$ are finite ordered sets, the test always accepts a
monotone $f$, and rejects $f$ with high probability if it is $\e$-far
from being monotone (i.e., every monotone ... more >>>

We extend the study of non-interactive statistical zero-knowledge
proofs. Our main focus is to compare the class NISZK of problems
possessing such non-interactive proofs to the class SZK of problems
possessing interactive statistical zero-knowledge proofs. Along these
lines, we first show that if statistical zero knowledge is non-trivial
then so ... more >>>

We show that given oracle access to a subroutine which
returns approximate closest vectors in a lattice, one may find in
polynomial-time approximate shortest vectors in a lattice.
The level of approximation is maintained; that is, for any function
$f$, the following holds:
Suppose that the subroutine, on input a ... more >>>

This paper initiates the study of deterministic amplification of space
bounded probabilistic algorithms. The straightforward implementations of
known amplification methods cannot be used for such algorithms, since they
consume too much space. We present a new implementation of the
Ajtai-Koml\'{o}s-Szemer\'{e}di method, that enables to amplify an $S$
more >>>

We consider the following (promise) problem, denoted ED (for Entropy
Difference): The input is a pairs of circuits, and YES instances (resp.,
NO instances) are such pairs in which the first (resp., second) circuit
generates a distribution with noticeably higher entropy.

On one hand we show that any language having ... more >>>

The Chinese Remainder Theorem states that a positive
integer m is uniquely specified by its remainder modulo
k relatively prime integers p_1,...,p_k, provided
m < \prod_{i=1}^k p_i. Thus the residues of m modulo
relatively prime integers p_1 < p_2 < ... < p_n
form a redundant representation of m if ... more >>>

This is a revised version of work which has appeared
in preliminary form in the 36th FOCS, 1995.

Given a function $f$ mapping $n$-variate inputs from a finite field
$F$ into $F$,
we consider the task of reconstructing a list of all $n$-variate
degree $d$ polynomials which agree with $f$
more >>>

A Uniform Generation procedure for $NP$ is an
algorithm which given any input in a fixed NP-language, outputs a uniformly
distributed NP-witness for membership of the input in the language.
We present a Uniform Generation procedure for $NP$ that runs in probabilistic
polynomial-time with an NP-oracle. This improves upon ... more >>>

We consider the existence of pairs of probability ensembles which
may be efficiently distinguished given $k$ samples
but cannot be efficiently distinguished given $k'<k$ samples.
It is well known that in any such pair of ensembles it cannot be that
both are efficiently computable
(and that such phenomena cannot ... more >>>

The input to the {\em Graph Clustering Problem}\/
consists of a sequence of integers $m_1,...,m_t$
and a sequence of $\sum_{i=1}^{t}m_i$ graphs.
The question is whether the equivalence classes,
under the graph isomorphism relation,
of the input graphs have sizes which match the input sequence of integers.
In this note we ... more >>>

In 1984, Leonid Levin has initiated a theory of average-case complexity.
We provide an exposition of the basic definitions suggested by Levin,
and discuss some of the considerations underlying these definitions.

We consider the question of determining whether
a given object has a predetermined property or is ``far'' from any
object having the property.
Specifically, objects are modeled by functions,
and distance between functions is measured as the fraction
of the domain on which the functions differ.
We ... more >>>

We provide another proof of the Sipser--Lautemann Theorem
by which $BPP\subseteq MA$ ($\subseteq PH$).
The current proof is based on strong
results regarding the amplification of $BPP$, due to Zuckerman.
Given these results, the current proof is even simpler than previous ones.
Furthermore, extending the proof leads to ... more >>>

We show simple constant-round interactive proof systems for
problems capturing the approximability, to within a factor of $\sqrt{n}$,
of optimization problems in integer lattices; specifically,
the closest vector problem (CVP), and the shortest vector problem (SVP).
These interactive proofs are for the ``coNP direction'';
that is, ... more >>>

In a variety of PAC learning models, a tradeoff between time and
information seems to exist: with unlimited time, a small amount of
information suffices, but with time restrictions, more information
sometimes seems to be required.
In addition, it has long been known that there are
concept classes that ... more >>>

We consider the problem of estimating the average of a huge set of values.
That is,
given oracle access to an arbitrary function $f:\{0,1\}^n\mapsto[0,1]$,
we need to estimate $2^{-n} \sum_{x\in\{0,1\}^n} f(x)$
upto an additive error of $\epsilon$.
We are allowed to employ a randomized algorithm which may err ... more >>>

Following Ajtai's lead, Ajtai and Dwork have recently introduced a
public-key encryption scheme which is secure under the assumption
that a certain computational problem on lattices is hard on the
worst-case. Their encryption method may cause decryption errors,
though with small probability (i.e., inversely proportional to the
more >>>

We present a simple proof to the existence of a probability ensemble
with tiny support which cannot be distinguished from the uniform ensemble
by any recursive computation.
Since the support is tiny (i.e, sub-polynomial),
this ensemble can be distinguish from the uniform ensemble
by a (non-uniform) family ... more >>>

In this paper, we consider the question of determining whether
a function $f$ has property $P$ or is $\e$-far from any
function with property $P$.
The property testing algorithm is given a sample of the value
of $f$ on instances drawn according to some distribution.
In some cases,
it ... more >>>

We present a new proposal for a trapdoor one-way function,
from which we derive public-key encryption and digital
signatures. The security of the new construction is based
on the conjectured computational difficulty of lattice-reduction
problems, providing a possible alternative to existing
more >>>

The Graph Clustering Problem is parameterized by a sequence
of positive integers, $m_1,...,m_t$.
The input is a sequence of $\sum_{i=1}^{t}m_i$ graphs,
and the question is whether the equivalence classes
under the graph isomorphism relation have sizes which match
the sequence of parameters.
In this note
we show that ... more >>>

The current proof of the PCP Theorem (i.e., NP=PCP(log,O(1)))
is very complicated.
One source of difficulty is the technically involved
analysis of low-degree tests.
Here, we refer to the difficulty of obtaining strong results
regarding low-degree tests; namely, results of the type obtained and
used by Arora ... more >>>

Recently Ajtai described a construction of one-way functions whose
security is equivalent to the difficulty of some well known approximation
problems in lattices. We show that essentially the same
construction can also be used to obtain collision-free hashing.

We consider the size of circuits which perfectly hash
an arbitrary subset $S\!\subset\!\bitset^n$ of cardinality $2^k$
into $\bitset^m$.
We observe that, in general, the size of such circuits is
exponential in $2k-m$,
and provide a matching upper bound.

We investigate the computational complexity of languages
which have interactive proof systems of bounded message complexity.
In particular, we show that
(1) If $L$ has an interactive proof in which the total
communication is bounded by $c(n)$ bits
then $L$ can be recognized a probabilitic machine
in time ... more >>>

We provide an exposition of three Lemmas which relate
general properties of distributions
with the exclusive-or of certain bit locations.

The first XOR-Lemma, commonly attributed to U.V. Vazirani,
relates the statistical distance of a distribution from uniform
to the maximum bias of the xor of certain bit positions.
The ... more >>>

We show how to construct length-preserving 1-1 one-way
functions based on popular intractability assumptions (e.g., RSA, DLP).
Such 1-1 functions should not
be confused with (infinite) families of (finite) one-way permutations.
What we want and obtain is a single (infinite) 1-1 one-way function.

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

Various types of probabilistic proof systems have played
a central role in the development of computer science in the last decade.
In this exposition, we concentrate on three such proof systems ---
interactive proofs, zero-knowledge proofs,
and probabilistic checkable proofs --- stressing the essential
role of randomness in each ... 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 >>>

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