Skip to content

Ran Raz

Publication record assembled from the DBLP archive of ranked conferences.

Papers indexed

65

Venues

5

Active years

1989–2023

Best venue rank

A*

Where they publish

Papers

65 indexed papers, newest first.

YearVenueTitleAuthors
2023FOCSCertified Hardness vs. Randomness for Log-Space.Edward Pyne, Ran Raz, Wei Zhan
2023STOCMemory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory.Qipeng Liu, Ran Raz, Wei Zhan
2022STOCParallel repetition for all 3-player games over binary alphabet.Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan
2021ICALPQuantum Logspace Algorithm for Powering Matrices with Bounded Norm.Uma Girish, Ran Raz, Wei Zhan
2020FOCSNear-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms.Sepehr Assadi, Ran Raz
2019STOCOracle separation of BQP and PH.Ran Raz, Avishay Tal
2018STOCExtractor-based time-space lower bounds for learning.Sumegha Garg, Ran Raz, Avishay Tal
2017FOCSA Time-Space Lower Bound for a Large Class of Learning Problems.Ran Raz
2017STOCTime-space hardness of learning sparse parities.Gillat Kol, Ran Raz, Avishay Tal
2016FOCSFast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning.Ran Raz
2016STOCExponential separation of communication and external information.Anat Ganor, Gillat Kol, Ran Raz
2015FOCSWelfare Maximization with Limited Interaction.Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein
2015STOCExponential Separation of Information and Communication for Boolean Functions.Anat Ganor, Gillat Kol, Ran Raz
2014FOCSExponential Separation of Information and Communication.Anat Ganor, Gillat Kol, Ran Raz
2014STOCHow to delegate computations: the power of no-signaling proofs.Yael Tauman Kalai, Ran Raz, Ron D. Rothblum
2013CRYPTOEfficient Multiparty Protocols via Log-Depth Threshold Formulae - (Extended Abstract).Gil Cohen, Ivan Bjerre Damgrd, Yuval Ishai, Jonas Klker, Peter Bro Miltersen, Ran Raz, Ron D. Rothblum
2013FOCSImproved Average-Case Lower Bounds for DeMorgan Formula Size.Ilan Komargodski, Ran Raz, Avishay Tal
2013ICALPArthur-Merlin Streaming Complexity.Tom Gur, Ran Raz
2013STOCDelegation for bounded space.Yael Tauman Kalai, Ran Raz, Ron D. Rothblum
2013STOCInteractive channel capacity.Gillat Kol, Ran Raz
2013STOCAverage-case lower bounds for formula size.Ilan Komargodski, Ran Raz
2012ICALPLabel Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner.Michael Dinitz, Guy Kortsarz, Ran Raz
2011CRYPTOMemory Delegation.Kai-Min Chung, Yael Tauman Kalai, Feng-Hao Liu, Ran Raz
2010FOCSPseudorandom Generators for Regular Branching Programs.Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff
2010STOCTensor-rank and lower bounds for arithmetic formulas.Ran Raz
2009CRYPTOProbabilistically Checkable Arguments.Yael Tauman Kalai, Ran Raz
2008FOCSTwo Query PCP with Sub-Constant Error.Dana Moshkovitz, Ran Raz
2008FOCSA Counterexample to Strong Parallel Repetition.Ran Raz
2008FOCSMultilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors.Ran Raz, Amir Yehudayoff
2008ICALPInteractive PCP.Yael Tauman Kalai, Ran Raz
2008STOCElusive functions and lower bounds for arithmetic circuits.Ran Raz
2007FOCSA Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits.Ran Raz, Amir Shpilka, Amir Yehudayoff
2007STOCExponential separations for one-way quantum communication complexity, with applications to cryptography.Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf
2006FOCSSuccinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP.Yael Tauman Kalai, Ran Raz
2006STOCSub-constant error low degree test of almost-linear size.Dana Moshkovitz, Ran Raz
2005FOCSDeterministic Extractors for Affine Sources over Large Fields.Ariel Gabizon, Ran Raz
2005FOCSQuantum Information and the PCP Theorem.Ran Raz
2005STOCExtractors with weak random seeds.Ran Raz
2004FOCSDeterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed.Ariel Gabizon, Ran Raz, Ronen Shaltiel
2004FOCSMultilinear-NC neq Multilinear-NC.Ran Raz
2004ICALPA Time Lower Bound for Satisfiability.Dieter van Melkebeek, Ran Raz
2004STOCMulti-linear formulas for permanent and determinant are of super-polynomial size.Ran Raz
2002FOCSBounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles.Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal
2002STOCOn the complexity of matrix product.Ran Raz
2002STOCResolution lower bounds for the weak pigeonhole principle.Ran Raz
2001SODADistance labeling in graphs.Cyril Gavoille, David Peleg, Stephane Perennes, Ran Raz
2001STOCExplicit lower bound ofOded Lachish, Ran Raz
2001STOCRegular resolution lower bounds for the weak pigeonhole principle.Toniann Pitassi, Ran Raz
2001STOCLower bounds for matrix product, in bounded depth circuits with arbitrary gates.Ran Raz, Amir Shpilka
2000ICALPOn the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors.Tzvika Hartman, Ran Raz
2000STOCHigher lower bounds on monotone size.Danny Harnik, Ran Raz
1999FOCSError Reduction for Extractors.Ran Raz, Omer Reingold, Salil P. Vadhan
1999STOCPCP Characterizations of NP: Towards a Polynomially-Small Error-Probability.Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
1999STOCExponential Separation of Quantum and Classical Communication Complexity.Ran Raz
1999STOCOn Recycling the Randomness of States in Space Bounded Computation.Ran Raz, Omer Reingold
1999STOCExtracting all the Randomness and Reducing the Error in Trevisan's Extractors.Ran Raz, Omer Reingold, Salil P. Vadhan
1997FOCSNo Feasible Interpolation for TC0-Frege Proofs.Maria Luisa Bonet, Toniann Pitassi, Ran Raz
1997FOCSSeparation of the Monotone NC Hierarchy.Ran Raz, Pierre McKenzie
1997STOCDirect Product Results and the GCD Problem, in Old and New Communication Models.Itzhak Parnafes, Ran Raz, Avi Wigderson
1997STOCA Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP.Ran Raz, Shmuel Safra
1995STOCLower bounds for cutting planes proofs with small coefficients.Maria Luisa Bonet, Toniann Pitassi, Ran Raz
1995STOCA parallel repetition theorem.Ran Raz
1993FOCSOn the "log rank"-Conjecture in Communication ComplexityRan Raz, Boris Spieker
1990STOCMonotone Circuits for Matching Require Linear DepthRan Raz, Avi Wigderson
1989FOCSProbabilistic Communication Complexity of Boolean Relations (Extended Abstract)Ran Raz, Avi Wigderson