• 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
Article
2018

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

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

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
2013

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

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
2010

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

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

Multi-linear formulas for permanent and determinant are of super-polynomial size

Raz, R., Apr 1 2009, In : Journal of the ACM. 56, 2, 8.

Research output: Contribution to journalArticle

76 Scopus citations

Quantum information and the pcp theorem

Raz, R., Nov 1 2009, In : Algorithmica (New York). 55, 3, p. 462-489 28 p.

Research output: Contribution to journalArticle

4 Scopus citations
2008

Analyzing linear mergers

Dvir, Z. & Raz, R., May 2008, In : Random Structures and Algorithms. 32, 3, p. 334-345 12 p.

Research output: Contribution to journalArticle

5 Scopus citations

Balancing syntactically multilinear arithmetic circuits

Raz, R. & Yehudayoff, A., Dec 1 2008, In : Computational Complexity. 17, 4, p. 515-535 21 p.

Research output: Contribution to journalArticle

35 Scopus citations

Deterministic extractors for affine sources over large fields

Gabizon, A. & Raz, R., Jul 1 2008, In : Combinatorica. 28, 4, p. 415-440 26 p.

Research output: Contribution to journalArticle

33 Scopus citations

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

Gavinsky, D., Kempe, J., Kerenidis, I., Raz, R. & De Wolf, R., Jan 1 2008, In : SIAM Journal on Computing. 38, 5, p. 1695-1708 14 p.

Research output: Contribution to journalArticle

38 Scopus citations

Resolution over linear equations and multilinear proofs

Raz, R. & Tzameret, I., Oct 1 2008, In : Annals of Pure and Applied Logic. 155, 3, p. 194-224 31 p.

Research output: Contribution to journalArticle

16 Scopus citations

Sub-constant error low degree test of almost-linear size

Moshkovitz, D. & Raz, R., 2008, In : SIAM Journal on Computing. 38, 1, p. 140-180 41 p.

Research output: Contribution to journalArticle

16 Scopus citations

The strength of multilinear proofs

Raz, R. & Tzameret, I., Oct 1 2008, In : Computational Complexity. 17, 3, p. 407-457 51 p.

Research output: Contribution to journalArticle

9 Scopus citations
2006

Deterministic extractors for bit-fixing sources by obtaining an independent seed

Gabizon, A., Raz, R. & Shaltiel, R., Dec 1 2006, In : SIAM Journal on Computing. 36, 4, p. 1072-1094 23 p.

Research output: Contribution to journalArticle

43 Scopus citations
2005

A time lower bound for satisfiability

Van Melkebeek, D. & Raz, R., Dec 8 2005, In : Theoretical Computer Science. 348, 2-3 SPEC. ISS., p. 311-320 10 p.

Research output: Contribution to journalArticle

5 Scopus citations

Bounded-depth frege lower bounds for weaker pigeonhole principles

Buresh-Oppenheim, J., Beame, P., Pitassi, T., Raz, R. & Sabharwal, A., May 23 2005, In : SIAM Journal on Computing. 34, 2, p. 261-276 16 p.

Research output: Contribution to journalArticle

1 Scopus citations

Deterministic polynomial identity testing in non-commutative models

Raz, R. & Shpilka, A., Apr 1 2005, In : Computational Complexity. 14, 1, p. 1-19 19 p.

Research output: Contribution to journalArticle

86 Scopus citations
2004

Distance labeling in graphs

Gavoille, C., Peleg, D., Pérennes, S. & Raz, R., Oct 1 2004, In : Journal of Algorithms. 53, 1, p. 85-112 28 p.

Research output: Contribution to journalArticle

132 Scopus citations

ProMate: A structure based prediction program to identify the location of protein-protein binding sites

Neuvirth, H., Raz, R. & Schreiber, G., Apr 16 2004, In : Journal of Molecular Biology. 338, 1, p. 181-199 19 p.

Research output: Contribution to journalArticle

342 Scopus citations

Regular resolution lower bounds for the weak pigeonhole principle

Pitassi, T. & Raz, R., Jan 1 2004, In : Combinatorica. 24, 3, p. 503-524 22 p.

Research output: Contribution to journalArticle

5 Scopus citations

Resolution lower bounds for the weak pigeonhole principle

Raz, R., Mar 2004, In : Journal of the ACM. 51, 2, p. 115-138 24 p.

Research output: Contribution to journalArticle

30 Scopus citations
2003

Approximating CVP to within almost-polynomial factors is NP-hard

Dinur, I., Kindler, G., Raz, R. & Safra, S., Oct 13 2003, In : Combinatorica. 23, 2, p. 205-243 39 p.

Research output: Contribution to journalArticle

75 Scopus citations

Lower bounds for matrix product in bounded depth circuits with arbitrary gates

Raz, R. & Sphlika, A., Feb 1 2003, In : SIAM Journal on Computing. 32, 2, p. 488-513 26 p.

Research output: Contribution to journalArticle

15 Scopus citations

On the complexity of matrix product

Raz, R., Aug 1 2003, In : SIAM Journal on Computing. 32, 5, p. 1356-1369 14 p.

Research output: Contribution to journalArticle

29 Scopus citations
2002

Extracting all the randomness and reducing the error in Trevisan's extractors

Raz, R., Reingold, O. & Vadhan, S., Aug 2002, In : Journal of Computer and System Sciences. 65, 1, p. 97-128 32 p.

Research output: Contribution to journalArticle

70 Scopus citations
1 Scopus citations
2000

On interpolation and automatization for Frege systems

Bonet, M. L., Pitassi, T. & Raz, R., Apr 1 2000, In : SIAM Journal on Computing. 29, 6, p. 1939-1967 29 p.

Research output: Contribution to journalArticle

80 Scopus citations

The BNS-Chung criterion for multi-party communication complexity

Raz, R., Jan 1 2000, In : Computational Complexity. 9, 2, p. 113-122 10 p.

Research output: Contribution to journalArticle

41 Scopus citations

VC-dimension of sets of permutations

Raz, R., Jan 1 2000, In : Combinatorica. 20, 2, p. 241-255 15 p.

Research output: Contribution to journalArticle

10 Scopus citations
1999

Separation of the monotone NC hierarchy

Raz, R. & McKenzie, P., Jan 1 1999, In : Combinatorica. 19, 3, p. 403-435 33 p.

Research output: Contribution to journalArticle

73 Scopus citations
1998

A parallel repetition theorem

Raz, R., Jan 1 1998, In : SIAM Journal on Computing. 27, 3, p. 763-803 41 p.

Research output: Contribution to journalArticle

426 Scopus citations

Lower bounds on the distortion of embedding finite metric spaces in graphs

Rabinovich, Y. & Raz, R., Jan 1998, In : Discrete and Computational Geometry. 19, 1, p. 79-94 16 p.

Research output: Contribution to journalArticle

63 Scopus citations
1997

Lower bounds for cutting planes proofs with small coefficients

Bonet, M., Pitassi, T. & Raz, R., Sep 1997, In : Journal of Symbolic Logic. 62, 3, p. 708-728 21 p.

Research output: Contribution to journalArticle

69 Scopus citations

Separation of the monotone NC hierarchy

Raz, R. & McKenzie, P., Dec 1 1997, In : Annual Symposium on Foundations of Computer Science - Proceedings. p. 234-243 10 p.

Research output: Contribution to journalArticle

28 Scopus citations
1995

Fourier analysis for probabilistic communication complexity

Raz, R., Sep 1 1995, In : Computational Complexity. 5, 3-4, p. 205-221 17 p.

Research output: Contribution to journalArticle

29 Scopus citations

On the "log rank"-conjecture in communication complexity

Raz, R. & Spieker, B., Dec 1 1995, In : Combinatorica. 15, 4, p. 567-588 22 p.

Research output: Contribution to journalArticle

25 Scopus citations

Super-logarithmic depth lower bounds via the direct sum in communication complexity

Karchmer, M., Raz, R. & Wigderson, A., Sep 1 1995, In : Computational Complexity. 5, 3-4, p. 191-204 14 p.

Research output: Contribution to journalArticle

64 Scopus citations
1992

Monotone Circuits for Matching Require Linear Depth

Raz, R. & Wigderson, A., Jan 7 1992, In : Journal of the ACM (JACM). 39, 3, p. 736-744 9 p.

Research output: Contribution to journalArticle

80 Scopus citations