Amir Shpilka

In this paper we introduce a new model for computing=20

polynomials - a depth 2 circuit with a symmetric gate at the top=20

and plus gates at the bottom, i.e the circuit computes a=20

symmetric function in linear functions -

$S_{m}^{d}(\ell_1,\ell_2,...,\ell_m)$ ($S_{m}^{d}$ is the $d$'th=20

elementary symmetric polynomial in $m$ ...
more >>>

Zeev Dvir, Amir Shpilka

In this work we study two seemingly unrelated notions. Locally Decodable Codes(LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial Identity Testing (PIT) is one of the fundamental problems of algebraic complexity: we are given a circuit computing ... more >>>

Neeraj Kayal, Nitin Saxena

We study the identity testing problem for depth $3$ arithmetic circuits ($\Sigma\Pi\Sigma$ circuits). We give the first deterministic polynomial time identity test for $\Sigma\Pi\Sigma$ circuits with bounded top fanin. We also show that the {\em rank} of a minimal and simple $\Sigma\Pi\Sigma$ circuit with bounded top fanin, computing zero, can ... more >>>

Amir Shpilka, Ilya Volkovich

An \emph{arithmetic read-once formula} (ROF for short) is a

formula (a circuit whose underlying graph is a tree) in which the

operations are $\{+,\times\}$ and such that every input variable

labels at most one leaf. A \emph{preprocessed ROF} (PROF for

short) is a ROF in which we are allowed to ...
more >>>

Gaurav Sinha

Reconstruction of arithmertic circuits has been heavily studied in the past few years and has connections to proving lower bounds and deterministic identity testing. In this paper we present a polynomial time randomized algorithm for reconstructing $\Sigma\Pi\Sigma(2)$ circuits over $\R$, i.e. depth$-3$ circuits with fan-in $2$ at the top addition ... more >>>

Joshua Cook

We give two results on the size of AC0 circuits computing promise majority. $\epsilon$-promise majority is majority promised that either at most an $\epsilon$ fraction of the input bits are 1, or at most $\epsilon$ are 0.

First, we show super quadratic lower bounds on both monotone and general depth ... more >>>