P. Harsha

activity

20092026

most citedComplexity of Inference in Graphical Models

85 citations · 294 across the 35 of their papers we have counts for

collaborators

Showing 2015Show all

3 papers · 1 filter

cs.DS2015

Embedding approximately low-dimensional $ℓ_{2}^{2}$ metrics into $ℓ_{1}$

Amit Deshpande, Prahladh Harsha, Rakesh Venkat

Goemans showed that any $n$ points $x_{1}, \dots x_{n}$ in $d$ -dimensions satisfying $ℓ_{2}^{2}$ triangle inequalities can be embedded into $ℓ_{1}$ , with worst-case distortion at mo…

cs.CC2015

Partition bound is quadratically tight for product distributions

Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan

Let $f : {0, 1}^{n} \times {0, 1}^{n} \to {0, 1}$ be a 2-party function. For every product distribution $μ$ on ${0, 1}^{n} \times {0, 1}^{n}$ , we show that $$\mathsf{CC}^μ_{0.…

cs.CC2015★ 7 cited

Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition

Irit Dinur, Prahladh Harsha, Guy Kindler

We show that every language in NP has a PCP verifier that tosses $O (lo g n)$ random coins, has perfect completeness, and a soundness error of at most $1/ poly (n)$ , while maki…

Embedding approximately low-dimensional ℓ22​ metrics into ℓ1​

Partition bound is quadratically tight for product distributions

Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition

Embedding approximately low-dimensional $ℓ_{2}^{2}$ metrics into $ℓ_{1}$