Online papers (Click here for thesis and surveys).

Papers are sorted by conference year. Please write to me if you think that some versions are not updated.

• On beating the hybrid argument.
• Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola.
• Accepted to ITCS 2012.

[Full version (pdf) (23/2/2012)].

• Dispersers for affine sources with sub-polynomial entropy.
• Ronen Shaltiel.
• In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, (FOCS), 2011.

[Proceedings version], [Full version (3/10/2011)].

• Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification.
• Sergei Artemenko, Ronen Shaltiel.
• In Proceedings of the 15th International Workshop on Randomization and Approximation Techniques in Computer Science, (RANDOM), 2011.
• Accepted to computational complexity.

[Full version (pdf) (28/2/2012)]. [Powerpoint presentation].

• Derandomized parallel repetition theorems for free games.
• Ronen Shaltiel.
• In Proceedings of the 25th Annual Conference on Computational Complexity, (CCC), 2010.
• Accepted to Computational Complexity.

[Proceedings version (pdf)], [Full version (pdf) (3/2/2011)], [powerpoint presentation].

• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds.
• Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel.
• In Proceedings of the 13th International Workshop on Randomization and Approximation Techniques in Computer Science, (RANDOM), 2009.
• Accepted to Computational Complexity (special issue of RANDOM 2009).

[Proceedings version (pdf)], [Full version (pdf) (16/8/2010)], [powerpoint presentation].

• Strong parallel repetition for free projection games.
• Boaz Barak, Anup Rao, Ran Raz, Ricky Rosen, Ronen Shaltiel.
• In Proceedings of the 13th International Workshop on Randomization and Approximation Techniques in Computer Science, (RANDOM), 2009.

[Full version (pdf)].

• Weak derandomization of weak algorithms: explicit versions of Yao's lemma.
•  Ronen Shaltiel.
• In Proceedings of the 24th Annual Conference on Computational Complexity, (CCC), 2009.
• Computational Complexity 20(1):87-143, 2011.

[Proceedings version (pdf)],  [Full version (pdf) (7/3/2010)], [Powerpoint presentation].

• On the (im)possibility of Arthur-Merlin witness hiding protocols.
• Iftach Haitner, Alon Rosen, Ronen Shaltiel.
• In Proceedings of the 6th Theory of Cryptography Conference, (TCC), 2009.

[Proceedings version (pdf)].

• Increasing the output length of zero-error dispersers.
• Ariel Gabizon, Ronen Shaltiel.
• In Proceedings of the 12th International Workshop on Randomization and Approximation Techniques in Computer Science, (RANDOM), 2008.
• Accepted to Random Structures & Algorithms.

[Proceedings version (ps)], [Proceedings version (pdf)], [Full version (pdf)].

• Hardness amplification proofs require majority.
• Ronen Shaltiel, Emanuele Viola.
• In Proceedings of the 40th Annual ACM Symposium on the Theory of Computing, (STOC), 2008.
• SIAM journal on computing (SICOMP) 39(7):3122-3154 , 2010.

[Proceedings version (ps)], [Proceedings version (pdf)], [Full version (ps) (21/9/2008)], [Full version (pdf) (21/9/2008)], [Powerpoint presentation].

• Low-end uniform hardness vs. randomness tradeoffs for AM.
• Ronen Shaltiel, Christopher Umans.
• In Proceedings of the 39th Annual ACM Symposium on the Theory of Computing, (STOC), 2007.
• SIAM journal on computing (SICOMP) 39(3):1006-1037, 2009. (Special issue of STOC 2007).

[Proceedings version (ps)], [Proceedings version (pdf)], [Full version (ps) (25/5/2008)], [Full version (pdf) (25/5/2008)], [Powerpoint presentation].

• How to get more mileage from randomness extractors.
• Ronen Shaltiel.
• In Proceedings of the 21st Annual Conference on Computational Complexity, (CCC), 2006.
• Random Structures & Algorithms 33(2):57-186, 2008.

[Proceedings version (ps)], [Full version (ps) (27/5/2008)], [Full version (pdf) (27/5/2008)], [Powerpoint presentation].

• 2-source dispersers for $n^{o(1)}$ entropy and Ramsey graphs beating the Frankl-Wilson construction.
• Boaz Barak, Anup Rao, Ronen Shaltiel, Avi Wigderson.
• In Proceedings of the 38th Annual ACM Symposium on the Theory of Computing, (STOC), 2006.

[Proceedings version (ps)], [Proceedings version (pdf)], [Full version (ps) (22/8/2008)], [Full version (pdf) (22/8/2008)], [Powerpoint presentation].

• If NP languages are hard on the worst-case then it is easy to find their hard instances.
• Danny Gutfreund, Ronen Shaltiel, Amnon Ta-Shma.
• In Proceedings of the 20th Annual Conference on Computational Complexity, (CCC), 2005.
• Computational Complexity 16(4):412-441, 2007. (Special issue on average case complexity).

[Proceedings version (ps)], [Full version (pdf) (27/5/2008)], [Powerpoint presentation].

• Reducing complexity assumptions for statistically-hiding commitment.
• Iftach Haitner, Omer Horvitz, Jonathan Katz, Chiu-Yuen Koo, Ruggero Morselli, Ronen Shaltiel.
• In Eurocrypt, 2005.
• Journal of Cryptology 22(3):283-310, 2009.

[Proceedings version (ps)], [Full version (ps) (7/8/2007)], [Full version (pdf)].

• Simulating independence: New constructions of condensers, Ramsey graphs, dispersers and extractors.
• Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson.
• In Proceedings of the 37th Annual ACM Symposium on the Theory of Computing, (STOC), 2005.
• Journal of the ACM 57(4), 2010.

[Proceedings version (ps)], [Proceedings version (pdf)], [Full version (ps) (20/5/2009)], [Full version (pdf) (20/5/2009)], [Powerpoint presentation].

• Pseudorandomness for approximate counting and sampling.
• Ronen Shaltiel, Christopher Umans.
• In Proceedings of the 20th Annual Conference on Computational Complexity, (CCC), 2005.
• Computational Complexity 15(4):298-341, 2007. (Special issue of selected papers from CCC 2005).

Winner of best paper award CCC 2005.

[Proceedings version (ps)],[Full version (ps) (19/10/06)], [Full version (pdf)], [Powerpoint presentation].

• Determininstic extractors for bit-fixing sources by obtaining an independent seed.
• Ariel Gabizon, Ran Raz, Ronen Shaltiel.
• In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, (FOCS), 2004.
• SIAM journal on computing (SICOMP) 36(4):1072-1094, 2006. (Special issue on randomness and complexity).

[Proceedings version (ps)], [Full version (ps) (18/8/05)], [Powerpoint presentation].

• Non-interactive timestamping in the bounded storage model.
• Tal Moran, Ronen Shaltiel, Amnon Ta-Shma.
• In Proceedings of the 24th Annual International Cryptology Conference, (CRYPTO), 2004.
• Journal of Cryptology 22(2):189-226, 2009.

[Proceedings version (ps)], [Full version (ps) (15/1/09)], [Full version (pdf) (15/1/09)].

• Constant round oblivious transfer in the bounded storage model.
• Yan Zong Ding, Danny Harnik, Alon Rosen, Ronen Shaltiel.
• In Proceedings of the 1st Theory of Cryptography Conference, (TCC), 2004.
• Journal of Cryptology 20(2):165-202, 2007.

[Proceedings version (ps)], [Full version (ps) (19/10/06)], [Powerpoint presentation].

• List Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument.
• Cynthia Dwork, Adam Smith, Ronen Shaltiel, Luca Trevisan.
• In Proceedings of the 1st Theory of Cryptography Conference, (TCC), 2004.

[Proceedings version (ps)].

• Computational analogues of entropy.
• Boaz Barak, Ronen Shaltiel, Avi Wigderson.
• In Proceedings of the 7th International Workshop on Randomization and Approximation Techniques in Computer Science, (RANDOM), 2003.

[Full version (pdf)]. (See erratum note in abstract).

• True random number generators secure in a changing environment.
• Boaz Barak, Ronen Shaltiel, Eran Tromer.
• In Proceedings of Cryptographic Hardness and Embedded Systems, (CHES), 2003.

[Proceedings version (ps)].

• Uniform hardness vs. randomness for Arthur-Merlin games.
• Danny Gutfreund, Ronen Shaltiel, Amnon Ta-Shma.
• In Proceedings of the 18th Annual Conference on Computational Complexity, (CCC), 2003.
• Computational Complexity 12(3-4):85-130, 2003.

[Proceedings version (ps)], [Full version (ps)], [Powerpoint presentation].

• Streaming computation of combinatorial objects.
• Ziv Bar-Yossef, Omer Reingold, Ronen Shaltiel, Luca Trevisan.
• In Proceedings of the 17th Annual Conference on Computational Complexity, (CCC), 2002.

[Proceedings version], [Full version (ps)].

• Simple extractors for all min-entropies and a new pseudorandom generator.
• Ronen Shaltiel, Christopher Umans.
• In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, (FOCS), 2001.
• Journal of the ACM 52(2):172-216, 2005.

[Proceedings version (ps)], [Full version (ps)], [Powerpoint presentation].

• Towards proving strong direct product theorems.
• Ronen Shaltiel.
• In Proceedings of the 16th Annual Conference on Computational Complexity, (CCC), 2001.
• Computational Complexity 12(1-2):1-22, 2003.

[Proceedings version (ps)], [Full version (ps)], [Full version (pdf)].

• Extracting randomness via repeated condensing.
• Omer Reingold, Ronen Shaltiel, Avi Wigderson.
• In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, (FOCS), 2000.
• SIAM journal on computing (SICOMP) 35(5):1185-1209, 2006.

[Proceedings version (ps)], [Full version (ps) (9/10/05)].

• Reducing the seed length in the Nisan-Wigderson generator.
• Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson.
• Combinatorica 26(6):647-681, 2006.

This is a full version that appends the two conference papers below.

[Full version (ps) (23/4/06)].

• Extractors and pesudo-random generators with optimal seed length.
• Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson.
• In Proceedings of the 32nd Annual ACM Symposium on the Theory of Computing, (STOC), 2000.

[Proceedings version (ps)].

• Near optimal conversion of hardness into pseudo-randomness. 
• Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson.
• In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, (FOCS), 1999.

[Proceedings version (ps)].

 

Thesis and Surveys

• An introduction to randomness extractors.
• Ronen Shaltiel.
• Invited paper for ICALP 2011.

      [Full version (pdf)], [Powerpoint presentation]

• Typically-correct derandomization.
• Ronen Shaltiel.
• SIGACT news complexity theory column 66, SIGACT News: 41(2):57-72, 2010.

This is a survey article on recent work that studies relaxed notions of derandomization in which the detereminitsic simulation of a randomized algorithm is allowed to err on some inputs.

[Full version (pdf)].

• Recent developments in extractors.
• Ronen Shaltiel.

This is a survey paper I wrote on randomness extractors and focuses on recent explicit constructions.

[Full version (ps)], [PowerPoint presentation (initially given at IAS workshop on expanders 2006)]

Appeared as a chapter in the book:

Current trends in theoretical computer science.
The Challenge of the New Century.
Vol 1: Algorithms and Complexity 
Edited by G Paun (Romanian Academy, Romania & Rovira I Virgili University, Spain), G Rozenberg (University of Leiden, The Netherlands & University of Colorado, USA) & A Salomaa (Turku Centre for Computer Science, Finland)

A preliminary version appeared in Bulletin of the European Association for Theoretical Computer Science, Volume 77, June 2002, pages 67-95. 

• Explicit constructions of pseudorandom generators and extractors.
• Ronen Shaltiel.
• Ph.D. Thesis, Hebrew University, 2001.

[Full version (ps)].

• Derandomizing BPP.

This is a manuscript I wrote based on a course by Avi Wigderson in the Hebrew University 1998. It is somewhat outdated. However, the presentation level is suitable for students who are just starting. Over the years some people found it helpful. Use at your own risk! Note that as this is the first latex document I wrote it is somewhat rough and does not contain a bibliography.

[Full version (ps)].