The DOI matches its Crossref record; 71 of the 71 references it cites were found in a registry or an index.
Arithmetic Circuits: A Survey of Recent Results and Open Questions
Abstract
A large class of problems in symbolic computation can be expressed as the task of computing some polynomials; and arithmetic circuits form the most standard model for studying the complexity of such computations. This algebraic model of computation attracted a large amount of research in the last five decades, partially due to its simplicity and elegance. Being a more structured model than Boolean circuits, one could hope that the fundamental problems of theoretical computer science, such as separating P from NP, will be easier to solve for arithmetic circuits. However, in spite of the appearing simplicity and the vast amount of mathematical tools available, no major breakthrough has been seen. In fact, all the fundamental questions are still open for this model as well. Nevertheless, there has been a lot of progress in the area and beautiful results have been found, some in the last few years. As examples we mention the connection between polynomial identity testing and lower bounds of Kabanets and Impagliazzo, the lower bounds of Raz for multilinear formulas, and two new approaches for proving lower bounds: Geometric Complexity Theory and Elusive Functions. The goal of this monograph is to survey the field of arithmetic circuit complexity, focusing mainly on what we find to be the most interesting and accessible research directions. We aim to cover the main results and techniques, with an emphasis on works from the last two decades. In particular, we discuss the recent lower bounds for multilinear circuits and formulas, the advances in the question of deterministically checking polynomial identities, and the results regarding reconstruction of arithmetic circuits. We do, however, also cover part of the classical works on arithmetic circuits. In order to keep this monograph at a reasonable length, we do not give full proofs of most theorems, but rather try to convey the main ideas behind each proof and demonstrate it, where possible, by proving some special cases.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
An algorithm for the machine calculation of complex Fourier series
Cooley, J. W., & Tukey, J. W. (1965) · Mathematics of Computation · doi:10.1090/s0025-5718-1965-0178586-1 · Cited by 13,154
Introduction to automata theory, languages and computation
(1981) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(81)90068-9 · Cited by 10,699
Bhatia, R., Bredon, G. E., Walter, W. L., Rotman, J. J., Murty, M. R., Gilman, J., Walters, P., Golubitsky, M., Karatzas, I., Cohen, H., et al. (1977) · Cited by 8,252
Handbook of theoretical computer science
Leeuwen, J. V. (1990) · Medical Entomology and Zoology · Cited by 4,259
Valiant, L. G. (1984) · Communications of the ACM · doi:10.1145/1968.1972 · Cited by 3,279
The complexity of computing the permanent
Valiant, L. G. (1979) · Theoretical Computer Science · doi:10.1016/0304-3975(79)90044-6 · Cited by 2,705
Gaussian elimination is not optimal
Strassen, V. (1969) · Numerische Mathematik · doi:10.1007/bf02165411 · Cited by 2,509
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · Cited by 2,371
On lattices, learning with errors, random linear codes, and cryptography
Regev, O. (2009) · Journal of the ACM · doi:10.1145/1568318.1568324 · Cited by 2,315
Matrix multiplication via arithmetic progressions
Coppersmith, D., & Winograd, S. (1990) · Journal of Symbolic Computation · doi:10.1016/s0747-7171(08)80013-2 · Cited by 2,248
How to construct random functions
Goldreich, O., Goldwasser, S., & Micali, S. (1986) · Journal of the ACM · doi:10.1145/6490.6503 · Cited by 2,115
Expander graphs and their applications
Hoory, S., Linial, N., & Wigderson, A. (2006) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-06-01126-8 · Cited by 1,723
Fast Probabilistic Algorithms for Verification of Polynomial Identities
Schwartz, J. T. (1980) · Journal of the ACM · doi:10.1145/322217.322225 · Cited by 1,701
An Introduction to Computational Learning Theory
Kearns, M. J., & Vazirani, U. (1994) · doi:10.7551/mitpress/3897.001.0001 · Cited by 1,697
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · doi:10.1017/cbo9780511804090 · Cited by 1,690
(2000) · Choice Reviews Online · doi:10.5860/choice.37-5723 · Cited by 1,616
Proof verification and the hardness of approximation problems
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1998) · Journal of the ACM · doi:10.1145/278298.278306 · Cited by 1,413
Complexity and real computation
(1998) · Choice Reviews Online · doi:10.5860/choice.35-6275c · Cited by 1,228
Probabilistic checking of proofs: a new characterization of NP
Arora, S., & Safra, S. (1998) · Journal of the ACM · doi:10.1145/273865.273901 · Cited by 1,153
Probabilistic algorithms for sparse polynomials
Zippel, R. (1979) · Lecture Notes in Computer Science · doi:10.1007/3-540-09519-5_73 · Cited by 1,101
Bürgisser, P., Clausen, M., & Shokrollahi, M. A. (1997) · Grundlehren der mathematischen Wissenschaften · doi:10.1007/978-3-662-03338-8 · Cited by 1,026
Ryser, H. (1963) · Carus Mathematical Monographs · doi:10.5948/upo9781614440147 · Cited by 969
Agrawal, M., Kayal, N., & Saxena, N. (2004) · Annals of Mathematics · doi:10.4007/annals.2004.160.781 · Cited by 931
Algebraic methods in the theory of lower bounds for Boolean circuit complexity
Smolensky, R. (1987) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/28395.28404 · Cited by 845
Nisan, N., & Wigderson, A. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80043-1 · Cited by 808
Cryptographic limitations on learning Boolean formulae and finite automata
Kearns, M., & Valiant, L. (1994) · Journal of the ACM · doi:10.1145/174644.174647 · Cited by 733
Algebraic methods for interactive proof systems
Lund, C., Fortnow, L., Karloff, H., & Nisan, N. (1992) · Journal of the ACM · doi:10.1145/146585.146605 · Cited by 711
PP is as Hard as the Polynomial-Time Hierarchy
Toda, S. (1991) · SIAM Journal on Computing · doi:10.1137/0220053 · Cited by 665
Shamir, A. (1992) · Journal of the ACM · doi:10.1145/146585.146609 · Cited by 662
Alon, N. (1999) · Combinatorics Probability Computing · doi:10.1017/s0963548398003411 · Cited by 653
Almost optimal lower bounds for small depth circuits
Hastad, J. (1986) · Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86 · doi:10.1145/12130.12132 · Cited by 620
Matching is as easy as matrix inversion
Mulmuley, K., Vazirani, U. V., & Vazirani, V. V. (1987) · Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87 · doi:10.1145/28395.383347 · Cited by 609
Håstad, J. (1990) · Journal of Algorithms · doi:10.1016/0196-6774(90)90014-6 · Cited by 584
P = BPP if E requires exponential circuits: derandomizing the XOR lemma
Impagliazzo, R., & Wigderson, A. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258590 · Cited by 534
Non-deterministic exponential time has two-prover interactive protocols
Babai, L., Fortnow, L., & Lund, C. (1992) · Computational Complexity · doi:10.1007/bf01200430 · Cited by 520
Razborov, A. A., & Rudich, S. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1494 · Cited by 479
The complexity of partial derivatives
Baur, W., & Strassen, V. (1983) · Theoretical Computer Science · doi:10.1016/0304-3975(83)90110-x · Cited by 468
Completeness Classes in Algebra
Valiant, L. G. (1979) · ACM eBooks · doi:10.1145/3749740.3749750 · Cited by 465
Non-deterministic exponential time has two-prover interactive protocols
Babai, L., Fortnow, L., & Lund, C. (1991) · Computational Complexity · doi:10.1007/bf01200056 · Cited by 458
Gaussian Elimination is not Optimal
Trassen, V. (2005) · Cited by 454
Fast Parallel Matrix Inversion Algorithms
Csanky, L. (1976) · SIAM Journal on Computing · doi:10.1137/0205040 · Cited by 397
Matching is as easy as matrix inversion
Mulmuley, K., Vazirani, U. V., & Vazirani, V. V. (1987) · Combinatorica · doi:10.1007/bf02579206 · Cited by 388
Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds
Kabanets, V., & Impagliazzo, R. (2004) · computational complexity · doi:10.1007/s00037-004-0182-6 · Cited by 378
Graph-theoretic arguments in low-level complexity
Valiant, L. G. (1977) · Lecture Notes in Computer Science · doi:10.1007/3-540-08353-7_135 · Cited by 312
In search of an easy witness: exponential time vs. probabilistic polynomial time
Impagliazzo, R., Kabanets, V., & Wigderson, A. (2002) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(02)00024-7 · Cited by 212
Group-theoretic Algorithms for Matrix Multiplication
Cohn, H., Kleinberg, R., Szegedy, B., & Umans, C. (2005) · 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05) · doi:10.1109/sfcs.2005.39 · Cited by 201
Geometric Complexity Theory I: An Approach to the P vs.NP and Related Problems
Mulmuley, K. D., & Sohoni, M. (2001) · SIAM Journal on Computing · doi:10.1137/s009753970038715x · Cited by 196
Arithmetic Circuits: A Chasm at Depth Four
Agrawal, M., & Vinay, V. (2008) · 2008 49th Annual IEEE Symposium on Foundations of Computer Science · doi:10.1109/focs.2008.32 · Cited by 185
Die Berechnungskomplexit�t von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
Strassen, V. (1973) · Numerische Mathematik · doi:10.1007/bf01436566 · Cited by 150
Arithmetic circuits: The chasm at depth four gets wider
Koiran, P. (2012) · Theoretical Computer Science · doi:10.1016/j.tcs.2012.03.041 · Cited by 135
Learning functions represented as multiplicity automata
Beimel, A., Bergadano, F., Bshouty, N. H., Kushilevitz, E., & Varricchio, S. (2000) · Journal of the ACM · doi:10.1145/337244.337257 · Cited by 132
Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties
Mulmuley, K., & Sohoni, M. (2008) · SIAM Journal on Computing · doi:10.1137/080718115 · Cited by 120
The matching problem for bipartite graphs with polynomially bounded permanents is in NC
Grigoriev, D. Y., & Karpiński, M. (1987) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1987.56 · Cited by 110
Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
Morgenstern, J. (1973) · Journal of the ACM · doi:10.1145/321752.321761 · Cited by 108
Cryptographic hardness for learning intersections of halfspaces
Klivans, A. R., & Sherstov, A. A. (2008) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2008.07.008 · Cited by 108
Factorization of Polynomials Given by Straight-Line Programs.
Kaltofen, E. (1989) · Cited by 108
A Group-theoretic Approach to Fast Matrix MultiplicationPreprint
Cohn, H., & Umans, C. (2003) · Cited by 105
Strassen, V. (1990) · Elsevier eBooks · doi:10.1016/b978-0-444-88071-0.50016-3 · Cited by 90
On the Complexity of Matrix Product
Raz, R. (2003) · SIAM Journal on Computing · doi:10.1137/s0097539702402147 · Cited by 84
Negation can be exponentially powerful
Valiant, L. G. (1980) · Theoretical Computer Science · doi:10.1016/0304-3975(80)90060-2 · Cited by 71
P=BPP unless E has sub-exponential circuits: Derandomizing the XOR Lemma
Impagliazzo, R., & Wigderson, A. (1997) · Cited by 69
Feasible arithmetic computations: Valiant's hypothesis
Gathen, J. V. Z. (1987) · Journal of Symbolic Computation · doi:10.1016/s0747-7171(87)80063-9 · Cited by 63
Deterministic extractors for affine sources over large fields
Gabizon, A., & Raz, R. (2008) · COMBINATORICA · doi:10.1007/s00493-008-2259-3 · Cited by 62
Efficient learning algorithms yield circuit lower bounds
Fortnow, L., & Klivans, A. R. (2008) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2008.07.006 · Cited by 39
Affine projections of symmetric polynomials
Shpilka, A. (2002) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(02)00021-1 · Cited by 36
Self-citationLower Bounds for Matrix Product
Shpilka, A. (2003) · SIAM Journal on Computing · doi:10.1137/s0097539702405954 · Cited by 35
Self-citationA 5/2n/sup 2/-lower bound for the rank of n×n-matrix multiplication over arbitrary fields
Bläser, M. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sffcs.1999.814576 · Cited by 32
On the structure of valiant's complexity classes
Bürgisser, P. (1998) · Lecture notes in computer science · doi:10.1007/bfb0028561 · Cited by 23
Relationless Completeness and Separations
Hrubeš, P., Wigderson, A., & Yehudayoff, A. (2010) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2010.34 · Cited by 16
Self-citationA - Lower Bound for the Rank of - Matrix Multiplication over Arbitrary Fields
Bläser, M. (1999) · Cited by 13
Valiant, L. G. (2026) · Foundations of Computation and Machine Learning · doi:10.1145/3749740.3749746
Cited by
(2016) · Conference on Learning Theory · Cited by 443
Metadata
- Authors
- Shpilka, A., & Yehudayoff, A.
- Venue
- Foundations and Trends® in Theoretical Computer Science
- Publisher
- Emerald
- Published
- 2010-12-14
- Volume
- 5
- Issue
- 3-4
- Pages
- 207-388
- ISSN
- 1551-305X (ISSN-L)
- 1551-3068
- OpenAlex
- W2026944800
- Cited by
- 363
- References
- 71
- FWCI
- 18.46
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.