Browsing FAS Scholarly Articles by Author "Vadhan, Salil"
Now showing items 120 of 62

Are PCPs Inherent in Efficient Arguments?
Rothblum, Guy N.; Vadhan, Salil P. (HassoPlattnerInstitut fuer Softwaresystemtechnik GmbH, 2009)Starting with Kilian (STOC ‘92), several works have shown how to use probabilistically checkable proofs (PCPs) and cryptographic primitives such as collisionresistant hashing to construct very efficient argument systems ... 
Boosting and Differential Privacy
Dwork, Cynthia; Rothblum, Guy N.; Vadhan, Salil P. (IEEE Computer Society, 2010)Boosting is a general method for improving the accuracy of learning algorithms. We use boosting to construct improved privacypreserving synopses of an input database. These are data structures that yield, for a given set ... 
Can Statistical Zero Knowledge be made NonInteractive? or On the Relationship of SZK and NISZK
Goldreich, Oded; Sahai, Amit; Vadhan, Salil P. (SpringerVerlag, 1999)We extend the study of noninteractive statistical zeroknowledge proofs. Our main focus is to compare the class NISZK of problems possessing such noninteractive proofs to the class SZK of problems possessing interactive ... 
Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions
Vadhan, Salil P.; Zheng, Colin Jia (ACM Press, 2012)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 ... 
Checking Polynomial Identities over any Field: Towards a Derandomization?
Lewin, Daniel; Vadhan, Salil P. (Association of Computing Machinery, 1998)We present a Monte Carlo algorithm for testing multivariate polynomial identities over any field using fewer random bits than other methods. To test if a polynomial \(P(x_1, ..., x_n)\) is zero, our method uses \(\sum_{i=1}^n ... 
Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK
Goldreich, Oded; Vadhan, Salil P. (IEEE Computer Society Press, 1999)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 Complete Problem for Statistical Zero Knowledge
Sahai, Amit; Vadhan, Salil P. (Association for Computing Machinery, 2003)We present the first complete problem for SZK, the class of (promise) problems possessing statistical zeroknowledge proofs (against an honest verifier). The problem, called STATISTICAL DIFFERENCE, is to decide whether two ... 
The Complexity of Computing the Optimal Composition of Differential Privacy
Murtagh, Jack; Vadhan, Salil P. (Springer Science + Business Media, 2015)In the study of differential privacy, composition theorems (starting with the original paper of Dwork, McSherry, Nissim, and Smith (TCC’06)) bound the degradation of privacy when composing several differentially private ... 
The Complexity of Counting in Sparse, Regular, and Planar Graphs
Vadhan, Salil (Society for Industrial and Applied Mathematics, 2001)We show that a number of graphtheoretic counting problems remain NPhard, indeed #Pcomplete, in very restricted classes of graphs. In particular, we prove that the problems of counting matchings, vertex covers, independent ... 
Composition of ZeroKnowledge Proofs with Efficient Provers
Birrell, Eleanor; Vadhan, Salil P. (Springer Verlag, 2010)We revisit the composability of different forms of zeroknowledge proofs when the honest prover strategy is restricted to be polynomial time (given an appropriate auxiliary input). Our results are: 1.) When restricted to ... 
Computational Complexity
Vadhan, Salil P. (Springer, 2011) 
The Computational Complexity of Nash Equilibria in Concisely Represented Games
Schoenebeck, Grant R.; Vadhan, Salil P. (Association for Computing Machinery (ACM), 2012)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 ... 
Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space
Murtagh, Jack; Reingold, Omer; Sidford, Aaron; Vadhan, Salil P. (2017)We give a deterministic O˜(log n)space algorithm for approximately solving linear systems given by Laplacians of undirected graphs, and consequently also approximating hitting times, commute times, and escape probabilities ... 
Deterministic Extractors for SmallSpace Sources
Kamp, Jesse; Rao, Anup; Vadhan, Salil P.; Zuckerman, David (Elsevier BV, 2011)We give polynomialtime, deterministic randomness extractors for sources generated in small space, where we model space s sources on n{0,1} as sources generated by width s2 branching programs. Specifically, there is a ... 
Deterministic PublicKey Encryption for Adaptively Chosen Plaintext Distributions
Raghunathan, Ananth; Segev, Gil; Vadhan, Salil P. (Springer Berlin Heidelberg, 2013)Bellare, Boldyreva, and O’Neill (CRYPTO ’07) initiated the study of deterministic publickey encryption as an alternative in scenarios where randomized encryption has inherent drawbacks. The resulting line of research has ... 
Differential Privacy with Imperfect Randomness
Dodis, Yevgeniy; LópezAlt, Adriana; Mironov, Ilya; Vadhan, Salil P. (Springer Verlag, 2012)In this work we revisit the question of basing cryptogra phy on imperfect randomness. Bosley and Dodis (TCC’07) showed that if a source of randomness R is “good enough” to generate a secret key capable of encrypting k ... 
Differentially Private ChiSquared Hypothesis Testing: Goodness of Fit and Independence Testing
Gaboardi, Marco; Lim, HyunWoo; Rogers, Ryan M.; Vadhan, Salil P. (JMLR, 2016)Hypothesis testing is a useful statistical tool in determining whether a given model should be rejected based on a sample from the population. Sample data may contain sensitive information about individuals, such as medical ... 
Differentially Private Release and Learning of Threshold Functions
Bun, Mark; Nissim, Kobbi; Stemmer, Uri; Vadhan, Salil P. (2015)We prove new upper and lower bounds on the sample complexity of (ε, δ) differentially private algorithms for releasing approximate answers to threshold functions. A threshold function cx over a totally ordered domain X ... 
Efficiency Improvements in Constructing Pseudorandom Generators from OneWay Functions
Haitner, Iftach; Reingold, Omer; Vadhan, Salil P. (HassoPlattnerInstitut fuer Softwaresystemtechnik GmbH, 2010)We give a new construction of pseudorandom generators from any oneway function. The construction achieves better parameters and is simpler than that given in the seminal work of Haastad, Impagliazzo, Levin and Luby [SICOMP ... 
Entropy Waves, The ZigZag Graph Product, and New ConstantDegree Expanders and Extractors
Reingold, Omer; Vadhan, Salil P.; Wigderson, Avi (Princeton University, 2002)The main contribution of this work is a new type of graph product, which we call the zigzag product. Taking a product of a large graph with a small graph, the resulting graph inherits (roughly) its size from the large ...