Ran Raz: Publications:
Probabilistically Checkable Proofs

1. ``A Strong Parallel Repetition Theorem for Projection Games on Expanders'' ,
   R.Raz, R.Rosen,
   
   • Manuscript 2010
   
   
2. ``Parallel Repetition of Two Prover Games'' (a short survey) ,
   R.Raz,
   
   • Proceeding of Computational Complexity, 2010
   
   
3. ``Bounds on Locally Testable Codes with Unique Tests'' ,
   G.Kol, R.Raz,
   
   • Manuscript 2009
   
   
4. ``Bounds on 2-Query Locally Testable Codes with Affine Tests'' ,
   G.Kol, R.Raz,
   
   • Manuscript 2009
   
   
5. ``Strong Parallel Repetition Theorem for Free Projection Games'',
   B.Barak, A.Rao, R.Raz, R.Rosen, R.Shaltiel,
   
   • Proceeding of RANDOM, 2009
   
   
6. ``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)
   
   
7. ``A Counterexample to Strong Parallel Repetition'',
   R.Raz,
   
   • Proceeding of the 49th FOCS, 2008
   • SIAM Journal of Computing 40(3): 771-777 (2011)
   
   
8. ``Interactive PCP'',
   Y.Kalai, R.Raz,
   
   • Proceeding of the 35th ICALP, 2008, pp. 536-547
   
   
9. ``Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size'',
   D.Moshkovitz, R.Raz,
   
   • Journal of Computational Complexity 19(3): 367-422 (2010)
   
   
10. ``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
    
    
11. ``Quantum Information and the PCP Theorem'',
    R.Raz,
    
    • Proceeding of the 46th FOCS, 2005, pp. 459-468
    • Algorithmica 55(3) (2009)
    
    
12. ``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
    
    
13. ``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 (to appear)
    
    
14. ``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
    
    
15. ``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
    
    
16. ``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