ECCC-Report TR16-187https://eccc.weizmann.ac.il/report/2016/187Comments and Revisions published for TR16-187en-usWed, 14 Dec 2016 20:53:19 +0200
Revision 3
| Almost Cubic Bound for Depth Three Circuits in VP |
morris yau
https://eccc.weizmann.ac.il/report/2016/187#revision3In "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)$.Wed, 14 Dec 2016 20:53:19 +0200https://eccc.weizmann.ac.il/report/2016/187#revision3
Revision 2
| Almost Cubic Bound for Depth Three Circuits in VP |
morris yau
https://eccc.weizmann.ac.il/report/2016/187#revision2In "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)$. Sun, 27 Nov 2016 04:26:17 +0200https://eccc.weizmann.ac.il/report/2016/187#revision2
Revision 1
| Almost Cubic Bound for Depth Three Circuits in VP |
morris yau
https://eccc.weizmann.ac.il/report/2016/187#revision1In "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)$.Wed, 23 Nov 2016 00:11:35 +0200https://eccc.weizmann.ac.il/report/2016/187#revision1
Paper TR16-187
| Almost Cubic Bound for Depth Three Circuits in VP |
morris yau
https://eccc.weizmann.ac.il/report/2016/187In "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)$.Mon, 21 Nov 2016 17:22:33 +0200https://eccc.weizmann.ac.il/report/2016/187