Ran Raz: Publications:
Communication Complexity
-
``Exponential Separation of Information and Communication''
,
A.Ganor, G.Kol, R.Raz
-
``Space Pseudorandom Generators by Communication Complexity Lower Bounds''
,
A.Ganor, R.Raz
-
Proceeding of RANDOM, 2014
-
``Interactive Channel Capacity''
,
G.Kol, R.Raz,
-
Proceeding of the 45th STOC, 2013
-
``Arthur-Merlin Streaming Complexity''
,
T.Gur, R.Raz,
-
Proceeding of ICALP, 2013
-
``Competing Provers Protocols for Circuit Evaluation''
,
G.Kol, R.Raz,
-
Proceeding of ITCS, 2013
-
Theory Of Computing (to appear)
-
``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)
-
``Exponential
Separations for One-Way Quantum Communication Complexity, with Applications
to Cryptography'',
D.Gavinsky, J.Kempe, I.Kerenidis, R.Raz, R.de-Wolf,
-
``On the power of Quantum Proofs'',
R.Raz, A.Shpilka,
-
Proceeding of Computational Complexity, 2004, pp. 260-274
-
``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
-
``The BNS-Chung Criterion for Multi-Party Communication Complexity'',
R.Raz,
-
Journal of Computational Complexity 9(2) (2000), pp. 113-122
-
``Exponential Separation of Quantum and Classical
Communication Complexity'',
R.Raz,
-
Proceeding of the 31st STOC, 1999, pp. 358-367
-
``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
-
``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
-
``Fourier Analysis for Probabilistic Communication Complexity'',
R.Raz,
-
Journal of Computational Complexity 5 (1995) pp. 205-221
-
``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
-
``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
-
``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
-
``Probabilistic Communication Complexity of Boolean Relations'',
R.Raz, A.Wigderson,
-
Proceeding of the 30th FOCS, 1989, pp. 562-567