Ran Raz: Publications
-
``Exponential Separation of Information and Communication''
,
A.Ganor, G.Kol, R.Raz
-
``Two Sides of the Coin Problem''
,
G.Cohen, A.Ganor, R.Raz
-
Proceeding of RANDOM, 2014
-
``Space Pseudorandom Generators by Communication Complexity Lower Bounds''
,
A.Ganor, R.Raz
-
Proceeding of RANDOM, 2014
-
``How to Delegate Computations: The Power of No-Signaling Proofs''
,
Y.Kalai, R.Raz, R.Rothblum
-
``Improved Average-Case Lower Bounds for DeMorgan Formula Size''
,
I.Komargodski, R.Raz, A.Tal
-
``Efficient Multiparty Protocols via Log-Depth Threshold Formulae'',
G.Cohen, I.Damgard, Y.Ishai, J.Kolker, P.B.Miltersen, R.Raz, R.Rothblum,
-
Proceeding of CRYPTO, 2013
-
``Delegation for Bounded Space''
,
Y.Kalai, R.Raz, R.Rothblum
-
Proceeding of the 45th STOC, 2013
-
``Interactive Channel Capacity''
,
G.Kol, R.Raz,
-
Proceeding of the 45th STOC, 2013
-
``Average-Case Lower Bounds for Formula Size''
,
I.Komargodski, 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)
-
``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
-
``Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification''
,
G.Cohen, R.Raz, G.Segev,
-
Proceeding of Computational Complexity, 2012
-
SIAM Journal of Computing 43(2): 450-476 (2014)
-
``A Strong Parallel Repetition Theorem for Projection Games on
Expanders''
,
R.Raz, R.Rosen,
-
Proceeding of Computational Complexity, 2012
-
``Bounds on Locally Testable Codes
with Unique Tests''
,
G.Kol, R.Raz,
-
``Memory Delegation'',
K.M.Chung, Y.Kalai, F.H.Liu, R.Raz,
-
Proceeding of CRYPTO, 2011
-
``The Surprise Examination Paradox and the Second Incompleteness Theorem''
,
S.Kritchman, R.Raz,
-
Notices of the American Mathematical Society 57(11) (2010)
-
``Pseudorandom Generators for Regular Branching Programs''
,
M.Braverman, A.Rao, R.Raz, A.Yehudayoff,
-
Proceeding of the 51st FOCS, 2010
-
SIAM Journal of Computing 43(3): 973-986 (2014)
-
``Tensor-Rank and Lower Bounds for Arithmetic
Formulas''
,
R.Raz,
-
Proceeding of the 42nd STOC, 2010
-
Journal of the Association for Computing Machinery
60(6) (2013)
-
``Parallel Repetition of Two Prover Games'' (a short survey)
,
R.Raz,
-
Proceeding of Computational Complexity, 2010
-
``Sub-Constant Error Probabilistically Checkable Proof of
Almost-Linear Size'',
D.Moshkovitz, R.Raz,
-
Journal of Computational Complexity 19(3): 367-422 (2010)
-
``Bounds on 2-Query Locally Testable Codes
with Affine Tests''
,
G.Kol, R.Raz,
-
``Strong Parallel Repetition Theorem for Free
Projection Games'',
B.Barak, A.Rao, R.Raz, R.Rosen, R.Shaltiel,
-
Proceeding of RANDOM, 2009
-
``Probabilistically Checkable Arguments'',
Y.Kalai, R.Raz,
-
Proceeding of CRYPTO, 2009
-
``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)
-
``A Counterexample to Strong Parallel Repetition'',
R.Raz,
-
Proceeding of the 49th FOCS, 2008
-
SIAM Journal of Computing 40(3): 771-777 (2011)
-
``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)
-
``Elusive Functions and Lower Bounds for Arithmetic Circuits'',
R.Raz,
-
Proceeding of the 40th STOC, 2008, pp. 711-720
-
Theory Of Computing Vol. 6, article 7 (2010)
-
``Lower Bounds and Separations for Constant Depth Multilinear Circuits
'',
R.Raz, A.Yehudayoff,
-
Proceeding of Computational Complexity, 2008, pp. 128-139
-
Journal of Computational Complexity
18(2): 171-207 (2009)
-
``Interactive PCP'',
Y.Kalai, R.Raz,
-
Proceeding of the 35th ICALP, 2008, pp. 536-547
-
``Analyzing Linear Mergers'',
Z.Dvir, R.Raz,
-
Random Structures and Algorithms 32(3) (2008), pp. 334-345
-
``Resolution over Linear Equations and Multilinear Proofs'',
R.Raz, I.Tzameret,
-
Annals of Pure and Applied Logic 155(3) (2008), pp. 194-224
-
``The Strength of Multilinear Proofs'',
R.Raz, I.Tzameret,
-
Journal of Computational Complexity 17(3) (2008)
-
``Balancing Syntactically Multilinear
Arithmetic Circuits'',
R.Raz, A.Yehudayoff,
-
Journal of Computational Complexity
17(4):515-535 (2008)
-
``A Lower Bound for the Size of Syntactically Multilinear
Arithmetic Circuits'',
R.Raz, A.Shpilka, A.Yehudayoff,
-
Proceeding of the 48th FOCS, 2007, pp. 438-448
-
SIAM Journal of Computing 38(4) (2008)
-
``Exponential
Separations for One-Way Quantum Communication Complexity, with Applications
to Cryptography'',
D.Gavinsky, J.Kempe, I.Kerenidis, R.Raz, R.de-Wolf,
-
``Succinct Non-Interactive Zero-Knowledge Proofs
with Preprocessing for LOGSNP'',
Y.Kalai, R.Raz,
-
Proceeding of the 47th FOCS, 2006, pp. 355-366
-
``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
-
``Quantum Information and the PCP Theorem'',
R.Raz,
-
Proceeding of the 46th FOCS, 2005, pp. 459-468
-
Algorithmica 55(3) (2009)
-
``Deterministic Extractors for Affine Sources over Large Fields'',
A.Gabizon, R.Raz,
-
Proceeding of the 46th FOCS, 2005, pp. 407-418
-
Combinatorica 28(4) (2008), pp. 415-440
-
``Extractors with Weak Random Seeds'',
R.Raz,
-
Proceeding of the 37th STOC, 2005, pp. 11-20
-
``Separation of Multilinear Circuit and Formula Size'',
R.Raz,
-
Proceeding of the 45th FOCS, 2004, pp. 344-351
(title:
``Multilinear-NC1 ≠ Multilinear-NC2'')
-
Theory Of Computing Vol. 2, article 6 (2006)
-
``Deterministic Extractors for Bit-Fixing Sources by Obtaining an
Independent Seed'',
A.Gabizon, R.Raz, R.Shaltiel,
-
Proceeding of the 45th FOCS, 2004, pp. 394-403
-
SIAM Journal of Computing 36(4) (2006), pp. 1072-1094
-
``Improved Randomness Extraction from Two Independent Sources'',
Y.Dodis, A.Elbaz, R.Oliveira, R.Raz,
-
Proceeding of the 8th RANDOM, 2004, pp. 334-344
-
``A Time Lower Bound for Satisfiability'',
D. van Melkebeek, R.Raz,
-
Proceeding of the 31st ICALP, 2004, pp. 971-982
-
Theoretical Computer Science 348 (2005), pp. 311-320
-
``Multi-Linear Formulas for Permanent and Determinant are
of Super-Polynomial Size'',
R.Raz,
-
Proceeding of the 36th STOC, 2004, pp. 633-641
-
Journal of the Association for Computing Machinery
56(2) (2009)
-
``Deterministic Polynomial Identity Testing in Non Commutative
Models'',
R.Raz, A.Shpilka,
-
Proceeding of Computational Complexity, 2004, pp. 215-222
-
Journal of Computational Complexity 14(1) (2005), pp. 1-19
-
``On the power of Quantum Proofs'',
R.Raz, A.Shpilka,
-
Proceeding of Computational Complexity, 2004, pp. 260-274
-
``ProMate: A Structure Based Prediction Program to Identify the Location
of Protein Protein Binding Sites'',
H.Neuvirth, R.Raz, G.Schreiber,
-
Journal of Molecular Biology 338(1) (2004), pp. 181-199
-
``Quantum Computation''
(lecture notes series from IAS summer school on Complexity Theory),
R.Raz,
-
Computational Complexity Theory, IAS/Park City Mathematical Series,
Volume 10 (2004), pp. 127-155
-
``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
-
``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
-
``Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles'',
J.Buresh-Oppenheim, P.Beame, T.Pitassi, R.Raz, A.Sabharwal,
-
Proceeding of the 43th FOCS, 2002, pp. 583-592
-
SIAM Journal of Computing 34(2) (2004), pp. 261-276
-
``P ≠ NP, Propositional Proof Complexity, and
Resolution Lower Bounds for the Weak Pigeonhole Principle'',
R.Raz,
-
Proceeding of the International Congress of Mathematicians,
ICM 2002, Vol III, pp. 685-693
-
``On the Complexity of Matrix Product'',
R.Raz,
-
Proceeding of the 34th STOC, 2002, pp. 144-151
-
SIAM Journal of Computing 32(5) (2003), pp. 1356-1369
-
``Resolution Lower Bounds for the Weak Pigeonhole Principle'',
R.Raz,
-
Proceeding of the 34th STOC, 2002, pp. 553-562
-
Journal of the Association for Computing Machinery 51(2) (2004)
pp. 115-138
-
``Regular Resolution Lower Bounds for the Weak Pigeonhole Principle'',
T.Pitassi, R.Raz,
-
Proceeding of the 33rd STOC, 2001, pp. 347-355
-
Combinatorica 24(3) (2004), pp. 503-524
-
``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
-
``An Explicit Lower Bound of 5n - o(n) for Boolean Circuits'',
K.Iwama, O.Lachish, H.Morizumi, R.Raz,
-
``Distance Labeling in Graphs'',
C.Gavoille, D.Peleg, S.Perennes, R.Raz,
-
Proceeding of SODA, 2001, pp. 210-219
-
Journal of Algorithms 53(1) (2004), pp. 85-112
-
``On the Distribution of the Number of Roots of Polynomials
and Explicit Weak Designs'',
T.Hartman, R.Raz,
-
Proceeding of the satellite workshops of the 27th ICALP, 2001,
pp. 3-22
(title:
``On the Distribution of the Number of Roots of Polynomials
and Explicit Logspace Extractors'')
-
Random Structures and Algorithms 23(3) (2003), pp. 235-263
-
``Higher Lower Bounds for Monotone Size'',
D.Harnik, R.Raz,
-
Proceeding of the 32nd STOC, 2000, pp. 191-201
-
``VC-Dimension of Sets of Permutations'',
R.Raz,
-
Combinatorica 20(1) (2000), pp. 1-15
-
``The BNS-Chung Criterion for Multi-Party Communication Complexity'',
R.Raz,
-
Journal of Computational Complexity 9(2) (2000), pp. 113-122
-
``Error Reduction for Extractors'',
R.Raz, O.Reingold, S.Vadhan,
-
Proceeding of the 40th FOCS, 1999, pp. 191-201
-
``Extracting all the Randomness and Reducing the Error
in Trevisan's Extractors'',
R.Raz, O.Reingold, S.Vadhan,
-
Proceeding of the 31st STOC, 1999, pp. 149-158
-
Journal of Computer and System Sciences
65(1) (2002), pp. 97-128
-
``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)
-
``On Recycling the Randomness of the
States in Bounded Space Computation'',
R.Raz, O.Reingold,
-
Proceeding of the 31st STOC, 1999, pp. 159-168
-
``Exponential Separation of Quantum and Classical
Communication Complexity'',
R.Raz,
-
Proceeding of the 31st STOC, 1999, pp. 358-367
-
``Lower Bounds on the Distortion of Embedding Finite Metric Spaces
in Graphs'',
Y.Rabinovich, R.Raz,
-
Discrete and Computational Geometry 19 (1998), pp. 79-94
-
``Arthur-Merlin Games in Boolean Decision Trees'',
R.Raz, G.Tardos, O.Verbitsky, N.Vereshchagin,
-
Proceeding of Computational Complexity, 1998, pp. 58-67
-
Journal of Computer and System Sciences
59(2) (1999), pp. 346-372
-
``On Interpolation and Automatization for Frege Systems'',
M.L.Bonet, T.Pitassi, R.Raz,
-
Proceeding of the 38th FOCS, 1997, pp. 254-263
(title: ``No Feasible Interpolation for Frege and TC0-Frege Proofs'')
-
SIAM Journal of Computing 29(6) (2000), pp. 1939-1967
-
``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
-
``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
-
``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
-
``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
-
``Lower Bounds for Cutting Planes Proofs with Small Coefficients'',
M.Bonet, T.Pitassi, R.Raz,
-
Proceeding of the 27th STOC 1995, pp. 575-584
-
Journal of Symbolic Logic 62(3) (1997) pp. 708-728
-
``Fourier Analysis for Probabilistic Communication Complexity'',
R.Raz,
-
Journal of Computational Complexity 5 (1995) pp. 205-221
-
``A Direct Product Theorem'',
R.Impagliazzo, R.Raz, A.Wigderson,
-
Proceeding of Structures in Complexity Theory, 1994, pp. 88-96
-
``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