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.
- 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 57th 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.
[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.
- Accepted to Computational Complexity.
[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.
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)].
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)].