Salil P. Vadhan

According to our database1, Salil P. Vadhan authored at least 145 papers between 1997 and 2020.

Collaborative distances:

Awards

ACM Fellow

ACM Fellow 2018, "For advancing computational complexity and cryptography, and for promoting public support for theoretical computer science".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
Privacy Games.
ACM Trans. Economics and Comput., 2020

Spectral Sparsification via Bounded-Independence Sampling.
Electronic Colloquium on Computational Complexity (ECCC), 2020

Differentially Private Simple Linear Regression.
CoRR, 2020

2019
Unifying computational entropies via Kullback-Leibler divergence.
IACR Cryptol. ePrint Arch., 2019

High-precision Estimation of Random Walks in Small Space.
CoRR, 2019

Deterministic Approximation of Random Walks in Small Space.
Proceedings of the Approximation, 2019

Computational entropy.
Proceedings of the Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, 2019

2018
The Complexity of Computing the Optimal Composition of Differential Privacy.
Theory Comput., 2018

Fingerprinting Codes and the Price of Approximate Differential Privacy.
SIAM J. Comput., 2018

Deterministic Public-Key Encryption for Adaptively-Chosen Plaintext Distributions.
J. Cryptology, 2018

A Tight Lower Bound for Entropy Flattening.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Usable Differential Privacy: A Case Study with PSI.
CoRR, 2018

Finite Sample Differentially Private Confidence Intervals.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Differential Privacy on Finite Computers.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017
Pseudorandomness and Fourier-Growth Bounds for Width-3 Branching Programs.
Theory Comput., 2017

The Many Entropies in One-Way Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Computational Notions of Quantum Min-Entropy.
CoRR, 2017

Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

On Learning vs. Refutation.
Proceedings of the 30th Conference on Learning Theory, 2017

The Complexity of Differential Privacy.
Proceedings of the Tutorials on the Foundations of Cryptography., 2017

The Many Entropies in One-Way Functions.
Proceedings of the Tutorials on the Foundations of Cryptography., 2017

2016
Truthful Mechanisms for Agents That Value Privacy.
ACM Trans. Economics and Comput., 2016

Separating Computational and Statistical Differential Privacy in the Client-Server Model.
IACR Cryptol. ePrint Arch., 2016

PSI (Ψ): a Private data Sharing Interface.
CoRR, 2016

Towards a Privacy Research Roadmap for the Computing Community.
CoRR, 2016

Locating a Small Cluster Privately.
Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

Privacy Odometers and Filters: Pay-as-you-Go Composition.
Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

Differentially Private Chi-Squared Hypothesis Testing: Goodness of Fit and Independence Testing.
Proceedings of the 33nd International Conference on Machine Learning, 2016

2015
Pseudorandomness for Read-Once, Constant-Depth Circuits.
CoRR, 2015

Robust Traceability from Trace Amounts.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Differentially Private Release and Learning of Threshold Functions.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014
Redrawing the boundaries on purchasing data from privacy-sensitive individuals.
Proceedings of the Innovations in Theoretical Computer Science, 2014

2013
Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream.
Theory Comput., 2013

On extractors and exposure-resilient functions for sublogarithmic entropy.
Random Struct. Algorithms, 2013

A Uniform Min-Max Theorem with Applications in Cryptography.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Pseudorandomness for Regular Branching Programs via Fourier Analysis.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Locally Testable Codes and Cayley Graphs.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Interactive proofs of proximity: delegating computation in sublinear time.
Proceedings of the Symposium on Theory of Computing Conference, 2013

Publicly verifiable proofs of sequential work.
Proceedings of the Innovations in Theoretical Computer Science, 2013

2012
Special Section on the Forty-Third Annual ACM Symposium on Theory of Computing (STOC 2011).
SIAM J. Comput., 2012

On the (im)possibility of obfuscating programs.
J. ACM, 2012

Differential Privacy with Imperfect Randomness.
IACR Cryptol. ePrint Arch., 2012

Pseudorandomness.
Foundations and Trends in Theoretical Computer Science, 2012

Better pseudorandom generators from milder pseudorandom restrictions.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Special issue from RANDOM'09: Editors' Foreword.
Comput. Complex., 2012

Randomness Condensers for Efficiently Samplable, Seed-Dependent Sources.
Proceedings of the Theory of Cryptography - 9th Theory of Cryptography Conference, 2012

Characterizing pseudoentropy.
Proceedings of the 2012 IEEE Information Theory Workshop, 2012

Faster Algorithms for Privately Releasing Marginals.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

The Privacy of the Analyst and the Power of the State.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011
Computational Complexity.
Proceedings of the Encyclopedia of Cryptography and Security, 2nd Ed., 2011

S-T connectivity on digraphs with a known stationary distribution.
ACM Trans. Algorithms, 2011

Deterministic extractors for small-space sources.
J. Comput. Syst. Sci., 2011

Non-Interactive Time-Stamping and Proofs of Work in the Random Oracle Model.
IACR Cryptol. ePrint Arch., 2011

Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions.
Electronic Colloquium on Computational Complexity (ECCC), 2011

The Limits of Two-Party Differential Privacy.
Electronic Colloquium on Computational Complexity (ECCC), 2011

On the complexity of computational problems regarding distributions (a survey).
Electronic Colloquium on Computational Complexity (ECCC), 2011

PCPs and the Hardness of Generating Private Synthetic Data.
Proceedings of the Theory of Cryptography - 8th Theory of Cryptography Conference, 2011

Time-Lock Puzzles in the Random Oracle Model.
Proceedings of the Advances in Cryptology - CRYPTO 2011, 2011

Simplified Derandomization of BPP Using a Hitting Set Generator.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On the Complexity of Computational Problems Regarding Distributions.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

2010
A Lower Bound on List Size for List Decoding.
IEEE Trans. Inf. Theory, 2010

Universal One-Way Hash Functions via Inaccessible Entropy.
IACR Cryptol. ePrint Arch., 2010

Improved Delegation of Computation using Fully Homomorphic Encryption.
IACR Cryptol. ePrint Arch., 2010

PCPs and the Hardness of Generating Synthetic Data.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Efficiency Improvements in Constructing Pseudorandom Generators from One-way Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2010

On Approximating the Entropy of Polynomial Mappings.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Are PCPs Inherent in Efficient Arguments?
Comput. Complex., 2010

Boosting and Differential Privacy.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009
Statistically Hiding Commitments and Statistical Zero-Knowledge Arguments from Any One-Way Function.
SIAM J. Comput., 2009

Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes.
J. ACM, 2009

Proofs of Retrievability via Hardness Amplification.
IACR Cryptol. ePrint Arch., 2009

Composition of Zero-Knowledge Proofs with Efficient Provers.
IACR Cryptol. ePrint Arch., 2009

Inaccessible Entropy.
Electronic Colloquium on Computational Complexity (ECCC), 2009

On the complexity of differentially private data release: efficient algorithms and hardness results.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Computational Differential Privacy.
Proceedings of the Advances in Cryptology, 2009

Pseudorandom Bit Generators That Fool Modular Sums.
Proceedings of the Approximation, 2009

2008
Simpler Session-Key Generation from Short Random Passwords.
J. Cryptology, 2008

Fairness with an Honest Minority and a Rational Majority.
IACR Cryptol. ePrint Arch., 2008

Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Dense Subsets of Pseudorandom Sets.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Limitations of Hardness vs. Randomness under Uniform Reductions.
Electronic Colloquium on Computational Complexity (ECCC), 2008

An Equivalence Between Zero Knowledge and Commitments.
Proceedings of the Theory of Cryptography, Fifth Theory of Cryptography Conference, 2008

Why simple hash functions work: exploiting the entropy in a data stream.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Tight Bounds for Hashing Block Sources.
Proceedings of the Approximation, 2008

The Complexity of Distinguishing Markov Random Fields.
Proceedings of the Approximation, 2008

2007
The unified theory of pseudorandomness: guest column.
SIGACT News, 2007

The hardness of the Expected Decision Depth problem.
Inf. Process. Lett., 2007

Interactive and Noninteractive Zero Knowledge Coincide in the Help Model.
IACR Cryptol. ePrint Arch., 2007

Interactive and Noninteractive Zero Knowledge are Equivalent in the Help Model.
IACR Cryptol. ePrint Arch., 2007

Pseudorandomness and Average-Case Complexity Via Uniform Reductions.
Comput. Complex., 2007

Special Issue On Worst-case Versus Average-case Complexity Editors' Foreword.
Comput. Complex., 2007

The Complexity of Zero Knowledge.
Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

Amplifying Collision Resistance: A Complexity-Theoretic Treatment.
Proceedings of the Advances in Cryptology, 2007

2006
Lower bounds for non-black-box zero knowledge.
J. Comput. Syst. Sci., 2006

An Unconditional Study of Computational Zero Knowledge.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Zero Knowledge and Soundness are Symmetric.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Statistical Zero-Knowledge Arguments for NP from Any One-Way Function.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Extractors and condensers from univariate polynomials.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Random Selection with an Adversarial Majority.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Pseudorandom walks on regular digraphs and the RL vs. L problem.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Zero knowledge with efficient provers.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

2005
Computational Complexity.
Proceedings of the Encyclopedia of Cryptography and Security, 2005

Derandomization in Cryptography
Electronic Colloquium on Computational Complexity (ECCC), 2005

The Round Complexity of Two-Party Random Selection
Electronic Colloquium on Computational Complexity (ECCC), 2005

Concurrent Zero Knowledge without Complexity Assumptions
Electronic Colloquium on Computational Complexity (ECCC), 2005

Derandomized Squaring of Graphs
Electronic Colloquium on Computational Complexity (ECCC), 2005

The Computational Complexity of Nash Equilibria in Concisely Represented Games
Electronic Colloquium on Computational Complexity (ECCC), 2005

Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem
Electronic Colloquium on Computational Complexity (ECCC), 2005

Compression of Samplable Sources.
Comput. Complex., 2005

Short PCPs Verifiable in Polylogarithmic Time.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004
Constructing Locally Computable Extractors and Cryptosystems in the Bounded-Storage Model.
J. Cryptology, 2004

Using Nondeterminism to Amplify Hardness
Electronic Colloquium on Computational Complexity (ECCC), 2004

Robust PCPs of Proximity, Shorter PCPs and Applications to Coding
Electronic Colloquium on Computational Complexity (ECCC), 2004

Notions of Reducibility between Cryptographic Primitives.
Proceedings of the Theory of Cryptography, First Theory of Cryptography Conference, 2004

Probabilistic proof systems - Part I.
Proceedings of the Computational Complexity Theory., 2004

2003
A complete problem for statistical zero knowledge.
J. ACM, 2003

Extractors: optimal up to constant factors.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Randomness-efficient low degree tests and short PCPs via epsilon-biased sets.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Statistical Zero-Knowledge Proofs with Efficient Provers: Lattice Problems and More.
Proceedings of the Advances in Cryptology, 2003

2002
Extracting all the Randomness and Reducing the Error in Trevisan's Extractors.
J. Comput. Syst. Sci., 2002

The Power of a Pebble: Exploring and Mapping Directed Graphs.
Inf. Comput., 2002

An Improved Pseudorandom Generator Based on Hardness of Factoring.
IACR Cryptol. ePrint Arch., 2002

On interactive proofs with a laconic prover.
Comput. Complex., 2002

Randomness conductors and constant-degree lossless expanders.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Randomness Extractors and their Many Guises.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001
The Complexity of Counting in Sparse, Regular, and Planar Graphs.
SIAM J. Comput., 2001

Pseudorandom Generators without the XOR Lemma.
J. Comput. Syst. Sci., 2001

Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors
Electronic Colloquium on Computational Complexity (ECCC), 2001

Order in Pseudorandomness.
Proceedings of the Approximation, 2001

2000
Simplified derandomization of BPP using a hitting set generator.
Electronic Colloquium on Computational Complexity (ECCC), 2000

On transformation of interactive proofs that preserve the prover's complexity.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Extracting Randomness from Samplable Distributions.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999
Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK
Electronic Colloquium on Computational Complexity (ECCC), 1999

Pseudorandom Generators Without the XOR Lemma (Extended Abstract).
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Error Reduction for Extractors.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Verifiable Random Functions.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Pseudorandom Generators without the XOR Lemma (Abstract).
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998
Many-to-one Trapdoor Functions and their Relation to Public-key Cryptosystems.
IACR Cryptol. ePrint Arch., 1998

Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK
Electronic Colloquium on Computational Complexity (ECCC), 1998

Extracting All the Randomness from a Weakly Random Source
Electronic Colloquium on Computational Complexity (ECCC), 1998

Checking Polynomial Identities over any Field: Towards a Derandomization?
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Many-to-One Trapdoor Functions and Their Ralation to Public-Key Cryptosystems.
Proceedings of the Advances in Cryptology, 1998

1997
A Complete Promise Problem for Statistical Zero-Knowledge.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Manipulating statistical difference.
Proceedings of the Randomization Methods in Algorithm Design, 1997


  Loading...