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.

• Extractors for Samplable Distributions from the Two-Source Extractor Recipe.
• Justin Oh, Ronen Shaltiel.
• ECCC TR25-107, 2025.

[Full Version (pdf) (1/8/2025)].

• Extractors for Samplable Distributions with Polynomially Small Min-Entropy.
• Ronen Shaltiel.
• Accepted to FOCS 2025.

[Full Version (pdf) (24/4/2025)].

• Extractors for Samplable Distributions with Low Min-Entropy.
• Marshall Ball, Ronen Shaltiel, Jad Silbak.
• In Proceedings of the 57th Annual ACM Symposium on the Theory of Computing, (STOC), 2025.

[Full Version (pdf) (16/12/2024)], [Powerpoint Presentation].

• Multiplicative Extractors for Samplable Distributions.
• Ronen Shaltiel.
• Accepted to CCC 2025.

[Full Version (pdf) (14/5/2025)], [Powerpoint Presentation].

• Non-malleable codes with optimal rate for poly-size circuits.
• Marshall Ball, Ronen Shaltiel, Jad Silbak.
• In Proceedings of EUROCRYPT 2024.

[Full Version (pdf) (13/11/2023)].

• Explicit Codes for Poly-Size Circuits and Functions that are Hard to Sample on Low Entropy Distributions.
• Ronen Shaltiel, Jad Silbak.
• In Proceedings of the 56th Annual ACM Symposium on the Theory of Computing, (STOC), 2024.

[Full Version (pdf) (6/10/2024)].

• Error Correcting Codes that Achieve BSC Capacity Against Channels that are Poly-Size Circuits.
• Ronen Shaltiel, Jad Silbak.
• In Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science, (FOCS), 2022.

[Full Version (pdf) (23/8/2022)].

• On hardness assumptions needed for “extreme high-end” PRGs and fast derandomization.
• Ronen Shaltiel, Emanuele Viola.
• In Proceedings of the 13th Innovations in Theoretical Computer Science Conference, (ITCS), 2022.

[Full Version (pdf) (20/11/2023)], [Powerpoint Presentation], [Video (ITCS 2022)].

• Explicit uniquely decodable codes for space bounded channels that achieve list-decoding capacity.
• Ronen Shaltiel, Jad Silbak.
• In Proceedings of the 53rd Annual ACM Symposium on the Theory of Computing, (STOC), 2021.

[Full Version (pdf) (5/11/2020)], [Powerpoint Presentation]. [Video (Jad’s talk, STOC 2021)].

• Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists).
• Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma.
• In Proceedings of the 12th Innovations in Theoretical Computer Science Conference, (ITCS), 2021.
• Accepted to Theory of Computing.

[Full Version (pdf) (9/9/2020)], [Video (Nithin’s talk, ITCS 2021)].

• Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle?
• Ronen Shaltiel.
• In Proceedings of the 20th International Workshop on Randomization and Approximation Techniques in Computer Science, (RANDOM), 2020.
• Computational Complexity 32(1): 5, 2023.

[Full Version (pdf) (22/12/2022)], [Powerpoint Presentation], [Video (RANDOM 2020)].

• Quasilinear time list-decodable codes for space bounded channels.
• Swastik Kopparty, Ronen Shaltiel, Jad Silbak.
• In Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science, (FOCS), 2019.

[Full Version (pdf) (13/11/2019)], [Powerpoint Presentation], [Video (Jad’s talk, STOC 2019)].

• Channels of Small Log-Ratio Leakage and Characterization of Two-Party Differentially Private Computation.
• Iftach Haitner, Noam Mazor, Ronen Shaltiel, Jad Silbak.

• In Proceedings of the 17th Theory of Cryptography Conference, (TCC), 2019.

[Full Version (pdf)].

• Computational two-party correlation.
• Iftach Haitner, Kobbi Nissim, Eran Omri, Ronen Shaltiel, Jad Silbak.
• In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science, (FOCS), 2018.
• SIAM Journal on Computing (SICOMP) 49(6): 1041-1082, 2020.

[Full Version (pdf) (05/4/2018)], [Powerpoint Presentation], [Video (Bertinoro)].

• Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs.
• Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola.
• In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science, (FOCS), 2018.

[Full Version (pdf) (3/8/2018)], [Powerpoint Presentation], [Video (FOCS 2018)].

• Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels.
• Ronen Shaltiel, Jad Silbak.
• In Proceedings of the 16th International Workshop on Randomization and Approximation Techniques in Computer Science, (RANDOM), 2016.
• Computational Complexity 30(1): 3, 2021.

[Full Version (pdf) (17/5/2019)], [Powerpoint Presentation].

• Pseudorandomness when the odds are against you.
• Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel.
• In Proceedings of the 31st Annual Conference on Computational Complexity, (CCC), 2016.

[Proceedings version (pdf)], [Full Version (pdf) (15/3/2016)], [Video for Avi's Birthday], [Video (Simons)].

• Parallel Hashing via List-Recoverability.
• Iftach Haitner, Yuval Ishai, Eran Omri, Ronen Shaltiel.
• CRYPTO 2015.

[Proceedings version (pdf)].

• Incompressible functions, relative error extractors, and the power of nondeterministic reductions.
• Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang.
• In Proceedings of the 30th Annual Conference on Computational Complexity, (CCC), 2015.
• Computational Complexity 25(2): 349-418, 2016. (Special Issue of CCC 2015).

[Proceedings version (pdf)], [Full version (pdf) (19/4/2015)], [Powerpoint presentation].

• Mining circuit lower bound proofs for meta-algorithms.
• Ruiwen Chen, Valentine Kabanets, Antonia Kolokolova, Ronen Shaltiel, David Zuckerman.
• In Proceedings of the 29th Annual Conference on Computational Complexity, (CCC), 2014.
• Computational Complexity 24(2): 333-392, 2015. (Special issue of CCC 2014).

[Full version (pdf) (25/6/2014)]

• Pseudorandom generators with optimal seed length for non-boolean poly-size circuits.
• Sergei Artemenko, Ronen Shaltiel.
• In Proceedings of the 6th Annual Symposium on the Theory of Computing, (STOC), 2014.
• ACM Trans. Comput. Theory (ToCT) 9(2): 6:1-6:26, 2017.

[Proceedings version (pdf)], [Full version (pdf) (19/4/2015)]. [Powerpoint presentation].

• Invertible zero-error dispersers and defective memory with stuck-at errors.
• Ariel Gabizon, Ronen Shaltiel.
• In Proceedings of the 16th International Workshop on Randomization and Approximation Techniques in Computer Science, (RANDOM), 2012.

[Full version (pdf) (10/6/2012)], [Powerpoint presentation].

· On beating the hybrid argument.

• Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola.
• In Proceedings of the 3rd Innovations in Theoretical Computer Science (ITCS), 2012.
• Theory of Computing 9(26), 2013.

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

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

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

• 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.
• Computational Complexity 23(1): 43-83, 2014.

[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.
• Computational Complexity 22(3): 565-594, 2013.

[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.

• Computational Complexity 21(1):3-61, 2012. (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.
• Accepted to Computational Complexity.

[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.
• Random Structures & Algorithms 40(1):74-104, 2012.

[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.
• Annals of Math 176(3):1483-1544, 2012.

[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 Proceedings of 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)].