Ran Raz: Publications:
Boolean Circuit Complexity

1. ``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
   
   
2. ``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
   
   
3. ``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
   
   
4. ``Higher Lower Bounds for Monotone Size'',
   D.Harnik, R.Raz,
   
   • Proceeding of the 32nd STOC, 2000, pp. 191-201
   
   
5. ``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
   
   
6. ``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
   
   
7. ``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
   
   
8. ``Probabilistic Communication Complexity of Boolean Relations'',
   R.Raz, A.Wigderson,
   
   • Proceeding of the 30th FOCS, 1989, pp. 562-567