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 number of ... 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 by the term ... 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 the proximity parameter, ... 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 a fixed ... 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 in ... 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 type presented below. ... 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 construct is ... 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 ``unique solutions'', the ... 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 of the object. ... 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 a single-bit ... 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 number ... 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 immediate ... 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, one can easily ... 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 ERH), we present a ... 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 the minimum vertex cover in ... 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 time-driven operations ... 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 obfuscator O is an (efficient, probabilistic) "compiler" that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is "unintelligible" in some sense. Obfuscators, if they exist, would have a wide variety of cryptographic and complexity-theoretic ... 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 {\em ... 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 specifically, these theorems relate ... 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 is to ... 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 of the observer ... 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 achieving the ... 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 much stronger conclusion ... 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 the prover to ... 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 preserve security ... 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$ space algorithm that ... 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 results ... 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'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. more >>>

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 consider (randomized) algorithms ... 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 two results ... 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, we give an interactive ... 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 can ... 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 with probability ... 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 security parameter). In ... 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 of small circuits. ... 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 is ... 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 public-key encryption algorithms and digital signatures such as RSA ... 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 this problem ... 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 and Safra and ... 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. more >>>

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

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 exponential in ... 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 second ... more >>>

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

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 of ... 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, most notably ... more >>>