Salil Vadhan's Research

My research interests are in the Theory of Computation, and focuses on complexity theory, cryptography, and randomness in computation.

• Full List of Papers
• Research Statement
• Research Descriptions by Area
• Survey Talks (still under construction)
• My Ph.D. thesis,   A Study of Statistical Zero-Knowledge Proofs, done under the supervision of Shafi Goldwasser at MIT in 1999.

---

Full List of Papers

Clicking on a paper will take you to webpage for that paper, which contains an abstract and a copy of the paper in postscript and/or other formats.  Papers posted or substantially revised in roughly the last year are marked  or , respectively.  If you have trouble reading any of the files, please send me email: MyFirstName AT seas.harvard.edu. The versions of papers here do not always correspond exactly to the published version, especially with respect to formatting and page numbering.  In particular, for journal papers, this site usually contains the last version prior to copyediting. In some cases, I include links to the publication's website, where you may be able to get the official version if you or your institution has an electronic subscription.

Copyright Notice. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.  These works may not be reposted without the explicit permission of the copyright holder.  Also, some of these works have been submitted for publication. Copyright may be transferred without further notice and this version may no longer be accessible.

This list of papers has not been updated since November 2010. For my more recent papers, please see Digital Access to Scholarship at Harvard (DASH), and the DBLP Computer Science Bibliography.

• B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan, K. Yang.
  On the (Im)possibility of Obfuscating Programs.
  CRYPTO `01, ECCC `01, Crypto ePrint `01.
• B. Barak, Y. Lindell, S. Vadhan.
  Lower Bounds for Non-Black-Box Zero Knowledge.
  FOCS `03. Crypto ePrint `04, ECCC `04, JCSS `06.
• B. Barak, S. J. Ong, S. Vadhan.
  Derandomization in Cryptography.
  CRYPTO `03. Crypto ePrint `05, ECCC `05, SICOMP `07.
  
• E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan, S. Vadhan.
  Robust PCPs of Proximity, Short PCPs, and Applications to Coding.
  STOC `04.  ECCC `04.  SICOMP `06.
• E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan, S. Vadhan.
  Short PCPs Verifiable in Polylogarithmic Time.
  CCC `05.
  
• E. Ben-Sasson, M. Sudan, S. Vadhan, A. Wigderson.
  Randomness-efficient low-degree tests and short PCPs via epsilon-biased sets.
  STOC `03.
  
• M. Bender , A. Fernández , D. Ron , A. Sahai , S.Vadhan.
  The Power of a Pebble: Exploring and Mapping Directed Graphs.
  STOC `98. Information & Computation `02.
• M. Bellare , S. Halevi , A. Sahai , S. Vadhan. 
  Many-to-one Trapdoor Functions and their Relation to Public-Key Cryptosystems.
  CRYPTO `98, Crypto ePrint `98.
  
• E. Birrell, S. Vadhan.
  Composition of Zero-Knowledge Proofs with Efficient Provers.
  Crypto ePrint `09, TCC `10.
  
  
• A. Bogdanov, E. Mossel, S. Vadhan.
  The Complexity of Distinguishing Markov Random Fields.
  RANDOM `08.
  
  
• M. Capalbo, O. Reingold, S. Vadhan, A. Wigderson.
  Randomness Conductors and Constant-Degree Lossless Expanders.
  STOC-CCC `02.
  
• R. Canetti, R. Rivest, M. Sudan, L. Trevisan, S. Vadhan, H. Wee.
  Amplifying Collision-Resistance: A Complexity-Theoretic Treatment.
  CRYPTO `07.
  
  
• K. M. Chung, O. Reingold, S. Vadhan.
  S-T Connectivity on Digraphs with a Known Stationary Distribution.
  CCC `07, TALG `09.
  
  
• K.M. Chung, Y. Kalai, S. Vadhan.
  Improved Delegation of Computation using Fully Homomorphic Encryption.
  Crypto ePrint `10, CRYPTO `10.
  
  
• K. M. Chung, S. Vadhan.
  Tight Bounds for Hashing Block Sources.
  RANDOM `08, arXiv `08.
  
  
• A. Chailloux, D. F. Ciocan, I. Kerenidis, S. Vadhan.
  Interactive and Noninteractive Zero Knowledge Are Equivalent in the Help Model.
  Crypto ePrint `07. TCC `08.
  
  
• N. Dedic, L. Reyzin, S. Vadhan.
  An Improved Pseudorandom Generator Based on Hardness of Factoring.
  SCN `02. Crypto ePrint `02.
  
• Y. Dodis, S. Vadhan, D. Wichs.
  Proofs of Retrievability via Hardness Amplification.
  TCC `09, Crypto ePrint `09.
  
  
• Z. Dvir, D. Gutfreund, G. Rothblum, S. Vadhan.
  On Approximating the Entropy of Polynomial Mappings.
  ICS `11.
  
  
• C. Dwork, M. Naor, O. Reingold, G. Rothblum, S. Vadhan.
  On the Complexity of Differentially Private Data Release: Efficient Algorithms and Hardness Results.
  STOC `09.
  
  
• C. Dwork, G. Rothblum, S. Vadhan.
  Boosting and Differential Privacy.
  FOCS `10.
  
  
• O. Goldreich, A. Sahai , S.Vadhan.
  Honest Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge.
  STOC `98.
  
• O. Goldreich, A. Sahai, S.Vadhan.
  Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK.
  CRYPTO `99, ECCC `99.
  
• O. Goldreich, S. Vadhan.
  Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK.
  CCC `99.
  
• O. Goldreich, S.Vadhan, A.Wigderson.
  On Interactive Proofs with a Laconic Prover.
  ICALP `01, Computational Complexity `02.
  
• O. Goldreich, S.Vadhan, A.Wigderson.
  Simplified Derandomization of BPP using a Hitting Set Generator.
  ECCC `00.
• R. Gradwohl, S. Vadhan, D. Zuckerman.
  Random Selection with an Adversarial Majority.
  ECCC `06. CRYPTO `06.
  
• D. Gutfreund, S. Vadhan.
  Limitations of Hardness vs. Randomness under Uniform Reductions.
  ECCC `08, RANDOM `08.
  
  
• V. Guruswami, C. Umans, S. Vadhan.
  Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes.
  ECCC `06, CCC `07, JACM `09.
  
  
• V. Guruswami, S. Vadhan.
  A Lower Bound on List Size for List Decoding.
  RANDOM `05, IEEE TIT `10.
  
• I. Haitner, T. Holenstein, O. Reingold, S. Vadhan, H. Wee.
  Universal One-Way Hash Functions via Inaccessible Entropy.
  EUROCRYPT `10. ePrint `10.
  
  
• I. Haitner, M. Nguyen, S.J. Ong, O. Reingold, S. Vadhan.
  Statistically Hiding Commitments and Statistical Zero-Knowledge Arguments from Any One-Way Function.
  SICOMP `09.
  
  
• I. Haitner, O. Reingold, S. Vadhan.
  Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions.
  STOC `10. ECCC `10.
  
  
• I. Haitner, O. Reingold, S. Vadhan, H. Wee.
  Inaccessible Entropy.
  STOC `09. ECCC `09.
  
  
• A. Healy, S. Vadhan, E. Viola.
  Using Nondeterminism to Amplify Hardness.
  STOC `04. SICOMP `05.
  
• J. Kamp, A. Rao, S. Vadhan, D. Zuckerman.
  Deterministic Extractors for Small-Space Sources.
  STOC `06. JCSS `10.
  
• D. Lewin, S. Vadhan.
  Checking Polynomial Identities over any Field: Towards a Derandomization?
  STOC `98.
  
  
• S. Lovett, O. Reingold, L. Trevisan, S. Vadhan.
  Pseudorandom Bit Generators that Fool Modular Sums.
  RANDOM `09.
• C.-J. Lu, O. Reingold, S. Vadhan, A. Wigderson.
  Extractors: Optimal up to Constant Factors.
  STOC `03.
  
  
• M.Mahmoody, T. Moran, S. Vadhan.
  Time-Lock Puzzles in the Random Oracle Model.
  CRYPTO `11.
  
  
• A. McGregor, I. Mironov, T. Pitassi, O. Reingold, K. Talwar, S. Vadhan.
  The Limits of Two-Party Differential Privacy.
  FOCS `10.
  
  
• D. Micciancio, S. J. Ong, A. Sahai, S. Vadhan.
  Concurrent Zero Knowledge without Complexity Assumptions.
  ECCC `05.  TCC `06. 
  
  
• D. Micciancio, S. Vadhan.
  Statistical Zero-Knowledge Proofs with Efficient Provers: Lattice Problems and More.
  CRYPTO `03.
  
• S. Micali, M. Rabin, S. Vadhan.
  Verifiable Random Functions.
  FOCS `99.
• I. Mironov, O. Pandey, O. Reingold, S. Vadhan.
  Computational Differential Privacy.
  CRYPTO `09.
• M. Mitzenmacher, S. Vadhan.
  Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream.
  SODA `08.
  
  
• M. Nguyen, S.J. Ong, S. Vadhan.
  Statistical Zero-Knowledge Arguments for NP from Any One-Way Function.
  ECCC `06. FOCS `06.
• M. Nguyen, S. Vadhan.
  Simpler Session-Key Generation from Short Random Passwords.
  TCC `04. JCrypt `08.
• M. Nguyen, S. Vadhan.
  Zero Knowledge with Efficient Provers.
  STOC `06.
• S. J. Ong, D. Parkes, A. Rosen, S. Vadhan.
  Fairness with an Honest Minority and a Rational Majority.
  ePrint `08. TCC `09.
  
  
• S. J. Ong, S. Vadhan.
  An Equivalence between Zero Knowledge and Commitments.
  TCC `08.
  
  
• S. J. Ong, S. Vadhan.
  Zero Knowledge and Soundness are Symmetric.
  EUROCRYPT `07.
  
  
• R. Raz, O. Reingold, S. Vadhan.
  Extracting all the Randomness and Reducing the Error in Trevisan's Extractors.
  STOC `99, JCSS `02.
  
• R. Raz, O. Reingold, S. Vadhan.
  Error Reduction for Extractors.
  FOCS `99.
  
• O. Reingold, L. Trevisan, M. Tulsiani, S. Vadhan.
  Dense Subsets of Pseudorandom Sets.
  ECCC `08, FOCS `08.
• O. Reingold, L. Trevisan, S. Vadhan.
  Notions of Reducibility between Cryptographic Primitives.
  TCC `04.
• O. Reingold, L. Trevisan, S. Vadhan.
  Pseudorandom Walks on Regular Digraphs and the RL vs. L Problem.
  ECCC `05. STOC `06.
  
• O. Reingold, S. Vadhan, A. Wigderson.
  Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors.
  FOCS `00, ECCC `01, DIMACS TR `01, Annals of Math `02.
  
• Y. Reshef, S. Vadhan.
  On Extractors and Exposure-Resilient Functions for Sublogarithmic Entropy.
  arXiv `10.
  
  
• D. Ron, A. Rosenfeld, S. Vadhan.
  The Hardness of the Expected Decision Depth Problem.
  IPL `08.
  
  
• G. Rothblum, S. Vadhan.
  Are PCPs Inherent in Efficient Arguments?
  CCC `09, CC `10.
  
  
• E. Rozenman, S. Vadhan.
  Derandomized Squaring of Graphs.
  RANDOM `05. ECCC `05.
  
• A. Sahai, S. Vadhan.
  A Complete Problem for Statistical Zero Knowledge.
  FOCS `97, JACM `03.
  
• A. Sahai, S. Vadhan.
  Manipulating Statistical Difference.
  DIMACS Workshop `97.
  
• S. Sanghvi, S. Vadhan.
  The Round Complexity of Two-Party Random Selection.
  STOC `05. ECCC `05. SICOMP `08.
  
• G. Schoenebeck, S. Vadhan.
  The Computational Complexity of Nash Equilibria in Concisely Represented Games.
  ECCC `05. EC `06. 
  
  
• M. Sudan, L. Trevisan, S. Vadhan.
  Pseudorandom Generators without the XOR Lemma.
  STOC-CCC `99 joint session, JCSS `01 (Special Issue on CCC `99).
  
• L. Trevisan, M. Tulsiani, S. Vadhan.
  Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution.
  ECCC `08, CCC `09.
  
  
• L. Trevisan, S. Vadhan.
  Pseudorandomness and Average-Case Complexity via Uniform Reductions.
  CCC `02. CC `07.
  
• L. Trevisan, S. Vadhan.
  Extracting Randomness from Samplable Distributions.
  FOCS `00.
  
• L. Trevisan, S. Vadhan, D. Zuckerman.
  Compression of Samplable Sources.
  CCC `04, ECCC `05, CC `05.
  
  
• J. Ullman, S. Vadhan.
  PCPs and the Hardness of Generating Synthetic Data.
  ECCC `10.
  
• S. Vadhan.
  The Complexity of Counting.
  Undergraduate Thesis, Harvard `95.
  
• S. Vadhan.
  The Complexity of Counting in Sparse, Regular, and Planar Graphs.
  SICOMP `01.
  
• S. Vadhan.
  The Complexity of Zero Knowledge.
  FSTTCS `07.
• S. Vadhan.
  Computational Complexity.
  Encyclopedia of Cryptography and Security `05.
• S. Vadhan.
  Constructing Locally Computable Extractors and Cryptosystems in the Bounded-Storage Model.
  CRYPTO `03, J. Cryptology `04.
• S. Vadhan.
  Interactive Proofs & Zero-Knowledge Proofs.
  IAS/PCMI Summer School `00.
  
• S. Vadhan.
  On Transformations of Interactive Proofs that Preserve the Prover's Complexity.
  STOC `00.
  
• S. Vadhan.
  Pseudorandomness.
  monograph in preparation for FnTTCS
  
  
• S. Vadhan.
  Rapidly Mixing Markov Chains and their Applications.
  Essay, Cambridge U. `96.
  
• S. Vadhan.
  A Study of Statistical Zero-Knowledge Proofs.
  PhD Thesis, MIT `99.  Revised 8/00.
• S. Vadhan.
  An Unconditional Study of Computational Zero Knowledge.
  FOCS `04. ECCC `06.  SICOMP `06.
  
  
• S. Vadhan.
  The Unified Theory of Pseudorandomness.
  SIGACT News `07, ICM `10.
  
  

[ Back to Salil's Home Page ] 
This page was last updated 3/29/15.