Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Salil Vadhan:

TR17-084 | 2nd May 2017
Iftach Haitner, Salil Vadhan

The Many Entropies in One-Way Functions

Computational analogues of information-theoretic notions have given rise to some of the most interesting phenomena in the theory of computation. For example, computational indistinguishability, Goldwasser and Micali '84, which is the computational analogue of statistical distance, enabled the bypassing of Shanon's impossibility results on perfectly secure encryption, and provided the ... more >>>

TR13-114 | 24th August 2013
Parikshit Gopalan, Salil Vadhan, Yuan Zhou

Locally Testable Codes and Cayley Graphs

Revisions: 1

We give two new characterizations of ($\F_2$-linear) locally testable error-correcting codes in terms of Cayley graphs over $\F_2^h$:

\item A locally testable code is equivalent to a Cayley graph over $\F_2^h$ whose set of generators is significantly larger than $h$ and has no short linear dependencies, but yields a ... more >>>

TR13-101 | 12th July 2013
Colin Jia Zheng, Salil Vadhan

A Uniform Min-Max Theorem with Applications in Cryptography

Revisions: 2

We present a new, more constructive proof of von Neumann's Min-Max Theorem for two-player zero-sum game --- specifically, an algorithm that builds a near-optimal mixed strategy for the second player from several best-responses of the second player to mixed strategies of the first player. The algorithm extends previous work of ... more >>>

TR13-086 | 13th June 2013
Omer Reingold, Thomas Steinke, Salil Vadhan

Pseudorandomness for Regular Branching Programs via Fourier Analysis

Revisions: 1

We present an explicit pseudorandom generator for oblivious, read-once, permutation branching programs of constant width that can read their input bits in any order. The seed length is $O(\log^2 n)$, where $n$ is the length of the branching program. The previous best seed length known for this model was $n^{1/2+o(1)}$, ... more >>>

TR12-123 | 28th September 2012
Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan

Better pseudorandom generators from milder pseudorandom restrictions

We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pseudorandom generators for combinatorial rectangles and read-once CNFs and a hitting set generator for width-3 branching programs, all of which achieve near optimal seed-length even in ... more >>>

TR11-141 | 2nd November 2011
Salil Vadhan, Colin Jia Zheng

Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions

Revisions: 3

We provide a characterization of pseudoentropy in terms of hardness of sampling: Let $(X,B)$ be jointly distributed random variables such that $B$ takes values in a polynomial-sized set. We show that $B$ is computationally indistinguishable from a random variable of higher Shannon entropy given $X$ if and only if there ... more >>>

TR11-106 | 6th August 2011
Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil Vadhan

The Limits of Two-Party Differential Privacy

We study differential privacy in a distributed setting where two parties would like to perform analysis of their joint data while preserving privacy for both datasets. Our results imply almost tight lower bounds on the accuracy of such data analyses, both for specific natural functions (such as Hamming distance) and ... more >>>

TR11-004 | 10th January 2011
Oded Goldreich, Salil Vadhan

On the complexity of computational problems regarding distributions (a survey)

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

TR10-160 | 28th October 2010
Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan

On Approximating the Entropy of Polynomial Mappings

We investigate the complexity of the following computational problem:

Polynomial Entropy Approximation (PEA):
Given a low-degree polynomial mapping
$p : F^n\rightarrow F^m$, where $F$ is a finite field, approximate the output entropy
$H(p(U_n))$, where $U_n$ is the uniform distribution on $F^n$ and $H$ may be any of several entropy measures.

... more >>>

TR10-089 | 26th May 2010
Iftach Haitner, Omer Reingold, Salil Vadhan

Efficiency Improvements in Constructing Pseudorandom Generators from One-way Functions

We give a new construction of pseudorandom generators from any one-way function. The construction achieves better parameters and is simpler than that given in the seminal work of Haastad, Impagliazzo, Levin and Luby [SICOMP '99]. The key to our construction is a new notion of next-block pseudoentropy, which is inspired ... more >>>

TR10-017 | 10th February 2010
Jonathan Ullman, Salil Vadhan

PCPs and the Hardness of Generating Synthetic Data

Revisions: 4

Assuming the existence of one-way functions, we show that there is no
polynomial-time, differentially private algorithm $A$ that takes a database
$D\in (\{0,1\}^d)^n$ and outputs a ``synthetic database'' $\hat{D}$ all of whose two-way
marginals are approximately equal to those of $D$. (A two-way marginal is the fraction
of database rows ... more >>>

TR09-089 | 26th September 2009
Guy Rothblum, Salil Vadhan

Are PCPs Inherent in Efficient Arguments?

Starting with Kilian (STOC `92), several works have shown how to use probabilistically checkable proofs (PCPs) and cryptographic primitives such as collision-resistant hashing to construct very efficient argument systems (a.k.a. computationally sound proofs), for example with polylogarithmic communication complexity. Ishai et al. (CCC `07) raised the question of whether PCPs ... more >>>

TR09-045 | 20th May 2009
Iftach Haitner, Omer Reingold, Salil Vadhan, Hoeteck Wee

Inaccessible Entropy

We put forth a new computational notion of entropy, which measures the
(in)feasibility of sampling high entropy strings that are consistent
with a given protocol. Specifically, we say that the i'th round of a
protocol (A, B) has _accessible entropy_ at most k, if no
polynomial-time strategy A^* can generate ... more >>>

TR08-103 | 22nd November 2008
Luca Trevisan, Madhur Tulsiani, Salil Vadhan

Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution

We show that every high-entropy distribution is indistinguishable from an
efficiently samplable distribution of the same entropy. Specifically, we prove
that if $D$ is a distribution over $\{ 0,1\}^n$ of min-entropy at least $n-k$,
then for every $S$ and $\epsilon$ there is a circuit $C$ of size at most
$S\cdot ... more >>>

TR08-045 | 23rd April 2008
Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil Vadhan

Dense Subsets of Pseudorandom Sets

A theorem of Green, Tao, and Ziegler can be stated (roughly)
as follows: if R is a pseudorandom set, and D is a dense subset of R,
then D may
be modeled by a set M that is dense in the entire domain such that D and
more >>>

TR08-007 | 6th February 2008
Dan Gutfreund, Salil Vadhan

Limitations of Hardness vs. Randomness under Uniform Reductions

We consider (uniform) reductions from computing a function f to the task of distinguishing the output of some pseudorandom generator G from uniform. Impagliazzo and Wigderson (FOCS `98, JCSS `01) and Trevisan and Vadhan (CCC `02, CC `07) exhibited such reductions for every function f in PSPACE. Moreover, their reductions ... more >>>

TR07-030 | 29th March 2007
Kai-Min Chung, Omer Reingold, Salil Vadhan

S-T Connectivity on Digraphs with a Known Stationary Distribution

We present a deterministic logspace algorithm for solving s-t connectivity on directed graphs if (i) we are given a stationary distribution for random walk on the graph and (ii) the random walk which starts at the source vertex $s$ has polynomial mixing time. This result generalizes the recent deterministic logspace ... more >>>

TR06-139 | 14th November 2006
Shien Jin Ong, Salil Vadhan

Zero Knowledge and Soundness are Symmetric

Revisions: 1

We give a complexity-theoretic characterization of the class of problems in NP having zero-knowledge argument systems that is symmetric in its treatment of the zero knowledge and the soundness conditions. From this, we deduce that the class of problems in NP intersect coNP having zero-knowledge arguments is closed under complement. ... more >>>

TR06-134 | 18th October 2006
Venkatesan Guruswami, Chris Umans, Salil Vadhan

Extractors and condensers from univariate polynomials

Revisions: 1

We give new constructions of randomness extractors and lossless condensers that are optimal to within constant factors in both the seed length and the output length. For extractors, this matches the parameters of the current best known construction [LRVW03]; for lossless condensers, the previous best constructions achieved optimality to within ... more >>>

TR06-075 | 19th June 2006
Minh-Huyen Nguyen, Shien Jin Ong, Salil Vadhan

Statistical Zero-Knowledge Arguments for NP from Any One-Way Function

We show that every language in NP has a *statistical* zero-knowledge
argument system under the (minimal) complexity assumption that
one-way functions exist. In such protocols, even a computationally
unbounded verifier cannot learn anything other than the fact that the
assertion being proven is true, whereas a polynomial-time prover
cannot convince ... more >>>

TR06-056 | 27th April 2006
Salil Vadhan

An Unconditional Study of Computational Zero Knowledge

We prove a number of general theorems about ZK, the class of problems possessing (computational) zero-knowledge proofs. Our results are unconditional, in contrast to most previous works on ZK, which rely on the assumption that one-way functions exist.

We establish several new characterizations of ZK, and use these characterizations to ... more >>>

TR06-026 | 27th February 2006
Ronen Gradwohl, Salil Vadhan, David Zuckerman

Random Selection with an Adversarial Majority

We consider the problem of random selection, where $p$ players follow a protocol to jointly select a random element of a universe of size $n$. However, some of the players may be adversarial and collude to force the output to lie in a small subset of the universe. We describe ... more >>>

TR05-114 | 9th October 2005
Boaz Barak, Shien Jin Ong, Salil Vadhan

Derandomization in Cryptography

We give two applications of Nisan--Wigderson-type ("non-cryptographic") pseudorandom generators in cryptography. Specifically, assuming the existence of an appropriate NW-type generator, we construct:

A one-message witness-indistinguishable proof system for every language in NP, based on any trapdoor permutation. This proof system does not assume a shared random string or any ... more >>>

TR05-110 | 3rd October 2005
Saurabh Sanghvi, Salil Vadhan

The Round Complexity of Two-Party Random Selection

We study the round complexity of two-party protocols for
generating a random $n$-bit string such that the output is
guaranteed to have bounded bias (according to some measure) even
if one of the two parties deviates from the protocol (even using
unlimited computational resources). Specifically, we require that
the output's ... more >>>

TR05-093 | 24th August 2005
Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan

Concurrent Zero Knowledge without Complexity Assumptions

We provide <i>unconditional</i> constructions of <i>concurrent</i>
statistical zero-knowledge proofs for a variety of non-trivial
problems (not known to have probabilistic polynomial-time
algorithms). The problems include Graph Isomorphism, Graph
Nonisomorphism, Quadratic Residuosity, Quadratic Nonresiduosity, a
restricted version of Statistical Difference, and approximate
versions of the (<b>coNP</b> forms of the) Shortest Vector ... more >>>

TR05-092 | 23rd August 2005
Eyal Rozenman, Salil Vadhan

Derandomized Squaring of Graphs

We introduce a "derandomized" analogue of graph squaring. This
operation increases the connectivity of the graph (as measured by the
second eigenvalue) almost as well as squaring the graph does, yet only
increases the degree of the graph by a constant factor, instead of
squaring the degree.

One application of ... more >>>

TR05-052 | 5th May 2005
Grant Schoenebeck, Salil Vadhan

The Computational Complexity of Nash Equilibria in Concisely Represented Games

Games may be represented in many different ways, and different representations of games affect the complexity of problems associated with games, such as finding a Nash equilibrium. The traditional method of representing a game is to explicitly list all the payoffs, but this incurs an exponential blowup as the number ... more >>>

TR05-022 | 19th February 2005
Omer Reingold, Luca Trevisan, Salil Vadhan

Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem

Motivated by Reingold's recent deterministic log-space algorithm for Undirected S-T Connectivity (ECCC TR 04-94), we revisit the general RL vs. L question, obtaining the following results.

1. We exhibit a new complete problem for RL: S-T Connectivity restricted to directed graphs for which the random walk is promised to have ... more >>>

TR05-012 | 17th January 2005
Luca Trevisan, Salil Vadhan, David Zuckerman

Compression of Samplable Sources

We study the compression of polynomially samplable sources. In particular, we give efficient prefix-free compression and decompression algorithms for three classes of such sources (whose support is a subset of {0,1}^n).

1. We show how to compress sources X samplable by logspace machines to expected length H(X)+O(1).

Our next ... more >>>

TR04-087 | 13th October 2004
Alexander Healy, Salil Vadhan, Emanuele Viola

Using Nondeterminism to Amplify Hardness

We revisit the problem of hardness amplification in $\NP$, as
recently studied by O'Donnell (STOC `02). We prove that if $\NP$
has a balanced function $f$ such that any circuit of size $s(n)$
fails to compute $f$ on a $1/\poly(n)$ fraction of inputs, then
$\NP$ has a function $f'$ such ... more >>>

TR04-083 | 8th September 2004
Boaz Barak, Yehuda Lindell, Salil Vadhan

Lower Bounds for Non-Black-Box Zero Knowledge

We show new lower bounds and impossibility results for general (possibly <i>non-black-box</i>) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions:
<li> There does not exist a two-round zero-knowledge <i>proof</i> system with perfect completeness for an NP-complete language. The previous impossibility result for two-round zero ... more >>>

TR04-021 | 23rd March 2004
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan

Robust PCPs of Proximity, Shorter PCPs and Applications to Coding

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

TR01-057 | 15th August 2001
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang

On the (Im)possibility of Obfuscating Programs

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

TR01-046 | 2nd July 2001
Oded Goldreich, Salil Vadhan, Avi Wigderson

On Interactive Proofs with a Laconic Prover

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

TR01-018 | 23rd February 2001
Omer Reingold, Salil Vadhan, Avi Wigderson

Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors

The main contribution of this work is a new type of graph product, which we call the zig-zag
product. Taking a product of a large graph with a small graph, the resulting graph inherits
(roughly) its size from the large one, its degree from the small one, and ... more >>>

TR00-084 | 6th November 2000
Salil Vadhan, Amit Sahai

A Complete Problem for Statistical Zero Knowledge

We present the first complete problem for SZK, the class of (promise)
problems possessing statistical zero-knowledge proofs (against an
honest verifier). The problem, called STATISTICAL DIFFERENCE, is to
decide whether two efficiently samplable distributions are either
statistically close or far apart. This gives a new characterization
of SZK that makes ... more >>>

TR00-004 | 14th January 2000
Oded Goldreich, Salil Vadhan, Avi Wigderson

Simplified derandomization of BPP using a hitting set generator.

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

TR99-046 | 17th November 1999
Ran Raz, Omer Reingold, Salil Vadhan

Extracting All the Randomness and Reducing the Error in Trevisan's Extractors

We give explicit constructions of extractors which work for a source of
any min-entropy on strings of length n. These extractors can extract any
constant fraction of the min-entropy using O(log^2 n) additional random
bits, and can extract all the min-entropy using O(log^3 n) additional
random bits. Both of these ... more >>>

TR99-013 | 28th May 1999
Oded Goldreich, Amit Sahai, Salil Vadhan

Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK

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

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

TR98-063 | 4th November 1998
Oded Goldreich, Salil Vadhan

Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK

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

TR98-047 | 21st August 1998
Salil Vadhan

Extracting All the Randomness from a Weakly Random Source

Revisions: 1 , Comments: 1

In this paper, we give explicit constructions of extractors which work for
a source of any min-entropy on strings of length $n$. The first
construction extracts any constant fraction of the min-entropy using
O(log^2 n) additional random bits. The second extracts all the
min-entropy using O(log^3 n) additional random ... more >>>

ISSN 1433-8092 | Imprint