Unexpected power of low-depth arithmetic circuits
Abstract
Complexity theory aims at understanding the "hardness" of certain tasks with respect to the number of "basic operations" required to perform it. In the case of arithmetic circuit complexity, the goal is to understand how hard it is to compute a formal polynomial in terms of the number of additions and multiplications required. Several earlier results have shown that it is possible to rearrange basic computational elements in surprising ways to give more efficient algorithms. The main result of this article is along a similar vein.
We present a simulation of any formal polynomial computed by an arithmetic circuit by a shallow circuit of not-much larger size. Roughly, depth corresponds to the time required in a massively parallel computation. This result shows that efficient computations can be speedup to run in depth three, while requiring surprisingly low size.
In addition to the possible usefulness of the shallow simulations, this theorem has implications in computational complexity lower bounds, since this implies that any small improvement in current lower bound approaches would lead to dramatic advances in lower bounds research.
References
[1]
Agrawal, M., Vinay, V. Arithmetic circuits: A chasm at depth four. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008) (2008), 67--75.
[2]
Arora, S., Barak, B. Computational Complexity: A Modern Approach, 1st edn. Cambridge University Press, New York, NY, USA, 2009.
[3]
Ellison, W. A 'waring's problem' for homogeneous forms. Proc. Cambr. Philos. Soc. 65 (1969), 663--672.
[4]
Fischer, I. Sums of like powers of multivariate linear forms. Math. Mag. 67, 1 (1994), 59--61.
[5]
Fournier, H., Limaye, N., Malod, G., Srinivasan, S. Lower bounds for depth 4 formulas computing iterated matrix multiplication. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014) (2014), 128--135.
[6]
Grigoriev, D., Karpinski, M. An exponential lower bound for depth 3 arithmetic circuits. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC 1998) (1998), 577--582.
[7]
Grigoriev, D., Razborov, A.A. Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields. Appl. Algebra Eng. Commun. Comput. 10, 6 (2000), 465--487.
[8]
Gupta, A., Kamath, P., Kayal, N., Saptharishi, R. Approaching the chasm at depth four. J. ACM 61, 6 (2014), 33:1--33:16. Preliminary version in the 28th Annual IEEE Conference on Computational Complexity (CCC 2013).
[9]
Hardy, G.H., Ramanujan, S. Asymptotic formulaæ in combinatory analysis. Proc. London Math. Soc. s2-17, 1 (1918), 75--115.
[10]
Kabanets, V., Impagliazzo, R. Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complex. 13, 1--2 (2004), 1--46.
[11]
Karatsuba, A., Ofman, Y. Multipication of multidigit numbers on automata. Engl. Transl. Soviet Phys. Dokl. 7 (1963), 595--596.
[12]
Kayal, N., Limaye, N., Saha, C., Srinivasan, S. An exponential lower bound for homogeneous depth four arithmetic circuits. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014) (2014).
[13]
Kayal, N., Saha, C., Saptharishi, R. A super-polynomial lower bound for regular arithmetic formulas. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014) (2014), 146--153.
[14]
Koiran, P. Arithmetic circuits: The chasm at depth four gets wider. Theor. Comput. Sci. 448 (2012), 56--65.
[15]
Kumar, M., Saraf, S. The limits of depth reduction for arithmetic formulas: It's all about the top fan-in. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014) (2014), 136--145.
[16]
Kumar, M., Saraf, S. On the power of homogeneous depth 4 arithmetic circuits. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014) (2014).
[17]
Nisan, N., Wigderson, A. Hardness vs randomness. J. Comput. Syst. Sci. 49, 2 (1994), 149--167.
[18]
Nisan, N., Wigderson, A. Lower bounds on arithmetic circuits via partial derivatives. Comput. Complex. 6, 3 (1997), 217--234.
[19]
Ryser, H.J. Combinatorial mathematics. Math. Assoc. Am. 14 (1963).
[20]
Saxena, N. Diagonal circuit identity testing and lower bounds. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008) (2008), 60--71.
[21]
Shpilka, A., Wigderson, A. Depth-3 arithmetic circuits over fields of characteristic zero. Comput. Complex. 10, 1 (2001), 1--27.
[22]
Strassen, V. Gaussian elimination is not optimal. Numer. Math. 13, 3 (1969), 354--356.
[23]
Tavenas, S. Improved bounds for reduction to depth 4 and 3. In Proceedings of the 38th Internationl Symposium on the Mathematical Foundations of Computer Science (MFCS 2013) (2013).
[24]
Valiant, L.G. Completeness classes in algebra. In Proceedings of the 11th Annual ACM Symposium on Theory of Computing (STOC 1979) (1979), 249--261.
[25]
Valiant, L.G., Skyum, S., Berkowitz, S., Rackoff, C. Fast parallel computation of polynomials using few processors. SIAM J. Comput. 12, 4 (1983), 641--644.
[26]
Wigderon, A. P, NP and mathematics -- A computational complexity perspective. In M. Sanz-Solé, J. Soria, J.L. Varona and J. Verdera, eds. Proceedings of the ICM 06 (Madrid), Volume 1 (2007). EMS Publishing House, Zurich, 665--712.
Index Terms
- Unexpected power of low-depth arithmetic circuits
Recommendations
Arithmetic circuits: The chasm at depth four gets wider
In their paper on the ''chasm at depth four'', Agrawal and Vinay have shown that polynomials in m variables of degree O(m) which admit arithmetic circuits of size 2^o^(^m^) also admit arithmetic circuits of depth four and size 2^o^(^m^). This theorem ...
Hardness-randomness tradeoffs for bounded depth arithmetic circuits
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingIn this paper we show that lower bounds for bounded depth arithmetic circuits imply derandomization of polynomial identity testing for bounded depth arithmetic circuits. More formally, if there exists an explicit polynomial f(x1,...,xm) that cannot be ...
Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
In this paper we show that lower bounds for bounded depth arithmetic circuits imply derandomization of polynomial identity testing for bounded depth arithmetic circuits. More formally, if there exists an explicit polynomial $f$ that cannot be computed ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2017
93 pages
Copyright © 2017 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 May 2017
Published in CACM Volume 60, Issue 6
Check for updates
Qualifiers
- Research-article
- Research
- Refereed
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 5,023Total Downloads
- Downloads (Last 12 months)314
- Downloads (Last 6 weeks)79
Reflects downloads up to 01 Mar 2025
Other Metrics
Citations
View Options
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderDigital Edition
View this article in digital edition.
Digital EditionMagazine Site
View this article on the magazine site (external)
Magazine SiteLogin options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in