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 since 08/07 are marked  or , respectively.  If you have trouble reading any of the files, please send me email: MyFirstName AT eecs.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.

• 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.
  
• 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.
  
  
• 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.
  
• 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.
  
  
• V. Guruswami, S. Vadhan.
  A Lower Bound on List Size for List Decoding.
  RANDOM `05.
  
• I. Haitner, M. Nguyen, S.J. Ong, O. Reingold, S. Vadhan.
  Statistically Hiding Commitments and Statistical Zero-Knowledge Arguments from Any One-Way Function.
  Manuscript, 2007.
  
  
• 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.
  
• D. Lewin, S. Vadhan.
  Checking Polynomial Identities over any Field: Towards a Derandomization?
  STOC `98.
  
  
• C.-J. Lu, O. Reingold, S. Vadhan, A. Wigderson.
  Extractors: Optimal up to Constant Factors.
  STOC `03.
• 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.
• 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.
  
  
• 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.
  
• D. Ron, A. Rosenfeld, S. Vadhan.
  The Hardness of the Expected Decision Depth Problem.
  IPL `08.
  
  
• 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, 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.
  
• 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.
  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.
  
  

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