BibSLEIGH corpus
BibSLEIGH tags
BibSLEIGH bundles
BibSLEIGH people
Open Knowledge
XHTML 1.0 W3C Rec
CSS 2.1 W3C CanRec
email twitter
Travelled to:
1 × Finland
1 × Greece
1 × Iceland
1 × Latvia
1 × United Kingdom
13 × USA
2 × Canada
Collaborated with:
Y.T.Kalai G.Kol T.Pitassi O.Reingold A.Wigderson S.Safra R.D.Rothblum T.Gur I.Komargodski D.Moshkovitz D.v.Melkebeek O.Lachish A.Shpilka D.Harnik A.Ganor M.Dinitz G.Kortsarz S.P.Vadhan I.Parnafes M.L.Bonet D.Gavinsky J.Kempe I.Kerenidis R.d.Wolf I.Dinur E.Fischer G.Kindler
Talks about:
bound (13) lower (10) error (5) communic (4) complex (4) circuit (4) size (4) exponenti (3) constant (3) product (3)

Person: Ran Raz


Contributed to:

STOC 20152015
STOC 20142014
ICALP (1) 20132013
STOC 20132013
ICALP (1) 20122012
STOC 20102010
ICALP (2) 20082008
STOC 20082008
STOC 20072007
STOC 20062006
STOC 20052005
ICALP 20042004
STOC 20042004
STOC 20022002
STOC 20012001
STOC 20002000
STOC 19991999
STOC 19971997
STOC 19951995
STOC 19901990

Wrote 30 papers:

STOC-2015-GanorKR #communication #exponential
Exponential Separation of Information and Communication for Boolean Functions (AG, GK, RR), pp. 557–566.
STOC-2014-KalaiRR #how #power of #proving
How to delegate computations: the power of no-signaling proofs (YTK, RR, RDR), pp. 485–494.
ICALP-v1-2013-GurR #complexity #streaming
Arthur-Merlin Streaming Complexity (TG, RR), pp. 528–539.
STOC-2013-KalaiRR #bound
Delegation for bounded space (YTK, RR, RDR), pp. 565–574.
STOC-2013-KolR #capacity #interactive
Interactive channel capacity (GK, RR), pp. 715–724.
STOC-2013-KomargodskiR #bound
Average-case lower bounds for formula size (IK, RR), pp. 171–180.
ICALP-v1-2012-DinitzKR #approximate #scalability
Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner (MD, GK, RR), pp. 290–301.
STOC-2010-Raz #bound
Tensor-rank and lower bounds for arithmetic formulas (RR), pp. 659–666.
ICALP-C-2008-KalaiR #interactive
Interactive PCP (YTK, RR), pp. 536–547.
STOC-2008-Raz #bound
Elusive functions and lower bounds for arithmetic circuits (RR), pp. 711–720.
STOC-2007-GavinskyKKRW #communication #complexity #encryption #exponential #quantum
Exponential separations for one-way quantum communication complexity, with applications to cryptography (DG, JK, IK, RR, RdW), pp. 516–525.
STOC-2006-MoshkovitzR #fault
Sub-constant error low degree test of almost-linear size (DM, RR), pp. 21–30.
STOC-2005-Raz #random
Extractors with weak random seeds (RR), pp. 11–20.
ICALP-2004-MelkebeekR #bound #satisfiability
A Time Lower Bound for Satisfiability (DvM, RR), pp. 971–982.
STOC-2004-Raz #multi
Multi-linear formulas for permanent and determinant are of super-polynomial size (RR), pp. 633–641.
STOC-2002-Raz #complexity #matrix #on the
On the complexity of matrix product (RR), pp. 144–151.
STOC-2002-Raz02a #bound #principle
Resolution lower bounds for the weak pigeonhole principle (RR), pp. 553–562.
STOC-2001-LachishR #bound
Explicit lower bound of 4.5n — o(n) for boolena circuits (OL, RR), pp. 399–408.
STOC-2001-PitassiR #bound #principle
Regular resolution lower bounds for the weak pigeonhole principle (TP, RR), pp. 347–355.
STOC-2001-RazS #bound #matrix
Lower bounds for matrix product, in bounded depth circuits with arbitrary gates (RR, AS), pp. 409–418.
STOC-2000-HarnikR #bound
Higher lower bounds on monotone size (DH, RR), pp. 378–387.
STOC-1999-DinurFKRS #towards
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability (ID, EF, GK, RR, SS), pp. 29–40.
STOC-1999-Raz #communication #complexity #exponential #quantum
Exponential Separation of Quantum and Classical Communication Complexity (RR), pp. 358–367.
STOC-1999-RazR #bound #on the
On Recycling the Randomness of States in Space Bounded Computation (RR, OR), pp. 159–168.
STOC-1999-RazRV #fault
Extracting all the Randomness and Reducing the Error in Trevisan’s Extractors (RR, OR, SPV), pp. 149–158.
STOC-1997-ParnafesRW #communication #modelling #problem
Direct Product Results and the GCD Problem, in Old and New Communication Models (IP, RR, AW), pp. 363–372.
A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP (RR, SS), pp. 475–484.
STOC-1995-BonetPR #bound #proving
Lower bounds for cutting planes proofs with small coefficients (MLB, TP, RR), pp. 575–584.
STOC-1995-Raz #parallel #theorem
A parallel repetition theorem (RR), pp. 447–456.
STOC-1990-RazW #linear
Monotone Circuits for Matching Require Linear Depth (RR, AW), pp. 287–292.

Bibliography of Software Language Engineering in Generated Hypertext (BibSLEIGH) is created and maintained by Dr. Vadim Zaytsev.
Hosted as a part of SLEBOK on GitHub.