Ran Raz: Publications

1. ``Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner'' ,
   M.Dinitz, G.Kortsarz, R.Raz,
   
   • Manuscript 2012
   
   
2. ``Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification'' ,
   G.Cohen, R.Raz, G.Segev,
   
   • Proceeding of Computational Complexity, 2012
   
   
3. ``A Strong Parallel Repetition Theorem for Projection Games on Expanders'' ,
   R.Raz, R.Rosen,
   
   • Proceeding of Computational Complexity, 2012
   
   
4. ``Bounds on Locally Testable Codes with Unique Tests'' ,
   G.Kol, R.Raz,
   
   • Proceeding of ITCS, 2012
   
   
5. ``Competing Provers Protocols for Circuit Evaluation'' ,
   G.Kol, R.Raz,
   
   • Manuscript 2011
   
   
6. ``Memory Delegation'',
   K.M.Chung, Y.Kalai, F.H.Liu, R.Raz,
   
   • Proceeding of CRYPTO, 2011
   
   
7. ``The Surprise Examination Paradox and the Second Incompleteness Theorem'' ,
   S.Kritchman, R.Raz,
   
   • Notices of the American Mathematical Society 57(11) (2010)
   
   
8. ``Pseudorandom Generators for Regular Branching Programs'' ,
   M.Braverman, A.Rao, R.Raz, A.Yehudayoff,
   
   • Proceeding of the 51st FOCS, 2010
   
   
9. ``Tensor-Rank and Lower Bounds for Arithmetic Formulas'' ,
   R.Raz,
   
   • Proceeding of the 42nd STOC, 2010
   
   
10. ``Parallel Repetition of Two Prover Games'' (a short survey) ,
    R.Raz,
    
    • Proceeding of Computational Complexity, 2010
    
    
11. ``Bounds on 2-Query Locally Testable Codes with Affine Tests'' ,
    G.Kol, R.Raz,
    
    • Manuscript 2009
    
    
12. ``Strong Parallel Repetition Theorem for Free Projection Games'',
    B.Barak, A.Rao, R.Raz, R.Rosen, R.Shaltiel,
    
    • Proceeding of RANDOM, 2009
    
    
13. ``Probabilistically Checkable Arguments'',
    Y.Kalai, R.Raz,
    
    • Proceeding of CRYPTO, 2009
    
    
14. ``Two Query PCP with Sub-Constant Error'',
    D.Moshkovitz, R.Raz,
    
    • Proceeding of the 49th FOCS, 2008
    • Journal of the Association for Computing Machinery 57(5) (2010)
    
    
15. ``A Counterexample to Strong Parallel Repetition'',
    R.Raz,
    
    • Proceeding of the 49th FOCS, 2008
    • SIAM Journal of Computing 40(3): 771-777 (2011)
    
    
16. ``Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors'',
    R.Raz, A.Yehudayoff,
    
    • Proceeding of the 49th FOCS, 2008
    • Journal of Computer and System Sciences 77(1): 167-190 (2011)
    
    
17. ``Elusive Functions and Lower Bounds for Arithmetic Circuits'',
    R.Raz,
    
    • Proceeding of the 40th STOC, 2008, pp. 711-720
    • Theory Of Computing Vol. 6, article 7 (2010)
    
    
18. ``Lower Bounds and Separations for Constant Depth Multilinear Circuits '',
    R.Raz, A.Yehudayoff,
    
    • Proceeding of Computational Complexity, 2008, pp. 128-139
    • Journal of Computational Complexity 18(2): 171-207 (2009)
    
    
19. ``Interactive PCP'',
    Y.Kalai, R.Raz,
    
    • Proceeding of the 35th ICALP, 2008, pp. 536-547
    
    
20. ``Analyzing Linear Mergers'',
    Z.Dvir, R.Raz,
    
    • Random Structures and Algorithms 32(3) (2008), pp. 334-345
    
    
21. ``Resolution over Linear Equations and Multilinear Proofs'',
    R.Raz, I.Tzameret,
    
    • Annals of Pure and Applied Logic 155(3) (2008), pp. 194-224
    
    
22. ``The Strength of Multilinear Proofs'',
    R.Raz, I.Tzameret,
    
    • Journal of Computational Complexity 17(3) (2008)
    
    
23. ``A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits'',
    R.Raz, A.Shpilka, A.Yehudayoff,
    
    • Proceeding of the 48th FOCS, 2007, pp. 438-448
    • SIAM Journal of Computing 38(4) (2008)
    
    
24. ``Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size'',
    D.Moshkovitz, R.Raz,
    
    • Journal of Computational Complexity 19(3): 367-422 (2010)
    
    
25. ``Balancing Syntactically Multilinear Arithmetic Circuits'',
    R.Raz, A.Yehudayoff,
    
    • Journal of Computational Complexity 17(4):515-535 (2008)
    
    
26. ``Exponential Separations for One-Way Quantum Communication Complexity, with Applications to Cryptography'',
    D.Gavinsky, J.Kempe, I.Kerenidis, R.Raz, R.de-Wolf,
    
    • Proceeding of the 39th STOC, 2007, pp. 516-525
    • SIAM Journal of Computing 38(5) (2008)
    • Older version: ``The One-Way Communication Complexity of the Boolean Hidden Matching Problem'', authors: I.Kerenidis, R.Raz
      
    
    
27. ``Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP'',
    Y.Kalai, R.Raz,
    
    • Proceeding of the 47th FOCS, 2006, pp. 355-366
    
    
28. ``Sub-Constant Error Low Degree Test of Almost Linear Size'',
    D.Moshkovitz, R.Raz,
    
    • Proceeding of the 38th STOC, 2006, pp. 21-30
    • SIAM Journal of Computing 38(1) (2008), pp. 140-180
    
    
29. ``Quantum Information and the PCP Theorem'',
    R.Raz,
    
    • Proceeding of the 46th FOCS, 2005, pp. 459-468
    • Algorithmica 55(3) (2009)
    
    
30. ``Deterministic Extractors for Affine Sources over Large Fields'',
    A.Gabizon, R.Raz,
    
    • Proceeding of the 46th FOCS, 2005, pp. 407-418
    • Combinatorica 28(4) (2008), pp. 415-440
    
    
31. ``Extractors with Weak Random Seeds'',
    R.Raz,
    
    • Proceeding of the 37th STOC, 2005, pp. 11-20
    
    
32. ``Separation of Multilinear Circuit and Formula Size'',
    R.Raz,
    
    • Proceeding of the 45th FOCS, 2004, pp. 344-351
      (title: ``Multilinear-NC1 ≠ Multilinear-NC2'')
    • Theory Of Computing Vol. 2, article 6 (2006)
    
    
33. ``Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed'',
    A.Gabizon, R.Raz, R.Shaltiel,
    
    • Proceeding of the 45th FOCS, 2004, pp. 394-403
    • SIAM Journal of Computing 36(4) (2006), pp. 1072-1094
    
    
34. ``Improved Randomness Extraction from Two Independent Sources'',
    Y.Dodis, A.Elbaz, R.Oliveira, R.Raz,
    
    • Proceeding of the 8th RANDOM, 2004, pp. 334-344
    
    
35. ``A Time Lower Bound for Satisfiability'',
    D. van Melkebeek, R.Raz,
    
    • Proceeding of the 31st ICALP, 2004, pp. 971-982
    • Theoretical Computer Science 348 (2005), pp. 311-320
    
    
36. ``Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size'',
    R.Raz,
    
    • Proceeding of the 36th STOC, 2004, pp. 633-641
    • Journal of the Association for Computing Machinery 56(2) (2009)
    
    
37. ``Deterministic Polynomial Identity Testing in Non Commutative Models'',
    R.Raz, A.Shpilka,
    
    • Proceeding of Computational Complexity, 2004, pp. 215-222
    • Journal of Computational Complexity 14(1) (2005), pp. 1-19
    
    
38. ``On the power of Quantum Proofs'',
    R.Raz, A.Shpilka,
    
    • Proceeding of Computational Complexity, 2004, pp. 260-274
    
    
39. ``ProMate: A Structure Based Prediction Program to Identify the Location of Protein Protein Binding Sites'',
    H.Neuvirth, R.Raz, G.Schreiber,
    
    • Journal of Molecular Biology 338(1) (2004), pp. 181-199
    
    
40. ``Quantum Computation''
    (lecture notes series from IAS summer school on Complexity Theory),
    R.Raz,
    
    • Computational Complexity Theory, IAS/Park City Mathematical Series, Volume 10 (2004), pp. 127-155
    
    
41. ``Circuit Complexity and Communication Complexity''
    (lecture notes series from IAS summer school on Complexity Theory),
    R.Raz,
    
    • Computational Complexity Theory, IAS/Park City Mathematical Series, Volume 10 (2004), pp. 159-197
    
    
42. ``Approximating CVP to Within Almost-Polynomial Factors is NP-Hard'',
    I.Dinur, G.Kindler, R.Raz, S.Safra,
    
    • Combinatorica 23(2) (2003), pp. 205-243
    
    
43. ``Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles'',
    J.Buresh-Oppenheim, P.Beame, T.Pitassi, R.Raz, A.Sabharwal,
    
    • Proceeding of the 43th FOCS, 2002, pp. 583-592
    • SIAM Journal of Computing 34(2) (2004), pp. 261-276
    
    
44. ``P ≠ NP, Propositional Proof Complexity, and Resolution Lower Bounds for the Weak Pigeonhole Principle'',
    R.Raz,
    
    • Proceeding of the International Congress of Mathematicians, ICM 2002, Vol III, pp. 685-693
    
    
45. ``On the Complexity of Matrix Product'',
    R.Raz,
    
    • Proceeding of the 34th STOC, 2002, pp. 144-151
      
    • SIAM Journal of Computing 32(5) (2003), pp. 1356-1369
    
    
46. ``Resolution Lower Bounds for the Weak Pigeonhole Principle'',
    R.Raz,
    
    • Proceeding of the 34th STOC, 2002, pp. 553-562
    • Journal of the Association for Computing Machinery 51(2) (2004) pp. 115-138
    
    
47. ``Regular Resolution Lower Bounds for the Weak Pigeonhole Principle'',
    T.Pitassi, R.Raz,
    
    • Proceeding of the 33rd STOC, 2001, pp. 347-355
      
    • Combinatorica 24(3) (2004), pp. 503-524
    
    
48. ``Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates'',
    R.Raz, A.Shpilka,
    
    • Proceeding of the 33rd STOC, 2001, pp. 409-418
      
    • SIAM Journal of Computing 32(2) (2003), pp. 488-513
    
    
49. ``An Explicit Lower Bound of 5n - o(n) for Boolean Circuits'',
    K.Iwama, O.Lachish, H.Morizumi, R.Raz,
    
    • Proceeding of the 33rd STOC, 2001, pp. 399-408
      (title: ``Explicit Lower Bound of 4.5n - o(n) for Boolean Circuits'', authors: O.Lachish, R.Raz)
    • Manuscript, 2005
    
    
50. ``Distance Labeling in Graphs'',
    C.Gavoille, D.Peleg, S.Perennes, R.Raz,
    
    • Proceeding of SODA, 2001, pp. 210-219
    • Journal of Algorithms 53(1) (2004), pp. 85-112
    
    
51. ``On the Distribution of the Number of Roots of Polynomials and Explicit Weak Designs'',
    T.Hartman, R.Raz,
    
    • Proceeding of the satellite workshops of the 27th ICALP, 2001, pp. 3-22
      (title: ``On the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors'')
    • Random Structures and Algorithms 23(3) (2003), pp. 235-263
    
    
52. ``Higher Lower Bounds for Monotone Size'',
    D.Harnik, R.Raz,
    
    • Proceeding of the 32nd STOC, 2000, pp. 191-201
    
    
53. ``VC-Dimension of Sets of Permutations'',
    R.Raz,
    
    • Combinatorica 20(1) (2000), pp. 1-15
    
    
54. ``The BNS-Chung Criterion for Multi-Party Communication Complexity'',
    R.Raz,
    
    • Journal of Computational Complexity 9(2) (2000), pp. 113-122
    
    
55. ``Error Reduction for Extractors'',
    R.Raz, O.Reingold, S.Vadhan,
    
    • Proceeding of the 40th FOCS, 1999, pp. 191-201
    
    
56. ``Extracting all the Randomness and Reducing the Error in Trevisan's Extractors'',
    R.Raz, O.Reingold, S.Vadhan,
    
    • Proceeding of the 31st STOC, 1999, pp. 149-158
      
    • Journal of Computer and System Sciences 65(1) (2002), pp. 97-128
    
    
57. ``PCP Characterization of NP: Towards a Polynomially Small Error Probability'',
    I.Dinur, E.Fischer, G.Kindler, R.Raz, S.Safra,
    
    • Proceeding of the 31st STOC, 1999, pp. 29-40
    • Journal of Computational Complexity 20(3): 413-504 (2011)
    
    
58. ``On Recycling the Randomness of the States in Bounded Space Computation'',
    R.Raz, O.Reingold,
    
    • Proceeding of the 31st STOC, 1999, pp. 159-168
    
    
59. ``Exponential Separation of Quantum and Classical Communication Complexity'',
    R.Raz,
    
    • Proceeding of the 31st STOC, 1999, pp. 358-367
    
    
60. ``Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs'',
    Y.Rabinovich, R.Raz,
    
    • Discrete and Computational Geometry 19 (1998), pp. 79-94
    
    
61. ``Arthur-Merlin Games in Boolean Decision Trees'',
    R.Raz, G.Tardos, O.Verbitsky, N.Vereshchagin,
    
    • Proceeding of Computational Complexity, 1998, pp. 58-67
    • Journal of Computer and System Sciences 59(2) (1999), pp. 346-372
    
    
62. ``On Interpolation and Automatization for Frege Systems'',
    M.L.Bonet, T.Pitassi, R.Raz,
    
    • Proceeding of the 38th FOCS, 1997, pp. 254-263
      (title: ``No Feasible Interpolation for Frege and TC0-Frege Proofs'')
    • SIAM Journal of Computing 29(6) (2000), pp. 1939-1967
    
    
63. ``Separation of the Monotone NC Hierarchy'',
    R.Raz, P.McKenzie,
    
    • Proceeding of the 38th FOCS, 1997, pp. 234-243
      
    • Combinatorica 19(3) (1999), pp. 403-435
    
    
64. ``A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP'',
    R.Raz, S.Safra,
    
    • Proceeding of the 29th STOC, 1997, pp. 475-484
    
    
65. ``Direct Product Results and the GCD Problem, in Old and New Communication Models'',
    I.Parnafes, R.Raz, A.Wigderson,
    
    • Proceeding of the 29th STOC, 1997, pp. 363-372
    
    
66. ``A Parallel Repetition Theorem'',
    R.Raz,
    
    • Proceeding of the 27th STOC, 1995, pp. 447-456
      
    • SIAM Journal of Computing 27(3) (1998) pp. 763-803
    
    
67. ``Lower Bounds for Cutting Planes Proofs with Small Coefficients'',
    M.Bonet, T.Pitassi, R.Raz,
    
    • Proceeding of the 27th STOC 1995, pp. 575-584
      
    • Journal of Symbolic Logic 62(3) (1997) pp. 708-728
    
    
68. ``Fourier Analysis for Probabilistic Communication Complexity'',
    R.Raz,
    
    • Journal of Computational Complexity 5 (1995) pp. 205-221
    
    
69. ``A Direct Product Theorem'',
    R.Impagliazzo, R.Raz, A.Wigderson,
    
    • Proceeding of Structures in Complexity Theory, 1994, pp. 88-96
    
    
70. ``On the 'Log-Rank' Conjecture in Communication Complexity'',
    R.Raz, B.Spieker,
    
    • Proceeding of the 34th FOCS, 1993, pp. 168-177
      
    • Combinatorica 15(4) (1995) pp. 567-588
    
    
71. ``On proving Super-Logarithmic Depth Lower Bounds via the Direct sum in Communication Complexity'',
    M.Karchmer, R.Raz, A.Wigderson,
    
    • Proceeding of Structures in Complexity Theory, 1991, pp. 299-304
      
    • Journal of Computational Complexity 5 (1995), pp. 191-204
    
    
72. ``Monotone Circuits for Matching Require Linear Depth'',
    R.Raz, A.Wigderson,
    
    • Proceeding of the 22th STOC, 1990, pp. 287-292
      
    • Journal of the Association for Computing Machinery 39 (1992) pp. 736-744
    
    
73. ``Probabilistic Communication Complexity of Boolean Relations'',
    R.Raz, A.Wigderson,
    
    • Proceeding of the 30th FOCS, 1989, pp. 562-567