All reports by Author Zohar Karnin:

__
TR10-162
| 30th October 2010
__

Zohar Karnin#### Deterministic Construction of a high dimensional $\ell_p$ section in $\ell_1^n$ for any $p<2$

__
TR09-121
| 22nd November 2009
__

Zohar Karnin, Yuval Rabani, Amir Shpilka#### Explicit Dimension Reduction and Its Applications

__
TR09-116
| 15th November 2009
__

Zohar Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich#### Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in

__
TR07-042
| 7th May 2007
__

Zohar Karnin, Amir Shpilka#### Black Box Polynomial Identity Testing of Depth-3 Arithmetic Circuits with Bounded Top Fan-in

Revisions: 2
,
Comments: 1

Zohar Karnin

For any $00$, we give an efficient

deterministic construction of a linear subspace $V \subseteq

\R^n$, of dimension $(1-\epsilon)n$ in which the $\ell_p$ and

$\ell_r$ norms are the same up to a multiplicative factor of

$\poly(\epsilon^{-1})$ (after the correct normalization). As a

corollary we get a deterministic compressed sensing algorithm

more >>>

Zohar Karnin, Yuval Rabani, Amir Shpilka

We construct a small set of explicit linear transformations mapping $R^n$ to $R^{O(\log n)}$, such that the $L_2$ norm of

any vector in $R^n$ is distorted by at most $1\pm o(1)$ in at

least a fraction of $1 - o(1)$ of the transformations in the set.

Albeit the tradeoff between ...
more >>>

Zohar Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich

We give the first sub-exponential time deterministic polynomial

identity testing algorithm for depth-$4$ multilinear circuits with

a small top fan-in. More accurately, our algorithm works for

depth-$4$ circuits with a plus gate at the top (also known as

$\Spsp$ circuits) and has a running time of

$\exp(\poly(\log(n),\log(s),k))$ where $n$ is ...
more >>>

Zohar Karnin, Amir Shpilka

In this paper we consider the problem of determining whether an

unknown arithmetic circuit, for which we have oracle access,

computes the identically zero polynomial. Our focus is on depth-3

circuits with a bounded top fan-in. We obtain the following

results.

1. A quasi-polynomial time deterministic black-box identity testing algorithm ... more >>>