Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On the Limits of Depth Reduction at Depth 3 Over Small Finite Fields   Recently, Gupta et.al. [GKKS2013] proved that over Q any $n^{O(1)}$-variate
and $n$-degree polynomial in VP can also be computed by a depth three
$\Sigma\Pi\Sigma$ circuit of size $2^{O(\sqrt{n}\log^{3/2}n)}$. Over fixed-size
finite fields, Grigoriev and Karpinski proved that any $\Sigma\Pi\Sigma$
circuit that computes $Det_n$ (or $Perm_n$) must be of size $2^{\Omega(n)}$
[GK1998]. In this paper, we prove that over fixed-size finite fields, any
$\Sigma\Pi\Sigma$ circuit for computing the iterated matrix multiplication
polynomial of $n$ generic matrices of size $n\times n$, must be of size
$2^{\Omega(n\log n)}$. The importance of this result is that over fixed-size
fields there is no depth reduction technique that can be used to compute all
the $n^{O(1)}$-variate and $n$-degree polynomials in VP by depth 3 circuits of
size $2^{o(n\log n)}$. The result [GK1998] can only rule out such a possibility
for depth 3 circuits of size $2^{o(n)}$.
  We also give an example of an explicit polynomial ($NW_{n,\epsilon}(X)$) in
VNP (not known to be in VP), for which any $\Sigma\Pi\Sigma$ circuit computing
it (over fixed-size fields) must be of size $2^{\Omega(n\log n)}$. The
polynomial we consider is constructed from the combinatorial design. An
interesting feature of this result is that we get the first examples of two
polynomials (one in VP and one in VNP) such that they have provably stronger
circuit size lower bounds than Permanent in a reasonably strong model of
computation.
  Next, we prove that any depth 4
$\Sigma\Pi^{[O(\sqrt{n})]}\Sigma\Pi^{[\sqrt{n}]}$ circuit computing
$NW_{n,\epsilon}(X)$ (over any field) must be of size $2^{\Omega(\sqrt{n}\log
n)}$. To the best of our knowledge, the polynomial $NW_{n,\epsilon}(X)$ is the
first example of an explicit polynomial in VNP such that it requires
$2^{\Omega(\sqrt{n}\log n)}$ size depth four circuits, but no known matching
upper bound.

19
The categories of this paper are: eess
36
The categories of this paper are: cmp-lg
16
The categories of this paper are: stat
28
The categories of this paper are: alg-geom
7
The categories of this paper are: hep-th
37
The categories of this paper are: supr-con
13
The categories of this paper are: quant-ph
32
The categories of this paper are: atom-ph
33
The categories of this paper are: plasm-ph
22
The categories of this paper are: chao-dyn
29
The categories of this paper are: funct-an
3
The categories of this paper are: physics
34
The categories of this paper are: chem-ph
0
The categories of this paper are: hep-ph
8
The categories of this paper are: hep-ex
6
The categories of this paper are: astro-ph