All reports by Author Salil Vadhan:

__
TR20-026
| 25th February 2020
__

Dean Doron, Jack Murtagh, Salil Vadhan, David Zuckerman#### Spectral Sparsification via Bounded-Independence Sampling

Revisions: 1

__
TR18-119
| 21st June 2018
__

YiHsiu Chen, Mika G\"o{\"o}s, Salil Vadhan, Jiapeng Zhang#### A Tight Lower Bound for Entropy Flattening

Revisions: 1

__
TR17-084
| 2nd May 2017
__

Iftach Haitner, Salil Vadhan#### The Many Entropies in One-Way Functions

Revisions: 1

__
TR13-114
| 24th August 2013
__

Parikshit Gopalan, Salil Vadhan, Yuan Zhou#### Locally Testable Codes and Cayley Graphs

Revisions: 1

__
TR13-101
| 12th July 2013
__

Colin Jia Zheng, Salil Vadhan#### A Uniform Min-Max Theorem with Applications in Cryptography

Revisions: 2

__
TR13-086
| 13th June 2013
__

Omer Reingold, Thomas Steinke, Salil Vadhan#### Pseudorandomness for Regular Branching Programs via Fourier Analysis

Revisions: 1

__
TR12-123
| 28th September 2012
__

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan#### Better pseudorandom generators from milder pseudorandom restrictions

__
TR11-141
| 2nd November 2011
__

Salil Vadhan, Colin Jia Zheng#### Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions

Revisions: 3

__
TR11-106
| 6th August 2011
__

Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil Vadhan#### The Limits of Two-Party Differential Privacy

__
TR11-004
| 10th January 2011
__

Oded Goldreich, Salil Vadhan#### On the complexity of computational problems regarding distributions (a survey)

Comments: 1

__
TR10-160
| 28th October 2010
__

Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan#### On Approximating the Entropy of Polynomial Mappings

__
TR10-089
| 26th May 2010
__

Iftach Haitner, Omer Reingold, Salil Vadhan#### Efficiency Improvements in Constructing Pseudorandom Generators from One-way Functions

__
TR10-017
| 10th February 2010
__

Jonathan Ullman, Salil Vadhan#### PCPs and the Hardness of Generating Synthetic Data

Revisions: 4

__
TR09-089
| 26th September 2009
__

Guy Rothblum, Salil Vadhan#### Are PCPs Inherent in Efficient Arguments?

__
TR09-045
| 20th May 2009
__

Iftach Haitner, Omer Reingold, Salil Vadhan, Hoeteck Wee#### Inaccessible Entropy

__
TR08-103
| 22nd November 2008
__

Luca Trevisan, Madhur Tulsiani, Salil Vadhan#### Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution

__
TR08-045
| 23rd April 2008
__

Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil Vadhan#### Dense Subsets of Pseudorandom Sets

__
TR08-007
| 6th February 2008
__

Dan Gutfreund, Salil Vadhan#### Limitations of Hardness vs. Randomness under Uniform Reductions

__
TR07-030
| 29th March 2007
__

Kai-Min Chung, Omer Reingold, Salil Vadhan#### S-T Connectivity on Digraphs with a Known Stationary Distribution

__
TR06-139
| 14th November 2006
__

Shien Jin Ong, Salil Vadhan#### Zero Knowledge and Soundness are Symmetric

Revisions: 1

__
TR06-134
| 18th October 2006
__

Venkatesan Guruswami, Chris Umans, Salil Vadhan#### Extractors and condensers from univariate polynomials

Revisions: 1

__
TR06-075
| 19th June 2006
__

Minh-Huyen Nguyen, Shien Jin Ong, Salil Vadhan#### Statistical Zero-Knowledge Arguments for NP from Any One-Way Function

__
TR06-056
| 27th April 2006
__

Salil Vadhan#### An Unconditional Study of Computational Zero Knowledge

__
TR06-026
| 27th February 2006
__

Ronen Gradwohl, Salil Vadhan, David Zuckerman#### Random Selection with an Adversarial Majority

__
TR05-114
| 9th October 2005
__

Boaz Barak, Shien Jin Ong, Salil Vadhan#### Derandomization in Cryptography

__
TR05-110
| 3rd October 2005
__

Saurabh Sanghvi, Salil Vadhan#### The Round Complexity of Two-Party Random Selection

__
TR05-093
| 24th August 2005
__

Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan#### Concurrent Zero Knowledge without Complexity Assumptions

__
TR05-092
| 23rd August 2005
__

Eyal Rozenman, Salil Vadhan#### Derandomized Squaring of Graphs

__
TR05-052
| 5th May 2005
__

Grant Schoenebeck, Salil Vadhan#### The Computational Complexity of Nash Equilibria in Concisely Represented Games

__
TR05-022
| 19th February 2005
__

Omer Reingold, Luca Trevisan, Salil Vadhan#### Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem

__
TR05-012
| 17th January 2005
__

Luca Trevisan, Salil Vadhan, David Zuckerman#### Compression of Samplable Sources

__
TR04-087
| 13th October 2004
__

Alexander Healy, Salil Vadhan, Emanuele Viola#### Using Nondeterminism to Amplify Hardness

__
TR04-083
| 8th September 2004
__

Boaz Barak, Yehuda Lindell, Salil Vadhan#### Lower Bounds for Non-Black-Box Zero Knowledge

__
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

__
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

__
TR01-046
| 2nd July 2001
__

Oded Goldreich, Salil Vadhan, Avi Wigderson#### On Interactive Proofs with a Laconic Prover

__
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

__
TR00-084
| 6th November 2000
__

Salil Vadhan, Amit Sahai#### A Complete Problem for Statistical Zero Knowledge

__
TR00-004
| 14th January 2000
__

Oded Goldreich, Salil Vadhan, Avi Wigderson#### Simplified derandomization of BPP using a hitting set generator.

__
TR99-046
| 17th November 1999
__

Ran Raz, Omer Reingold, Salil Vadhan#### Extracting All the Randomness and Reducing the Error in Trevisan's Extractors

__
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

__
TR98-074
| 16th December 1998
__

Madhu Sudan, Luca Trevisan, Salil Vadhan#### Pseudorandom generators without the XOR Lemma

Revisions: 2

__
TR98-063
| 4th November 1998
__

Oded Goldreich, Salil Vadhan#### Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK

__
TR98-047
| 21st August 1998
__

Salil Vadhan#### Extracting All the Randomness from a Weakly Random Source

Revisions: 1
,
Comments: 1

Dean Doron, Jack Murtagh, Salil Vadhan, David Zuckerman

We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph $G$ on $n$ vertices described by a binary string of length $N$, an integer $k\leq \log n$ and an error parameter $\varepsilon > 0$, our algorithm runs in space $\tilde{O}(k\log (N\cdot ... more >>>

YiHsiu Chen, Mika G\"o{\"o}s, Salil Vadhan, Jiapeng Zhang

We study \emph{entropy flattening}: Given a circuit $\mathcal{C}_X$ implicitly describing an $n$-bit source $X$ (namely, $X$ is the output of $\mathcal{C}_X$ on a uniform random input), construct another circuit $\mathcal{C}_Y$ describing a source $Y$ such that (1) source $Y$ is nearly \emph{flat} (uniform on its support), and (2) the Shannon ... more >>>

Iftach Haitner, Salil Vadhan

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

Parikshit Gopalan, Salil Vadhan, Yuan Zhou

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

\begin{enumerate}

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

Colin Jia Zheng, Salil Vadhan

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

Omer Reingold, Thomas Steinke, Salil Vadhan

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

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan

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

Salil Vadhan, Colin Jia Zheng

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

Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil Vadhan

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

Oded Goldreich, Salil Vadhan

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

Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan

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.

Iftach Haitner, Omer Reingold, Salil Vadhan

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

Jonathan Ullman, Salil Vadhan

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

Guy Rothblum, Salil Vadhan

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

Iftach Haitner, Omer Reingold, Salil Vadhan, Hoeteck Wee

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

Luca Trevisan, Madhur Tulsiani, Salil Vadhan

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

Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil Vadhan

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

Dan Gutfreund, Salil Vadhan

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

Kai-Min Chung, Omer Reingold, Salil Vadhan

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

Shien Jin Ong, Salil Vadhan

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

Venkatesan Guruswami, Chris Umans, Salil Vadhan

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

Minh-Huyen Nguyen, Shien Jin Ong, Salil Vadhan

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

Salil Vadhan

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

Ronen Gradwohl, Salil Vadhan, David Zuckerman

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

Boaz Barak, Shien Jin Ong, Salil Vadhan

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

Saurabh Sanghvi, Salil Vadhan

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

Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan

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

Eyal Rozenman, Salil Vadhan

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

Grant Schoenebeck, Salil Vadhan

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

Omer Reingold, Luca Trevisan, Salil Vadhan

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

Luca Trevisan, Salil Vadhan, David Zuckerman

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

Alexander Healy, Salil Vadhan, Emanuele Viola

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

Boaz Barak, Yehuda Lindell, Salil Vadhan

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:

<ol>

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

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan

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

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang

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

Oded Goldreich, Salil Vadhan, Avi Wigderson

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

Omer Reingold, Salil Vadhan, Avi Wigderson

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

Salil Vadhan, Amit Sahai

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

Oded Goldreich, Salil Vadhan, Avi Wigderson

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

Ran Raz, Omer Reingold, Salil Vadhan

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

Oded Goldreich, Amit Sahai, Salil Vadhan

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

Madhu Sudan, Luca Trevisan, Salil Vadhan

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

Oded Goldreich, Salil Vadhan

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

Salil Vadhan

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