Browsing FAS Scholarly Articles by Author "Vadhan, Salil"

Now showing items 1-20 of 62

    • Are PCPs Inherent in Efficient Arguments? 

      Rothblum, Guy N.; Vadhan, Salil P. (Hasso-Plattner-Institut 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 collision-resistant 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 privacy-preserving synopses of an input database. These are data structures that yield, for a given set ...

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

      Goldreich, Oded; Sahai, Amit; Vadhan, Salil P. (Springer-Verlag, 1999)
      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 ...

    • 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 polynomial-sized 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 zero-knowledge 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 graph-theoretic counting problems remain NP-hard, indeed #P-complete, in very restricted classes of graphs. In particular, we prove that the problems of counting matchings, vertex covers, independent ...

    • Composition of Zero-Knowledge Proofs with Efficient Provers 

      Birrell, Eleanor; Vadhan, Salil P. (Springer Verlag, 2010)
      We revisit the composability of different forms of zero-knowledge 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 Small-Space Sources 

      Kamp, Jesse; Rao, Anup; Vadhan, Salil P.; Zuckerman, David (Elsevier BV, 2011)
      We give polynomial-time, 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 Public-Key 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 public-key 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ópez-Alt, 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 Chi-Squared Hypothesis Testing: Goodness of Fit and Independence Testing 

      Gaboardi, Marco; Lim, Hyun-Woo; 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 One-Way Functions 

      Haitner, Iftach; Reingold, Omer; Vadhan, Salil P. (Hasso-Plattner-Institut fuer Softwaresystemtechnik GmbH, 2010)
      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 ...

    • Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree 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 zig-zag product. Taking a product of a large graph with a small graph, the resulting graph inherits (roughly) its size from the large ...