Ran Raz

According to our database, Ran Raz authored at least 131 papers between 1989 and 2024.

Collaborative distances:

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

2024

Quantum Logspace Computations are Verifiable.

Uma Girish, Ran Raz, Wei Zhan

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

Information Dissemination via Broadcasts in the Presence of Adversarial Noise.

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Ran Raz, Raghuvansh R. Saxena

Proceedings of the 39th Computational Complexity Conference, 2024

2023

On the works of Avi Wigderson.

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

CoRR, 2023

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

Qipeng Liu, Ran Raz, Wei Zhan

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Is Untrusted Randomness Helpful?

Uma Girish, Ran Raz, Wei Zhan

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

Certified Hardness vs. Randomness for Log-Space.

Edward Pyne, Ran Raz, Wei Zhan

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Parallel repetition for all 3-player games over binary alphabet.

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

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Eliminating Intermediate Measurements Using Pseudorandom Generators.

Uma Girish, Ran Raz

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs.

Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan

Proceedings of the Approximation, 2022

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

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

Kunal Mittal, Ran Raz

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Quantum Versus Randomized Communication Complexity, with Efficient Players.

Uma Girish, Ran Raz, Avishay Tal

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Quantum Logspace Algorithm for Powering Matrices with Bounded Norm.

Uma Girish, Ran Raz, Wei Zhan

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Lower Bounds for XOR of Forrelations.

Uma Girish, Ran Raz, Wei Zhan

Proceedings of the Approximation, 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

A Parallel Repetition Theorem for the GHZ Game.

Justin Holmgren, Ran Raz

Electron. Colloquium Comput. Complex., 2020

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

Ran Raz, Wei Zhan

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 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

Oracle separation of BQP and PH.

Ran Raz, Avishay Tal

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Time-Space Lower Bounds for Two-Pass Learning.

Sumegha Garg, Ran Raz, Avishay Tal

Proceedings of the 34th Computational Complexity Conference, 2019

2018

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

Yael Tauman Kalai, Ilan Komargodski, Ran Raz

Proceedings of the 32nd International Symposium on Distributed Computing, 2018

Extractor-based time-space lower bounds for learning.

Sumegha Garg, Ran Raz, Avishay Tal

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 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

Time-space hardness of learning sparse parities.

Gillat Kol, Ran Raz, Avishay Tal

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

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

Ran Raz

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 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 communication and external information.

Anat Ganor, Gillat Kol, Ran Raz

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 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

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

Ran Raz

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Exponential Separation of Information and Communication for Boolean Functions.

Anat Ganor, Gillat Kol, Ran Raz

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Welfare Maximization with Limited Interaction.

Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

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

How to delegate computations: the power of no-signaling proofs.

Yael Tauman Kalai, Ran Raz, Ron D. Rothblum

Proceedings of the Symposium on Theory of Computing, 2014

Exponential Separation of Information and Communication.

Anat Ganor, Gillat Kol, Ran Raz

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Space Pseudorandom Generators by Communication Complexity Lower Bounds.

Anat Ganor, Ran Raz

Proceedings of the Approximation, 2014

Two Sides of the Coin Problem.

Gil Cohen, Anat Ganor, Ran Raz

Proceedings of the Approximation, 2014

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

Average-case lower bounds for formula size.

Ilan Komargodski, Ran Raz

Proceedings of the Symposium on Theory of Computing Conference, 2013

Interactive channel capacity.

Gillat Kol, Ran Raz

Proceedings of the Symposium on Theory of Computing Conference, 2013

Delegation for bounded space.

Yael Tauman Kalai, Ran Raz, Ron D. Rothblum

Proceedings of the Symposium on Theory of Computing Conference, 2013

Competing provers protocols for circuit evaluation.

Gillat Kol, Ran Raz

Proceedings of the Innovations in Theoretical Computer Science, 2013

Arthur-Merlin Streaming Complexity.

Tom Gur, Ran Raz

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Improved Average-Case Lower Bounds for DeMorgan Formula Size.

Ilan Komargodski, Ran Raz, Avishay Tal

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 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

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

A Strong Parallel Repetition Theorem for Projection Games on Expanders.

Ran Raz, Ricky Rosen

Proceedings of the 27th Conference on Computational Complexity, 2012

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

Gil Cohen, Ran Raz, Gil Segev

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

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

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

Comput. Complex., 2011

Memory Delegation.

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

Proceedings of the Advances in Cryptology - CRYPTO 2011, 2011

2010

Two-query PCP with subconstant error.

Dana Moshkovitz, Ran Raz

J. ACM, 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

Tensor-rank and lower bounds for arithmetic formulas.

Ran Raz

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Pseudorandom Generators for Regular Branching Programs.

Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Parallel Repetition of Two Prover Games (Invited Survey).

Ran Raz

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

2009

Bounds on 2-Query Locally Testable Codes with Affine Tests.

Gillat Kol, Ran Raz

Electron. Colloquium Comput. Complex., 2009

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

Gillat Kol, Ran Raz

Electron. Colloquium Comput. Complex., 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

Balancing Syntactically Multilinear Arithmetic Circuits.

Ran Raz, Amir Yehudayoff

Comput. Complex., 2008

The Strength of Multilinear Proofs.

Ran Raz, Iddo Tzameret

Comput. Complex., 2008

Elusive functions and lower bounds for arithmetic circuits.

Ran Raz

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Interactive PCP.

Yael Tauman Kalai, Ran Raz

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors.

Ran Raz, Amir Yehudayoff

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

A Counterexample to Strong Parallel Repetition.

Ran Raz

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Two Query PCP with Sub-Constant Error.

Dana Moshkovitz, Ran Raz

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Lower Bounds and Separations for Constant Depth Multilinear Circuits.

Ran Raz, Amir Yehudayoff

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007

Resolution over Linear Equations and Multilinear Proofs.

Ran Raz, Iddo Tzameret

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

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

Ran Raz, Amir Shpilka, Amir Yehudayoff

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007

2006

Separation of Multilinear Circuit and Formula Size.

Ran Raz

Theory Comput., 2006

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

Iordanis Kerenidis, Ran Raz

Electron. Colloquium Comput. Complex., 2006

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

Dana Moshkovitz, Ran Raz

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 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, 2006

2005

Analyzing Linear Mergers

Zeev Dvir, Ran Raz

Electron. Colloquium Comput. Complex., 2005

Extractors with weak random seeds.

Ran Raz

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Quantum Information and the PCP Theorem.

Ran Raz

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005

Deterministic Extractors for Affine Sources over Large Fields.

Ariel Gabizon, Ran Raz

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005

2004

Multilinear-NC₁ != Multilinear-NC₂

Ran Raz

Electron. Colloquium Comput. Complex., 2004

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

Ran Raz

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

A Time Lower Bound for Satisfiability.

Dieter van Melkebeek, Ran Raz

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Multilinear-NC neq Multilinear-NC.

Ran Raz

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

Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed.

Ariel Gabizon, Ran Raz, Ronen Shaltiel

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

On the Power of Quantum Proofs.

Ran Raz, Amir Shpilka

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

Deterministic Polynomial Identity Testing in Non-Commutative Models.

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

On the complexity of matrix product.

Ran Raz

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles.

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

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

Resolution Lower Bounds for the Weak Pigeonhole Principle.

Ran Raz

Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001

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

Ran Raz, Amir Shpilka

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

Regular resolution lower bounds for the weak pigeonhole principle.

Toniann Pitassi, Ran Raz

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 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

Distance labeling in graphs.

Cyril Gavoille, David Peleg, Stephane Perennes, Ran Raz

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

2000

On Interpolation and Automatization for Frege Systems.

Maria Luisa Bonet, Toniann Pitassi, Ran Raz

SIAM J. Comput., 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

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

Tzvika Hartman, Ran Raz

Proceedings of the ICALP Workshops 2000, 2000

1999

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

Ran Raz, Omer Reingold, Salil P. Vadhan

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 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

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

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

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

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

Yuri Rabinovich, Ran Raz

Discret. Comput. Geom., 1998

Arthur-Merlin Games in Boolean Decision Trees.

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

Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

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

Separation of the Monotone NC Hierarchy.

Ran Raz, Pierre McKenzie

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 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

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

A parallel repetition theorem.

Ran Raz

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Lower bounds for cutting planes proofs with small coefficients.

Maria Luisa Bonet, Toniann Pitassi, Ran Raz

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 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

1993

On the "log rank"-Conjecture in Communication Complexity

Ran Raz, Boris Spieker

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992

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

Ran Raz

PhD thesis, 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

1990

Monotone Circuits for Matching Require Linear Depth

Ran Raz, Avi Wigderson

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

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