Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #3 to TR16-187 | 14th December 2016 20:53

#### Almost Cubic Bound for Depth Three Circuits in VP

Revision #3
Authors: morris yau
Accepted on: 14th December 2016 20:53
Keywords:

Abstract:

In "An almost Cubic Lower Bound for Depth Three Arithmetic Circuits", [KST15] present an infinite family of polynomials in VNP, $\{P_n\}_{n \in \mathbb{Z}^+}$ on $n$ variables with degree $n$ such that every $\sum\prod\sum$ circuit computing $P_n$ is of size $\tilde\Omega(n^3)$. A similar result was proven in [BLS16] for polynomials in VP with lower bound $\Omega\big(\frac{n^3}{2^{\sqrt{\log n}}}\big)$.
We present a modified polynomial and perform a tighter analysis to obtain an $\tilde\Omega(n^3)$ lower bound for a family of polynomials in VP effectively bridging the VP and VNP results up to a $polylog(n)$ factor.
More generally, we show that for every $N$ and $D$ satisfying $poly(N) > D > \log^2 N$, there exist
polynomials $P_{N,D}$ on $N$ variable of degree $D$ in VP that can not be computed by circuits of size $\tilde\Omega(N^2D)$.

Changes to previous version:

Formatting

Revision #2 to TR16-187 | 27th November 2016 04:26

#### Almost Cubic Bound for Depth Three Circuits in VP

Revision #2
Authors: morris yau
Accepted on: 27th November 2016 04:26
Keywords:

Abstract:

In "An almost Cubic Lower Bound for Depth Three Arithmetic Circuits", \cite{KST} present an infinite family of polynomials in VNP, $\{P_n\}_{n \in \mathbb{Z}^+}$ on $n$ variables with degree $n$ such that every $\sum\prod\sum$ circuit computing $P_n$ is of size $\tilde\Omega(n^3)$. A similar result was proven in $\cite{BLS}$ for polynomials in VP with lower bound $\Omega\big(\frac{n^3}{2^{\sqrt{\log n}}}\big)$.
We present a modified polynomial and perform a tighter analysis to obtain an $\tilde\Omega(n^3)$ lower bound for a family of polynomials in VP effectively bridging the VP and VNP results up to a $\log^4n$ factor.
More generally, we show that for every $N$ and $D$ satisfying $poly(N) > D > \log^2 N$, there exist
polynomials $P_{N,D}$ on $N$ variable of degree $D$ in VP that can not be computed by circuits of size $\tilde\Omega(N^2D)$.

Changes to previous version:

minor changes to abstract and notation

Revision #1 to TR16-187 | 23rd November 2016 00:11

#### Almost Cubic Bound for Depth Three Circuits in VP

Revision #1
Authors: morris yau
Accepted on: 23rd November 2016 00:11
Keywords:

Abstract:

In "An Almost Cubic Lower Bound for $\sum\prod\sum$ circuits in VP", [BLS16] present an infinite family of polynomials, $\{P_n\}_{n \in \mathbb{Z}^+}$, with $P_n$
on $N = \Theta(n polylog(n))$
variables with degree $N$ being in VP such that every
$\sum\prod\sum$ circuit computing $P_n$ is of size $\Omega\big(\frac{N^3}{2^{\sqrt{\log N}}}\big)$.
We present a modified polynomial and perform a tighter analysis to obtain an $\tilde\Omega(N^3)$ lower bound.
More generally, we show that for every $N$ and $D$ satisfying $poly(N) > D > \log^2 N$, there exist
polynomials $P_{N,D}$ on $N$ variable of degree $D$ in VP that can not be computed by circuits of size $\tilde\Omega(N^2D)$.

Changes to previous version:

### Paper:

TR16-187 | 21st November 2016 16:58

#### Almost Cubic Bound for Depth Three Circuits in VP

TR16-187
Authors: morris yau
Publication: 21st November 2016 17:22
Keywords:

Abstract:

In "An Almost Cubic Lower Bound for $\sum\prod\sum$ circuits in VP", [BLS16] present an infinite family of polynomials, $\{P_n\}_{n \in \mathbb{Z}^+}$, with $P_n$
on $N = \Theta(n polylog(n))$
variables with degree $N$ being in VP such that every
$\sum\prod\sum$ circuit computing $P_n$ is of size $\Omega\big(\frac{N^3}{2^{\sqrt{\log N}}}\big)$.
We present a modified polynomial and perform a tighter analysis to obtain an $\tilde\Omega(N^3)$ lower bound.
More generally, we show that for every $N$ and $D$ satisfying $poly(N) > D > \log^2 N$, there exist
polynomials $P_{N,D}$ on $N$ variable of degree $D$ in VP that can not be computed by circuits of size $\tilde\Omega(N^2D)$.

ISSN 1433-8092 | Imprint