Ran Raz
Contact Expert

View Scopus Profile

Ran Raz

Calculated based on number of publications stored in Pure and citations from Scopus
1989 …2023

Research activity per year

If you made any changes in Pure these will be visible here soon.

Search results

  • Review article

    On the Distribution of the Number of Roots of Polynomials and Explicit Weak Designs

    Hartman, T. & Raz, R., Oct 2003, In: Random Structures and Algorithms. 23, 3, p. 235-263 29 p.

    Research output: Contribution to journal › Review article › peer-review

    19 Scopus citations
  • Editorial

    Foreword

    Balcázar, J., Buhrman, H., Crescenzi, P., Gottlob, G., Pitassi, T., Raz, R., Sántha, M. & Wagner, K., Jan 1 1997, In: Proceedings of the Annual IEEE Conference on Computational Complexity. p. VIII 612294.

    Research output: Contribution to journal › Editorial › peer-review

  • Preface

    Raz, R., May 1 2016, In: Leibniz International Proceedings in Informatics, LIPIcs. 50, p. ix

    Research output: Contribution to journal › Editorial › peer-review

  • Preface

    Atserias, A., Beigel, R., Gavinsky, D., Kaufman, T., Koebler, J., Pitassi, T., Raghavendra, P., Rao, A., Ran, R., Reingold, O. & Saxena, N., 2011, In: Proceedings of the Annual IEEE Conference on Computational Complexity. p. 8 1 p., 5959829.

    Research output: Contribution to journal › Editorial › peer-review

  • Conference contribution

    A candidate for a strong separation of information and communication

    Braverman, M., Ganor, A., Kol, G. & Raz, R., Jan 1 2018, 9th Innovations in Theoretical Computer Science, ITCS 2018. Karlin, A. R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 11. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 94).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    3 Scopus citations

  • A counterexample to strong parallel repetition

    Raz, R., 2008, Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008. p. 369-373 5 p. 4690970. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    32 Scopus citations

  • A lower bound for adaptively-secure collective coin-flipping protocols

    Kalai, Y. T., Komargodski, I. & Raz, R., Oct 1 2018, 32nd International Symposium on Distributed Computing, DISC 2018. Schmid, U. & Widder, J. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 34. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 121).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    5 Scopus citations

  • A lower bound for the size of syntactically multilinear arithmetic circuits

    Raz, R., Shpilka, A. & Yehudayoff, A., 2007, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007. p. 438-448 11 p. 4389514. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    9 Scopus citations

  • Arthur-Merlin games in Boolean decision trees

    Raz, R., Tardos, G., Verbitsky, O. & Vereshagin, N., 1998, Proceedings - 13th Annual IEEE Conference on Computational Complexity, CCC 1998. IEEE Computer Society, p. 58-67 10 p. 694591. (Proceedings of the Annual IEEE Conference on Computational Complexity).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    3 Scopus citations

  • Arthur-Merlin streaming complexity

    Gur, T. & Raz, R., 2013, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings. PART 1 ed. p. 528-539 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7965 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    14 Scopus citations

  • A strong parallel repetition theorem for projection games on expanders

    Raz, R. & Rosen, R., 2012, Proceedings - 2012 IEEE 27th Conference on Computational Complexity, CCC 2012. p. 247-257 11 p. 6243401. (Proceedings of the Annual IEEE Conference on Computational Complexity).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    10 Scopus citations

  • A time-space lower bound for a large class of learning problems

    Raz, R., Nov 10 2017, Proceedings - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017. IEEE Computer Society, p. 732-742 11 p. 8104105. (Annual Symposium on Foundations of Computer Science - Proceedings; vol. 2017-October).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    31 Scopus citations

  • Average-case lower bounds for formula size

    Komargodski, I. & Raz, R., 2013, STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing. p. 171-180 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    31 Scopus citations

  • Block rigidity: Strong multiplayer parallel repetition implies super-linear lower bounds for turing machines

    Mittal, K. & Raz, R., Feb 1 2021, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021. Lee, J. R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 71. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 185).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    3 Scopus citations

  • Bounds on locally testable codes with unique tests

    Kol, G. & Raz, R., 2012, ITCS 2012 - Innovations in Theoretical Computer Science Conference. p. 190-202 13 p. (ITCS 2012 - Innovations in Theoretical Computer Science Conference).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    1 Scopus citations

  • Competing provers protocols for circuit evaluation

    Kol, G. & Raz, R., 2013, ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science. p. 473-484 12 p. (ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    4 Scopus citations

  • Delegation for bounded space

    Kalai, Y. T., Raz, R. & Rothblum, R. D., 2013, STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing. p. 565-574 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    51 Scopus citations

  • Deterministic extractors for affine sources over large fields

    Gabizon, A. & Raz, R., 2005, Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005. p. 407-418 12 p. 1530733. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2005).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    33 Scopus citations

  • Direct product theorem

    Impagliazzo, R., Raz, R. & Wigderson, A., Dec 1 1994, Proceedings of the IEEE Annual Structure in Complexity Theory Conference. Anon (ed.). Publ by IEEE, p. 88-96 9 p. (Proceedings of the IEEE Annual Structure in Complexity Theory Conference).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    12 Scopus citations

  • Distance labeling in graphs

    Gavoille, C., Peleg, D., Pérennes, S. & Raz, R., 2001, Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. p. 210-219 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    107 Scopus citations

  • Efficient multiparty protocols via log-depth threshold formulae (Extended abstract)

    Cohen, G., Damgård, I. B., Ishai, Y., Kölker, J., Miltersen, P. B., Raz, R. & Rothblum, R. D., 2013, Advances in Cryptology, CRYPTO 2013 - 33rd Annual Cryptology Conference, Proceedings. PART 2 ed. p. 185-202 18 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8043 LNCS, no. PART 2).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    23 Scopus citations

  • Eliminating Intermediate Measurements Using Pseudorandom Generators

    Girish, U. & Raz, R., Jan 1 2022, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022. Braverman, M. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 76. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 215).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

  • Elusive functions and lower bounds for arithmetic circuits

    Raz, R., 2008, STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 711-720 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    23 Scopus citations

  • Exponential separation of communication and external information

    Ganor, A., Kol, G. & Raz, R., Jun 19 2016, STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. Mansour, Y. & Wichs, D. (eds.). Association for Computing Machinery, p. 977-986 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 19-21-June-2016).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    16 Scopus citations

  • Exponential separation of information and communication

    Ganor, A., Kol, G. & Raz, R., Dec 7 2014, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. IEEE Computer Society, p. 176-185 10 p. 6979002. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    36 Scopus citations

  • Exponential separation of information and communication for boolean functions

    Ganor, A., Kol, G. & Raz, R., Jun 14 2015, STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 557-566 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 14-17-June-2015).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    20 Scopus citations

  • Exponential separations for one-way quantum communication complexity, with applications to cryptography

    Gavinsky, D., Kempe, J., Kerenidis, I., Raz, R. & De Wolf, R., 2007, STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing. p. 516-525 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    93 Scopus citations

  • Extractor-Based time-Space lower bounds for learning

    Garg, S., Raz, R. & Tal, A., Jun 20 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Henzinger, M., Kempe, D. & Diakonikolas, I. (eds.). Association for Computing Machinery, p. 297-310 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    25 Scopus citations

  • Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning

    Raz, R., Dec 14 2016, Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016. IEEE Computer Society, p. 266-275 10 p. 7782939. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2016-December).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    24 Scopus citations

  • Higher lower bounds on monotone size

    Harnik, D. & Raz, R., 2000, Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000. p. 378-387 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    28 Scopus citations

  • How to delegate computations: The power of no-signaling proofs

    Kalai, Y. T., Razy, R. & Rothblumz, R. D., 2014, STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 485-494 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    79 Scopus citations

  • Improved average-case lower bounds for demorgan formula size

    Komargodski, I., Raz, R. & Tal, A., Dec 1 2013, Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013. p. 588-597 10 p. 6686195

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    33 Scopus citations

  • Interactive channel capacity

    Kol, G. & Raz, R., 2013, STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing. p. 715-724 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    70 Scopus citations

  • Interactive PCP

    Kalai, Y. T. & Raz, R., 2008, Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings. PART 2 ed. p. 536-547 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5126 LNCS, no. PART 2).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    49 Scopus citations

  • Is Untrusted Randomness Helpful?

    Girish, U., Raz, R. & Zhan, W., Jan 1 2023, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023. Kalai, Y. T. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 56. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 251).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

  • Label cover instances with large girth and the hardness of approximating basic k-spanner

    Dinitz, M., Kortsarz, G. & Raz, R., 2012, Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings. PART 1 ed. p. 290-301 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7391 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    6 Scopus citations

  • Lower bounds and separations for constant depth multilinear circuits

    Raz, R. & Yehudayoff, A., 2008, Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008. p. 128-139 12 p. 4558817. (Proceedings of the Annual IEEE Conference on Computational Complexity).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    16 Scopus citations

  • Lower bounds for XOR of forrelations

    Girish, U., Raz, R. & Zhan, W., Sep 1 2021, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021. Wootters, M. & Sanita, L. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 52. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 207).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    2 Scopus citations

  • Memory delegation

    Chung, K. M., Kalai, Y. T., Liu, F. H. & Raz, R., 2011, Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Proceedings. p. 151-168 18 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6841 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    92 Scopus citations

  • Memory-sample lower bounds for learning parity with noise

    Garg, S., Kothari, P. K., Liu, P. & Raz, R., Sep 1 2021, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021. Wootters, M. & Sanita, L. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 60. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 207).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    3 Scopus citations

  • Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory

    Liu, Q., Raz, R. & Zhan, W., Jun 2 2023, STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing. Saha, B. & Servedio, R. A. (eds.). Association for Computing Machinery, p. 1097-1110 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access

  • Monotone circuits for matching require linear depth

    Raz, R. & Wigderson, A., 1990, Proc 22nd Annu ACM Symp Theory Comput. Publ by ACM, p. 287-292 6 p. (Proc 22nd Annu ACM Symp Theory Comput).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    30 Scopus citations

  • Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors

    Raz, R. & Yehudayofft, A., 2008, Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008. p. 273-282 10 p. 4690961. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    5 Scopus citations

  • Near-quadratic lower bounds for two-pass graph streaming algorithms

    Assadi, S. & Raz, R., Nov 2020, Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE Computer Society, p. 342-353 12 p. 9317947. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2020-November).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    15 Scopus citations

  • Non-malleable extractors with short seeds and applications to privacy amplification

    Cohen, G., Raz, R. & Segev, G., Sep 26 2012, Proceedings - 2012 IEEE 27th Conference on Computational Complexity, CCC 2012. p. 298-308 11 p. 6243406. (Proceedings of the Annual IEEE Conference on Computational Complexity).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    17 Scopus citations

  • On the `log rank' - conjecture in communication complexity

    Raz, R. & Spieker, B., Dec 1 1993, Annual Symposium on Foundatons of Computer Science (Proceedings). Anon (ed.). Publ by IEEE, p. 168-176 9 p. (Annual Symposium on Foundatons of Computer Science (Proceedings)).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    15 Scopus citations

  • On the space complexity of linear programming with preprocessing

    Kalai, Y. T., Raz, R. & Regev, O., Jan 14 2016, ITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science. Association for Computing Machinery, Inc, p. 293-300 8 p. (ITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    6 Scopus citations

  • Oracle separation of BQP and pH

    Raz, R. & Tal, A., Jun 23 2019, STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Charikar, M. & Cohen, E. (eds.). Association for Computing Machinery, p. 13-23 11 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    29 Scopus citations

  • Parallel repetition for all 3-player games over binary alphabet

    Girish, U., Holmgren, J., Mittal, K., Raz, R. & Zhan, W., Sep 6 2022, STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Leonardi, S. & Gupta, A. (eds.). Association for Computing Machinery, p. 998-1009 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    1 Scopus citations

  • Parallel repetition for the GHZ game: A simpler proof

    Girish, U., Holmgren, J., Mittal, K., Raz, R. & Zhan, W., Sep 1 2021, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021. Wootters, M. & Sanita, L. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 62. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 207).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    2 Scopus citations