• 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

Filter
Conference contribution
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
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

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

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
2015

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

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

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

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

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

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
2009

Probabilistically checkable arguments

Kalai, Y. T. & Raz, R., Oct 29 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

34 Scopus citations

Strong parallel repetition theorem for free projection games

Barak, B., Rao, A., Raz, R., Rosen, R. & Shaltiel, R., Nov 6 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

15 Scopus citations
2008

A counterexample to strong parallel repetition

Raz, R., Dec 31 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 proceedingConference contribution

28 Scopus citations

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

18 Scopus citations

Interactive PCP

Kalai, Y. T. & Raz, R., Aug 14 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

37 Scopus citations

Lower bounds and separations for constant depth multilinear circuits

Raz, R. & Yehudayoff, A., Sep 23 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

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

Raz, R. & Yehudayofft, A., Dec 30 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

Two query PCP with sub-constant error

Moshkovitz, D. & Raz, R., Dec 30 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
2007

A lower bound for the size of syntactically multilinear arithmetic circuits

Raz, R., Shpilka, A. & Yehudayoff, A., Dec 1 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 proceedingConference contribution

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

65 Scopus citations
2006

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

15 Scopus citations
2005

Deterministic extractors for affine sources over large fields

Gabizon, A. & Raz, R., Dec 1 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 proceedingConference contribution

31 Scopus citations

Quantum information and the PCP theorem

Raz, R., Dec 1 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

7 Scopus citations
2001

Distance labeling in graphs

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

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

98 Scopus citations
2000

Higher lower bounds on monotone size

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

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

19 Scopus citations
1998

Arthur-Merlin games in Boolean decision trees

Raz, R., Tardos, G., Verbitsky, O. & Vereshagin, N., Jan 1 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 proceedingConference contribution

2 Scopus citations