• Source: Scopus
  • Calculated based on no. of publications stored in Pure and citations from Scopus
1989 …2020

Research activity per year

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

Search results

  • 2020

    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

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

    8 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

    3 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

    3 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

    10 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

    14 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

    13 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

    15 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

    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

    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

    19 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

    16 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

    36 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

    58 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

    9 Scopus citations
  • 2013

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

    13 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

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

    19 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

    32 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

    63 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., 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

    83 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., 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

    32 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

    24 Scopus citations
  • 2009

    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

    36 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

    15 Scopus citations
  • 2008

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

    19 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

    41 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
  • 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
  • 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
  • 2007

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

    73 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., 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., 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., 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 proceedingConference contribution

    101 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

    21 Scopus citations