Ran Raz: Publications:
Communication Complexity

1. ``Exponential Separation of Information and Communication'' ,
   A.Ganor, G.Kol, R.Raz
   
   • Proceeding of FOCS, 2014
   
   
2. ``Space Pseudorandom Generators by Communication Complexity Lower Bounds'' ,
   A.Ganor, R.Raz
   
   • Proceeding of RANDOM, 2014
   
   
3. ``Interactive Channel Capacity'' ,
   G.Kol, R.Raz,
   
   • Proceeding of the 45th STOC, 2013
   
   
4. ``Arthur-Merlin Streaming Complexity'' ,
   T.Gur, R.Raz,
   
   • Proceeding of ICALP, 2013
   
   
5. ``Competing Provers Protocols for Circuit Evaluation'' ,
   G.Kol, R.Raz,
   
   • Proceeding of ITCS, 2013
   • Theory Of Computing (to appear)
   
   
6. ``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)
   
   
7. ``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
     
   
   
8. ``On the power of Quantum Proofs'',
   R.Raz, A.Shpilka,
   
   • Proceeding of Computational Complexity, 2004, pp. 260-274
   
   
9. ``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
   
   
10. ``The BNS-Chung Criterion for Multi-Party Communication Complexity'',
    R.Raz,
    
    • Journal of Computational Complexity 9(2) (2000), pp. 113-122
    
    
11. ``Exponential Separation of Quantum and Classical Communication Complexity'',
    R.Raz,
    
    • Proceeding of the 31st STOC, 1999, pp. 358-367
    
    
12. ``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
    
    
13. ``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
    
    
14. ``Fourier Analysis for Probabilistic Communication Complexity'',
    R.Raz,
    
    • Journal of Computational Complexity 5 (1995) pp. 205-221
    
    
15. ``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
    
    
16. ``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
    
    
17. ``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
    
    
18. ``Probabilistic Communication Complexity of Boolean Relations'',
    R.Raz, A.Wigderson,
    
    • Proceeding of the 30th FOCS, 1989, pp. 562-567