Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Almost Cubic Bound for Depth Three Circuits in VP

RSS-Feed




Revision #3
Authors: morris yau
Accepted on: 14th December 2016 20:53
Downloads: 872
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
Downloads: 812
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
Downloads: 831
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:

Added Acknowledgement Section


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
Downloads: 1105
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