 | 2009 |
|---|
| 115 |       | Boaz Barak,
Anup Rao,
Ran Raz,
Ricky Rosen,
Ronen Shaltiel:
Strong Parallel Repetition Theorem for Free Projection Games.
APPROX-RANDOM 2009: 352-365 |
| 114 | | Yael Tauman Kalai,
Ran Raz:
Probabilistically Checkable Arguments.
CRYPTO 2009: 143-159 |
| 113 | | Ran Raz:
Quantum Information and the PCP Theorem.
Algorithmica 55(3): 462-489 (2009) |
| 112 | | Ran Raz,
Amir Yehudayoff:
Lower Bounds and Separations for Constant Depth Multilinear Circuits.
Computational Complexity 18(2): 171-207 (2009) |
| 111 | | Ran Raz:
Multi-linear formulas for permanent and determinant are of super-polynomial size.
J. ACM 56(2): (2009) |
| 2008 |
|---|
| 110 | | Ran Raz,
Amir Yehudayoff:
Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors.
FOCS 2008: 273-282 |
| 109 | | Dana Moshkovitz,
Ran Raz:
Two Query PCP with Sub-Constant Error.
FOCS 2008: 314-323 |
| 108 | | Ran Raz:
A Counterexample to Strong Parallel Repetition.
FOCS 2008: 369-373 |
| 107 | | Yael Tauman Kalai,
Ran Raz:
Interactive PCP.
ICALP (2) 2008: 536-547 |
| 106 | | Ran Raz,
Amir Yehudayoff:
Lower Bounds and Separations for Constant Depth Multilinear Circuits.
IEEE Conference on Computational Complexity 2008: 128-139 |
| 105 | | Ran Raz:
Elusive functions and lower bounds for arithmetic circuits.
STOC 2008: 711-720 |
| 104 | | Ran Raz,
Iddo Tzameret:
Resolution over linear equations and multilinear proofs.
Ann. Pure Appl. Logic 155(3): 194-224 (2008) |
| 103 | | Ariel Gabizon,
Ran Raz:
Deterministic extractors for affine sources over large fields.
Combinatorica 28(4): 415-440 (2008) |
| 102 | | Ran Raz,
Iddo Tzameret:
The Strength of Multilinear Proofs.
Computational Complexity 17(3): 407-457 (2008) |
| 101 | | Ran Raz,
Amir Yehudayoff:
Balancing Syntactically Multilinear Arithmetic Circuits.
Computational Complexity 17(4): 515-535 (2008) |
| 100 | | Ran Raz:
Elusive Functions and Lower Bounds for Arithmetic Circuits.
Electronic Colloquium on Computational Complexity (ECCC) 15(001): (2008) |
| 99 | | Ran Raz,
Amir Yehudayoff:
Lower Bounds and Separations for Constant Depth Multilinear Circuits.
Electronic Colloquium on Computational Complexity (ECCC) 15(006): (2008) |
| 98 | | Ran Raz:
A Counterexample to Strong Parallel Repetition.
Electronic Colloquium on Computational Complexity (ECCC) 15(018): (2008) |
| 97 | | Dana Moshkovitz,
Ran Raz:
Two Query PCP with Sub-Constant Error.
Electronic Colloquium on Computational Complexity (ECCC) 15(071): (2008) |
| 96 | | Zeev Dvir,
Ran Raz:
Analyzing linear mergers.
Random Struct. Algorithms 32(3): 334-345 (2008) |
| 95 | | Dana Moshkovitz,
Ran Raz:
Sub-Constant Error Low Degree Test of Almost-Linear Size.
SIAM J. Comput. 38(1): 140-180 (2008) |
| 94 | | Ran Raz,
Amir Shpilka,
Amir Yehudayoff:
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits.
SIAM J. Comput. 38(4): 1624-1647 (2008) |
| 93 | | Dmitry Gavinsky,
Julia Kempe,
Iordanis Kerenidis,
Ran Raz,
Ronald de Wolf:
Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography.
SIAM J. Comput. 38(5): 1695-1708 (2008) |
| 2007 |
|---|
| 92 | | Ran Raz,
Amir Shpilka,
Amir Yehudayoff:
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits.
FOCS 2007: 438-448 |
| 91 | | Dmitry Gavinsky,
Julia Kempe,
Iordanis Kerenidis,
Ran Raz,
Ronald de Wolf:
Exponential separations for one-way quantum communication complexity, with applications to cryptography.
STOC 2007: 516-525 |
| 90 | | Ran Raz,
Iddo Tzameret:
Resolution over Linear Equations and Multilinear Proofs
CoRR abs/0708.1529: (2007) |
| 89 | | Dana Moshkovitz,
Ran Raz:
Sub-Constant Error Probabilistically Checkable Proof of Almost Linear Size.
Electronic Colloquium on Computational Complexity (ECCC) 14(026): (2007) |
| 88 | | Yael Tauman Kalai,
Ran Raz:
Interactive PCP.
Electronic Colloquium on Computational Complexity (ECCC) 14(031): (2007) |
| 87 | | Ran Raz,
Iddo Tzameret:
Resolution over Linear Equations and Multilinear Proofs.
Electronic Colloquium on Computational Complexity (ECCC) 14(078): (2007) |
| 86 | | Ran Raz,
Amir Yehudayoff:
Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors.
Electronic Colloquium on Computational Complexity (ECCC) 14(085): (2007) |
| 2006 |
|---|
| 85 | | Yael Tauman Kalai,
Ran Raz:
Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP.
FOCS 2006: 355-366 |
| 84 | | Dana Moshkovitz,
Ran Raz:
Sub-constant error low degree test of almost-linear size.
STOC 2006: 21-30 |
| 83 | | Iordanis Kerenidis,
Ran Raz:
The one-way communication complexity of the Boolean Hidden Matching Problem
CoRR abs/quant-ph/0607173: (2006) |
| 82 | | Ran Raz,
Iddo Tzameret:
The Strength of Multilinear Proofs
Electronic Colloquium on Computational Complexity (ECCC)(001): (2006) |
| 81 | | Ran Raz,
Amir Shpilka,
Amir Yehudayoff:
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits.
Electronic Colloquium on Computational Complexity (ECCC) 13(060): (2006) |
| 80 | | Iordanis Kerenidis,
Ran Raz:
The one-way communication complexity of the Boolean Hidden Matching Problem.
Electronic Colloquium on Computational Complexity (ECCC) 13(087): (2006) |
| 79 | | Ariel Gabizon,
Ran Raz,
Ronen Shaltiel:
Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed.
SIAM J. Comput. 36(4): 1072-1094 (2006) |
| 78 | | Ran Raz:
Separation of Multilinear Circuit and Formula Size.
Theory of Computing 2(1): 121-135 (2006) |
| 2005 |
|---|
| 77 | | Ariel Gabizon,
Ran Raz:
Deterministic Extractors for Affine Sources over Large Fields.
FOCS 2005: 407-418 |
| 76 | | Ran Raz:
Quantum Information and the PCP Theorem.
FOCS 2005: 459-468 |
| 75 | | Ran Raz:
Extractors with weak random seeds.
STOC 2005: 11-20 |
| 74 | | Ran Raz,
Amir Shpilka:
Deterministic polynomial identity testing in non-commutative models.
Computational Complexity 14(1): 1-19 (2005) |
| 73 | | Zeev Dvir,
Ran Raz:
Analyzing Linear Mergers
Electronic Colloquium on Computational Complexity (ECCC)(025): (2005) |
| 72 | | Ran Raz:
Quantum Information and the PCP Theorem
Electronic Colloquium on Computational Complexity (ECCC)(038): (2005) |
| 71 | | Dana Moshkovitz,
Ran Raz:
Sub-Constant Error Low Degree Test of Almost Linear Size
Electronic Colloquium on Computational Complexity (ECCC)(086): (2005) |
| 70 | | Ariel Gabizon,
Ran Raz:
Deterministic Extractors for Affine Sources over Large Fields
Electronic Colloquium on Computational Complexity (ECCC)(108): (2005) |
| 69 | | Ariel Gabizon,
Ran Raz,
Ronen Shaltiel:
Deterministic Extractors for Bit-fixing Sources by Obtaining an Independent Seed
Electronic Colloquium on Computational Complexity (ECCC)(109): (2005) |
| 68 | | Dieter van Melkebeek,
Ran Raz:
A time lower bound for satisfiability.
Theor. Comput. Sci. 348(2-3): 311-320 (2005) |
| 2004 |
|---|
| 67 | | Yevgeniy Dodis,
Ariel Elbaz,
Roberto Oliveira,
Ran Raz:
Improved Randomness Extraction from Two Independent Sources.
APPROX-RANDOM 2004: 334-344 |
| 66 | | Ran Raz:
Multilinear-NC neq Multilinear-NC.
FOCS 2004: 344-351 |
| 65 | | Ariel Gabizon,
Ran Raz,
Ronen Shaltiel:
Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed.
FOCS 2004: 394-403 |
| 64 | | Dieter van Melkebeek,
Ran Raz:
A Time Lower Bound for Satisfiability.
ICALP 2004: 971-982 |
| 63 | | Ran Raz,
Amir Shpilka:
Deterministic Polynomial Identity Testing in Non-Commutative Models.
IEEE Conference on Computational Complexity 2004: 215-222 |
| 62 | | Ran Raz,
Amir Shpilka:
On the Power of Quantum Proofs.
IEEE Conference on Computational Complexity 2004: 260-274 |
| 61 | | Ran Raz:
Multi-linear formulas for permanent and determinant are of super-polynomial size.
STOC 2004: 633-641 |
| 60 | | Toniann Pitassi,
Ran Raz:
Regular Resolution Lower Bounds For The Weak Pigeonhole Principle.
Combinatorica 24(3): 503-524 (2004) |
| 59 | | Ran Raz:
Multilinear-NC1 != Multilinear-NC2
Electronic Colloquium on Computational Complexity (ECCC)(042): (2004) |
| 58 | | Ran Raz:
Extractors with Weak Random Seeds
Electronic Colloquium on Computational Complexity (ECCC)(099): (2004) |
| 57 | | Ran Raz:
Resolution lower bounds for the weak pigeonhole principle.
J. ACM 51(2): 115-138 (2004) |
| 56 | | Cyril Gavoille,
David Peleg,
Stéphane Pérennes,
Ran Raz:
Distance labeling in graphs.
J. Algorithms 53(1): 85-112 (2004) |
| 55 | | Joshua Buresh-Oppenheim,
Paul Beame,
Toniann Pitassi,
Ran Raz,
Ashish Sabharwal:
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles.
SIAM J. Comput. 34(2): 261-276 (2004) |
| 2003 |
|---|
| 54 | | Ran Raz:
P != NP, propositional proof complexity, and resolution lower bounds for the weak pigeonhole principle
CoRR cs.CC/0304041: (2003) |
| 53 | | Irit Dinur,
Guy Kindler,
Ran Raz,
Shmuel Safra:
Approximating CVP to Within Almost-Polynomial Factors is NP-Hard.
Combinatorica 23(2): 205-243 (2003) |
| 52 | | Ran Raz:
Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size
Electronic Colloquium on Computational Complexity (ECCC)(067): (2003) |
| 51 | | Tzvika Hartman,
Ran Raz:
On the distribution of the number of roots of polynomials and explicit weak designs.
Random Struct. Algorithms 23(3): 235-263 (2003) |
| 50 | | Ran Raz,
Amir Shpilka:
Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates.
SIAM J. Comput. 32(2): 488-513 (2003) |
| 49 | | Ran Raz:
On the Complexity of Matrix Product.
SIAM J. Comput. 32(5): 1356-1369 (2003) |
| 2002 |
|---|
| 48 | | Josh Buresh-Oppenheim,
Paul Beame,
Toniann Pitassi,
Ran Raz,
Ashish Sabharwal:
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles.
FOCS 2002: 583-592 |
| 47 | | Ran Raz:
Resolution Lower Bounds for the Weak Pigeonhole Principle.
IEEE Conference on Computational Complexity 2002: 3 |
| 46 | | Ran Raz:
On the complexity of matrix product.
STOC 2002: 144-151 |
| 45 | | Ran Raz:
Resolution lower bounds for the weak pigeonhole principle.
STOC 2002: 553-562 |
| 44 | | Ran Raz:
On the Complexity of Matrix Product
Electronic Colloquium on Computational Complexity (ECCC)(012): (2002) |
| 43 | | Josh Buresh-Oppenheim,
Paul Beame,
Toniann Pitassi,
Ran Raz,
Ashish Sabharwal:
Bounded-depth Frege lower bounds for weaker pigeonhole principles
Electronic Colloquium on Computational Complexity (ECCC)(023): (2002) |
| 42 | | Ran Raz,
Omer Reingold,
Salil P. Vadhan:
Extracting all the Randomness and Reducing the Error in Trevisan's Extractors.
J. Comput. Syst. Sci. 65(1): 97-128 (2002) |
| 2001 |
|---|
| 41 | | Cyril Gavoille,
David Peleg,
Stephane Perennes,
Ran Raz:
Distance labeling in graphs.
SODA 2001: 210-219 |
| 40 | | Toniann Pitassi,
Ran Raz:
Regular resolution lower bounds for the weak pigeonhole principle.
STOC 2001: 347-355 |
| 39 | | Oded Lachish,
Ran Raz:
Explicit lower bound of 4.5n - o(n) for boolena circuits.
STOC 2001: 399-408 |
| 38 | | Ran Raz,
Amir Shpilka:
Lower bounds for matrix product, in bounded depth circuits with arbitrary gates.
STOC 2001: 409-418 |
| 37 | | Ran Raz:
Resolution Lower Bounds for the Weak Pigeonhole Principle
Electronic Colloquium on Computational Complexity (ECCC) 8(21): (2001) |
| 2000 |
|---|
| 36 |  | Tzvika Hartman,
Ran Raz:
On the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors.
ICALP Satellite Workshops 2000: 3-22 |
| 35 | | Danny Harnik,
Ran Raz:
Higher lower bounds on monotone size.
STOC 2000: 378-387 |
| 34 | | Ran Raz:
VC-Dimension of Sets of Permutations.
Combinatorica 20(2): 241-255 (2000) |
| 33 | | Ran Raz:
The BNS-Chung criterion for multi-party communication complexity.
Computational Complexity 9(2): 113-122 (2000) |
| 32 | | Ran Raz,
Amir Shpilka:
Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates
Electronic Colloquium on Computational Complexity (ECCC) 7(29): (2000) |
| 31 | | Tzvika Hartman,
Ran Raz:
On the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors
Electronic Colloquium on Computational Complexity (ECCC) 7(44): (2000) |
| 30 | | Maria Luisa Bonet,
Toniann Pitassi,
Ran Raz:
On Interpolation and Automatization for Frege Systems.
SIAM J. Comput. 29(6): 1939-1967 (2000) |
| 1999 |
|---|
| 29 | | Ran Raz,
Omer Reingold,
Salil P. Vadhan:
Error Reduction for Extractors.
FOCS 1999: 191-201 |
| 28 | | Ran Raz,
Omer Reingold,
Salil P. Vadhan:
Extracting all the Randomness and Reducing the Error in Trevisan's Extractors.
STOC 1999: 149-158 |
| 27 | | Ran Raz,
Omer Reingold:
On Recycling the Randomness of States in Space Bounded Computation.
STOC 1999: 159-168 |
| 26 | | Irit Dinur,
Eldar Fischer,
Guy Kindler,
Ran Raz,
Shmuel Safra:
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability.
STOC 1999: 29-40 |
| 25 | | Ran Raz:
Exponential Separation of Quantum and Classical Communication Complexity.
STOC 1999: 358-367 |
| 24 | | Ran Raz,
Pierre McKenzie:
Separation of the Monotone NC Hierarchy.
Combinatorica 19(3): 403-435 (1999) |
| 23 | | Ran Raz,
Omer Reingold,
Salil P. Vadhan:
Extracting All the Randomness and Reducing the Error in Trevisan's Extractors
Electronic Colloquium on Computational Complexity (ECCC)(46): (1999) |
| 22 | | Ran Raz,
Gábor Tardos,
Oleg Verbitsky,
Nikolai K. Vereshchagin:
Arthur-Merlin Games in Boolean Decision Trees.
J. Comput. Syst. Sci. 59(2): 346-372 (1999) |
| 1998 |
|---|
| 21 | | Ran Raz,
Gábor Tardos,
Oleg Verbitsky,
Nikolai K. Vereshchagin:
Arthur-Merlin Games in Boolean Decision Trees.
IEEE Conference on Computational Complexity 1998: 58-67 |
| 20 | | Yuri Rabinovich,
Ran Raz:
Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs.
Discrete & Computational Geometry 19(1): 79-94 (1998) |
| 19 | | Irit Dinur,
Eldar Fischer,
Guy Kindler,
Ran Raz,
Shmuel Safra:
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability
Electronic Colloquium on Computational Complexity (ECCC) 5(66): (1998) |
| 18 | | Ran Raz:
A Parallel Repetition Theorem.
SIAM J. Comput. 27(3): 763-803 (1998) |
| 1997 |
|---|
| 17 | | Ran Raz,
Pierre McKenzie:
Separation of the Monotone NC Hierarchy.
FOCS 1997: 234-243 |
| 16 | | Maria Luisa Bonet,
Toniann Pitassi,
Ran Raz:
No Feasible Interpolation for TC0-Frege Proofs.
FOCS 1997: 254-263 |
| 15 | | Itzhak Parnafes,
Ran Raz,
Avi Wigderson:
Direct Product Results and the GCD Problem, in Old and New Communication Models.
STOC 1997: 363-372 |
| 14 | | Ran Raz,
Shmuel Safra:
A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP.
STOC 1997: 475-484 |
| 13 | | Ran Raz,
Gábor Tardos,
Oleg Verbitsky,
Nikolai K. Vereshchagin:
Arthur-Merlin Games in Boolean Decision Trees
Electronic Colloquium on Computational Complexity (ECCC) 4(54): (1997) |
| 12 | | Maria Luisa Bonet,
Toniann Pitassi,
Ran Raz:
Lower Bounds for Cutting Planes Proofs with Small Coefficients.
J. Symb. Log. 62(3): 708-728 (1997) |
| 1995 |
|---|
| 11 | | Ran Raz:
A parallel repetition theorem.
STOC 1995: 447-456 |
| 10 | | Maria Luisa Bonet,
Toniann Pitassi,
Ran Raz:
Lower bounds for cutting planes proofs with small coefficients.
STOC 1995: 575-584 |
| 9 | | Ran Raz,
Boris Spieker:
On the ``Log Rank''-Conjecture in Communication Complexity.
Combinatorica 15(4): 567-588 (1995) |
| 8 | | Mauricio Karchmer,
Ran Raz,
Avi Wigderson:
Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity.
Computational Complexity 5(3/4): 191-204 (1995) |
| 7 | | Ran Raz:
Fourier Analysis for Probabilistic Communication Complexity.
Computational Complexity 5(3/4): 205-221 (1995) |
| 1994 |
|---|
| 6 | | Russell Impagliazzo,
Ran Raz,
Avi Wigderson:
A Direct Product Theorem.
Structure in Complexity Theory Conference 1994: 88-96 |
| 1993 |
|---|
| 5 | | Ran Raz,
Boris Spieker:
On the ``log rank''-Conjecture in Communication Complexity
FOCS 1993: 168-176 |
| 1992 |
|---|
| 4 | | Ran Raz,
Avi Wigderson:
Monotone Circuits for Matching Require Linear Depth.
J. ACM 39(3): 736-744 (1992) |
| 1991 |
|---|
| 3 | | Mauricio Karchmer,
Ran Raz,
Avi Wigderson:
Super-logarithmic Depth Lower Bounds via Direct Sum in Communication Coplexity.
Structure in Complexity Theory Conference 1991: 299-304 |
| 1990 |
|---|
| 2 | | Ran Raz,
Avi Wigderson:
Monotone Circuits for Matching Require Linear Depth
STOC 1990: 287-292 |
| 1989 |
|---|
| 1 | | Ran Raz,
Avi Wigderson:
Probabilistic Communication Complexity of Boolean Relations (Extended Abstract)
FOCS 1989: 562-567 |
