default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDRan 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
- 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, Wei Zhan:
Is Untrusted Randomness Helpful? ITCS 2023: 56:1-56:18 - [c93]Qipeng Liu, Ran Raz, Wei Zhan:
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, Avishay Tal:
Quantum versus Randomized Communication Complexity, with Efficient Players. Comput. Complex. 31(2): 17 (2022) - [j56]Yael Tauman Kalai, Ran Raz, Ron D. Rothblum:
How to Delegate Computations: The Power of No-Signaling Proofs. J. ACM 69(1): 1:1-1:82 (2022) - [j55]Ran Raz, Avishay Tal:
Oracle Separation of BQP and PH. J. ACM 69(4): 30:1-30:21 (2022) - [c92]Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan:
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, Kunal Mittal, Ran Raz, Wei Zhan:
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, Kunal Mittal, Ran Raz, Wei Zhan:
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, Wei Zhan:
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, Kunal Mittal, Ran Raz, Wei Zhan:
Parallel Repetition for the GHZ Game: A Simpler Proof. APPROX-RANDOM 2021: 62:1-62:19 - [c86]Uma Girish, Ran Raz, Wei Zhan:
Quantum Logspace Algorithm for Powering Matrices with Bounded Norm. ICALP 2021: 73:1-73:20 - [c85]Uma Girish, Ran Raz, Avishay Tal:
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, Kunal Mittal, Ran Raz, Wei Zhan:
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, Wei Zhan:
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, Ran Raz:
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, Avishay Tal:
Time-Space Lower Bounds for Two-Pass Learning. CCC 2019: 22:1-22:39 - [c79]Ran Raz, Avishay Tal:
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, Avishay Tal:
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, Avishay Tal:
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, Avishay Tal:
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, Guy Kortsarz, Ran Raz:
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, Oded Regev:
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, Ran Raz:
Arthur-Merlin streaming complexity. Inf. Comput. 243: 145-165 (2015) - [c70]Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein:
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, Gil Segev:
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, Amir Yehudayoff:
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, Ron D. Rothblum:
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, Avishay Tal:
Improved Average-Case Lower Bounds for DeMorgan Formula Size. FOCS 2013: 588-597 - [c62]Tom Gur, Ran Raz:
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, Ron D. Rothblum:
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, Ricky Rosen:
A Strong Parallel Repetition Theorem for Projection Games on Expanders. CCC 2012: 247-257 - [c56]Gil Cohen, Ran Raz, Gil Segev:
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, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra:
PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability. Comput. Complex. 20(3): 413-504 (2011) - [j41]Ran Raz, Amir Yehudayoff:
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]