Ran Raz
#14,969
Most Influential Person Now
Israeli theoretical computer scientist
Ran Raz's AcademicInfluence.com Rankings
Ran Razcomputer-science Degrees
Computer Science
#936
World Rank
#971
Historical Rank
Theoretical Computer Science
#18
World Rank
#18
Historical Rank
Database
#7292
World Rank
#7548
Historical Rank
Download Badge
Computer Science
Why Is Ran Raz Influential?
(Suggest an Edit or Addition)According to Wikipedia, Ran Raz is a computer scientist who works in the area of computational complexity theory. He was a professor in the faculty of mathematics and computer science at the Weizmann Institute. He is now a professor of computer science at Princeton University.
Ran Raz's Published Works
Number of citations in a given year to any of this author's works
Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author
Published Works
- A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP (1997) (919)
- A parallel repetition theorem (1995) (792)
- ProMate: a structure based prediction program to identify the location of protein-protein binding sites. (2004) (446)
- Distance labeling in graphs (2001) (350)
- Exponential separation of quantum and classical communication complexity (1999) (251)
- Extracting all the randomness and reducing the error in Trevisan's extractors (1999) (222)
- Exponential separations for one-way quantum communication complexity, with applications to cryptography (2006) (213)
- Lower bounds for cutting planes proofs with small coefficients (1995) (190)
- Extractors with weak random seeds (2005) (185)
- Separation of the Monotone NC Hierarchy (1997) (184)
- Two Query PCP with Sub-Constant Error (2008) (183)
- Deterministic polynomial identity testing in non-commutative models (2004) (159)
- Super-logarithmic depth lower bounds via the direct sum in communication complexity (1991) (153)
- Monotone circuits for matching require linear depth (1990) (147)
- Multi-linear formulas for permanent and determinant are of super-polynomial size (2004) (142)
- Memory Delegation (2011) (132)
- How to delegate computations: the power of no-signaling proofs (2014) (132)
- On the complexity of matrix product (2002) (127)
- Monotone circuits for matching require linear depth (1992) (116)
- Resolution lower bounds for the weak pigeon hole principle (2002) (113)
- Lower Bounds and Separations for Constant Depth Multilinear Circuits (2008) (111)
- On Interpolation and Automatization for Frege Systems (2000) (110)
- Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs (1998) (102)
- On recycling the randomness of states in space bounded computation (1999) (101)
- Deterministic extractors for affine sources over large fields (2005) (98)
- Deterministic extractors for bit-fixing sources by obtaining an independent seed (2004) (96)
- A Counterexample to Strong Parallel Repetition (2008) (95)
- Separation of Multilinear Circuit and Formula Size (2006) (89)
- Interactive channel capacity (2013) (84)
- Elusive functions and lower bounds for arithmetic circuits (2008) (83)
- Interactive PCP (2008) (76)
- Pseudorandom Generators for Regular Branching Programs (2010) (74)
- The BNS-Chung criterion for multi-party communication complexity (2000) (73)
- Oracle separation of BQP and PH (2019) (72)
- Improved Randomness Extraction from Two Independent Sources (2004) (71)
- On the “log rank”-conjecture in communication complexity (1993) (70)
- Resolution over linear equations and multilinear proofs (2007) (68)
- Tensor-Rank and Lower Bounds for Arithmetic Formulas (2013) (66)
- A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits (2007) (66)
- Delegation for bounded space (2013) (65)
- Exponential Separation of Information and Communication (2014) (65)
- Non-malleable Extractors with Short Seeds and Applications to Privacy Amplification (2012) (64)
- Multi-linear formulas for permanent and determinant are of super-polynomial size (2009) (63)
- PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability (1999) (63)
- Probabilistically Checkable Arguments (2009) (63)
- Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning (2016) (60)
- Direct product results and the GCD problem, in old and new communication models (1997) (56)
- Balancing Syntactically Multilinear Arithmetic Circuits (2008) (54)
- Sub-constant error low degree test of almost-linear size (2006) (53)
- A Time-Space Lower Bound for a Large Class of Learning Problems (2017) (53)
- Explicit lower bound of 4.5n - o(n) for boolena circuits (2001) (51)
- Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors (2008) (51)
- Regular resolution lower bounds for the weak pigeonhole principle (2001) (49)
- Error reduction for extractors (1999) (49)
- Lower bounds for matrix product, in bounded depth circuits with arbitrary gates (2001) (48)
- Extractor-based time-space lower bounds for learning (2017) (46)
- Time-space hardness of learning sparse parities (2017) (45)
- Probabilistic communication complexity of Boolean relations (1989) (43)
- Improved Average-Case Lower Bounds for DeMorgan Formula Size (2013) (43)
- Fourier analysis for probabilistic communication complexity (1995) (43)
- The Surprise Examination Paradox and the Second Incompleteness Theorem (2010) (38)
- Strong Parallel Repetition Theorem for Free Projection Games (2009) (38)
- Exponential Separation of Information and Communication for Boolean Functions (2015) (37)
- Higher lower bounds on monotone size (2000) (35)
- Efficient Multiparty Protocols via Log-Depth Threshold Formulae (2013) (35)
- Average-case lower bounds for formula size (2013) (34)
- Exponential Separation of Information and Communication for Boolean Functions (2016) (34)
- Welfare Maximization with Limited Interaction (2015) (33)
- Exponential separation of communication and external information (2016) (33)
- Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner (2012) (32)
- On the power of quantum proofs (2004) (30)
- Quantum Information and the PCP Theorem (2005) (28)
- No feasible interpolation for TC/sup 0/-Frege proofs (1997) (27)
- Arthur-Merlin streaming complexity (2013) (27)
- Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP (2006) (26)
- On the distribution of the number of roots of polynomials and explicit weak designs (2003) (25)
- Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size (2010) (24)
- A Strong Parallel Repetition Theorem for Projection Games on Expanders (2012) (24)
- A direct product theorem (1994) (23)
- Tensor-rank and lower bounds for arithmetic formulas (2010) (23)
- Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound (2017) (19)
- Two Sides of the Coin Problem (2014) (18)
- A time lower bound for satisfiability (2004) (18)
- VC-Dimension of Sets of Permutations (2000) (17)
- The Strength of Multilinear Proofs (2008) (16)
- Extracting all the Randomness and Reducing the Error in Trevisan's Extractors (2002) (16)
- Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms (2020) (15)
- A Lower Bound for Adaptively-Secure Collective Coin Flipping Protocols (2018) (15)
- Lower Bounds for the Weak Pigeonhole Principle (2002) (14)
- Competing provers protocols for circuit evaluation (2013) (14)
- Time-space lower bounds for two-pass learning (2019) (13)
- The one-way communication complexity of the Boolean Hidden Matching Problem (2006) (13)
- Multilinear-NC/sub 1/ /spl ne/ multilinear-NC/sub 2/ (2004) (12)
- Multilinear-NC 1 != Multilinear-NC 2 (2004) (12)
- Regular Resolution Lower Bounds For The Weak Pigeonhole Principle (2004) (12)
- On the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors (2000) (11)
- Probabilistic Communication Complexity of Boolean Relations (Extended Abstract) (1989) (11)
- Lower Bounds for XOR of Forrelations (2020) (10)
- Analyzing linear mergers (2008) (10)
- Multilinear-NC1 != Multilinear-NC2 (2004) (9)
- Fast Learning Requires Good Memory : A Time-Space Lower Bound for Parity Learning (2018) (9)
- On the Space Complexity of Linear Programming with Preprocessing (2016) (9)
- Quantum Logspace Algorithm for Powering Matrices with Bounded Norm (2020) (8)
- Space Pseudorandom Generators by Communication Complexity Lower Bounds (2013) (8)
- Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG (2020) (6)
- Quantum versus Randomized Communication Complexity, with Efficient Players (2019) (6)
- Parallel Repetition of Two Prover Games (Invited Survey) (2010) (6)
- Bounded-depth Frege lower bounds for weaker pigeonhole principles (2002) (6)
- The Spectrum of Small DeMorgan Formulas (2012) (5)
- A Sub-constant Error-probability Pcp Characterization of Np Part I: the Main Proof (1996) (5)
- Locally Testable Codes Analogues to the Unique Games Conjecture Do Not Exist (2009) (5)
- Arthur-Merlin games in Boolean decision trees (1998) (5)
- A Parallel Repetition Theorem for the GHZ Game (2020) (5)
- Bounds on 2-query Locally Testable Codes with affine tests (2016) (4)
- Parallel Repetition for the GHZ Game: A Simpler Proof (2021) (4)
- A Candidate for a Strong Separation of Information and Communication (2018) (4)
- Quantum Information and the PCP Theorem (4)
- Memory-Sample Lower Bounds for Learning Parity with Noise (2021) (4)
- Parallel Repetition of Two Prover Games (2010) (4)
- A Sub-constant Error-probability Pcp Characterization of Np Part Ii: the Consistency Test (1996) (3)
- Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines (2020) (3)
- Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs (2022) (3)
- On the Noise Stability of Small De Morgan Formulas (2013) (3)
- Super-logarithmic Depth Lower Bounds via Direct Sum in Communication Coplexity (1991) (3)
- Fast Learning Requires Good Memory (2018) (3)
- Multilinear-NC neq Multilinear-NC (2004) (2)
- Parallel repetition for all 3-player games over binary alphabet (2022) (2)
- Proceedings of the 31st Conference on Computational Complexity (2016) (2)
- Eliminating Intermediate Measurements using Pseudorandom Generators (2021) (2)
- Multilinear-NC 1 6 = Multilinear-NC 2 (2007) (2)
- How to Delegate Computations: The Power of No-Signaling Proofs (2021) (1)
- Min-Rep instances with large supergirth and the hardness of approximating basic spanners (2011) (1)
- Is Untrusted Randomness Helpful? (2023) (1)
- Circuit and Communication Complexity (2004) (1)
- Monotone Complexity by Switching Lemma ∗ (2007) (1)
- The Random-Query Model and the Memory-Bounded Coupon Collector (2019) (1)
- LIPIcs, Volume 50, CCC'16, Complete Volume (2016) (0)
- C C ] 1 0 A ug 2 00 7 RESOLUTION OVER LINEAR EQUATIONS AND MULTILINEAR PROOFS (0)
- A Lower Bound for Adaptively-Secure Collective Coin Flipping Protocols (2020) (0)
- Interactive PCP 2007 (2017) (0)
- Front Matter, Table of Contents, Preface, Awards, Conference Organization, External Reviewers (2017) (0)
- An Improved Lower Bound for Ap-proximating CVP (2000) (0)
- Information and Computation Arthur-Merlin Streaming Complexity (2014) (0)
- Bounds on locally testable codes with unique tests (2012) (0)
- Example 4 in Subsection 3.2 We Proved That ~ R (1) (1994) (0)
- Error Reduction for Extractors The Harvard community has made this article openly available. Please share how this access benefits you. Your story matters (2009) (0)
- Quantum computation (2004) (0)
- The Random-Query Model and the Memory-Bounded Coupon Collector (2019) (0)
- Explicit lower bound of for boolena circuits (2001) (0)
- חסמים תחתונים לסיבוכיות תקשורת הסתברותית ולעומק מעגלים בוליאנים מונוטונים (Lower bounds for probabilistic communication complexity and for the depth of monotone boolean circuits.) (1992) (0)
- Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory (2023) (0)
- Circuit and Communication Complexity (2016) (0)
- Oracle Separation of BQP and PH (2022) (0)
- Certified Hardness vs. Randomness for Log-Space (2023) (0)
This paper list is powered by the following services:
Other Resources About Ran Raz
What Schools Are Affiliated With Ran Raz?
Ran Raz is affiliated with the following schools:
