Ran Raz: Publications:
Probabilistically Checkable Proofs

1. ``How to Delegate Computations: The Power of No-Signaling Proofs'' ,
   Y.Kalai, R.Raz, R.Rothblum
   
   • Proceeding of STOC, 2014
   
   
2. ``Delegation for Bounded Space'' ,
   Y.Kalai, R.Raz, R.Rothblum
   
   • Proceeding of the 45th STOC, 2013
   
   
3. ``Competing Provers Protocols for Circuit Evaluation'' ,
   G.Kol, R.Raz,
   
   • Proceeding of ITCS, 2013
   • Theory Of Computing (to appear)
   
   
4. ``Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner'' ,
   M.Dinitz, G.Kortsarz, R.Raz,
   
   • Proceeding of the 39th ICALP, 2012
   
   
5. ``A Strong Parallel Repetition Theorem for Projection Games on Expanders'' ,
   R.Raz, R.Rosen,
   
   • Proceeding of Computational Complexity, 2012
   
   
6. ``Bounds on Locally Testable Codes with Unique Tests'' ,
   G.Kol, R.Raz,
   
   • Proceeding of ITCS, 2012
   
   
7. ``Parallel Repetition of Two Prover Games'' (a short survey) ,
   R.Raz,
   
   • Proceeding of Computational Complexity, 2010
   
   
8. ``Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size'',
   D.Moshkovitz, R.Raz,
   
   • Journal of Computational Complexity 19(3): 367-422 (2010)
   
   
9. ``Bounds on 2-Query Locally Testable Codes with Affine Tests'' ,
   G.Kol, R.Raz,
   
   • Manuscript 2009
   
   
10. ``Strong Parallel Repetition Theorem for Free Projection Games'',
    B.Barak, A.Rao, R.Raz, R.Rosen, R.Shaltiel,
    
    • Proceeding of RANDOM, 2009
    
    
11. ``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)
    
    
12. ``A Counterexample to Strong Parallel Repetition'',
    R.Raz,
    
    • Proceeding of the 49th FOCS, 2008
    • SIAM Journal of Computing 40(3): 771-777 (2011)
    
    
13. ``Interactive PCP'',
    Y.Kalai, R.Raz,
    
    • Proceeding of the 35th ICALP, 2008, pp. 536-547
    
    
14. ``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
    
    
15. ``Quantum Information and the PCP Theorem'',
    R.Raz,
    
    • Proceeding of the 46th FOCS, 2005, pp. 459-468
    • Algorithmica 55(3) (2009)
    
    
16. ``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
    
    
17. ``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)
    
    
18. ``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
    
    
19. ``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
    
    
20. ``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