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

Research activity per year

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

Search results

  • Conference contribution

    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 proceedingConference contribution

    Open Access
    25 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 proceedingConference contribution

    71 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 proceedingConference contribution

    33 Scopus citations
  • Interactive channel capacity

    Kol, G. & Raz, R., Jul 11 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 proceedingConference contribution

    67 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 proceedingConference contribution

    47 Scopus citations
  • 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 proceedingConference 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 proceedingConference 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 proceedingConference contribution

  • 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 proceedingConference contribution

    88 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 proceedingConference contribution

  • 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 proceedingConference contribution

    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 proceedingConference 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 proceedingConference contribution

    6 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 proceedingConference 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 proceedingConference 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 proceedingConference contribution

    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 proceedingConference contribution

    20 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 proceedingConference contribution

  • 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 proceedingConference contribution

    1 Scopus citations
  • Parallel repetition of two prover games

    Raz, R., Aug 10 2010, Proceedings - 25th Annual IEEE Conference on Computational Complexity, CCC 2010. p. 3-6 4 p. 5497862. (Proceedings of the Annual IEEE Conference on Computational Complexity).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    4 Scopus citations
  • Probabilistically checkable arguments

    Kalai, Y. T. & Raz, R., 2009, Advances in Cryptology - CRYPTO 2009 - 29th Annual International Cryptology Conference, Proceedings. p. 143-159 17 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5677 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    39 Scopus citations
  • Probabilistic communication complexity of Boolean relations

    Raz, R. & Wigderson, A., 1989, Annual Symposium on Foundations of Computer Science (Proceedings). Publ by IEEE, p. 562-567 6 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    32 Scopus citations
  • Pseudorandom generators for regular branching programs

    Braverman, M., Rao, A., Raz, R. & Yehudayoff, A., 2010, Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010. IEEE Computer Society, p. 40-47 8 p. 5670950. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    36 Scopus citations
  • Quantum information and the PCP theorem

    Raz, R., 2005, Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005. p. 459-468 10 p. 1530738. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2005).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    9 Scopus citations
  • Quantum logspace algorithm for powering matrices with bounded norm

    Girish, U., Raz, R. & Zhan, W., Jul 1 2021, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021. Bansal, N., Merelli, E. & Worrell, J. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 73. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 198).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    1 Scopus citations
  • Quantum versus randomized communication complexity, with efficient players

    Girish, U., Raz, R. & Tal, A., 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, 54. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 185).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    2 Scopus citations
  • Space pseudorandom generators by communication complexity lower bounds

    Ganor, A. & Raz, R., Sep 1 2014, Leibniz International Proceedings in Informatics, LIPIcs. Jansen, K., Rolim, J. D. P., Devanur, N. R. & Moore, C. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 692-703 12 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 28).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    5 Scopus citations
  • 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).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    19 Scopus citations
  • Sub-constant error low degree test of almost-linear size

    Moshkovitz, D. & Raz, R., 2006, STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery (ACM), p. 21-30 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 2006).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    13 Scopus citations
  • Succinct non-interactive zero-knowledge proofs with preprocessing for LOGSNP

    Kalai, Y. T. & Razt, R., Dec 1 2006, 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006. p. 355-366 12 p. 4031371. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    17 Scopus citations
  • Super-logarithmic depth lower bounds via direct sum in communication complexity

    Karchmer, M., Raz, R. & Wigderson, A., Dec 1 1991, Proc 6 Annu Struct Complexity Theor. Publ by IEEE, p. 299-304 6 p. (Proc 6 Annu Struct Complexity Theor).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    26 Scopus citations
  • Tensor-rank and lower bounds for arithmetic formulas

    Raz, R., 2010, STOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing. p. 659-666 8 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    26 Scopus citations
  • The random-query model and the memory-bounded coupon collector

    Raz, R. & Zhan, W., Jan 2020, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020. Vidick, T. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 20. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 151).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Time-space hardness of learning sparse parities

    Kol, G., Raz, R. & Tal, A., Jun 19 2017, STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. McKenzie, P., King, V. & Hatami, H. (eds.). Association for Computing Machinery, p. 1067-1080 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F128415).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    18 Scopus citations
  • Time-space lower bounds for two-pass learning

    Garg, S., Raz, R. & Tal, A., Jul 1 2019, 34th Computational Complexity Conference, CCC 2019. Shpilka, A. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, (Leibniz International Proceedings in Informatics, LIPIcs; vol. 137).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    4 Scopus citations
  • Time-space tradeoffs for distinguishing distributions and applications to security of Goldreich's PRG

    Garg, S., Kothari, P. K. & Raz, R., Aug 1 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, APPROX21. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 176).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Two query PCP with sub-constant error

    Moshkovitz, D. & Raz, R., 2008, Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008. p. 314-323 10 p. 4690965. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    20 Scopus citations
  • Two sides of the coin problem

    Cohen, G., Ganor, A. & Raz, R., Sep 1 2014, Leibniz International Proceedings in Informatics, LIPIcs. Jansen, K., Rolim, J. D. P., Devanur, N. R. & Moore, C. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 618-629 12 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 28).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    13 Scopus citations
  • Welfare Maximization with Limited Interaction

    Alon, N., Nisan, N., Raz, R. & Weinstein, O., Dec 11 2015, Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015. IEEE Computer Society, p. 1499-1512 14 p. 7354469. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2015-December).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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 journalEditorialpeer-review

  • Preface

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

    Research output: Contribution to journalEditorialpeer-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 journalEditorialpeer-review

  • 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 journalReview articlepeer-review

    17 Scopus citations