About
Ronen Shaltiel is a Professor of Computer Science at the University of Haifa. His research is in the Theory of Computer Science, with a focus on Complexity Theory and Pseudorandomness. He is also interested in the Theory of Cryptography and Coding Theory. He is a recipient of an ERC Consolidator Grant (2011) and received the Best Paper Award at the Conference on Computational Complexity (CCC) in 2005. He has served on the steering committees of the Conference on Computational Complexity (CCC) and the International Conference on Randomization and Computation (RANDOM), and was Program Committee Chair of RANDOM 2010.
Publications
- Extractors for Samplable Distributions from the Two-Source Extractor Recipe, Oh, J. & Shaltiel, R., 9 Jun 2026, STOC 2026 - Proceedings of the 58th Annual ACM Symposium on Theory of Computing. Bhaskara, A. & Czumaj, A. (eds.). Association for Computing Machinery, p. 1344-1352 9 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).
- Multiplicative Extractors for Samplable Distributions, Shaltiel, R., 29 Jul 2025, 40th Computational Complexity Conference, CCC 2025. Srinivasan, S. & Srinivasan, S. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 22. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 339).
- Extractors for Samplable Distributions with Low Min-Entropy, Ball, M., Shaltiel, R. & Silbak, J., 15 Jun 2025, STOC 2025 - Proceedings of the 57th Annual ACM Symposium on Theory of Computing. Koucky, M. & Bansal, N. (eds.). Association for Computing Machinery, p. 596-603 8 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).
- Extractors for Samplable Distributions with Polynomially Small Min-Entropy, Shaltiel, R., 2025, Proceedings - 2025 IEEE 66th Annual Symposium on Foundations of Computer Science, FOCS 2025. IEEE Computer Society, p. 934-946 13 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).
- Explicit Codes for Poly-Size Circuits and Functions That Are Hard to Sample on Low Entropy Distributions, Shaltiel, R. & Silbak, J., 10 Jun 2024, STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Mohar, B., Shinkar, I. & O�Donnell, R. (eds.). Association for Computing Machinery, p. 2028-2038 11 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).
- Non-malleable Codes with Optimal Rate for Poly-Size Circuits, Ball, M., Shaltiel, R. & Silbak, J., 2024, Advances in Cryptology – EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Joye, M. & Leander, G. (eds.). Springer Science and Business Media Deutschland GmbH, p. 33-54 22 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 14654 LNCS).
- Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle?, Shaltiel, R., Jun 2023, In: Computational Complexity. 32, 1, 5.
- Error Correcting Codes that Achieve BSC Capacity Against Channels that are Poly-Size Circuits, Shaltiel, R. & Silbak, J., 2022, Proceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022. IEEE Computer Society, p. 13-23 11 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2022-October).
- On Hardness Assumptions Needed for “Extreme High-End” PRGs and Fast Derandomization, Shaltiel, R. & Viola, E., 1 Jan 2022, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022. Braverman, M. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 116. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 215).
- Explicit uniquely decodable codes for space bounded channels that achieve list-decoding capacity, Shaltiel, R. & Silbak, J., 15 Jun 2021, STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Khuller, S. & Williams, V. V. (eds.). Association for Computing Machinery, p. 1516-1526 11 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).
- Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels, Shaltiel, R. & Silbak, J., Jun 2021, In: Computational Complexity. 30, 1, 3.
- Query complexity lower bounds for local list-decoding and hard-core predicates (Even for small rate and huge lists), Ron-Zewi, N., Shaltiel, R. & Varma, N., 1 Feb 2021, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021. Lee, J. R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 33. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 185).
- Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle?, Shaltiel, R., 1 Aug 2020, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020. Byrka, J. & Meka, R. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, APPROX10. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 176).
- Computational two-party correlation: A dichotomy for key-agreement protocols, Haitner, I., Nissim, K., Omri, E., Shaltiel, R. & Silbak, J., 2020, In: SIAM Journal on Computing. 49, 6, p. 1041-1082 42 p.
- Guest editors’ foreword, Chechik, S. & Shaltiel, R., 2019, In: Theory of Computing. 15, Special Issue, p. 1-3 3 p.
- Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs, Grinberg, A., Shaltiel, R. & Viola, E., 30 Nov 2018, Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018. Thorup, M. (ed.). IEEE Computer Society, p. 956-966 11 p. 8555172. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2018-October).
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions (extended abstract), Applebaum, B., Artemenko, S., Shaltiel, R. & Yang, G., 1 Jun 2015, 30th Conference on Computational Complexity, CCC 2015. Zuckerman, D. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 582-600 19 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 33).
- Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification, Artemenko, S. & Shaltiel, R., Mar 2014, In: Computational Complexity. 23, 1, p. 43-83 41 p.
- Mining circuit lower bound proofs for meta-algorithms, Chen, R., Kabanets, V., Kolokolova, A., Shaltiel, R. & Zuckerman, D., 2014, Proceedings - IEEE 29th Conference on Computational Complexity, CCC 2014. IEEE Computer Society, p. 262-273 12 p. 6875495. (Proceedings of the Annual IEEE Conference on Computational Complexity).
- Derandomized Parallel Repetition Theorems for Free Games, Shaltiel, R., Sep 2013, In: Computational Complexity. 22, 3, p. 565-594 30 p.
- On beating the hybrid argument, Fefferman, B., Shaltiel, R., Umans, C. & Viola, E., 2013, In: Theory of Computing. 9, 1, p. 809-843 35 p.
- On beating the hybrid argument, Fefferman, B., Shaltiel, R., Umans, C. & Viola, E., 2012, ITCS 2012 - Innovations in Theoretical Computer Science Conference. p. 468-483 16 p. (ITCS 2012 - Innovations in Theoretical Computer Science Conference).
- An introduction to randomness extractors, Shaltiel, R., 2011, Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings. PART 2 ed. p. 21-41 21 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6756 LNCS, no. PART 2).
- Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification, Artemenko, S. & Shaltiel, R., 2011, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, Proceedings. p. 377-388 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6845 LNCS).
- Simulating independence: New constructions of condensers, ramsey graphs, dispersers, and extractors, Barak, B., Kindler, G., Shaltiel, R., Sudakov, B. & Wigderson, A., 1 Apr 2010, In: Journal of the ACM. 57, 4, 20.
- Typically-correct derandomization, Shaltiel, R., 2010, In: SIGACT. 41, 2, p. 57-72
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface, Serna, M., Shaltiel, R., Jansen, K. & Rolim, J. D. P., 2010, In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6302 LNCS, p. V-VI
- Hardness amplification proofs require majority, Shaltiel, R. & Viola, E., 2010, In: SIAM Journal on Computing. 39, 7, p. 3122-3154 33 p.
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, Serna, M., Shaltiel, R., Jansen, K. & Rolim, J. D. P., 2010, Springer Berlin. 782 p.
- Reducing complexity assumptions for statistically-hiding commitment, Haitner, I., Horvitz, O., Katz, J., Koo, C. Y., Morselli, R. & Shaltiel, R., Jul 2009, In: Journal of Cryptology. 22, 3, p. 283-310 28 p.
- Strong parallel repetition theorem for free projection games, Barak, B., Rao, A., Raz, R., Rosen, R. & Shaltiel, R., 2009, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings. p. 352-365 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5687 LNCS).
- Low-End Uniform Hardness versus Randomness Tradeoffs for AM, Shaltiel, R. & Umans, C., 2009, In: SIAM Journal on Computing. 39, 3, p. 1006-1037 32 p.
- How to get more mileage from randomness extractors, Shaltiel, R., Sep 2008, In: Random Structures and Algorithms. 33, 2, p. 157-186 30 p.
- Hardness amplification proofs require majority, Shaltiel, R. & Viola, E., 2008, STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing. Association for Computing Machinery (ACM), p. 589-598 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).
- Proceedings Twenty-Second Annual IEEE Conference on Computational Complexity: Preface, Downey, R., Khot, S., Klivans, A., Lutz, J., Miltersen, P. B., Pitassi, T., Shaltiel, R., Szegedy, M., Thierauf, T. & Yao, A. C. C., 2007, In: Proceedings of the Annual IEEE Conference on Computational Complexity. p. 8 1 p., 4262741.
- Low-end uniform hardness vs. randomness tradeoffs for AM, Shaltiel, R. & Umans, C., 2007, STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing. p. 430-439 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).
- Pseudorandomness for approximate counting and sampling, Shaltiel, R. & Umans, C., Dec 2006, In: Computational Complexity. 15, 4, p. 298-341 44 p.
- 2-Source dispersers for sub-polynomial entropy and ramsay graphs beating the frankl-wilson construction, Barak, B., Rao, A., Shaltiel, R. & Wigderson, A., 2006, STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 671-680 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 2006).
- Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors, Barak, B., Kindler, G., Shaltiel, R., Sudakov, B. & Wigderson, A., 2005, In: Proceedings of the Annual ACM Symposium on Theory of Computing. p. 1-10 10 p.
- Deterministic extractors for bit-fixing sources by obtaining an independent seed, Gabizon, A., Raz, R. & Shaltiel, R., 2004, In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. p. 394-403 10 p.
- Constant-Round Oblivious Transfer in the Bounded Storage Model, Ding, Y. Z., Harnik, D., Rosen, A. & Shaltie, R., 2004, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Naor, M. (ed.). Springer Verlag, p. 446-472 27 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2951).
- Recent developments in explicit constructions of extractors, Shaltiel, R., 2004, Current Trends in Theoretical Computer Science. G. P., G. R. & A. S. (eds.). World Scientific, p. 189-228
- List-decoding of linear functions and analysis of a two-round zero-knowledge argument, Dwork, C., Shaltiel, R., Smith, A. & Trevisan, L., 2004, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Naor, M. (ed.). Springer Verlag, p. 101-120 20 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2951).
- Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games, Gutfreund, D., Shaltiel, R. & Ta-Shma, A., 2003, In: Proceedings of the Annual IEEE Conference on Computational Complexity. p. 33-47 15 p.
- True random number generators secure in a changing environment, Barak, B., Shaltiel, R. & Tromer, E., 2003, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Walter, C. D., Koc, C. K. & Paar, C. (eds.). Springer Verlag, p. 166-180 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2779).
- Recent developments in explicit constructions of extractors, Shaltiel, R., 2002, Invited survey paper. L. F. (ed.). EATCS, p. 67-95
- Streaming computation of combinatorial objects, Bar-Yossef, Z., Reingold, O., Shaltiel, R. & Trevisan, L., 2002, In: Proceedings of the Annual IEEE Conference on Computational Complexity. p. 165-174 10 p.
- Towards proving strong direct product theorems, Shaltiel, R., 2001, In: Proceedings of the Annual IEEE Conference on Computational Complexity. p. 107-117 11 p.
- Extractors and pseudo-random generators with optimal seed length, Impagliazzo, R., Shaltiel, R. & Wigderson, A., 2000, In: Conference Proceedings of the Annual ACM Symposium on Theory of Computing. p. 1-10 10 p.
- Near-optimal conversion of hardness into pseudo-randomness, Impagliazzo, R., Shaltiel, R. & Wigderson, A., 1999, In: Annual Symposium on Foundations of Computer Science - Proceedings. p. 181-190 10 p.
Education
Ronen Shaltiel received his Ph.D. in Computer Science from the Hebrew University of Jerusalem in 2002, under the supervision of Avi Wigderson. Ronen Shaltiel was a postdoctoral researcher at the Weizmann Institute of Science (2001–2004), under the guidance of Oded Goldreich and Moni Naor.
Research Areas
I study the interplay between randomness and computation. In particular, I am motivated by two fundamental questions: (1) Are randomized algorithms more powerful than deterministic algorithms? and (2) How can computers obtain high-quality random bits? Within complexity theory, these questions lead to technical problems in pseudorandomness, especially the design and analysis of pseudorandom generators, randomness extractors, and error-correcting codes.
Awards
Ronen Shaltiel is a recipient of an ERC Consolidator Grant (2011). He received the Best Paper Award at the Conference on Computational Complexity (CCC) in 2005.