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)$.

Formatting

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)$.

minor changes to abstract and notation

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)$.

Added Acknowledgement Section

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)$.