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 >>>

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 >>>

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 >>>

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 >>>