Name
Abstract | ||
|---|---|---|
Tavenas (Proceedings of mathematical foundations of computer science (MFCS), 2013) has recently proved that any \(n^{O(1)}\)-variate and degree n polynomial in \(\mathsf {VP}\) can be computed by a depth-4
\(\Sigma \Pi \Sigma \Pi \)
circuit of size \(2^{O(\sqrt{n}\log n)}\). So, to prove \(\mathsf {VP}\ne \mathsf {VNP}\) it is sufficient to show that an explicit polynomial in \(\mathsf {VNP}\) of degree n requires \(2^{\omega (\sqrt{n}\log n)}\) size depth-4 circuits. Soon after Tavenas’ result, for two different explicit polynomials, depth-4 circuit-size lower bounds of \(2^{\Omega (\sqrt{n}\log n)}\) have been proved (see Kayal et al. in Proceedings of symposium on theory of computing, ACM, 2014b. http://doi.acm.org/10.1145/2591796.2591847; Fournier et al. in Proceedings of symposium on theory of computing, ACM, 2014). In particular, using a combinatorial design Kayal et al. (2014b) construct an explicit polynomial in \(\mathsf {VNP}\) that requires depth-4 circuits of size \(2^{\Omega (\sqrt{n}\log n)}\) and Fournier et al. (Proceedings of symposium on theory of computing, ACM, 2014) show that the iterated matrix multiplication polynomial (which is in \(\mathsf {VP}\)) also requires \(2^{\Omega (\sqrt{n}\log n)}\) size depth-4 circuits. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.4230/LIPIcs.STACS.2014.239 | STACS |
Keywords | Field | DocType |
Lower bounds, Determinantal complexity, Constant depth, Arithmetic circuits, 68Q17 | Binary logarithm,Discrete mathematics,Combinatorics,Polynomial,Upper and lower bounds,Matrix (mathematics),Omega,Combinatorial design,Matrix multiplication,Iterated function,Mathematics | Conference |
Volume | Issue | ISSN |
28 | 4 | 1420-8954 |
Citations | PageRank | References |
4 | 0.46 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Suryajith Chillara | 1 | 14 | 3.68 |
| Partha Mukhopadhyay | 2 | 91 | 12.71 |