Salil Vadhan

Q: What Schools Are Affiliated With Salil Vadhan

Salil Vadhan is affiliated with the following schools: Massachusetts Institute of Technology, Harvard University

Salil Vadhan's AcademicInfluence.com Rankings

Salil Vadhan

Computer Science

#993

World Rank

#1029

Historical Rank

#536

USA Rank

Database

#2579

World Rank

#2701

Historical Rank

#546

USA Rank

computer-science Degrees

Download Badge

Computer Science

Why Is Salil Vadhan Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Salil Vadhan is an American computer scientist. He is Vicky Joseph Professor of Computer Science and Applied Mathematics at Harvard University. After completing his undergraduate degree in Mathematics and Computer Science at Harvard in 1995, he obtained his PhD in Applied Mathematics from Massachusetts Institute of Technology in 1999, where his advisor was Shafi Goldwasser. His research centers around the interface between computational complexity theory and cryptography. He focuses on the topics of pseudorandomness and zero-knowledge proofs. His work on the zig-zag product, with Omer Reingold and Avi Wigderson, was awarded the 2009 Gödel Prize.

(See a Problem?)

Salil Vadhan's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Computational Complexity (2005) (3596)
On the (im)possibility of obfuscating programs (2001) (1429)
Boosting and Differential Privacy (2010) (821)
Verifiable random functions (1999) (547)
Proofs of Retrievability via Hardness Amplification (2009) (489)
Pseudorandom generators without the XOR Lemma (1999) (408)
Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors (2000) (406)
On the complexity of differentially private data release: efficient algorithms and hardness results (2009) (403)
Improved Delegation of Computation using Fully Homomorphic Encryption (2010) (401)
Robust pcps of proximity, shorter pcps and applications to coding (2004) (290)
The Complexity of Counting in Sparse, Regular, and Planar Graphs (2002) (268)
Notions of Reducibility between Cryptographic Primitives (2004) (262)
Computational Differential Privacy (2009) (249)
The power of a pebble: exploring and mapping directed graphs (1998) (247)
Extracting all the randomness and reducing the error in Trevisan's extractors (1999) (222)
The Complexity of Differential Privacy (2017) (217)
Randomness conductors and constant-degree lossless expanders (2002) (214)
Extracting randomness from samplable distributions (2000) (201)
Constructing Locally Computable Extractors and Cryptosystems in the Bounded-Storage Model (2003) (182)
The Limits of Two-Party Differential Privacy (2010) (178)
Why simple hash functions work: exploiting the entropy in a data stream (2008) (170)
Pseudorandomness (2012) (168)
Fingerprinting codes and the price of approximate differential privacy (2013) (167)
Differentially Private Release and Learning of Threshold Functions (2015) (163)
Statistical Zero-Knowledge Proofs with Efficient Provers: Lattice Problems and More (2003) (154)
Extractors: optimal up to constant factors (2003) (149)
Differential Privacy: A Primer for a Non-Technical Audience (2018) (145)
Robust Traceability from Trace Amounts (2015) (135)
Finite Sample Differentially Private Confidence Intervals (2017) (133)
Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge (1998) (133)
Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes (2007) (131)
Randomness-efficient low degree tests and short PCPs via epsilon-biased sets (2003) (131)
Dense Subsets of Pseudorandom Sets (2008) (127)
ENTROPY WAVES, THE ZIG-ZAG GRAPH PRODUCT, AND NEW CONSTANT-DEGREE (2004) (117)
Differentially Private Chi-Squared Hypothesis Testing: Goodness of Fit and Independence Testing (2016) (116)
Short PCPs verifiable in polylogarithmic time (2005) (116)
Lower bounds for non-black-box zero knowledge (2003) (116)
Derandomization in Cryptography (2003) (113)
Proceedings of the 43rd annual ACM symposium on Theory of computing (2011) (113)
On interactive proofs with a laconic prover (2001) (112)
Pseudorandomness and Average-Case Complexity Via Uniform Reductions (2007) (108)
Truthful Mechanisms for Agents That Value Privacy (2011) (105)
The Complexity of Computing the Optimal Composition of Differential Privacy (2015) (101)
Can Statistical Zero Knowledge Be Made Non-interactive? or On the Relationship of SZK and NISZK (1998) (100)
Fairness with an Honest Minority and a Rational Majority (2009) (93)
Comparing entropies in statistical zero knowledge with applications to the structure of SZK (1999) (93)
A complete promise problem for statistical zero-knowledge (1997) (93)
PCPs and the Hardness of Generating Private Synthetic Data (2011) (90)
Statistically Hiding Commitments and Statistical Zero-Knowledge Arguments from Any One-Way Function (2009) (90)
Proceedings of the forty-third annual ACM symposium on Theory of computing (2011) (87)
Deterministic extractors for small-space sources (2006) (86)
Publicly verifiable proofs of sequential work (2013) (83)
Faster Algorithms for Privately Releasing Marginals (2012) (81)
Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions (2013) (81)
Better Pseudorandom Generators from Milder Pseudorandom Restrictions (2012) (80)
Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution (2009) (79)
An unconditional study of computational zero knowledge (2004) (77)
Using nondeterminism to amplify hardness (2004) (77)
Derandomized Squaring of Graphs (2005) (74)
Pseudorandom walks on regular digraphs and the RL vs. L problem (2006) (70)
Privacy Odometers and Filters: Pay-as-you-Go Composition (2016) (68)
Many-to-One Trapdoor Functions and Their Ralation to Public-Key Cryptosystems (1998) (67)
Redrawing the boundaries on purchasing data from privacy-sensitive individuals (2014) (64)
Characterizing pseudoentropy and simplifying pseudorandom generator constructions (2012) (63)
Interactive proofs of proximity: delegating computation in sublinear time (2013) (63)
Randomness Conductors and Constant-Degree Expansion Beyond the Degree / 2 Barrier (2001) (58)
A complete problem for statistical zero knowledge (2003) (58)
Pseudorandomness for Regular Branching Programs via Fourier Analysis (2013) (58)
Time-Lock Puzzles in the Random Oracle Model (2011) (58)
Checking polynomial identities over any field: towards a derandomization? (1998) (57)
On the (im)possibility of obfuscating programs : (Extended abstract) (2001) (55)
Statistical Zero-Knowledge Arguments for NP from Any One-Way Function (2006) (55)
Pseudorandom generators without the XOR Lemma (extended abstract) (1999) (55)
Inaccessible entropy (2009) (55)
Differential Privacy on Finite Computers (2017) (53)
Randomness conductors and constant-degree lossless expanders (2002) (53)
Simpler Session-Key Generation from Short Random Passwords (2004) (51)
Bridging the Gap between Computer Science and Legal Approaches to Privacy (2018) (51)
Zero knowledge with efficient provers (2006) (49)
Error reduction for extractors (1999) (49)
An Equivalence Between Zero Knowledge and Commitments (2008) (49)
Randomness Condensers for Efficiently Samplable, Seed-Dependent Sources (2012) (48)
Theory of Cryptography (2016) (48)
PSI (Ψ): a Private data Sharing Interface (2016) (47)
Amplifying Collision Resistance: A Complexity-Theoretic Treatment (2007) (46)
On Constructing Locally Computable Extractors and Cryptosystems in the Bounded Storage Model (2003) (46)
Pseudorandomness and average-case complexity via uniform reductions (2002) (46)
A Lower Bound on List Size for List Decoding (2005) (45)
Locating a Small Cluster Privately (2016) (42)
Deterministic Public-Key Encryption for Adaptively-Chosen Plaintext Distributions (2013) (42)
The Complexity of Distinguishing Markov Random Fields (2008) (40)
A Uniform Min-Max Theorem with Applications in Cryptography (2013) (40)
Concurrent Zero Knowledge without Complexity Assumptions (2006) (40)
The unified theory of pseudorandomness (2010) (36)
Manipulating statistical difference (1997) (35)
The Computational Complexity of Nash Equilibria in Concisely Represented Games (2012) (34)
Universal One-Way Hash Functions via Inaccessible Entropy (2010) (33)
Are PCPs Inherent in Efficient Arguments? (2009) (32)
Differential Privacy with Imperfect Randomness (2012) (30)
The Privacy of the Analyst and the Power of the State (2012) (30)
The complexity of hardness amplification and derandomization (2006) (29)
The unified theory of pseudorandomness: guest column (2007) (28)
New Proofs of the Green-Tao-Ziegler Dense Model Theorem: An Exposition (2008) (27)
On Approximating the Entropy of Polynomial Mappings (2010) (26)
Towards a Modern Approach to Privacy-Aware Government Data Releases (2016) (26)
Interactive and Noninteractive Zero Knowledge are Equivalent in the Help Model (2008) (26)
Zero Knowledge and Soundness Are Symmetric (2007) (26)
Simplified Derandomization of BPP Using a Hitting Set Generator (2000) (26)
Pseudorandom Bit Generators That Fool Modular Sums (2009) (26)
A Study of Statistical Zero-Knowledge Proofs (2021) (24)
High-precision Estimation of Random Walks in Small Space (2019) (24)
Random Selection with an Adversarial Majority (2006) (23)
Compression of Samplable Sources (2004) (22)
Differentially Private Simple Linear Regression (2020) (22)
Randomness extractors and their many guises (2002) (21)
On Learning vs. Refutation (2017) (20)
The computational complexity of nash equilibria in concisely represented games (2006) (19)
Extracting All the Randomness from a Weakly Random Source (1998) (19)
On the complexity of computational problems regarding distributions (a survey) (2011) (18)
Tight Bounds for Hashing Block Sources (2008) (18)
Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space (2017) (17)
S-T Connectivity on Digraphs with a Known Stationary Distribution (2007) (17)
Efficiency improvements in constructing pseudorandom generators from one-way functions (2010) (17)
A note on ex-tracting randomness from Santha-Vazirani sources (2004) (17)
The round complexity of two-party random selection (2005) (16)
Extracting all the Randomness and Reducing the Error in Trevisan's Extractors (2002) (16)
Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem (2005) (16)
Limitations of Hardness vs. Randomness under Uniform Reductions (2008) (15)
On transformation of interactive proofs that preserve the prover's complexity (2000) (15)
Pseudorandom Generators for Unbounded-Width Permutation Branching Programs (2020) (15)
Towards a Privacy Research Roadmap for the Computing Community (2016) (15)
Privacy Games (2014) (14)
A Programming Framework for OpenDP∗† (2020) (14)
Time-Lock Puzzles in the Random Oracle (2011) (13)
Cryptography and Computer Security (2003) (13)
Fairness with an Honest Minority and a (2008) (13)
Deterministic Approximation of Random Walks in Small Space (2019) (12)
Proceedings of the 6th International Workshop on Randomization and Approximation Techniques (2002) (11)
17 58 v 3 [ cs . D S ] 1 4 M ar 2 01 4 Faster Algorithms for Privately Releasing Marginals ∗ (2018) (11)
An Improved Pseudorandom Generator Based on Hardness of Factoring (2002) (11)
Truthful mechanisms for agents that value privacy (2013) (10)
Pseudorandomness II (2009) (9)
PCPs and the Hardness of Generating Synthetic Data (2020) (9)
Pseudorandomness for Read-Once, Constant-Depth Circuits (2015) (9)
Extractors and condensers from univariate polynomials (2006) (9)
Pseudodistributions that beat all pseudorandom generators (extended abstract) (2021) (9)
Concurrent Composition of Differential Privacy (2021) (8)
Pseudorandom Generators without the XOR Lemma (Abstract). (1999) (8)
Separating Computational and Statistical Differential Privacy in the Client-Server Model (2016) (8)
A Tight Lower Bound for Entropy Flattening (2018) (7)
Integrating Approaches to Privacy Across the Research Lifecycle: When Is Information Purely Public? (2015) (7)
The Complexity of Zero Knowledge (2007) (7)
A On the ( Im ) (2012) (6)
Concurrent Composition Theorems for all Standard Variants of Differential Privacy (2022) (6)
Non-Interactive Time-Stamping and Proofs of Work in the Random Oracle Model (2011) (6)
A study of statistical zero-knowledge proofs (information security and cryptography) (2018) (6)
Deterministic Approximation of Random Walks via Queries in Graphs of Unbounded Size (2021) (6)
Pseudorandomness and Fourier-Growth Bounds for Width-3 Branching Programs (2017) (5)
Unifying computational entropies via Kullback-Leibler divergence (2019) (5)
Computational Notions of Quantum Min-Entropy (2017) (5)
The Many Entropies in One-Way Functions (2017) (5)
Monotone Branching Programs: Pseudorandomness and Circuit Complexity (2021) (5)
Proceedings of the 4th conference on Theory of cryptography (2007) (5)
Inaccessible Entropy I: Inaccessible Entropy Generators and Statistically Hiding Commitments from One-Way Functions (2020) (5)
Special Issue On Worst-case Versus Average-case Complexity Editors’ Foreword (2007) (5)
Interactive and Noninteractive Zero Knowledge Coincide in the Help Model (2007) (4)
Pseudorandomness of expander random walks for symmetric functions and permutation branching programs (2022) (4)
Hypothesis Testing for Differentially Private Linear Regression (2022) (4)
Randomization and Approximation Techniques in Computer Science: 6th International Workshop, RANDOM 2002, Cambridge, MA, USA, September 13-15, 2002, Proceedings (2002) (4)
Usable Differential Privacy: A Case Study with PSI (2018) (4)
Pseudodistributions That Beat All Pseudorandom Generators (2021) (4)
Pseudorandom Generators for Read-Once Monotone Branching Programs (2021) (4)
Canonical Noise Distributions and Private Hypothesis Tests (2021) (4)
The Complexity of Counting (1995) (4)
Harnessing the Known Unknowns: Differential Privacy and the 2020 Census (2022) (3)
Concurrent Composition Theorems for Differential Privacy (2022) (3)
Characterizing pseudoentropy (2012) (3)
Locally testable codes and cayley graphs (2013) (3)
Universal One-Way Hash Functions via Inaccessible (2010) (3)
Cellular Network Security (2011) (3)
Integrating Approaches to Privacy Across the Research Lifecycle: Long-Term Longitudinal Studies (2014) (3)
Unconditional relationships within zero knowledge (2007) (3)
Conceptual Modeling (2012) (3)
On extractors and exposure-resilient functions for sublogarithmic entropy (2010) (2)
Limitations of the Impagliazzo-Nisan-Wigderson Pseudorandom Generator against Permutation Branching Programs (2021) (2)
Introduction to Homomorphic Encryption (2011) (2)
Don’t Look at the Data! How Differential Privacy Reconfigures the Practices of Data Science (2023) (2)
Efficient parallel repetition theorems with applications to security amplification (2011) (2)
Composition of Zero-Knowledge Proofs with Efficient Provers (2010) (2)
The hardness of the Expected Decision Depth problem (2007) (2)
Fourier Growth of Regular Branching Programs (2022) (2)
Analyzing the Differentially Private Theil-Sen Estimator for Simple Linear Regression (2022) (2)
Pseudorandom generators without the XOR lemma (1999) (2)
Computational entropy (2019) (2)
Theory of Cryptography, 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21-24, 2007, Proceedings (2007) (2)
Spectral Sparsification via Bounded-Independence Sampling (2020) (2)
Special Section on the Forty-Third Annual ACM Symposium on Theory of Computing (STOC 2011) (2012) (1)
When and How Can Data be Efficiently Released with Privacy ? (2008) (1)
Inaccessible Entropy II: IE Functions and Universal One-Way Hashing (2021) (1)
C R ] 2 4 A pr 2 01 7 Computational Notions of Quantum Min-Entropy (2017) (1)
Privacy Games (2020) (1)
Dense Subsets of Pseudorandom Sets (Extended Abstract) (2008) (1)
Finite Sample Differentially Private Confidence Intervals ( Extended Abstract ) ∗ (2017) (1)
Randomness Conductors and Constant-Degree (2009) (1)
Probabilistic proof systems - Part I (2004) (1)
Randomization and Approximation Techniques, 6th International Workshop, RANDOM 2002, Cambridge, MA, USA, September 13-15, 2002, Proceedings (2002) (1)
Lecture Notes for the 26th Mcgill Invitational Workshop on Computational Complexity (2016) (1)
Widespread Underestimation of Sensitivity in Differentially Private Libraries and How to Fix It (2022) (1)
Zero knowledge and efficient provers (2006) (1)
OpenDP : An Open-Source Suite of Differential Privacy Tools (2019) (1)
Theory of Pseudorandomness (2010) (1)
AN THE CHURCH-TURING (2015) (1)
Order in Pseudorandomness (2001) (1)
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (2009) (1)
When Simple Hash Functions Suffice (2020) (1)
Deterministic Public-Key Encryption for Adaptively Chosen (2014) (1)
Composition of Zero-Knowledge Proofs with Efficient (2009) (1)
An Unconditional Study of Computational Zero Knowledge | SIAM Journal on Computing | Vol. 36, No. 4 | Society for Industrial and Applied Mathematics (2006) (1)
Differential Privacy 2 a Bayesian Forumulation of Differential Privacy (2011) (0)
Euclidean TSP (2009) (0)
Time-Lock Puzzles in the Random (2011) (0)
C R ] 5 O ct 2 01 7 Computational Notions of Quantum Min-Entropy (2018) (0)
Universal One-Way Hash Functions and Average Case Complexity via Inaccessible Entropy (2014) (0)
Lecture 22: Black-box Prg Constructions and Extractors 1 Putting Together the Prg Construction (0)
Pseudorandom Generators via Mild Pseudorandom Restrictions (2013) (0)
ffl)-Approximation Scheme for the Euclidean TSP (1996) (0)
Privacy Games The Harvard community has made this article openly available. Please share how this access benefits you. Your story matters (2014) (0)
Special issue from RANDOM’09: Editors’ Foreword (2012) (0)
CAREER: A Unified Theory of Pseudorandomness (2013) (0)
NCRN Meeting Spring 2017: Formal Privacy Models and Title 13 (2017) (0)
Title : Mechanism Design and Differential Privacy Name : (2019) (0)
Lecture 17: Pseudorandom Generators Based on Scribe Notes (2007) (0)
Singular Value Approximation and Reducing Directed to Undirected Graph Sparsification (2023) (0)
1 Rapid Mixing of Random Walks (0)
Lecture 2: Randomized Algorithms and Complexity Classes 1 Polynomial Identity Testing (0)
Cs221: Computational Complexity Lecture 20: Circuit Complexity (2002) (0)
Special issue from RANDOM’09: Editors’ Foreword (2012) (0)
Lecture 13: More Connections with Expanders Based on Scribe Notes (0)
Randomness Conductors and Constant-Degree Lossless Expanders [Extended Abstract] (2009) (0)
Complexity Theory (2019) (0)
Computational Complexity: a Conceptual Perspective Organization and Chapter Summaries (0)
D S ] 1 1 Ju n 20 08 Tight Bounds for Hashing Block Sources ∗ (2018) (0)
Arora's (1 + E)-ApproximationScheme for the (1996) (0)
Efficiency Improvements in Constructing Pseudorandom Generators (2010) (0)
Faster Algorithms for Privately Releasing Marginals Please share how this access benefits you. Your story matters (2012) (0)
Cryptographic Protocol (2011) (0)
On Learning versus Refutation (2017) (0)
Lecture 3: Sampling and Approximation Problems (0)
Privacy Tools project response to Common Rule Notice of Proposed Rule Making (2016) (0)
On Extractors and Exposure-Resilient Functions for (2012) (0)
A standardised differential privacy framework for epidemiological modelling with mobile phone data (2023) (0)
Credential Verification (2011) (0)
In memory of the second author's loving father, Yaakov (Yasha) Rosenfeld (2006) (0)
Session details: Session 9A (2007) (0)
Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space (2021) (0)
Manipulating Statistical Di � erence (2018) (0)
C C ] 23 A ug 2 01 3 Locally Testable Codes and Cayley Graphs (2018) (0)
The Unified Theory of Pseudorandomness The Harvard community has made this article openly available. Please share how this access benefits you. Your story matters (2010) (0)
Randomness Conductors and Constant-Degree Lossless (2009) (0)
Mathematisches Forschungsinstitut Oberwolfach Proving Hard-core Predicates Using List Decoding Proving Integrality Gaps without Knowing the Linear Program How to Go beyond the Black-box Simulation Barrier Derandomization in Cryptography Formula Caching Proof Systems Algebras of Minimal Rank over Arb (2003) (0)
A Programming Framework for OpenDP (extended abstract)∗ (2021) (0)
Session details: Session 5 (2011) (0)
Dense Subsets of Pseudorandom Sets ∗ [ Extended (2008) (0)
Lecture 1: Introduction 1 Course Overview (0)
Lecture 7: Expander Graphs (0)
Weak Random Sources and Deterministic Extractors (0)

This paper list is powered by the following services:

Other Resources About Salil Vadhan

en.wikipedia.org

What Schools Are Affiliated With Salil Vadhan?

Salil Vadhan is affiliated with the following schools:

Salil Vadhan's Academic­Influence.com Rankings