`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

### DBLP: Raz:Ran

### Contributed to:

### 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.
- STOC-1997-RazS
- 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.