default search action
Ran Raz
Person information
- affiliation: Weizmann Institute of Science, Rehovot, Israel
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2025
- [i98]Klim Efremenko, Gillat Kol, Dmitry Paramonov, Ran Raz, Raghuvansh Saxena:
Information Dissemination via Broadcasts in the Presence of Adversarial Noise. Electron. Colloquium Comput. Complex. TR25 (2025) - 2024
- [c97]Klim Efremenko
, Gillat Kol, Dmitry Paramonov, Ran Raz, Raghuvansh R. Saxena:
Information Dissemination via Broadcasts in the Presence of Adversarial Noise. CCC 2024: 19:1-19:33 - [c96]Uma Girish, Ran Raz, Wei Zhan:
Quantum Logspace Computations are Verifiable. SOSA 2024: 144-150 - 2023
- [c95]Edward Pyne, Ran Raz, Wei Zhan:
Certified Hardness vs. Randomness for Log-Space. FOCS 2023: 989-1007 - [c94]Uma Girish, Ran Raz
Is Untrusted Randomness Helpful? ITCS 2023: 56:1-56:18 - [c93]Qipeng Liu, Ran Raz
Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory. STOC 2023: 1097-1110 - [i97]Qipeng Liu, Ran Raz, Wei Zhan:
Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory. CoRR abs/2303.00209 (2023) - [i96]Edward Pyne, Ran Raz, Wei Zhan:
Certified Hardness vs. Randomness for Log-Space. CoRR abs/2303.16413 (2023) - [i95]Boaz Barak, Yael Kalai, Ran Raz, Salil P. Vadhan, Nisheeth K. Vishnoi:
On the works of Avi Wigderson. CoRR abs/2307.09524 (2023) - [i94]Uma Girish, Ran Raz, Wei Zhan:
Quantum Logspace Computations are Verifiable. CoRR abs/2307.11083 (2023) - [i93]Uma Girish, Ran Raz, Wei Zhan:
Quantum Logspace Computations are Verifiable. Electron. Colloquium Comput. Complex. TR23 (2023) - [i92]Qipeng Liu, Ran Raz, Wei Zhan:
Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory. Electron. Colloquium Comput. Complex. TR23 (2023) - [i91]Edward Pyne, Ran Raz, Wei Zhan:
Certified Hardness vs. Randomness for Log-Space. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [j57]Uma Girish, Ran Raz
Quantum versus Randomized Communication Complexity, with Efficient Players. Comput. Complex. 31(2): 17 (2022) - [j56]Yael Tauman Kalai, Ran Raz
How to Delegate Computations: The Power of No-Signaling Proofs. J. ACM 69(1): 1:1-1:82 (2022) - [j55]Ran Raz
Oracle Separation of BQP and PH. J. ACM 69(4): 30:1-30:21 (2022) - [c92]Uma Girish, Kunal Mittal, Ran Raz
Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs. APPROX/RANDOM 2022: 6:1-6:17 - [c91]Uma Girish, Ran Raz
Eliminating Intermediate Measurements Using Pseudorandom Generators. ITCS 2022: 76:1-76:18 - [c90]Uma Girish, Justin Holmgren
Parallel repetition for all 3-player games over binary alphabet. STOC 2022: 998-1009 - [i90]Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan:
Parallel Repetition For All 3-Player Games Over Binary Alphabet. CoRR abs/2202.06826 (2022) - [i89]Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan:
Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs. CoRR abs/2204.00858 (2022) - [i88]Uma Girish, Justin Holmgren
Parallel Repetition For All 3-Player Games Over Binary Alphabet. Electron. Colloquium Comput. Complex. TR22 (2022) - [i87]Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan:
Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [j54]Yael Tauman Kalai, Ilan Komargodski, Ran Raz
A Lower Bound for Adaptively-Secure Collective Coin Flipping Protocols. Comb. 41(1): 75-98 (2021) - [j53]Anat Ganor, Gillat Kol, Ran Raz
Exponential Separation of Communication and External Information. SIAM J. Comput. 50(3) (2021) - [c89]Uma Girish, Ran Raz
Lower Bounds for XOR of Forrelations. APPROX-RANDOM 2021: 52:1-52:14 - [c88]Sumegha Garg, Pravesh K. Kothari, Pengda Liu, Ran Raz
Memory-Sample Lower Bounds for Learning Parity with Noise. APPROX-RANDOM 2021: 60:1-60:19 - [c87]Uma Girish, Justin Holmgren
Parallel Repetition for the GHZ Game: A Simpler Proof. APPROX-RANDOM 2021: 62:1-62:19 - [c86]Uma Girish, Ran Raz
Quantum Logspace Algorithm for Powering Matrices with Bounded Norm. ICALP 2021: 73:1-73:20 - [c85]Uma Girish, Ran Raz
Quantum Versus Randomized Communication Complexity, with Efficient Players. ITCS 2021: 54:1-54:20 - [c84]Kunal Mittal, Ran Raz
Block Rigidity: Strong Multiplayer Parallel Repetition Implies Super-Linear Lower Bounds for Turing Machines. ITCS 2021: 71:1-71:15 - [i86]Uma Girish, Ran Raz:
Eliminating Intermediate Measurements using Pseudorandom Generators. CoRR abs/2106.11877 (2021) - [i85]Sumegha Garg, Pravesh K. Kothari, Pengda Liu, Ran Raz:
Memory-Sample Lower Bounds for Learning Parity with Noise. CoRR abs/2107.02320 (2021) - [i84]Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan:
Parallel Repetition for the GHZ Game: A Simpler Proof. CoRR abs/2107.06156 (2021) - [i83]Uma Girish, Justin Holmgren
A Parallel Repetition Theorem for the GHZ Game: A Simpler Proof. Electron. Colloquium Comput. Complex. TR21 (2021) - [i82]Uma Girish, Ran Raz:
Eliminating Intermediate Measurements using Pseudorandom Generators. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [c83]Sumegha Garg, Pravesh K. Kothari, Ran Raz
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG. APPROX-RANDOM 2020: 21:1-21:18 - [c82]Sepehr Assadi, Ran Raz
Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms. FOCS 2020: 342-353 - [c81]Ran Raz
The Random-Query Model and the Memory-Bounded Coupon Collector. ITCS 2020: 20:1-20:11 - [i81]Sumegha Garg, Pravesh K. Kothari, Ran Raz:
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG. CoRR abs/2002.07235 (2020) - [i80]Uma Girish, Ran Raz, Wei Zhan:
Quantum Logspace Algorithm for Powering Matrices with Bounded Norm. CoRR abs/2006.04880 (2020) - [i79]Uma Girish, Ran Raz, Wei Zhan:
Lower Bounds for XOR of Forrelations. CoRR abs/2007.03631 (2020) - [i78]Justin Holmgren, Ran Raz:
A Parallel Repetition Theorem for the GHZ Game. CoRR abs/2008.05059 (2020) - [i77]Sepehr Assadi, Ran Raz:
Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms. CoRR abs/2009.01161 (2020) - [i76]Kunal Mittal, Ran Raz:
Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines. CoRR abs/2011.09093 (2020) - [i75]Uma Girish, Ran Raz, Wei Zhan:
Quantum Logspace Algorithm for Powering Matrices with Bounded Norm. Electron. Colloquium Comput. Complex. TR20 (2020) - [i74]Uma Girish, Ran Raz, Wei Zhan:
Lower Bounds for XOR of Forrelations. Electron. Colloquium Comput. Complex. TR20 (2020) - [i73]Justin Holmgren
A Parallel Repetition Theorem for the GHZ Game. Electron. Colloquium Comput. Complex. TR20 (2020) - [i72]Kunal Mittal, Ran Raz:
Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j52]Ran Raz
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning. J. ACM 66(1): 3:1-3:18 (2019) - [c80]Sumegha Garg, Ran Raz
Time-Space Lower Bounds for Two-Pass Learning. CCC 2019: 22:1-22:39 - [c79]Ran Raz
Oracle separation of BQP and PH. STOC 2019: 13-23 - [i71]Uma Girish, Ran Raz, Avishay Tal:
Quantum versus Randomized Communication Complexity, with Efficient Players. CoRR abs/1911.02218 (2019) - [i70]Sumegha Garg, Ran Raz, Avishay Tal:
Time-Space Lower Bounds for Two-Pass Learning. Electron. Colloquium Comput. Complex. TR19 (2019) - [i69]Uma Girish, Ran Raz, Avishay Tal:
Quantum versus Randomized Communication Complexity, with Efficient Players. Electron. Colloquium Comput. Complex. TR19 (2019) - [i68]Ran Raz, Wei Zhan:
The Random-Query Model and the Memory-Bounded Coupon Collector. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [c78]Mark Braverman, Anat Ganor, Gillat Kol, Ran Raz
A Candidate for a Strong Separation of Information and Communication. ITCS 2018: 11:1-11:13 - [c77]Sumegha Garg, Ran Raz
Extractor-based time-space lower bounds for learning. STOC 2018: 990-1002 - [c76]Yael Tauman Kalai, Ilan Komargodski, Ran Raz
A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols. DISC 2018: 34:1-34:16 - [i67]Ilan Komargodski, Ran Raz, Yael Tauman Kalai:
A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols. Electron. Colloquium Comput. Complex. TR18 (2018) - [i66]Ran Raz, Avishay Tal:
Oracle Separation of BQP and PH. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j51]Ilan Komargodski, Ran Raz
Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound. SIAM J. Comput. 46(1): 37-57 (2017) - [c75]Ran Raz
A Time-Space Lower Bound for a Large Class of Learning Problems. FOCS 2017: 732-742 - [c74]Gillat Kol, Ran Raz
Time-space hardness of learning sparse parities. STOC 2017: 1067-1080 - [i65]Sumegha Garg, Ran Raz, Avishay Tal:
Extractor-Based Time-Space Lower Bounds for Learning. CoRR abs/1708.02639 (2017) - [i64]Sumegha Garg, Ran Raz, Avishay Tal:
Extractor-Based Time-Space Lower Bounds for Learning. Electron. Colloquium Comput. Complex. TR17 (2017) - [i63]Ran Raz:
A Time-Space Lower Bound for a Large Class of Learning Problems. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j50]Gillat Kol, Ran Raz
Bounds on 2-query Locally Testable Codes with affine tests. Inf. Process. Lett. 116(8): 521-525 (2016) - [j49]Anat Ganor, Gillat Kol, Ran Raz
Exponential Separation of Information and Communication for Boolean Functions. J. ACM 63(5): 46:1-46:31 (2016) - [j48]Michael Dinitz
Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner. ACM Trans. Algorithms 12(2): 25:1-25:16 (2016) - [c73]Ran Raz
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning. FOCS 2016: 266-275 - [c72]Yael Tauman Kalai, Ran Raz
On the Space Complexity of Linear Programming with Preprocessing. ITCS 2016: 293-300 - [c71]Anat Ganor, Gillat Kol, Ran Raz
Exponential separation of communication and external information. STOC 2016: 977-986 - [e1]Ran Raz:
31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan. LIPIcs 50, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2016, ISBN 978-3-95977-008-8 [contents] - [i62]Ran Raz:
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning. CoRR abs/1602.05161 (2016) - [i61]Gillat Kol, Ran Raz, Avishay Tal:
Time-Space Hardness of Learning Sparse Parities. Electron. Colloquium Comput. Complex. TR16 (2016) - [i60]Ran Raz:
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning. Electron. Colloquium Comput. Complex. TR16 (2016) - [i59]Ran Raz:
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning. IACR Cryptol. ePrint Arch. 2016: 170 (2016) - 2015
- [j47]Tom Gur
Arthur-Merlin streaming complexity. Inf. Comput. 243: 145-165 (2015) - [c70]Noga Alon, Noam Nisan
Welfare Maximization with Limited Interaction. FOCS 2015: 1499-1512 - [c69]Anat Ganor, Gillat Kol, Ran Raz
Exponential Separation of Information and Communication for Boolean Functions. STOC 2015: 557-566 - [i58]Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein:
Welfare Maximization with Limited Interaction. CoRR abs/1504.01780 (2015) - [i57]Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein:
Welfare Maximization with Limited Interaction. Electron. Colloquium Comput. Complex. TR15 (2015) - [i56]Anat Ganor, Gillat Kol, Ran Raz:
Exponential Separation of Communication and External Information. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j46]Gil Cohen, Ran Raz
Nonmalleable Extractors with Short Seeds and Applications to Privacy Amplification. SIAM J. Comput. 43(2): 450-476 (2014) - [j45]Mark Braverman, Anup Rao, Ran Raz
Pseudorandom Generators for Regular Branching Programs. SIAM J. Comput. 43(3): 973-986 (2014) - [j44]Gillat Kol, Ran Raz
Competing-Provers Protocols for Circuit Evaluation. Theory Comput. 10: 107-131 (2014) - [c68]Gil Cohen, Anat Ganor, Ran Raz
Two Sides of the Coin Problem. APPROX-RANDOM 2014: 618-629 - [c67]Anat Ganor, Ran Raz
Space Pseudorandom Generators by Communication Complexity Lower Bounds. APPROX-RANDOM 2014: 692-703 - [c66]Anat Ganor, Gillat Kol, Ran Raz
Exponential Separation of Information and Communication. FOCS 2014: 176-185 - [c65]Yael Tauman Kalai, Ran Raz
How to delegate computations: the power of no-signaling proofs. STOC 2014: 485-494 - [i55]Gil Cohen, Anat Ganor, Ran Raz:
Two Sides of the Coin Problem. Electron. Colloquium Comput. Complex. TR14 (2014) - [i54]Anat Ganor, Gillat Kol, Ran Raz:
Exponential Separation of Information and Communication. Electron. Colloquium Comput. Complex. TR14 (2014) - [i53]Anat Ganor, Gillat Kol, Ran Raz:
Exponential Separation of Information and Communication for Boolean Functions. Electron. Colloquium Comput. Complex. TR14 (2014) - [i52]Yael Tauman Kalai, Ran Raz:
On the Space Complexity of Linear Programming with Preprocessing. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j43]Ran Raz
Tensor-Rank and Lower Bounds for Arithmetic Formulas. J. ACM 60(6): 40:1-40:15 (2013) - [c64]Gil Cohen, Ivan Bjerre Damgård, Yuval Ishai, Jonas Kölker, Peter Bro Miltersen, Ran Raz, Ron D. Rothblum:
Efficient Multiparty Protocols via Log-Depth Threshold Formulae - (Extended Abstract). CRYPTO (2) 2013: 185-202 - [c63]Ilan Komargodski, Ran Raz
Improved Average-Case Lower Bounds for DeMorgan Formula Size. FOCS 2013: 588-597 - [c62]Tom Gur
Arthur-Merlin Streaming Complexity. ICALP (1) 2013: 528-539 - [c61]Gillat Kol, Ran Raz
Competing provers protocols for circuit evaluation. ITCS 2013: 473-484 - [c60]Ilan Komargodski, Ran Raz
Average-case lower bounds for formula size. STOC 2013: 171-180 - [c59]Yael Tauman Kalai, Ran Raz
Delegation for bounded space. STOC 2013: 565-574 - [c58]Gillat Kol, Ran Raz
Interactive channel capacity. STOC 2013: 715-724 - [i51]Tom Gur, Ran Raz:
Arthur-Merlin Streaming Complexity. CoRR abs/1302.0418 (2013) - [i50]Gil Cohen, Ivan Bjerre Damgård, Yuval Ishai, Jonas Kölker, Peter Bro Miltersen, Ran Raz, Ron Rothblum:
Efficient Multiparty Protocols via Log-Depth Threshold Formulae. Electron. Colloquium Comput. Complex. TR13 (2013) - [i49]Anat Ganor, Ran Raz:
Space Pseudorandom Generators by Communication Complexity Lower Bounds. Electron. Colloquium Comput. Complex. TR13 (2013) - [i48]Tom Gur, Ran Raz:
Arthur-Merlin Streaming Complexity. Electron. Colloquium Comput. Complex. TR13 (2013) - [i47]Yael Tauman Kalai, Ran Raz, Ron Rothblum:
How to Delegate Computations: The Power of No-Signaling Proofs. Electron. Colloquium Comput. Complex. TR13 (2013) - [i46]Gillat Kol, Ran Raz:
Interactive Channel Capacity. Electron. Colloquium Comput. Complex. TR13 (2013) - [i45]Ilan Komargodski, Ran Raz, Avishay Tal:
Improved Average-Case Lower Bounds for DeMorgan Formula Size. Electron. Colloquium Comput. Complex. TR13 (2013) - [i44]Gil Cohen, Ivan Bjerre Damgård, Yuval Ishai, Jonas Kölker, Peter Bro Miltersen, Ran Raz, Ron D. Rothblum:
Efficient Multiparty Protocols via Log-Depth Threshold Formulae. IACR Cryptol. ePrint Arch. 2013: 480 (2013) - [i43]Yael Tauman Kalai, Ran Raz, Ron Rothblum:
How to Delegate Computations: The Power of No-Signaling Proofs. IACR Cryptol. ePrint Arch. 2013: 862 (2013) - 2012
- [c57]Ran Raz
A Strong Parallel Repetition Theorem for Projection Games on Expanders. CCC 2012: 247-257 - [c56]Gil Cohen, Ran Raz
Non-malleable Extractors with Short Seeds and Applications to Privacy Amplification. CCC 2012: 298-308 - [c55]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 - [c54]Gillat Kol, Ran Raz
Bounds on locally testable codes with unique tests. ITCS 2012: 190-202 - [i42]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) - [i41]Anat Ganor, Ilan Komargodski, Ran Raz:
The Spectrum of Small DeMorgan Formulas. Electron. Colloquium Comput. Complex. TR12 (2012) - [i40]Ilan Komargodski, Ran Raz:
Average-Case Lower Bounds for Formula Size. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j42]Irit Dinur
PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability. Comput. Complex. 20(3): 413-504 (2011) - [j41]Ran Raz
Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors. J. Comput. Syst. Sci. 77(1): 167-190 (2011) - [j40]Ran Raz
A Counterexample to Strong Parallel Repetition. SIAM J. Comput. 40(3): 771-777 (2011) - [c53]Kai-Min Chung, Yael Tauman Kalai, Feng-Hao Liu, Ran Raz:
Memory Delegation. CRYPTO 2011: 151-168 - [i39]Gil Cohen, Ran Raz, Gil Segev:
Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification. Electron. Colloquium Comput. Complex. TR11 (2011) - [i38]Gillat Kol, Ran Raz:
Competing Provers Protocols for Circuit Evaluation. Electron. Colloquium Comput. Complex. TR11 (2011) - [i37]Kai-Min Chung, Yael Tauman Kalai, Feng-Hao Liu, Ran Raz:
Memory Delegation. IACR Cryptol. ePrint Arch. 2011: 273 (2011) - 2010
- [j39]Dana Moshkovitz, Ran Raz
Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size. Comput. Complex. 19(3): 367-422 (2010) - [j38]Dana Moshkovitz, Ran Raz
Two-query PCP with subconstant error. J. ACM 57(5): 29:1-29:29 (2010) - [j37]Ran Raz
Elusive Functions and Lower Bounds for Arithmetic Circuits. Theory Comput. 6(1): 135-177 (2010) - [c52]Ran Raz
Parallel Repetition of Two Prover Games (Invited Survey). CCC 2010: 3-6 - [c51]Mark Braverman, Anup Rao, Ran Raz
Pseudorandom Generators for Regular Branching Programs. FOCS 2010: 40-47 - [c50]Ran Raz
Tensor-rank and lower bounds for arithmetic formulas. STOC 2010: 659-666 - [i36]Shira Kritchman, Ran Raz:
The Surprise Examination Paradox and the Second Incompleteness Theorem. CoRR abs/1011.4974 (2010) - [i35]Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff:
Pseudorandom Generators for Regular Branching Programs. Electron. Colloquium Comput. Complex. TR10 (2010) - [i34]Ran Raz:
Tensor-Rank and Lower Bounds for Arithmetic Formulas. Electron. Colloquium Comput. Complex. TR10 (2010) - [i33]Ran Raz, Ricky Rosen:
A Strong Parallel Repetition Theorem for Projection Games on Expanders. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j36]Ran Raz
Quantum Information and the PCP Theorem. Algorithmica 55(3): 462-489 (2009) - [j35]Ran Raz
Lower Bounds and Separations for Constant Depth Multilinear Circuits. Comput. Complex. 18(2): 171-207 (2009) - [j34]Ran Raz
Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM 56(2): 8:1-8:17 (2009) - [c49]Boaz Barak, Anup Rao, Ran Raz, Ricky Rosen, Ronen Shaltiel:
Strong Parallel Repetition Theorem for Free Projection Games. APPROX-RANDOM 2009: 352-365 - [c48]Yael Tauman Kalai, Ran Raz:
Probabilistically Checkable Arguments. CRYPTO 2009: 143-159 - [i32]Gillat Kol, Ran Raz:
Locally Testable Codes Analogues to the Unique Games Conjecture Do Not Exist. Electron. Colloquium Comput. Complex. TR09 (2009) - [i31]Gillat Kol, Ran Raz:
Bounds on 2-Query Locally Testable Codes with Affine Tests. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [j33]Ran Raz
Resolution over linear equations and multilinear proofs. Ann. Pure Appl. Log. 155(3): 194-224 (2008) - [j32]Ran Raz
The Strength of Multilinear Proofs. Comput. Complex. 17(3): 407-457 (2008) - [j31]Ran Raz
Balancing Syntactically Multilinear Arithmetic Circuits. Comput. Complex. 17(4): 515-535 (2008) - [j30]Ariel Gabizon, Ran Raz
Deterministic extractors for affine sources over large fields. Comb. 28(4): 415-440 (2008) - [j29]Zeev Dvir, Ran Raz
Analyzing linear mergers. Random Struct. Algorithms 32(3): 334-345 (2008) - [j28]Dana Moshkovitz, Ran Raz
Sub-Constant Error Low Degree Test of Almost-Linear Size. SIAM J. Comput. 38(1): 140-180 (2008) - [j27]Ran Raz
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. SIAM J. Comput. 38(4): 1624-1647 (2008) - [j26]Dmitry Gavinsky, Julia Kempe
Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography. SIAM J. Comput. 38(5): 1695-1708 (2008) - [c47]Ran Raz
Lower Bounds and Separations for Constant Depth Multilinear Circuits. CCC 2008: 128-139 - [c46]Ran Raz
Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors. FOCS 2008: 273-282 - [c45]Dana Moshkovitz, Ran Raz
Two Query PCP with Sub-Constant Error. FOCS 2008: 314-323 - [c44]Ran Raz
A Counterexample to Strong Parallel Repetition. FOCS 2008: 369-373 - [c43]Yael Tauman Kalai, Ran Raz:
Interactive PCP. ICALP (2) 2008: 536-547 - [c42]Ran Raz
Elusive functions and lower bounds for arithmetic circuits. STOC 2008: 711-720 - [i30]Dana Moshkovitz, Ran Raz:
Two Query PCP with Sub-Constant Error. Electron. Colloquium Comput. Complex. TR08 (2008) - [i29]Ran Raz:
Elusive Functions and Lower Bounds for Arithmetic Circuits. Electron. Colloquium Comput. Complex. TR08 (2008) - [i28]Ran Raz:
A Counterexample to Strong Parallel Repetition. Electron. Colloquium Comput. Complex. TR08 (2008) - [i27]Ran Raz, Amir Yehudayoff:
Lower Bounds and Separations for Constant Depth Multilinear Circuits. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [c41]Ran Raz
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. FOCS 2007: 438-448 - [c40]Dmitry Gavinsky, Julia Kempe
Exponential separations for one-way quantum communication complexity, with applications to cryptography. STOC 2007: 516-525 - [i26]Ran Raz, Iddo Tzameret:
Resolution over Linear Equations and Multilinear Proofs. CoRR abs/0708.1529 (2007) - [i25]Yael Tauman Kalai, Ran Raz:
Interactive PCP. Electron. Colloquium Comput. Complex. TR07 (2007) - [i24]Dana Moshkovitz, Ran Raz:
Sub-Constant Error Probabilistically Checkable Proof of Almost Linear Size. Electron. Colloquium Comput. Complex. TR07 (2007) - [i23]Ran Raz, Iddo Tzameret:
Resolution over Linear Equations and Multilinear Proofs. Electron. Colloquium Comput. Complex. TR07 (2007) - [i22]Ran Raz, Amir Yehudayoff:
Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [j25]Ariel Gabizon, Ran Raz
Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed. SIAM J. Comput. 36(4): 1072-1094 (2006) - [j24]Ran Raz
Separation of Multilinear Circuit and Formula Size. Theory Comput. 2(6): 121-135 (2006) - [c39]Yael Tauman Kalai, Ran Raz
Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP. FOCS 2006: 355-366 - [c38]Dana Moshkovitz, Ran Raz
Sub-constant error low degree test of almost-linear size. STOC 2006: 21-30 - [i21]Iordanis Kerenidis, Ran Raz:
The one-way communication complexity of the Boolean Hidden Matching Problem. CoRR abs/quant-ph/0607173 (2006) - [i20]Ran Raz, Iddo Tzameret:
The Strength of Multilinear Proofs. Electron. Colloquium Comput. Complex. TR06 (2006) - [i19]Iordanis Kerenidis, Ran Raz:
The one-way communication complexity of the Boolean Hidden Matching Problem. Electron. Colloquium Comput. Complex. TR06 (2006) - [i18]Ran Raz, Amir Shpilka, Amir Yehudayoff:
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [j23]Ran Raz
Deterministic polynomial identity testing in non-commutative models. Comput. Complex. 14(1): 1-19 (2005) - [j22]Dieter van Melkebeek, Ran Raz
A time lower bound for satisfiability. Theor. Comput. Sci. 348(2-3): 311-320 (2005) - [c37]Ariel Gabizon, Ran Raz
Deterministic Extractors for Affine Sources over Large Fields. FOCS 2005: 407-418 - [c36]Ran Raz
Quantum Information and the PCP Theorem. FOCS 2005: 459-468 - [c35]Ran Raz
Extractors with weak random seeds. STOC 2005: 11-20 - [i17]Zeev Dvir, Ran Raz:
Analyzing Linear Mergers. Electron. Colloquium Comput. Complex. TR05 (2005) - [i16]Ran Raz:
Quantum Information and the PCP Theorem. Electron. Colloquium Comput. Complex. TR05 (2005) - [i15]Dana Moshkovitz, Ran Raz:
Sub-Constant Error Low Degree Test of Almost Linear Size. Electron. Colloquium Comput. Complex. TR05 (2005) - [i14]Ariel Gabizon, Ran Raz:
Deterministic Extractors for Affine Sources over Large Fields. Electron. Colloquium Comput. Complex. TR05 (2005) - [i13]Ariel Gabizon, Ran Raz, Ronen Shaltiel:
Deterministic Extractors for Bit-fixing Sources by Obtaining an Independent Seed. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j21]Toniann Pitassi, Ran Raz
Regular Resolution Lower Bounds For The Weak Pigeonhole Principle. Comb. 24(3): 503-524 (2004) - [j20]Ran Raz
Resolution lower bounds for the weak pigeonhole principle. J. ACM 51(2): 115-138 (2004) - [j19]Cyril Gavoille, David Peleg, Stéphane Pérennes, Ran Raz
Distance labeling in graphs. J. Algorithms 53(1): 85-112 (2004) - [j18]Joshua Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles. SIAM J. Comput. 34(2): 261-276 (2004) - [c34]Yevgeniy Dodis, Ariel Elbaz, Roberto Oliveira, Ran Raz:
Improved Randomness Extraction from Two Independent Sources. APPROX-RANDOM 2004: 334-344 - [c33]Ran Raz
Deterministic Polynomial Identity Testing in Non-Commutative Models. CCC 2004: 215-222 - [c32]Ran Raz
On the Power of Quantum Proofs. CCC 2004: 260-274 - [c31]Ran Raz
Multilinear-NC neq Multilinear-NC. FOCS 2004: 344-351 - [c30]Ariel Gabizon, Ran Raz
Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed. FOCS 2004: 394-403 - [c29]Dieter van Melkebeek, Ran Raz:
A Time Lower Bound for Satisfiability. ICALP 2004: 971-982 - [c28]Ran Raz
Multi-linear formulas for permanent and determinant are of super-polynomial size. STOC 2004: 633-641 - [p2]Ran Raz
Quantum computation. Computational Complexity Theory 2004: 127-155 - [p1]Ran Raz
Circuit and Communication Complexity. Computational Complexity Theory 2004: 159-155 - [i12]Ran Raz:
Multilinear-NC1 != Multilinear-NC2. Electron. Colloquium Comput. Complex. TR04 (2004) - [i11]Ran Raz:
Extractors with Weak Random Seeds. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [j17]Irit Dinur
Approximating CVP to Within Almost-Polynomial Factors is NP-Hard. Comb. 23(2): 205-243 (2003) - [j16]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) - [j15]Ran Raz
Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates. SIAM J. Comput. 32(2): 488-513 (2003) - [j14]Ran Raz
On the Complexity of Matrix Product. SIAM J. Comput. 32(5): 1356-1369 (2003) - [i10]Ran Raz:
P != NP, propositional proof complexity, and resolution lower bounds for the weak pigeonhole principle. CoRR cs.CC/0304041 (2003) - [i9]Ran Raz:
Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size. Electron. Colloquium Comput. Complex. TR03 (2003) - 2002
- [j13]Ran Raz
Extracting all the Randomness and Reducing the Error in Trevisan's Extractors. J. Comput. Syst. Sci. 65(1): 97-128 (2002) - [c27]Ran Raz
Resolution Lower Bounds for the Weak Pigeonhole Principle. CCC 2002: 3 - [c26]Josh Buresh-Oppenheim, Paul Beame
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles. FOCS 2002: 583-592 - [c25]Ran Raz
On the complexity of matrix product. STOC 2002: 144-151 - [c24]Ran Raz
Resolution lower bounds for the weak pigeonhole principle. STOC 2002: 553-562 - [i8]Ran Raz:
On the Complexity of Matrix Product. Electron. Colloquium Comput. Complex. TR02 (2002) - [i7]Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal:
Bounded-depth Frege lower bounds for weaker pigeonhole principles. Electron. Colloquium Comput. Complex. TR02 (2002) - 2001
- [c23]Cyril Gavoille, David Peleg, Stephane Perennes, Ran Raz
Distance labeling in graphs. SODA 2001: 210-219 - [c22]Toniann Pitassi, Ran Raz
Regular resolution lower bounds for the weak pigeonhole principle. STOC 2001: 347-355 - [c21]Oded Lachish, Ran Raz
Explicit lower bound of 4.5n - o(n) for boolena circuits. STOC 2001: 399-408 - [c20]Ran Raz
Lower bounds for matrix product, in bounded depth circuits with arbitrary gates. STOC 2001: 409-418 - [i6]Ran Raz:
Resolution Lower Bounds for the Weak Pigeonhole Principle. Electron. Colloquium Comput. Complex. TR01 (2001) - 2000
- [j12]Ran Raz
The BNS-Chung criterion for multi-party communication complexity. Comput. Complex. 9(2): 113-122 (2000) - [j11]Ran Raz
VC-Dimension of Sets of Permutations. Comb. 20(2): 241-255 (2000) - [j10]Maria Luisa Bonet
On Interpolation and Automatization for Frege Systems. SIAM J. Comput. 29(6): 1939-1967 (2000) - [c19]Tzvika Hartman, Ran Raz:
On the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors. ICALP Satellite Workshops 2000: 3-22 - [c18]Danny Harnik, Ran Raz
Higher lower bounds on monotone size. STOC 2000: 378-387 - [i5]Ran Raz, Amir Shpilka:
Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates. Electron. Colloquium Comput. Complex. TR00 (2000) - [i4]Tzvika Hartman, Ran Raz:
On the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors. Electron. Colloquium Comput. Complex. TR00 (2000)
1990 – 1999
- 1999
- [j9]Ran Raz
Separation of the Monotone NC Hierarchy. Comb. 19(3): 403-435 (1999) - [j8]Ran Raz
Arthur-Merlin Games in Boolean Decision Trees. J. Comput. Syst. Sci. 59(2): 346-372 (1999) - [c17]Ran Raz
Error Reduction for Extractors. FOCS 1999: 191-201 - [c16]Irit Dinur
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability. STOC 1999: 29-40 - [c15]Ran Raz
Extracting all the Randomness and Reducing the Error in Trevisan's Extractors. STOC 1999: 149-158 - [c14]Ran Raz
On Recycling the Randomness of States in Space Bounded Computation. STOC 1999: 159-168 - [c13]Ran Raz
Exponential Separation of Quantum and Classical Communication Complexity. STOC 1999: 358-367 - [i3]Ran Raz, Omer Reingold, Salil P. Vadhan:
Extracting All the Randomness and Reducing the Error in Trevisan's Extractors. Electron. Colloquium Comput. Complex. TR99 (1999) - 1998
- [j7]Yuri Rabinovich, Ran Raz
Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs. Discret. Comput. Geom. 19(1): 79-94 (1998) - [j6]Ran Raz
A Parallel Repetition Theorem. SIAM J. Comput. 27(3): 763-803 (1998) - [c12]Ran Raz
Arthur-Merlin Games in Boolean Decision Trees. CCC 1998: 58-67 - [i2]Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability. Electron. Colloquium Comput. Complex. TR98 (1998) - 1997
- [j5]Maria Luisa Bonet, Toniann Pitassi, Ran Raz
Lower Bounds for Cutting Planes Proofs with Small Coefficients. J. Symb. Log. 62(3): 708-728 (1997) - [c11]Ran Raz
Separation of the Monotone NC Hierarchy. FOCS 1997: 234-243 - [c10]Maria Luisa Bonet, Toniann Pitassi, Ran Raz
No Feasible Interpolation for TC0-Frege Proofs. FOCS 1997: 254-263 - [c9]Itzhak Parnafes, Ran Raz
Direct Product Results and the GCD Problem, in Old and New Communication Models. STOC 1997: 363-372 - [c8]Ran Raz
A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP. STOC 1997: 475-484 - [i1]Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin:
Arthur-Merlin Games in Boolean Decision Trees. Electron. Colloquium Comput. Complex. TR97 (1997) - 1995
- [j4]Mauricio Karchmer, Ran Raz
Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity. Comput. Complex. 5(3/4): 191-204 (1995) - [j3]Ran Raz
Fourier Analysis for Probabilistic Communication Complexity. Comput. Complex. 5(3/4): 205-221 (1995) - [j2]Ran Raz
On the "Log Rank"-Conjecture in Communication Complexity. Comb. 15(4): 567-588 (1995) - [c7]Ran Raz
A parallel repetition theorem. STOC 1995: 447-456 - [c6]Maria Luisa Bonet, Toniann Pitassi, Ran Raz
Lower bounds for cutting planes proofs with small coefficients. STOC 1995: 575-584 - 1994
- [c5]Russell Impagliazzo
A Direct Product Theorem. SCT 1994: 88-96 - 1993
- [c4]Ran Raz
On the "log rank"-Conjecture in Communication Complexity. FOCS 1993: 168-176 - 1992
- [b1]Ran Raz:
חסמים תחתונים לסיבוכיות תקשורת הסתברותית ולעומק מעגלים בוליאנים מונוטונים (Lower bounds for probabilistic communication complexity and for the depth of monotone boolean circuits.). Hebrew University of Jerusalem, Israel, 1992 - [j1]Ran Raz
Monotone Circuits for Matching Require Linear Depth. J. ACM 39(3): 736-744 (1992) - 1991
- [c3]Mauricio Karchmer, Ran Raz
Super-logarithmic Depth Lower Bounds via Direct Sum in Communication Coplexity. SCT 1991: 299-304 - 1990
- [c2]Ran Raz
Monotone Circuits for Matching Require Linear Depth. STOC 1990: 287-292
1980 – 1989
- 1989
- [c1]Ran Raz
Probabilistic Communication Complexity of Boolean Relations (Extended Abstract). FOCS 1989: 562-567
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-05-03 00:04 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: