Ran Raz: Publications

  1. ``Exponential Separation of Information and Communication'' ,
    A.Ganor, G.Kol, R.Raz

  2. ``Two Sides of the Coin Problem'' ,
    G.Cohen, A.Ganor, R.Raz

  3. ``Space Pseudorandom Generators by Communication Complexity Lower Bounds'' ,
    A.Ganor, R.Raz

  4. ``How to Delegate Computations: The Power of No-Signaling Proofs'' ,
    Y.Kalai, R.Raz, R.Rothblum

  5. ``Improved Average-Case Lower Bounds for DeMorgan Formula Size'' ,
    I.Komargodski, R.Raz, A.Tal

  6. ``Efficient Multiparty Protocols via Log-Depth Threshold Formulae'',
    G.Cohen, I.Damgard, Y.Ishai, J.Kolker, P.B.Miltersen, R.Raz, R.Rothblum,

  7. ``Delegation for Bounded Space'' ,
    Y.Kalai, R.Raz, R.Rothblum

  8. ``Interactive Channel Capacity'' ,
    G.Kol, R.Raz,

  9. ``Average-Case Lower Bounds for Formula Size'' ,
    I.Komargodski, R.Raz,

  10. ``Arthur-Merlin Streaming Complexity'' ,
    T.Gur, R.Raz,

  11. ``Competing Provers Protocols for Circuit Evaluation'' ,
    G.Kol, R.Raz,

  12. ``Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner'' ,
    M.Dinitz, G.Kortsarz, R.Raz,

  13. ``Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification'' ,
    G.Cohen, R.Raz, G.Segev,

  14. ``A Strong Parallel Repetition Theorem for Projection Games on Expanders'' ,
    R.Raz, R.Rosen,

  15. ``Bounds on Locally Testable Codes with Unique Tests'' ,
    G.Kol, R.Raz,

  16. ``Memory Delegation'',
    K.M.Chung, Y.Kalai, F.H.Liu, R.Raz,

  17. ``The Surprise Examination Paradox and the Second Incompleteness Theorem'' ,
    S.Kritchman, R.Raz,

  18. ``Pseudorandom Generators for Regular Branching Programs'' ,
    M.Braverman, A.Rao, R.Raz, A.Yehudayoff,

  19. ``Tensor-Rank and Lower Bounds for Arithmetic Formulas'' ,

  20. ``Parallel Repetition of Two Prover Games'' (a short survey) ,

  21. ``Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size'',
    D.Moshkovitz, R.Raz,

  22. ``Bounds on 2-Query Locally Testable Codes with Affine Tests'' ,
    G.Kol, R.Raz,

  23. ``Strong Parallel Repetition Theorem for Free Projection Games'',
    B.Barak, A.Rao, R.Raz, R.Rosen, R.Shaltiel,

  24. ``Probabilistically Checkable Arguments'',
    Y.Kalai, R.Raz,

  25. ``Two Query PCP with Sub-Constant Error'',
    D.Moshkovitz, R.Raz,

  26. ``A Counterexample to Strong Parallel Repetition'',

  27. ``Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors'',
    R.Raz, A.Yehudayoff,

  28. ``Elusive Functions and Lower Bounds for Arithmetic Circuits'',

  29. ``Lower Bounds and Separations for Constant Depth Multilinear Circuits '',
    R.Raz, A.Yehudayoff,

  30. ``Interactive PCP'',
    Y.Kalai, R.Raz,

  31. ``Analyzing Linear Mergers'',
    Z.Dvir, R.Raz,

  32. ``Resolution over Linear Equations and Multilinear Proofs'',
    R.Raz, I.Tzameret,

  33. ``The Strength of Multilinear Proofs'',
    R.Raz, I.Tzameret,

  34. ``Balancing Syntactically Multilinear Arithmetic Circuits'',
    R.Raz, A.Yehudayoff,

  35. ``A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits'',
    R.Raz, A.Shpilka, A.Yehudayoff,

  36. ``Exponential Separations for One-Way Quantum Communication Complexity, with Applications to Cryptography'',
    D.Gavinsky, J.Kempe, I.Kerenidis, R.Raz, R.de-Wolf,

  37. ``Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP'',
    Y.Kalai, R.Raz,

  38. ``Sub-Constant Error Low Degree Test of Almost Linear Size'',
    D.Moshkovitz, R.Raz,

  39. ``Quantum Information and the PCP Theorem'',

  40. ``Deterministic Extractors for Affine Sources over Large Fields'',
    A.Gabizon, R.Raz,

  41. ``Extractors with Weak Random Seeds'',

  42. ``Separation of Multilinear Circuit and Formula Size'',

  43. ``Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed'',
    A.Gabizon, R.Raz, R.Shaltiel,

  44. ``Improved Randomness Extraction from Two Independent Sources'',
    Y.Dodis, A.Elbaz, R.Oliveira, R.Raz,

  45. ``A Time Lower Bound for Satisfiability'',
    D. van Melkebeek, R.Raz,

  46. ``Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size'',

  47. ``Deterministic Polynomial Identity Testing in Non Commutative Models'',
    R.Raz, A.Shpilka,

  48. ``On the power of Quantum Proofs'',
    R.Raz, A.Shpilka,

  49. ``ProMate: A Structure Based Prediction Program to Identify the Location of Protein Protein Binding Sites'',
    H.Neuvirth, R.Raz, G.Schreiber,

  50. ``Quantum Computation''
    (lecture notes series from IAS summer school on Complexity Theory),

  51. ``Circuit Complexity and Communication Complexity''
    (lecture notes series from IAS summer school on Complexity Theory),

  52. ``Approximating CVP to Within Almost-Polynomial Factors is NP-Hard'',
    I.Dinur, G.Kindler, R.Raz, S.Safra,

  53. ``Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles'',
    J.Buresh-Oppenheim, P.Beame, T.Pitassi, R.Raz, A.Sabharwal,

  54. ``P ≠ NP, Propositional Proof Complexity, and Resolution Lower Bounds for the Weak Pigeonhole Principle'',

  55. ``On the Complexity of Matrix Product'',

  56. ``Resolution Lower Bounds for the Weak Pigeonhole Principle'',

  57. ``Regular Resolution Lower Bounds for the Weak Pigeonhole Principle'',
    T.Pitassi, R.Raz,

  58. ``Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates'',
    R.Raz, A.Shpilka,

  59. ``An Explicit Lower Bound of 5n - o(n) for Boolean Circuits'',
    K.Iwama, O.Lachish, H.Morizumi, R.Raz,

  60. ``Distance Labeling in Graphs'',
    C.Gavoille, D.Peleg, S.Perennes, R.Raz,

  61. ``On the Distribution of the Number of Roots of Polynomials and Explicit Weak Designs'',
    T.Hartman, R.Raz,

  62. ``Higher Lower Bounds for Monotone Size'',
    D.Harnik, R.Raz,

  63. ``VC-Dimension of Sets of Permutations'',

  64. ``The BNS-Chung Criterion for Multi-Party Communication Complexity'',

  65. ``Error Reduction for Extractors'',
    R.Raz, O.Reingold, S.Vadhan,

  66. ``Extracting all the Randomness and Reducing the Error in Trevisan's Extractors'',
    R.Raz, O.Reingold, S.Vadhan,

  67. ``PCP Characterization of NP: Towards a Polynomially Small Error Probability'',
    I.Dinur, E.Fischer, G.Kindler, R.Raz, S.Safra,

  68. ``On Recycling the Randomness of the States in Bounded Space Computation'',
    R.Raz, O.Reingold,

  69. ``Exponential Separation of Quantum and Classical Communication Complexity'',

  70. ``Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs'',
    Y.Rabinovich, R.Raz,

  71. ``Arthur-Merlin Games in Boolean Decision Trees'',
    R.Raz, G.Tardos, O.Verbitsky, N.Vereshchagin,

  72. ``On Interpolation and Automatization for Frege Systems'',
    M.L.Bonet, T.Pitassi, R.Raz,

  73. ``Separation of the Monotone NC Hierarchy'',
    R.Raz, P.McKenzie,

  74. ``A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP'',
    R.Raz, S.Safra,

  75. ``Direct Product Results and the GCD Problem, in Old and New Communication Models'',
    I.Parnafes, R.Raz, A.Wigderson,

  76. ``A Parallel Repetition Theorem'',

  77. ``Lower Bounds for Cutting Planes Proofs with Small Coefficients'',
    M.Bonet, T.Pitassi, R.Raz,

  78. ``Fourier Analysis for Probabilistic Communication Complexity'',

  79. ``A Direct Product Theorem'',
    R.Impagliazzo, R.Raz, A.Wigderson,

  80. ``On the 'Log-Rank' Conjecture in Communication Complexity'',
    R.Raz, B.Spieker,

  81. ``On proving Super-Logarithmic Depth Lower Bounds via the Direct sum in Communication Complexity'',
    M.Karchmer, R.Raz, A.Wigderson,

  82. ``Monotone Circuits for Matching Require Linear Depth'',
    R.Raz, A.Wigderson,

  83. ``Probabilistic Communication Complexity of Boolean Relations'',
    R.Raz, A.Wigderson,