Ran Raz

According to our database, Ran Raz authored at least 130 papers between 1989 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2023

Certified Hardness vs. Randomness for Log-Space.

Edward Pyne, Ran Raz, Wei Zhan

Electron. Colloquium Comput. Complex., 2023

Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory.

Qipeng Liu, Ran Raz, Wei Zhan

Electron. Colloquium Comput. Complex., 2023

Quantum Logspace Computations are Verifiable.

Uma Girish, Ran Raz, Wei Zhan

Electron. Colloquium Comput. Complex., 2023

On the works of Avi Wigderson.

Boaz Barak, Yael Kalai, Ran Raz, Salil P. Vadhan, Nisheeth K. Vishnoi

CoRR, 2023

Is Untrusted Randomness Helpful?

Uma Girish, Ran Raz, Wei Zhan

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022

Oracle Separation of BQP and PH.

Ran Raz, Avishay Tal

J. ACM, 2022

How to Delegate Computations: The Power of No-Signaling Proofs.

Yael Tauman Kalai, Ran Raz, Ron D. Rothblum

J. ACM, 2022

Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs.

Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan

Electron. Colloquium Comput. Complex., 2022

Parallel Repetition For All 3-Player Games Over Binary Alphabet.

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

Electron. Colloquium Comput. Complex., 2022

Quantum versus Randomized Communication Complexity, with Efficient Players.

Uma Girish, Ran Raz, Avishay Tal

Comput. Complex., 2022

2021

Eliminating Intermediate Measurements using Pseudorandom Generators.

Uma Girish, Ran Raz

Electron. Colloquium Comput. Complex., 2021

A Parallel Repetition Theorem for the GHZ Game: A Simpler Proof.

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

Electron. Colloquium Comput. Complex., 2021

A Lower Bound for Adaptively-Secure Collective Coin Flipping Protocols.

Yael Tauman Kalai, Ilan Komargodski, Ran Raz

Comb., 2021

Parallel Repetition for the GHZ Game: A Simpler Proof.

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

Proceedings of the Approximation, 2021

Memory-Sample Lower Bounds for Learning Parity with Noise.

Sumegha Garg, Pravesh K. Kothari, Pengda Liu, Ran Raz

Proceedings of the Approximation, 2021

2020

Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines.

Kunal Mittal, Ran Raz

Electron. Colloquium Comput. Complex., 2020

A Parallel Repetition Theorem for the GHZ Game.

Justin Holmgren, Ran Raz

Electron. Colloquium Comput. Complex., 2020

Lower Bounds for XOR of Forrelations.

Uma Girish, Ran Raz, Wei Zhan

Electron. Colloquium Comput. Complex., 2020

Quantum Logspace Algorithm for Powering Matrices with Bounded Norm.

Uma Girish, Ran Raz, Wei Zhan

Electron. Colloquium Comput. Complex., 2020

Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms.

Sepehr Assadi, Ran Raz

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG.

Sumegha Garg, Pravesh K. Kothari, Ran Raz

Proceedings of the Approximation, 2020

2019

Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning.

Ran Raz

J. ACM, 2019

The Random-Query Model and the Memory-Bounded Coupon Collector.

Ran Raz, Wei Zhan

Electron. Colloquium Comput. Complex., 2019

Time-Space Lower Bounds for Two-Pass Learning.

Sumegha Garg, Ran Raz, Avishay Tal

Electron. Colloquium Comput. Complex., 2019

2018

A Candidate for a Strong Separation of Information and Communication.

Mark Braverman, Anat Ganor, Gillat Kol, Ran Raz

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017

Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound.

Ilan Komargodski, Ran Raz, Avishay Tal

SIAM J. Comput., 2017

A Time-Space Lower Bound for a Large Class of Learning Problems.

Ran Raz

Electron. Colloquium Comput. Complex., 2017

Extractor-Based Time-Space Lower Bounds for Learning.

Sumegha Garg, Ran Raz, Avishay Tal

Electron. Colloquium Comput. Complex., 2017

2016

Label Cover Instances with Large Girth and the Hardness of Approximating Basic <i>k</i>-Spanner.

Michael Dinitz, Guy Kortsarz, Ran Raz

ACM Trans. Algorithms, 2016

Exponential Separation of Information and Communication for Boolean Functions.

Anat Ganor, Gillat Kol, Ran Raz

J. ACM, 2016

Bounds on 2-query Locally Testable Codes with affine tests.

Gillat Kol, Ran Raz

Inf. Process. Lett., 2016

Time-Space Hardness of Learning Sparse Parities.

Gillat Kol, Ran Raz, Avishay Tal

Electron. Colloquium Comput. Complex., 2016

On the Space Complexity of Linear Programming with Preprocessing.

Yael Tauman Kalai, Ran Raz, Oded Regev

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

2015

Exponential Separation of Communication and External Information.

Anat Ganor, Gillat Kol, Ran Raz

Electron. Colloquium Comput. Complex., 2015

Welfare Maximization with Limited Interaction.

Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein

Electron. Colloquium Comput. Complex., 2015

2014

Competing-Provers Protocols for Circuit Evaluation.

Gillat Kol, Ran Raz

Theory Comput., 2014

Nonmalleable Extractors with Short Seeds and Applications to Privacy Amplification.

Gil Cohen, Ran Raz, Gil Segev

SIAM J. Comput., 2014

On the Space Complexity of Linear Programming with Preprocessing.

Yael Tauman Kalai, Ran Raz

Electron. Colloquium Comput. Complex., 2014

Exponential Separation of Information and Communication.

Anat Ganor, Gillat Kol, Ran Raz

Electron. Colloquium Comput. Complex., 2014

Two Sides of the Coin Problem.

Gil Cohen, Anat Ganor, Ran Raz

Electron. Colloquium Comput. Complex., 2014

2013

Tensor-Rank and Lower Bounds for Arithmetic Formulas.

Ran Raz

J. ACM, 2013

Improved Average-Case Lower Bounds for DeMorgan Formula Size.

Ilan Komargodski, Ran Raz, Avishay Tal

Electron. Colloquium Comput. Complex., 2013

Interactive Channel Capacity.

Gillat Kol, Ran Raz

Electron. Colloquium Comput. Complex., 2013

Arthur-Merlin Streaming Complexity.

Tom Gur, Ran Raz

Electron. Colloquium Comput. Complex., 2013

Space Pseudorandom Generators by Communication Complexity Lower Bounds.

Anat Ganor, Ran Raz

Electron. Colloquium Comput. Complex., 2013

Efficient Multiparty Protocols via Log-Depth Threshold Formulae.

Gil Cohen, Ivan Bjerre Damgård, Yuval Ishai, Jonas Kölker, Peter Bro Miltersen, Ran Raz, Ron Rothblum

Electron. Colloquium Comput. Complex., 2013

Delegation for bounded space.

Yael Tauman Kalai, Ran Raz, Ron D. Rothblum

Proceedings of the Symposium on Theory of Computing Conference, 2013

Efficient Multiparty Protocols via Log-Depth Threshold Formulae - (Extended Abstract).

Gil Cohen, Ivan Bjerre Damgård, Yuval Ishai, Jonas Kölker, Peter Bro Miltersen, Ran Raz, Ron D. Rothblum

Proceedings of the Advances in Cryptology - CRYPTO 2013, 2013

2012

Average-Case Lower Bounds for Formula Size.

Ilan Komargodski, Ran Raz

Electron. Colloquium Comput. Complex., 2012

The Spectrum of Small DeMorgan Formulas.

Anat Ganor, Ilan Komargodski, Ran Raz

Electron. Colloquium Comput. Complex., 2012

Bounds on locally testable codes with unique tests.

Gillat Kol, Ran Raz

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner.

Michael Dinitz, Guy Kortsarz, Ran Raz

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

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

Ran Raz, Amir Yehudayoff

J. Comput. Syst. Sci., 2011

Memory Delegation.

Kai-Min Chung, Yael Tauman Kalai, Feng-Hao Liu, Ran Raz

IACR Cryptol. ePrint Arch., 2011

Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification.

Gil Cohen, Ran Raz, Gil Segev

Electron. Colloquium Comput. Complex., 2011

PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability.

Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra

Comput. Complex., 2011

2010

Elusive Functions and Lower Bounds for Arithmetic Circuits.

Ran Raz

Theory Comput., 2010

Two-query PCP with subconstant error.

Dana Moshkovitz, Ran Raz

J. ACM, 2010

A Strong Parallel Repetition Theorem for Projection Games on Expanders.

Ran Raz, Ricky Rosen

Electron. Colloquium Comput. Complex., 2010

Pseudorandom Generators for Regular Branching Programs.

Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff

Electron. Colloquium Comput. Complex., 2010

The Surprise Examination Paradox and the Second Incompleteness Theorem

Shira Kritchman, Ran Raz

CoRR, 2010

Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size.

Dana Moshkovitz, Ran Raz

Comput. Complex., 2010

Parallel Repetition of Two Prover Games (Invited Survey).

Ran Raz

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009

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

Ran Raz

J. ACM, 2009

Locally Testable Codes Analogues to the Unique Games Conjecture Do Not Exist.

Gillat Kol, Ran Raz

Electron. Colloquium Comput. Complex., 2009

Lower Bounds and Separations for Constant Depth Multilinear Circuits.

Ran Raz, Amir Yehudayoff

Comput. Complex., 2009

Quantum Information and the PCP Theorem.

Ran Raz

Algorithmica, 2009

Probabilistically Checkable Arguments.

Yael Tauman Kalai, Ran Raz

Proceedings of the Advances in Cryptology, 2009

Strong Parallel Repetition Theorem for Free Projection Games.

Boaz Barak, Anup Rao, Ran Raz, Ricky Rosen, Ronen Shaltiel

Proceedings of the Approximation, 2009

2008

Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography.

Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf

SIAM J. Comput., 2008

A Counterexample to Strong Parallel Repetition.

Ran Raz

Electron. Colloquium Comput. Complex., 2008

Two Query PCP with Sub-Constant Error.

Dana Moshkovitz, Ran Raz

Electron. Colloquium Comput. Complex., 2008

Deterministic extractors for affine sources over large fields.

Ariel Gabizon, Ran Raz

Comb., 2008

Balancing Syntactically Multilinear Arithmetic Circuits.

Ran Raz, Amir Yehudayoff

Comput. Complex., 2008

The Strength of Multilinear Proofs.

Ran Raz, Iddo Tzameret

Comput. Complex., 2008

2007

Resolution over Linear Equations and Multilinear Proofs.

Ran Raz, Iddo Tzameret

Electron. Colloquium Comput. Complex., 2007

Interactive PCP.

Yael Tauman Kalai, Ran Raz

Electron. Colloquium Comput. Complex., 2007

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

Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006

Separation of Multilinear Circuit and Formula Size.

Ran Raz

Theory Comput., 2006

A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits.

Ran Raz, Amir Shpilka, Amir Yehudayoff

Electron. Colloquium Comput. Complex., 2006

The one-way communication complexity of the Boolean Hidden Matching Problem.

Iordanis Kerenidis, Ran Raz

Electron. Colloquium Comput. Complex., 2006

Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP.

Yael Tauman Kalai, Ran Raz

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005

A time lower bound for satisfiability.

Dieter van Melkebeek, Ran Raz

Theor. Comput. Sci., 2005

Deterministic Extractors for Bit-fixing Sources by Obtaining an Independent Seed

Ariel Gabizon, Ran Raz, Ronen Shaltiel

Electron. Colloquium Comput. Complex., 2005

Sub-Constant Error Low Degree Test of Almost Linear Size

Dana Moshkovitz, Ran Raz

Electron. Colloquium Comput. Complex., 2005

Analyzing Linear Mergers

Zeev Dvir, Ran Raz

Electron. Colloquium Comput. Complex., 2005

Deterministic polynomial identity testing in non-commutative models.

Ran Raz, Amir Shpilka

Comput. Complex., 2005

2004

Distance labeling in graphs.

Cyril Gavoille, David Peleg, Stéphane Pérennes, Ran Raz

J. Algorithms, 2004

Resolution lower bounds for the weak pigeonhole principle.

Ran Raz

J. ACM, 2004

Extractors with Weak Random Seeds

Ran Raz

Electron. Colloquium Comput. Complex., 2004

Multilinear-NC₁ != Multilinear-NC₂

Ran Raz

Electron. Colloquium Comput. Complex., 2004

Regular Resolution Lower Bounds For The Weak Pigeonhole Principle.

Toniann Pitassi, Ran Raz

Comb., 2004

Multilinear-NC neq Multilinear-NC.

Ran Raz

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

On the Power of Quantum Proofs.

Ran Raz, Amir Shpilka

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

Improved Randomness Extraction from Two Independent Sources.

Yevgeniy Dodis, Ariel Elbaz, Roberto Oliveira, Ran Raz

Proceedings of the Approximation, 2004

Circuit and Communication Complexity.

Ran Raz

Proceedings of the Computational Complexity Theory., 2004

Quantum computation.

Ran Raz

Proceedings of the Computational Complexity Theory., 2004

2003

On the distribution of the number of roots of polynomials and explicit weak designs.

Tzvika Hartman, Ran Raz

Random Struct. Algorithms, 2003

P != NP, propositional proof complexity, and resolution lower bounds for the weak pigeonhole principle

Ran Raz

CoRR, 2003

Approximating CVP to Within Almost-Polynomial Factors is NP-Hard.

Irit Dinur, Guy Kindler, Ran Raz, Shmuel Safra

Comb., 2003

2002

Extracting all the Randomness and Reducing the Error in Trevisan's Extractors.

Ran Raz, Omer Reingold, Salil P. Vadhan

J. Comput. Syst. Sci., 2002

Bounded-depth Frege lower bounds for weaker pigeonhole principles

Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal

Electron. Colloquium Comput. Complex., 2002

On the Complexity of Matrix Product

Ran Raz

Electron. Colloquium Comput. Complex., 2002

2001

Explicit lower bound of <i>4.5n - o(n)</i> for boolena circuits.

Oded Lachish, Ran Raz

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

2000

On Interpolation and Automatization for Frege Systems.

Maria Luisa Bonet, Toniann Pitassi, Ran Raz

SIAM J. Comput., 2000

On the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors

Tzvika Hartman, Ran Raz

Electron. Colloquium Comput. Complex., 2000

Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates

Ran Raz, Amir Shpilka

Electron. Colloquium Comput. Complex., 2000

VC-Dimension of Sets of Permutations.

Ran Raz

Comb., 2000

The BNS-Chung criterion for multi-party communication complexity.

Ran Raz

Comput. Complex., 2000

Higher lower bounds on monotone size.

Danny Harnik, Ran Raz

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

1999

Arthur-Merlin Games in Boolean Decision Trees.

Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin

J. Comput. Syst. Sci., 1999

Separation of the Monotone NC Hierarchy.

Ran Raz, Pierre McKenzie

Comb., 1999

On Recycling the Randomness of States in Space Bounded Computation.

Ran Raz, Omer Reingold

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Exponential Separation of Quantum and Classical Communication Complexity.

Ran Raz

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Error Reduction for Extractors.

Ran Raz, Omer Reingold, Salil P. Vadhan

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998

A Parallel Repetition Theorem.

Ran Raz

SIAM J. Comput., 1998

PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability

Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra

Electron. Colloquium Comput. Complex., 1998

Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs.

Yuri Rabinovich, Ran Raz

Discret. Comput. Geom., 1998

1997

Lower Bounds for Cutting Planes Proofs with Small Coefficients.

Maria Luisa Bonet, Toniann Pitassi, Ran Raz

J. Symb. Log., 1997

A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP.

Ran Raz, Shmuel Safra

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Direct Product Results and the GCD Problem, in Old and New Communication Models.

Itzhak Parnafes, Ran Raz, Avi Wigderson

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

No Feasible Interpolation for TC0-Frege Proofs.

Maria Luisa Bonet, Toniann Pitassi, Ran Raz

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1995

On the "Log Rank"-Conjecture in Communication Complexity.

Ran Raz, Boris Spieker

Comb., 1995

Fourier Analysis for Probabilistic Communication Complexity.

Ran Raz

Comput. Complex., 1995

Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity.

Mauricio Karchmer, Ran Raz, Avi Wigderson

Comput. Complex., 1995

1994

A Direct Product Theorem.

Russell Impagliazzo, Ran Raz, Avi Wigderson

Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1992

חסמים תחתונים לסיבוכיות תקשורת הסתברותית ולעומק מעגלים בוליאנים מונוטונים (Lower bounds for probabilistic communication complexity and for the depth of monotone boolean circuits.).

Ran Raz

PhD thesis, 1992

Monotone Circuits for Matching Require Linear Depth.

Ran Raz, Avi Wigderson

J. ACM, 1992

1991

Super-logarithmic Depth Lower Bounds via Direct Sum in Communication Coplexity.

Mauricio Karchmer, Ran Raz, Avi Wigderson

Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

1989

Probabilistic Communication Complexity of Boolean Relations (Extended Abstract)

Ran Raz, Avi Wigderson

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989