Schoenebeck, Grant, and Salil Vadhan. “
The computational complexity of Nash equilibria in concisely represented games.”
ACM Transactions on Computation Theory 4, no. 2 (2012).
Publisher's VersionAbstract
Version History: Preliminary versions as ECCC TOR0552 (https://eccc.weizmann.ac.il/report/2005/052/; attached as ECCC2005.pdf) and in EC '06 (https://dl.acm.org/doi/10.1145/1134707.1134737; attached as EC2006.pdf).
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 of agents grows. We study two models of concisely represented games: circuit games, where the payoffs are computed by a given boolean circuit, and graph games, where each agent’s payoff is a function of only the strategies played by its neighbors in a given graph. For these two models, we study the complexity of four questions: determining if a given strategy is a Nash equilibrium, finding a Nash equilibrium, determining if there exists a pure Nash equilibrium, and determining if there exists a Nash equilibrium in which the payoffs to a player meet some given guarantees. In many cases, we obtain tight results, showing that the problems are complete for various complexity classes.
ACM2012.pdf EC2006.pdf ECCC2005.pdf Dodis, Yevgeniy, Thomas Ristenpart, and Salil Vadhan. “
Randomness condensers for efficiently samplable, seeddependent sources.” In
Ronald Cramer, editor, Proceedings of the 9th IACR Theory of Cryptography Conference (TCC ‘12), Lecture Notes on Computer Science, 7194:618635. SpringerVerlag, 2012.
Publisher's VersionAbstract
We initiate a study of randomness condensers for sources that are efficiently samplable but may depend on the seed of the condenser. That is, we seek functions \(\mathsf{Cond} : \{0,1\}^n \times \{0,1\}^d \to \{0,1\}^m\)such that if we choose a random seed \(S \gets \{0,1\}^d\), and a source \(X = \mathcal{A}(S)\) is generated by a randomized circuit \(\mathcal{A}\) of size \(t\) such that \(X\) has min entropy at least \(k\) given \(S\), then \(\mathsf{Cond}(X ; S)\) should have minentropy at least some \(k'\) given \(S\). The distinction from the standard notion of randomness condensers is that the source \(X\) may be correlated with the seed \(S\) (but is restricted to be efficiently samplable). Randomness extractors of this type (corresponding to the special case where \(k' = m\)) have been implicitly studied in the past (by Trevisan and Vadhan, FOCS ‘00).
We show that:

Unlike extractors, we can have randomness condensers for samplable, seeddependent sources whose computational complexity is smaller than the size \(t\) of the adversarial sampling algorithm \(\mathcal{A}\). Indeed, we show that sufficiently strong collisionresistant hash functions are seeddependent condensers that produce outputs with minentropy \(k' = m – \mathcal{O}(\log t)\), i.e. logarithmic entropy deficiency.

Randomness condensers suffice for key derivation in many cryptographic applications: when an adversary has negligible success probability (or negligible “squared advantage” [3]) for a uniformly random key, we can use instead a key generated by a condenser whose output has logarithmic entropy deficiency.

Randomness condensers for seeddependent samplable sources that are robust to side information generated by the sampling algorithm imply soundness of the FiatShamir Heuristic when applied to any constantround, publiccoin interactive proof system.
IACR2012.pdf Vadhan, Salil, and Colin Jia Zheng. “
Characterizing pseudoentropy and simplifying pseudorandom generator constructions.” In
Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC ‘12), 817836. ACM, 2012.
Publisher's VersionAbstract
Version History: Full version posted as ECCC TR11141.
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 polynomialsized set. We show that \(B\) is computationally indistinguishable from a random variable of higher Shannon entropy given \(X\) if and only if there is no probabilistic polynomialtime \(S\) such that \((X, S(X))\) has small KL divergence from \((X, B)\). This can be viewed as an analogue of the Impagliazzo Hard core Theorem (FOCS ‘95) for Shannon entropy (rather than minentropy).
Using this characterization, we show that if \(f\) is a oneway function, then \((f(U_n), U_n)\) has “nextbit pseudoentropy” at least \(n + \log n\), establishing a conjecture of Haitner, Reingold, and Vadhan (STOC ‘10). Plugging this into the construction of Haitner et al., this yields a simpler construction of pseudorandom generators from oneway functions. In particular, the construction only performs hashing once, and only needs the hash functions that are randomness extractors (e.g. universal hash functions) rather than needing them to support “local listdecoding” (as in the Goldreich–Levin hardcore predicate, STOC ‘89).
With an additional idea, we also show how to improve the seed length of the pseudorandom generator to \(\tilde{O}(n^3)\), compared to \(\tilde{O}(n^4)\) in the construction of Haitner et al.
STOC2012.pdf ECCC2013.pdf Thaler, Justin, Jonathan Ullman, and Salil Vadhan. “
Faster algorithms for privately releasing marginals.” In
Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer, editors, Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP ‘12), Lecture Notes on Computer Science, 7391:810821. SpringerVerlag, 2012.
Publisher's VersionAbstract
Version History: Full version posted as arXiv:1205.1758v2.
We study the problem of releasing kway marginals of a database \(D ∈ ({0,1}^d)^n\), while preserving differential privacy. The answer to a \(k\)way marginal query is the fraction of \(D\)’s records \(x \in \{0,1\}^d\) with a given value in each of a given set of up to \(k\) columns. Marginal queries enable a rich class of statistical analyses of a dataset, and designing efficient algorithms for privately releasing marginal queries has been identified as an important open problem in private data analysis (cf. Barak et. al., PODS ’07).
We give an algorithm that runs in time \(d^{O(\sqrt{K})}\) and releases a private summary capable of answering any \(k\)way marginal query with at most ±.01 error on every query as long as \(n \geq d^{O(\sqrt{K})}\). To our knowledge, ours is the first algorithm capable of privately releasing marginal queries with nontrivial worstcase accuracy guarantees in time substantially smaller than the number of kway marginal queries, which is \(d^{\Theta(k)}\) (for \(k ≪ d\)).
ArXiv2018.pdf ICALP2012.pdf Dodis, Yevgeniy, Adriana LópezAlt, Ilya Mironov, and Salil Vadhan. “
Differential privacy with imperfect randomness.” In
Ran Canetti and Rei SafaviNaini, editors, Proceedings of the 32nd International Cryptology Conference (CRYPTO ‘12), Lecture Notes on Computer Science, 7417:497516. SpringerVerlag, 2012.
Publisher's VersionAbstract
In this work we revisit the question of basing cryptography on imperfect randomness. Bosley and Dodis (TCC’07) showed that if a source of randomness \(\mathcal{R}\) is “good enough” to generate a secret key capable of encrypting \(k\) bits, then one can deterministically extract nearly \(k\) almost uniform bits from \(\mathcal{R}\), suggesting that traditional privacy notions (namely, indistinguishability of encryption) requires an “extractable” source of randomness. Other, even stronger impossibility results are known for achieving privacy under specific “nonextractable” sources of randomness, such as the \(\gamma\)SanthaVazirani (SV) source, where each next bit has fresh entropy, but is allowed to have a small bias \(\gamma < 1\) (possibly depending on prior bits).
We ask whether similar negative results also hold for a more recent notion of privacy called differential privacy (Dwork et al., TCC’06), concentrating, in particular, on achieving differential privacy with the SanthaVazirani source. We show that the answer is no. Specifically, we give a differentially private mechanism for approximating arbitrary “low sensitivity” functions that works even with randomness coming from a \(\gamma\)SanthaVazirani source, for any \(\gamma < 1\). This provides a somewhat surprising “separation” between traditional privacy and differential privacy with respect to imperfect randomness.
Interestingly, the design of our mechanism is quite different from the traditional “additivenoise” mechanisms (e.g., Laplace mechanism) successfully utilized to achieve differential privacy with perfect randomness. Indeed, we show that any (nontrivial) “SVrobust” mechanism for our problem requires a demanding property called consistent sampling, which is strictly stronger than differential privacy, and cannot be satisfied by any additivenoise mechanism.
CRYPTO2012.pdf IACR2012.pdf Dwork, Cynthia, Moni Naor, and Salil Vadhan. “
The privacy of the analyst and the power of the state.” In
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS ‘12), 400409. IEEE, 2012.
Publisher's VersionAbstractWe initiate the study of privacy for the analyst in differentially private data analysis. That is, not only will we be concerned with ensuring differential privacy for the data (i.e. individuals or customers), which are the usual concern of differential privacy, but we also consider (differential) privacy for the set of queries posed by each data analyst. The goal is to achieve privacy with respect to other analysts, or users of the system. This problem arises only in the context of stateful privacy mechanisms, in which the responses to queries depend on other queries posed (a recent wave of results in the area utilized cleverly coordinated noise and state in order to allow answering privately hugely many queries). We argue that the problem is real by proving an exponential gap between the number of queries that can be answered (with nontrivial error) by stateless and stateful differentially private mechanisms. We then give a stateful algorithm for differentially private data analysis that also ensures differential privacy for the analyst and can answer exponentially many queries.
IEEE2012.pdf Gopalan, Parikshit, Raghu Meka, Omer Reingold, Luca Tevisan, and Salil Vadhan. “
Better pseudorandom generators via milder pseudorandom restrictions.” In
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS ‘12), 120129. IEEE, 2012.
Publisher's VersionAbstract
Version History: Full version posted as ECCC TR12123 and as arXiv:1210.0049 [cs.CC].
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 readonce \(\mathsf{CNF}\)s and a hitting set generator for width3 branching programs, all of which achieve nearoptimal seedlength even in the lowerror regime: We get seedlength \(\tilde{O}(\log(n/\epsilon))\) for error \(\epsilon\). Previously, only constructions with seedlength \(O(log^{3/2}n)\) or \(O(log^2n)\)were known for these classes with error \(\epsilon = 1/\mathrm{poly}(n)\). The (pseudo)random restrictions we use are milder than those typically used for proving circuit lower bounds in that we only set a constant fraction of the bits at a time. While such restrictions do not simplify the functions drastically, we show that they can be derandomized using smallbias spaces.
ArXiv2012.pdf IEEE2012.pdf ECCC2012.pdf