Person: Ran Raz

DBLP: Raz:Ran

Contributed to:

2015

2014

2013

2013

2012

2010

2008

2008

2007

2006

2005

2004

2004

2002

2001

2000

1999

1997

1995

1990

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.