Kamp, Jesse, Anup Rao, Salil Vadhan, and David Zuckerman. “
Deterministic extractors for smallspace sources.”
Journal of Computer and System Sciences 77, no. 1 (2011): 191220.
Publisher's VersionAbstract
Version History: Special issue to celebrate Richard Karp's Kyoto Prize. Extended abstract in STOC '06.
We give polynomialtime, deterministic randomness extractors for sources generated in small space, where we model space \(s\) sources on\(\{0,1\}^n\) as sources generated by width \(2^s\) branching programs. Specifically, there is a constant \(η > 0\) such that for any \(ζ > n^{−η}\), our algorithm extracts \(m = (δ − ζ)n\) bits that are exponentially close to uniform (in variation distance) from space \(s\) sources with minentropy \(δn\), where \(s = Ω(ζ^ 3n)\). Previously, nothing was known for \(δ \ll 1/2,\), even for space \(0\). Our results are obtained by a reduction to the class of totalentropy independent sources. This model generalizes both the wellstudied models of independent sources and symbolfixing sources. These sources consist of a set of \(r\) independent smaller sources over \(\{0, 1\}^\ell\), where the total minentropy over all the smaller sources is \(k\). We give deterministic extractors for such sources when \(k\) is as small as \(\mathrm{polylog}(r)\), for small enough \(\ell\).
JCSS2011.pdf STOC052006.pdf Chung, KaiMin, Omer Reingold, and Salil Vadhan. “
ST connectivity on digraphs with a known stationary distribution.” In
ACM Transactions on Algorithms. Vol. 7. 3rd ed. ACM, 2011.
Publisher's VersionAbstract
Version history: Preliminary versions in CCC '07 and on ECCC (TR07030).
We present a deterministic logspace algorithm for solving ST Connectivity on directed graphs if: (i) we are given a stationary distribution of the random walk on the graph in which both of the input vertices \(s\) and \(t\) have nonnegligible probability mass and (ii) the random walk which starts at the source vertex \(s\) has polynomial mixing time. This result generalizes the recent deterministic logspace algorithm for ST Connectivity on undirected graphs [Reingold, 2008]. It identifies knowledge of the stationary distribution as the gap between the ST Connectivity problems we know how to solve in logspace (L) and those that capture all of randomized logspace (RL).
ECCC2007.pdf ACM2011.pdf Ullman, Jon, and Salil Vadhan. “
PCPs and the hardness of generating synthetic data.” In
Yuval Ishai, editor, Proceedings of the 8th IACR Theory of Cryptography Conference (TCC ‘11), Lecture Notes on Computer Science, 5978:572587. SpringerVerlag, 2011.
Publisher's VersionAbstract
Version History: Full version posted as ECCC TR10017. Invited to J. Cryptology selected papers from TCC 2011.
Assuming the existence of oneway functions, we show that there is no polynomialtime, differentially private algorithm \(\mathcal{A}\) that takes a database \(D ∈ ({0, 1}^d)^n\) and outputs a “synthetic database” \(\hat{D}\) all of whose twoway marginals are approximately equal to those of \(D\). (A twoway marginal is the fraction of database rows \(x ∈ {0, 1}^d\) with a given pair of values in a given pair of columns.) This answers a question of Barak et al. (PODS ‘07), who gave an algorithm running in time \(\mathrm{poly} (n, 2^d)\).
Our proof combines a construction of hardtosanitize databases based on digital signatures (by Dwork et al., STOC ‘09) with encodings based on probabilistically checkable proofs.
We also present both negative and positive results for generating “relaxed” synthetic data, where the fraction of rows in \(D\) satisfying a predicate \(c\) are estimated by applying \(c\) to each row of \(\hat{D}\) and aggregating the results in some way.
TCC2011.pdf ECCC2014.pdf Dvir, Zeev, Dan Gutfreund, Guy Rothblum, and Salil Vadhan. “
On approximating the entropy of polynomial mappings.” In
Proceedings of the Second Symposium on Innovations in Computer Science (ICS 2011), 460475. Tsinghua University Press, 2011.
Publisher's VersionAbstract
Version History: Full version posted as ECCC TR1060.
We investigate the complexity of the following computational problem:
Polynomial Entropy Approximation (PEA): Given a lowdegree polynomial mapping \(p : \mathbb{F}^n → \mathbb{F}^m\), where F is a finite field, approximate the output entropy \(H(p(U_n))\), where \(U_n\) is the uniform distribution on \(\mathbb{F}^n\) and \(H\) may be any of several entropy measures.
We show:

Approximating the Shannon entropy of degree 3 polynomials \(p : \mathbb{F}_2^n \to \mathbb{F}^m_2\) over \(\mathbb{F}_2\) to within an additive constant (or even \(n^.9\)) is complete for \(\mathbf{SZKP_L}\), the class of problems having statistical zeroknowledge proofs where the honest verifier and its simulator are computable in logarithmic space. (\(\mathbf{SZKP_L}\)contains most of the natural problems known to be in the full class \(\mathbf{SZKP}\).)

For prime fields \(\mathbb{F} \neq \mathbb{F}_2\) and homogeneous quadratic polynomials \(p : \mathbb{F}^n \to \mathbb{F}^m\), there is a probabilistic polynomialtime algorithm that distinguishes the case that \(p(U_n)\)) has entropy smaller than k from the case that \(p(U_n))\) has minentropy (or even Renyi entropy) greater than \((2 + o(1))k\).

For degree d polynomials \(p : \mathbb{F}^n_2 \to \mathbb{F}^m_2\) , there is a polynomialtime algorithm that distinguishes the case that \(p(U_n)\) has maxentropy smaller than \(k\) (where the maxentropy of a random variable is the logarithm of its support size) from the case that \(p(U_n)\) has maxentropy at least \((1 + o(1)) \cdot k^d\) (for fixed \(d\) and large \(k\)).
ICS2011.pdf ECCC2010.pdf Mahmoody, Mohammad, Tal Moran, and Salil Vadhan. “
Timelock puzzles in the random oracle model.” In
P. Rogaway, editor, Advances in Cryptology—CRYPTO ‘11, Lecture Notes in Computer Science, 6841:3950. SpringerVerlag, 2011.
Publisher's VersionAbstract
A timelock puzzle is a mechanism for sending messages “to the future”. The sender publishes a puzzle whose solution is the message to be sent, thus hiding it until enough time has elapsed for the puzzle to be solved. For timelock puzzles to be useful, generating a puzzle should take less time than solving it. Since adversaries may have access to many more computers than honest solvers, massively parallel solvers should not be able to produce a solution much faster than serial ones.
To date, we know of only one mechanism that is believed to satisfy these properties: the one proposed by Rivest, Shamir and Wagner (1996), who originally introduced the notion of timelock puzzles. Their puzzle is based on the serial nature of exponentiation and the hardness of factoring, and is therefore vulnerable to advances in factoring techniques (as well as to quantum attacks).
In this work, we study the possibility of constructing timelock puzzles in the randomoracle model. Our main result is negative, ruling out timelock puzzles that require more parallel time to solve than the total work required to generate a puzzle. In particular, this should rule out blackbox constructions of such timelock puzzles from oneway permutations and collisionresistant hashfunctions. On the positive side, we construct a timelock puzzle with a linear gap in parallel time: a new puzzle can be generated with one round of \({n}\) parallel queries to the random oracle, but \({n}\) rounds of serial queries are required to solve it (even for massively parallel adversaries).
CRYPTO2011.pdf IACR2011.pdf