Ran Raz

Gillat Kol, Ran Raz: Competing provers protocols for circuit evaluation. ITCS 2013: 473-484

Tom Gur, Ran Raz: Arthur-Merlin Streaming Complexity. CoRR abs/1302.0418 (2013)

Gillat Kol, Ran Raz: Interactive Channel Capacity. Electronic Colloquium on Computational Complexity (ECCC) 20: 1 (2013)

Tom Gur, Ran Raz: Arthur-Merlin Streaming Complexity. Electronic Colloquium on Computational Complexity (ECCC) 20: 20 (2013)

Ilan Komargodski, Ran Raz, Avishay Tal: Improved Average-Case Lower Bounds for DeMorgan Formula Size. Electronic Colloquium on Computational Complexity (ECCC) 20: 58 (2013)

Anat Ganor, Ran Raz: Space Pseudorandom Generators by Communication Complexity Lower Bounds. Electronic Colloquium on Computational Complexity (ECCC) 20: 64 (2013)

Ran Raz, Ricky Rosen: A Strong Parallel Repetition Theorem for Projection Games on Expanders. IEEE Conference on Computational Complexity 2012: 247-257

Gil Cohen, Ran Raz, Gil Segev: Non-malleable Extractors with Short Seeds and Applications to Privacy Amplification. IEEE Conference on Computational Complexity 2012: 298-308

Michael Dinitz, Guy Kortsarz, Ran Raz: Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner. ICALP (1) 2012: 290-301

Gillat Kol, Ran Raz: Bounds on locally testable codes with unique tests. ITCS 2012: 190-202

Michael Dinitz, Guy Kortsarz, Ran Raz: Label Cover instances with large girth and the hardness of approximating basic k-spanner. CoRR abs/1203.0224 (2012)

Ilan Komargodski, Ran Raz: Average-Case Lower Bounds for Formula Size. Electronic Colloquium on Computational Complexity (ECCC) 19: 62 (2012)

Anat Ganor, Ilan Komargodski, Ran Raz: The Spectrum of Small DeMorgan Formulas. Electronic Colloquium on Computational Complexity (ECCC) 19: 174 (2012)

Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra: PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability. Computational Complexity 20(3): 413-504 (2011)

Ran Raz, Amir Yehudayoff: Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors. J. Comput. Syst. Sci. 77(1): 167-190 (2011)

Ran Raz: A Counterexample to Strong Parallel Repetition. SIAM J. Comput. 40(3): 771-777 (2011)

Kai-Min Chung, Yael Tauman Kalai, Feng-Hao Liu, Ran Raz: Memory Delegation. CRYPTO 2011: 151-168

Gil Cohen, Ran Raz, Gil Segev: Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification. Electronic Colloquium on Computational Complexity (ECCC) 18: 96 (2011)

Gillat Kol, Ran Raz: Competing Provers Protocols for Circuit Evaluation. Electronic Colloquium on Computational Complexity (ECCC) 18: 122 (2011)

Kai-Min Chung, Yael Tauman Kalai, Feng-Hao Liu, Ran Raz: Memory Delegation. IACR Cryptology ePrint Archive 2011: 273 (2011)

Dana Moshkovitz, Ran Raz: Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size. Computational Complexity 19(3): 367-422 (2010)

Dana Moshkovitz, Ran Raz: Two-query PCP with subconstant error. J. ACM 57(5) (2010)

Ran Raz: Elusive Functions and Lower Bounds for Arithmetic Circuits. Theory of Computing 6(1): 135-177 (2010)

Ran Raz: Parallel Repetition of Two Prover Games (Invited Survey). IEEE Conference on Computational Complexity 2010: 3-6

Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff: Pseudorandom Generators for Regular Branching Programs. FOCS 2010: 40-47

Ran Raz: Tensor-rank and lower bounds for arithmetic formulas. STOC 2010: 659-666

Shira Kritchman, Ran Raz: The Surprise Examination Paradox and the Second Incompleteness Theorem. CoRR abs/1011.4974 (2010)

Ran Raz: Tensor-Rank and Lower Bounds for Arithmetic Formulas. Electronic Colloquium on Computational Complexity (ECCC) 17: 2 (2010)

Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff: Pseudorandom Generators for Regular Branching Programs. Electronic Colloquium on Computational Complexity (ECCC) 17: 35 (2010)

Ran Raz: A Strong Parallel Repetition Theorem for Projection Games on Expanders. Electronic Colloquium on Computational Complexity (ECCC) 17: 141 (2010)

Ran Raz, Ricky Rosen: A Strong Parallel Repetition Theorem for Projection Games on Expanders. Electronic Colloquium on Computational Complexity (ECCC) 17: 142 (2010)

Ran Raz: Quantum Information and the PCP Theorem. Algorithmica 55(3): 462-489 (2009)

Ran Raz, Amir Yehudayoff: Lower Bounds and Separations for Constant Depth Multilinear Circuits. Computational Complexity 18(2): 171-207 (2009)

Ran Raz: Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM 56(2) (2009)

Boaz Barak, Anup Rao, Ran Raz, Ricky Rosen, Ronen Shaltiel: Strong Parallel Repetition Theorem for Free Projection Games. APPROX-RANDOM 2009: 352-365

Yael Tauman Kalai, Ran Raz: Probabilistically Checkable Arguments. CRYPTO 2009: 143-159

Gillat Kol, Ran Raz: Locally Testable Codes Analogues to the Unique Games Conjecture Do Not Exist. Electronic Colloquium on Computational Complexity (ECCC) 16: 128 (2009)

Gillat Kol, Ran Raz: Bounds on 2-Query Locally Testable Codes with Affine Tests. Electronic Colloquium on Computational Complexity (ECCC) 16: 138 (2009)

Ran Raz, Iddo Tzameret: Resolution over linear equations and multilinear proofs. Ann. Pure Appl. Logic 155(3): 194-224 (2008)

Ran Raz, Iddo Tzameret: The Strength of Multilinear Proofs. Computational Complexity 17(3): 407-457 (2008)

Ran Raz, Amir Yehudayoff: Balancing Syntactically Multilinear Arithmetic Circuits. Computational Complexity 17(4): 515-535 (2008)

Ariel Gabizon, Ran Raz: Deterministic extractors for affine sources over large fields. Combinatorica 28(4): 415-440 (2008)

Zeev Dvir, Ran Raz: Analyzing linear mergers. Random Struct. Algorithms 32(3): 334-345 (2008)

Dana Moshkovitz, Ran Raz: Sub-Constant Error Low Degree Test of Almost-Linear Size. SIAM J. Comput. 38(1): 140-180 (2008)

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)

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)

Ran Raz, Amir Yehudayoff: Lower Bounds and Separations for Constant Depth Multilinear Circuits. IEEE Conference on Computational Complexity 2008: 128-139

Ran Raz, Amir Yehudayoff: Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors. FOCS 2008: 273-282

Dana Moshkovitz, Ran Raz: Two Query PCP with Sub-Constant Error. FOCS 2008: 314-323

Ran Raz: A Counterexample to Strong Parallel Repetition. FOCS 2008: 369-373

Yael Tauman Kalai, Ran Raz: Interactive PCP. ICALP (2) 2008: 536-547

Ran Raz: Elusive functions and lower bounds for arithmetic circuits. STOC 2008: 711-720

Ran Raz: Elusive Functions and Lower Bounds for Arithmetic Circuits. Electronic Colloquium on Computational Complexity (ECCC) 15(001) (2008)

Ran Raz, Amir Yehudayoff: Lower Bounds and Separations for Constant Depth Multilinear Circuits. Electronic Colloquium on Computational Complexity (ECCC) 15(006) (2008)

Ran Raz: A Counterexample to Strong Parallel Repetition. Electronic Colloquium on Computational Complexity (ECCC) 15(018) (2008)

Dana Moshkovitz, Ran Raz: Two Query PCP with Sub-Constant Error. Electronic Colloquium on Computational Complexity (ECCC) 15(071) (2008)

Ran Raz, Amir Shpilka, Amir Yehudayoff: A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. FOCS 2007: 438-448

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

Ran Raz, Iddo Tzameret: Resolution over Linear Equations and Multilinear Proofs. CoRR abs/0708.1529 (2007)

Dana Moshkovitz, Ran Raz: Sub-Constant Error Probabilistically Checkable Proof of Almost Linear Size. Electronic Colloquium on Computational Complexity (ECCC) 14(026) (2007)

Yael Tauman Kalai, Ran Raz: Interactive PCP. Electronic Colloquium on Computational Complexity (ECCC) 14(031) (2007)

Ran Raz, Iddo Tzameret: Resolution over Linear Equations and Multilinear Proofs. Electronic Colloquium on Computational Complexity (ECCC) 14(078) (2007)

Ran Raz, Amir Yehudayoff: Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors. Electronic Colloquium on Computational Complexity (ECCC) 14(085) (2007)

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)

Ran Raz: Separation of Multilinear Circuit and Formula Size. Theory of Computing 2(1): 121-135 (2006)

Yael Tauman Kalai, Ran Raz: Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP. FOCS 2006: 355-366

Dana Moshkovitz, Ran Raz: Sub-constant error low degree test of almost-linear size. STOC 2006: 21-30

Iordanis Kerenidis, Ran Raz: The one-way communication complexity of the Boolean Hidden Matching Problem. CoRR abs/quant-ph/0607173 (2006)

Ran Raz, Iddo Tzameret: The Strength of Multilinear Proofs. Electronic Colloquium on Computational Complexity (ECCC)(001) (2006)

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)

Iordanis Kerenidis, Ran Raz: The one-way communication complexity of the Boolean Hidden Matching Problem. Electronic Colloquium on Computational Complexity (ECCC) 13(087) (2006)

Ran Raz, Amir Shpilka: Deterministic polynomial identity testing in non-commutative models. Computational Complexity 14(1): 1-19 (2005)

Dieter van Melkebeek, Ran Raz: A time lower bound for satisfiability. Theor. Comput. Sci. 348(2-3): 311-320 (2005)

Ariel Gabizon, Ran Raz: Deterministic Extractors for Affine Sources over Large Fields. FOCS 2005: 407-418

Ran Raz: Quantum Information and the PCP Theorem. FOCS 2005: 459-468

Ran Raz: Extractors with weak random seeds. STOC 2005: 11-20

Zeev Dvir, Ran Raz: Analyzing Linear Mergers. Electronic Colloquium on Computational Complexity (ECCC)(025) (2005)

Ran Raz: Quantum Information and the PCP Theorem. Electronic Colloquium on Computational Complexity (ECCC)(038) (2005)

Dana Moshkovitz, Ran Raz: Sub-Constant Error Low Degree Test of Almost Linear Size. Electronic Colloquium on Computational Complexity (ECCC)(086) (2005)

Ariel Gabizon, Ran Raz: Deterministic Extractors for Affine Sources over Large Fields. Electronic Colloquium on Computational Complexity (ECCC)(108) (2005)

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)

Toniann Pitassi, Ran Raz: Regular Resolution Lower Bounds For The Weak Pigeonhole Principle. Combinatorica 24(3): 503-524 (2004)

Ran Raz: Resolution lower bounds for the weak pigeonhole principle. J. ACM 51(2): 115-138 (2004)

Cyril Gavoille, David Peleg, Stéphane Pérennes, Ran Raz: Distance labeling in graphs. J. Algorithms 53(1): 85-112 (2004)

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)

Yevgeniy Dodis, Ariel Elbaz, Roberto Oliveira, Ran Raz: Improved Randomness Extraction from Two Independent Sources. APPROX-RANDOM 2004: 334-344

Ran Raz, Amir Shpilka: Deterministic Polynomial Identity Testing in Non-Commutative Models. IEEE Conference on Computational Complexity 2004: 215-222

Ran Raz, Amir Shpilka: On the Power of Quantum Proofs. IEEE Conference on Computational Complexity 2004: 260-274

Ran Raz: Multilinear-NC neq Multilinear-NC. FOCS 2004: 344-351

Ariel Gabizon, Ran Raz, Ronen Shaltiel: Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed. FOCS 2004: 394-403

Dieter van Melkebeek, Ran Raz: A Time Lower Bound for Satisfiability. ICALP 2004: 971-982

Ran Raz: Multi-linear formulas for permanent and determinant are of super-polynomial size. STOC 2004: 633-641

Ran Raz: Multilinear-NC₁ != Multilinear-NC₂. Electronic Colloquium on Computational Complexity (ECCC)(042) (2004)

Ran Raz: Extractors with Weak Random Seeds. Electronic Colloquium on Computational Complexity (ECCC)(099) (2004)

Irit Dinur, Guy Kindler, Ran Raz, Shmuel Safra: Approximating CVP to Within Almost-Polynomial Factors is NP-Hard. Combinatorica 23(2): 205-243 (2003)

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)

Ran Raz, Amir Shpilka: Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates. SIAM J. Comput. 32(2): 488-513 (2003)

Ran Raz: On the Complexity of Matrix Product. SIAM J. Comput. 32(5): 1356-1369 (2003)

Ran Raz: P != NP, propositional proof complexity, and resolution lower bounds for the weak pigeonhole principle. CoRR cs.CC/0304041 (2003)

Ran Raz: Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size. Electronic Colloquium on Computational Complexity (ECCC)(067) (2003)

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)

Ran Raz: Resolution Lower Bounds for the Weak Pigeonhole Principle. IEEE Conference on Computational Complexity 2002: 3

Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal: Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles. FOCS 2002: 583-592

Ran Raz: On the complexity of matrix product. STOC 2002: 144-151

Ran Raz: Resolution lower bounds for the weak pigeonhole principle. STOC 2002: 553-562

Ran Raz: On the Complexity of Matrix Product. Electronic Colloquium on Computational Complexity (ECCC)(012) (2002)

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)

Cyril Gavoille, David Peleg, Stephane Perennes, Ran Raz: Distance labeling in graphs. SODA 2001: 210-219

Toniann Pitassi, Ran Raz: Regular resolution lower bounds for the weak pigeonhole principle. STOC 2001: 347-355

Oded Lachish, Ran Raz: Explicit lower bound of 4.5n - o(n) for boolena circuits. STOC 2001: 399-408

Ran Raz, Amir Shpilka: Lower bounds for matrix product, in bounded depth circuits with arbitrary gates. STOC 2001: 409-418

Ran Raz: Resolution Lower Bounds for the Weak Pigeonhole Principle. Electronic Colloquium on Computational Complexity (ECCC) 8(21) (2001)

Ran Raz: The BNS-Chung criterion for multi-party communication complexity. Computational Complexity 9(2): 113-122 (2000)

Ran Raz: VC-Dimension of Sets of Permutations. Combinatorica 20(2): 241-255 (2000)

Maria Luisa Bonet, Toniann Pitassi, Ran Raz: On Interpolation and Automatization for Frege Systems. SIAM J. Comput. 29(6): 1939-1967 (2000)

Tzvika Hartman, Ran Raz: On the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors. ICALP Satellite Workshops 2000: 3-22

Danny Harnik, Ran Raz: Higher lower bounds on monotone size. STOC 2000: 378-387

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)

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)

Ran Raz, Pierre McKenzie: Separation of the Monotone NC Hierarchy. Combinatorica 19(3): 403-435 (1999)

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)

Ran Raz, Omer Reingold, Salil P. Vadhan: Error Reduction for Extractors. FOCS 1999: 191-201

Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra: PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability. STOC 1999: 29-40

Ran Raz, Omer Reingold, Salil P. Vadhan: Extracting all the Randomness and Reducing the Error in Trevisan's Extractors. STOC 1999: 149-158

Ran Raz, Omer Reingold: On Recycling the Randomness of States in Space Bounded Computation. STOC 1999: 159-168

Ran Raz: Exponential Separation of Quantum and Classical Communication Complexity. STOC 1999: 358-367

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)

Yuri Rabinovich, Ran Raz: Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs. Discrete & Computational Geometry 19(1): 79-94 (1998)

Ran Raz: A Parallel Repetition Theorem. SIAM J. Comput. 27(3): 763-803 (1998)

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

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)

Maria Luisa Bonet, Toniann Pitassi, Ran Raz: Lower Bounds for Cutting Planes Proofs with Small Coefficients. J. Symb. Log. 62(3): 708-728 (1997)

Ran Raz, Pierre McKenzie: Separation of the Monotone NC Hierarchy. FOCS 1997: 234-243

Maria Luisa Bonet, Toniann Pitassi, Ran Raz: No Feasible Interpolation for TC0-Frege Proofs. FOCS 1997: 254-263

Itzhak Parnafes, Ran Raz, Avi Wigderson: Direct Product Results and the GCD Problem, in Old and New Communication Models. STOC 1997: 363-372

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

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)

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)

Ran Raz: Fourier Analysis for Probabilistic Communication Complexity. Computational Complexity 5(3/4): 205-221 (1995)

Ran Raz, Boris Spieker: On the "Log Rank"-Conjecture in Communication Complexity. Combinatorica 15(4): 567-588 (1995)

Ran Raz: A parallel repetition theorem. STOC 1995: 447-456

Maria Luisa Bonet, Toniann Pitassi, Ran Raz: Lower bounds for cutting planes proofs with small coefficients. STOC 1995: 575-584

Russell Impagliazzo, Ran Raz, Avi Wigderson: A Direct Product Theorem. Structure in Complexity Theory Conference 1994: 88-96

Ran Raz, Boris Spieker: On the ``log rank''-Conjecture in Communication Complexity. FOCS 1993: 168-176

Ran Raz, Avi Wigderson: Monotone Circuits for Matching Require Linear Depth. J. ACM 39(3): 736-744 (1992)

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

Ran Raz, Avi Wigderson: Monotone Circuits for Matching Require Linear Depth. STOC 1990: 287-292

Ran Raz, Avi Wigderson: Probabilistic Communication Complexity of Boolean Relations (Extended Abstract). FOCS 1989: 562-567