• 4698 Citations
  • 34 h-Index
1989 …2020

Research output per year

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

Research Output

2020

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

2019

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

2 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

2 Scopus citations
2018

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

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

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

7 Scopus citations

Fast learning requires good memory: A time-space lower bound for parity learning

Raz, R., Dec 2018, In : Journal of the ACM. 66, 1, 3.

Research output: Contribution to journalArticle

4 Scopus citations
2017

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

12 Scopus citations

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

11 Scopus citations
2016

Bounds on 2-query Locally Testable Codes with affine tests

Kol, G. & Raz, R., Aug 1 2016, In : Information Processing Letters. 116, 8, p. 521-525 5 p.

Research output: Contribution to journalArticle

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

14 Scopus citations

Exponential separation of information and communication for boolean functions

Ganor, A., Kol, G. & Raz, R., Nov 2016, In : Journal of the ACM. 63, 5, 46.

Research output: Contribution to journalArticle

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

13 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

5 Scopus citations

Preface

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

Research output: Contribution to journalEditorial

2015

Arthur-Merlin streaming complexity

Gur, T. & Raz, R., Jul 28 2015, In : Information and Computation. 243, p. 145-165 21 p.

Research output: Contribution to journalArticle

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

18 Scopus citations

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

Dinitz, M., Kortsarz, G. & Raz, R., Dec 1 2015, In : ACM Transactions on Algorithms. 12, 2, 25.

Research output: Contribution to journalArticle

11 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

15 Scopus citations
2014

Competing-provers protocols for circuit evaluation

Kol, G. & Raz, R., Aug 9 2014, In : Theory of Computing. 10, p. 107-131 25 p.

Research output: Contribution to journalArticle

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

34 Scopus citations

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

Kalai, Y. T., Razy, R. & Rothblumz, R. D., Jan 1 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

55 Scopus citations

Nonmalleable extractors with short seeds and applications to privacy amplification

Cohen, G., Raz, R. & Segev, G., Jan 1 2014, In : SIAM Journal on Computing. 43, 2, p. 450-476 27 p.

Research output: Contribution to journalArticle

16 Scopus citations

Pseudorandom generators for regular branching programs

Braverman, M., Rao, A., Raz, R. & Yehudayoff, A., Jan 1 2014, In : SIAM Journal on Computing. 43, 3, p. 973-986 14 p.

Research output: Contribution to journalArticle

15 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., Moore, C., Devanur, N. R. & Rolim, J. D. P. (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

Two sides of the coin problem

Cohen, G., Ganor, A. & Raz, R., Sep 1 2014, Leibniz International Proceedings in Informatics, LIPIcs. Jansen, K., Moore, C., Devanur, N. R. & Rolim, J. D. P. (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

8 Scopus citations
2013

Arthur-Merlin streaming complexity

Gur, T. & Raz, R., Jul 23 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 proceedingConference contribution

12 Scopus citations

Average-case lower bounds for formula size

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

25 Scopus citations

Competing provers protocols for circuit evaluation

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

4 Scopus citations

Delegation for bounded space

Kalai, Y. T., Raz, R. & Rothblum, R. D., Jul 11 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 proceedingConference contribution

33 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., Sep 26 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 proceedingConference contribution

17 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

31 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

58 Scopus citations

Tensor-Rank and lower bounds for arithmetic formulas

Raz, R., Nov 1 2013, In : Journal of the ACM. 60, 6, 40.

Research output: Contribution to journalArticle

20 Scopus citations
2012

A strong parallel repetition theorem for projection games on expanders

Raz, R. & Rosen, R., Sep 26 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 proceedingConference contribution

8 Scopus citations

Bounds on locally testable codes with unique tests

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

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

1 Scopus citations

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

Dinitz, M., Kortsarz, G. & Raz, R., Dec 1 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

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

16 Scopus citations
2011

A counterexample to strong parallel repetition

Raz, R., Jul 20 2011, In : SIAM Journal on Computing. 40, 3, p. 771-777 7 p.

Research output: Contribution to journalArticle

17 Scopus citations

Memory delegation

Chung, K. M., Kalai, Y. T., Liu, F. H. & Raz, R., Aug 29 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

80 Scopus citations

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

Raz, R. & Yehudayoff, A., Jan 1 2011, In : Journal of Computer and System Sciences. 77, 1, p. 167-190 24 p.

Research output: Contribution to journalArticle

14 Scopus citations

PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability

Dinur, I., Fischer, E., Kindler, G., Raz, R. & Safra, S., Sep 1 2011, In : Computational Complexity. 20, 3, p. 413-504 92 p.

Research output: Contribution to journalArticle

10 Scopus citations

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 journalEditorial

2010

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

1 Scopus citations

Pseudorandom generators for regular branching programs

Braverman, M., Rao, A., Raz, R. & Yehudayoff, A., Dec 1 2010, Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010. 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

30 Scopus citations

Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size

Moshkovitz, D. & Raz, R., Jan 1 2010, In : Computational Complexity. 19, 3, p. 367-422 56 p.

Research output: Contribution to journalArticle

6 Scopus citations

Tensor-rank and lower bounds for arithmetic formulas

Raz, R., Jul 23 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

23 Scopus citations

Two-query PCP with subconstant error

Moshkovitz, D. & Raz, R., Jun 1 2010, In : Journal of the ACM. 57, 5, 29.

Research output: Contribution to journalArticle

64 Scopus citations
2009

Lower bounds and sparations for constant depth multilinear circuits

Raz, R. & Yehudayoff, A., Jun 2009, In : Computational Complexity. 18, 2, p. 171-207 37 p.

Research output: Contribution to journalArticle

71 Scopus citations