Fact-checked by Grok 2 weeks ago

Arithmetic circuit complexity

Arithmetic circuit complexity is a subfield of algebraic complexity theory that investigates the computational resources, primarily size and depth, needed to evaluate multivariate polynomials using arithmetic circuits—directed acyclic graphs composed of addition and multiplication gates over a field, with inputs from variables or constants.^[1] These circuits model the efficient symbolic computation of polynomials, analogous to Boolean circuits for decision problems, and serve as a foundational framework for understanding algebraic analogs of central questions in complexity theory, such as the separation of classes like VP (polynomials computable by polynomial-sized, polynomial-degree circuits) and VNP (polynomials expressible as polynomial-sized sums of VP polynomials).^[1]^[2] Key complexity measures include circuit size, defined as the number of gates or wires, and depth, the length of the longest path from input to output, which quantify the efficiency of polynomial computation.^[1] Variants of the model, such as formulas (tree-like circuits), multilinear circuits (where each variable appears at most once in any monomial), algebraic branching programs (layered graphs for matrix-like computations), and depth-bounded circuits (e.g., depth-3 or depth-4 with alternating sum and product layers), allow for refined analyses of specific computational paradigms.^[1]^[2] Notable applications extend to polynomial identity testing (PIT), which determines whether a circuit computes the zero polynomial, with black-box (via random evaluations) and white-box (via circuit structure) algorithms enabling derandomization efforts; for instance, polynomial-time PIT exists for noncommutative formulas, while quasi-polynomial algorithms handle certain depth-bounded cases.^[1] Central challenges revolve around proving lower bounds on circuit size for explicit polynomials, such as the determinant (efficiently computable in polynomial size) versus the permanent (believed to require super-polynomial size), highlighting the non-uniformity of algebraic computation.^[2] Early results include Strassen's \Omega(n \log r) lower bound for computing degree-r polynomials in n variables and Kalorkoti's \Omega(n^3 / \log^2 n) bound for determinant formulas, but super-polynomial lower bounds for general circuits remain elusive, akin to the P vs. NP barrier.^[1] Post-2010 progress has focused on restricted models: superpolynomial lower bounds for constant-depth circuits were established in 2021 by Limaye, Srinivasan, and Tavenas, providing the first such separations for all constant depths over characteristic-zero fields and implying sub-exponential deterministic PIT for such circuits. This bound was improved in 2024 by Bhargav and Dutta, achieving a slightly stronger exponent and establishing a barrier to further progress using shifted partials methods.^[3] Other advances include n^{\Omega(\sqrt{d})} bounds for depth-4 circuits computing the d \times d determinant and exponential separations between multilinear formulas and algebraic branching programs for explicit polynomials.^[2] Recent connections link arithmetic circuit complexity to broader areas, including proof complexity (e.g., ideal proof system lower bounds implying circuit separations) and even machine learning, where low-complexity structured matrices (like kaleidoscope matrices) enable efficient neural network representations with reduced parameters.^[4] Despite these strides, major open problems persist, such as establishing super-polynomial lower bounds for general (unrestricted-depth) circuits, fully separating VP from VNP via explicit polynomials, and developing deterministic polynomial-time PIT for multilinear formulas—challenges that continue to drive research in algebraic and computational complexity.^[2]^[1]

Basic Concepts

Arithmetic Circuits

Arithmetic circuits provide a computational model for evaluating multivariate polynomials, serving as a fundamental tool in algebraic complexity theory. Formally, an arithmetic circuit over a field \mathbb{F} and a set of variables X = \{x_1, \dots, x_n\} is defined as a directed acyclic graph (DAG), where nodes represent gates: input gates (with in-degree 0) are labeled either with variables from X or scalar constants from \mathbb{F}, and internal gates (with in-degree 2) are labeled with either addition (+) or multiplication (\times). Edges direct the flow from input gates to an output gate, which computes the overall polynomial represented by the circuit.^[1] To evaluate the circuit, values are propagated bottom-up from the input gates: each input gate yields its labeled value (a variable or constant), each sum gate outputs the sum of the polynomials from its incoming edges, and each product gate outputs their product, all computed over \mathbb{F}. The output gate thus yields the value of a multivariate polynomial in the variables X, with coefficients in \mathbb{F}. This model allows for efficient reuse of intermediate computations through multiple fan-outs, distinguishing general arithmetic circuits from more restrictive variants.^[1] A key distinction exists between general arithmetic circuits, which permit fan-out greater than 1 (enabling shared subcomputations via DAG structure), and arithmetic formulas, which are tree-like with fan-out exactly 1 (no sharing, resembling expression trees). For example, a simple circuit for [x + y](/page/X%26Y) consists of two input gates connected to a single sum gate, while one for xy uses a product gate similarly; more complex cases include circuits for elementary symmetric polynomials, such as \sigma_{k,m} = \sum_{S \subseteq , |S|=k} \prod_{i \in S} x_i, which sum products over all subsets of fixed size.^[1] Arithmetic circuits are typically defined over fields like the rationals \mathbb{Q}, finite fields \mathbb{F}_p, or the reals \mathbb{R}, where operations are closed and invertible as needed; however, they can also operate over rings such as the integers \mathbb{Z}, though certain results may require characteristic restrictions (e.g., non-zero characteristic for some identities). This flexibility allows the model to capture polynomial computations in diverse algebraic settings.^[1]

Size and Depth Measures

In arithmetic circuit complexity, two primary measures quantify the efficiency of a circuit: its size and depth. The size of an arithmetic circuit C, denoted s(C), is the total number of gates in C.^[1] This metric captures the overall computational resources required, encompassing both input gates (labeled by constants or variables) and operation gates (for addition or multiplication).^[5] Similarly, the depth of C, denoted d(C), is the length of the longest directed path from an input gate to any output gate, measured by the number of edges along that path.^[1] Depth reflects the inherent parallelism or sequentiality in the computation, with shallower depths indicating greater potential for parallel evaluation.^[5] Arithmetic circuits are analyzed in both uniform and non-uniform models. In the non-uniform model, circuit families are given explicitly as arbitrary collections, one for each input size, without requiring a compact description.^[1] In contrast, the uniform model restricts circuit families to those generatable by a Turing machine in polynomial time relative to the input size n, ensuring that the circuit description itself can be produced efficiently.^[5] This distinction is crucial, as non-uniform families can exploit problem-specific structures unavailable in uniform settings, though the two models often coincide for many natural problems under standard complexity assumptions.^[1] Efficiency in arithmetic circuits is typically assessed relative to the number of variables n. A circuit family is said to have polynomial size if s(C_n) = O(\poly(n)) for the circuit C_n computing a function on n variables.^[1] Likewise, logarithmic depth requires d(C_n) = O(\log n), enabling computations that balance resource usage with parallelism.^[5] These notions underpin complexity classes like VP, which capture problems solvable by polynomial-size, polynomial-depth circuits.^[1] A representative example illustrates these measures: consider an arithmetic circuit computing x^d as the product of d copies of the input variable x, structured as a balanced binary tree where leaves are inputs labeled x and internal nodes perform multiplication. This construction yields size s(C) = O(d), as it requires d-1 multiplication gates, and depth d(C) = O(\log d), due to the balanced layering of the tree.^[1] Such examples highlight how tree-like topologies can trade off size for reduced depth in basic powering tasks.^[5]

Complexity Bounds

Upper Bounds

Strassen's algorithm marked a breakthrough in efficient matrix multiplication, demonstrating that two n \times n matrices over fields of characteristic zero can be multiplied using an arithmetic circuit of size O(n^{\log_2 7}) \approx O(n^{2.807}) and depth O(\log n), achieved through recursive decomposition into seven multiplications and eighteen additions of (n/2) \times (n/2) submatrices. This 1969 result initiated the study of fast matrix multiplication in arithmetic circuit complexity, improving upon the standard cubic-time approach. Subsequent refinements, including laser methods and asymmetric constructions, have lowered the exponent \omega to approximately 2.371, yielding circuits of size O(n^\omega) and depth O(\log n). For the determinant of an n \times n matrix, Berkowitz's algorithm constructs a division-free arithmetic circuit of polynomial size—specifically O(n^{3.496})—and depth O(\log^2 n) over any field, by iteratively computing traces of powers of a companion-like matrix derived from the input.^[6] This parallelizable method ensures efficient computation in the nonuniform model, with each step involving matrix-vector multiplications that can be parallelized further using fast matrix multiplication techniques. Ryser's inclusion-exclusion formula computes the permanent of an n \times n matrix using a depth-3 arithmetic circuit of size O(n \cdot 2^n) over rings such as the integers, consisting of summation gates over subsets followed by products of row sums.^[7] This construction, while exponential in size, achieves constant depth and highlights the permanent's computability within bounded parallel time despite its higher complexity compared to the determinant. The iterated matrix multiplication polynomial, which evaluates the (1,1)-entry of the product of n generic d \times d matrices, admits arithmetic circuits of polynomial size and logarithmic depth over fields, obtained by balancing a multiplication tree with fast matrix multiplication at each level.^[8] Similarly, matrix inversion over fields of characteristic zero can be realized with polynomial-size circuits of polylogarithmic depth, using iterative refinement methods or reductions to determinant computations via the adjugate formula, where the latter leverages efficient minor evaluations.^[9]

Lower Bounds

In arithmetic circuit complexity, early lower bounds focused on demonstrating that certain polynomials require more than linear resources, even for seemingly simple computations. A seminal result is due to Strassen, who proved that any arithmetic circuit over a field computing the individual power polynomials x_1^d, \dots, x_n^d requires size \Omega(n \log d). This bound extends to the power sum polynomial \sum_{i=1}^n x_i^d, which also demands size \Omega(n \log d) provided that d does not divide the characteristic of the field. These results highlight the logarithmic dependence on the degree, showing that high-degree computations cannot be efficiently reduced to linear-size circuits without exploiting field-specific properties.^[10] Further progress came with the partial derivatives method introduced by Baur and Strassen, which relates the size of a circuit to the complexity of computing its partial derivatives. Specifically, if a circuit of size s computes a polynomial f, then all first-order partial derivatives of f can be computed by a circuit of size O(s). The method can be used to derive lower bounds by considering the affine dimension of the space spanned by the partial derivatives; for instance, it implies linear lower bounds \Omega(n) for polynomials depending on n variables. This remains among the basic techniques, though stronger superlinear bounds like Strassen's \Omega(n \log d) are known for higher-degree explicit polynomials.^[11] Adaptations of the Razborov-Smolensky approximation method, originally developed for Boolean constant-depth circuits, have been extended to arithmetic settings over finite fields, particularly for bounded-depth circuits. In the arithmetic case, these techniques yield exponential lower bounds for depth-3 circuits (ΣΠΣ form) computing certain multilinear polynomials, such as those related to modular gates like MOD_q over \mathbb{F}_p (with distinct primes p \neq q), requiring size $2^{\Omega(n)}. For multilinear arithmetic circuits of constant depth, superlinear lower bounds have been obtained for explicit multilinear polynomials using similar polynomial approximation arguments, demonstrating that low-degree approximations cannot capture the full complexity of these functions. Post-2010 advances include superpolynomial lower bounds for constant-depth circuits in general, such as the exponential separation for all constant depths over characteristic-zero fields established by Limaye, Srinivasan, and Tavenas in 2021.^[12] Significant barriers limit progress toward stronger lower bounds, particularly in separating the complexity classes VP and VNP. In the 1990s, Shamir and others identified limitations in proof techniques relying on rank concentrators and matrix concentration arguments, showing that such methods fail to establish VP \neq VNP because they cannot distinguish between low-rank and high-rank representations for VNP-complete polynomials like the permanent. These barriers imply that new paradigms, beyond rank-based or approximation methods, are needed to prove superpolynomial lower bounds. A major open problem persists: no explicit polynomial of polynomial degree is known to require superpolynomial circuit size for general unrestricted-depth circuits, despite the belief that such separations exist; as of 2025, this remains unresolved.^[1]

Algebraic Complexity Classes

VP and VNP

In arithmetic circuit complexity, the class VP consists of all families of polynomials \{f_n\} that are p-bounded, meaning there exists a polynomial t(n) such that for each n, the polynomial f_n in n variables has degree at most t(n) and can be computed by an arithmetic circuit of size at most t(n) over a field \mathbb{F}.^[1] This class serves as the arithmetic analogue of the complexity class P, capturing polynomials that admit efficient symbolic computation via polynomial-sized circuits. Typically, such families are considered over fields of characteristic zero, like the rationals \mathbb{Q}, or over finite fields with sufficiently large characteristic to avoid degree issues, ensuring the circuits operate over expanding rings as n grows.^[1] A classic example in VP is the family of determinants \{\det_n\}, where \det_n(X) = \sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i=1}^n x_{i,\sigma(i)} for an n \times n matrix X over \mathbb{F}, which can be computed using Gaussian elimination or Leibniz formula in polynomial size.^[1] The class VNP is defined as the collection of p-definable families of polynomials \{f_n\}, where there exist polynomially bounded functions t(n) and k(n), along with a family \{g_m\} \in \mathrm{VP}_\mathbb{F}, such that f_n(x_1, \dots, x_{k(n)}) = \sum_{w \in \{0,1\}^{t(n)}} g_{k(n) + t(n)}(x_1, \dots, x_{k(n)}, w_1, \dots, w_{t(n)}).^[1] This formulation introduces a counting element analogous to #P, where the coefficients of f_n are computed by summing over a polynomial-length witness string w using a polynomial-sized circuit, reflecting the counting nature of problems like those in #P.^[1] Like VP, VNP is studied over fields such as \mathbb{Q} or large finite fields to handle the summation over exponentially many witnesses without collapsing degrees. A prominent example in VNP (but not known to be in VP) is the family of permanents \{\perm_n\}, defined by \perm_n(X) = \sum_{\sigma \in S_n} \prod_{i=1}^n x_{i,\sigma(i)} for an n \times n matrix X, which lacks an efficient polynomial-sized circuit despite admitting a depth-3 representation via Ryser's formula.^[13]^[1] A key structural result, established by Valiant, is that VP is closed under p-projections, meaning if \{f_n\} \in \mathrm{VP}_\mathbb{F} and \{g_n\} is obtained by substituting affine linear forms (projections) into a polynomially larger instance of another family in VP, then \{g_n\} \in \mathrm{VP}_\mathbb{F}.^[14]^[1] This closure property, proven using polynomial identity testing techniques, ensures that VP behaves robustly under Turing-style reductions in the arithmetic setting, facilitating the study of relative complexities without increasing circuit size beyond polynomial bounds. The analogous closure holds for VNP under p-projections, underscoring the parallel between these classes and their Boolean counterparts.^[14]

Completeness and Reductions

In 1979, Leslie Valiant established that the permanent polynomial family, denoted \mathrm{PERM}_n, is complete for the class VNP under p-projections over fields of characteristic not equal to 2.^[14] This result positions the permanent as one of the hardest problems in VNP, meaning any problem in VNP can be reduced to it via p-projections, which involve substituting variables with constants or linear forms computable in polynomial time.^[1] Valiant also showed in the same work that the determinant polynomial family, \mathrm{DET}_n, is complete for VP under quasi-polynomial projections, highlighting a fundamental separation candidate between the classes.^[14] Reductions in arithmetic circuit complexity primarily use p-projections, which allow for affine substitutions that may scale coefficients but preserve the essential structure of the polynomial family.^[1] In contrast, parsimonious reductions, borrowed from boolean counting complexity, preserve the exact coefficients (such as the number of solutions) without scaling, making them stricter and more challenging to construct in the arithmetic setting.^[15] For example, #P-complete problems like counting the number of satisfying assignments to a boolean formula can be mapped to VNP via arithmetic encodings, such as interpreting the formula as a generating function whose coefficients encode solution counts, though these reductions often rely on projections rather than fully parsimonious ones to fit within VNP's framework.^[13] Valiant's completeness proof for the permanent leverages such projections to reduce other VNP problems to it, demonstrating that even 0-1 permanents (over integer matrices) capture #P-hardness.^[13] The hypothesis VP = VNP, if true, would imply that all VNP-complete problems like the permanent admit polynomial-size arithmetic circuits, effectively collapsing the algebraic complexity hierarchy to its first level, where VP = VNP = VNP^{VP} = \cdots.^[1] This equivalence would also yield efficient deterministic algorithms for polynomial identity testing, with broader ramifications for derandomization in both algebraic and boolean settings.^[1] Valiant's hypothesis, conversely, posits that VP \neq VNP, motivated by the stark computational gap between the permanent (believed to require super-polynomial circuits) and the determinant (computable in polynomial time via Gaussian elimination, and thus in VP).^[14] This conjecture underscores the permanent-determinant distinction as a core challenge, suggesting that no polynomial-size circuit exists for \mathrm{PERM}_n unless the classes coincide.^[1] Arithmetic circuit complexity connects to boolean complexity through shared hardness results, particularly via #P-completeness of problems like the permanent, which Valiant proved independently.^[13]

Advanced Techniques

Depth Reduction

Depth reduction in arithmetic circuit complexity refers to techniques that transform circuits or formulas computing multivariate polynomials into equivalent ones with significantly smaller depth, at the potential cost of increased size. These results are crucial for understanding the parallel computability of algebraic problems, as depth corresponds to the time in parallel models. Seminal works in this area provide trade-offs between size and depth for arithmetic formulas and circuits over fields of characteristic zero or finite fields. In 1979, Laurent Hyafil established a foundational result for arithmetic formulas. Specifically, any arithmetic formula of size s computing a polynomial of degree r can be converted to an equivalent arithmetic circuit of depth O(\log s \cdot \log r) and size s^{O(\log r)}.^[16] This simulation preserves the computed polynomial and applies to formulas where gates perform addition or multiplication over the input variables. This was improved in 1983 by Valiant, Skyum, Berkowitz, and Rackoff, who showed that any arithmetic formula of size s and degree r has an equivalent circuit of depth O(\log r \cdot \log s) and size s^{O(\log r)}.^[17] Their theorem extends to general arithmetic circuits of size s and degree r, yielding the same depth and size bounds, thus demonstrating that the class VP of polynomial-size, polynomial-degree arithmetic circuits equals the class VNC^2 of polynomial-size circuits of O(\log^2 n) depth (up to superpolynomial size in the simulation).^[17] These depth reduction procedures have key applications in algebraic complexity, notably placing the determinant polynomial in the class of algebraic NC, which consists of families computable by uniform, polynomial-size arithmetic circuits of polylogarithmic depth. The n \times n determinant, which has a known polynomial-size circuit of degree n, can thus be computed by a polynomial-size circuit of O(\log^2 n) depth using refinements like the Berkowitz algorithm, which leverages iterative matrix powering to achieve this parallelization.^[18] The proofs of these depth reduction theorems rely on a recursive decomposition strategy combined with Kronecker substitution, a technique to encode multivariate multiplications into univariate ones. To simulate a high-degree multiplication gate in a formula, variables are substituted as x_i \mapsto X^{b^i} for a base b > r, allowing the product to be evaluated as powers of a single indeterminate X, which can then be parallelized using fast exponentiation circuits of logarithmic depth; recursion on subformulas then reduces the overall depth logarithmically.^[17]^[16] Despite these advances, depth reduction incurs limitations: in the worst case, reducing depth to a constant can require exponential size blowup, as evidenced by exponential lower bounds for constant-depth arithmetic circuits computing explicit polynomials like the permanent.^[19] This highlights the inherent trade-offs and motivates ongoing research into tighter size-depth relations.

Monotone Arithmetic Circuits

Monotone arithmetic circuits are a restricted model of arithmetic computation where all constants are non-negative, and the only allowed operations are addition and multiplication, forbidding subtraction, negation, or negative constants. This restriction prevents cancellations that could otherwise simplify computations, making monotone circuits a natural model for problems involving non-negative data, such as counting or optimization over positive weights.^[20]^[21] In contrast to general arithmetic circuits, which permit subtractions and thus enable cancellations to achieve smaller sizes for certain polynomials, monotone circuits cannot exploit such mechanisms and often require significantly larger sizes to compute the same functions. For instance, Valiant demonstrated that general arithmetic circuits with negation can be exponentially more powerful than their monotone counterparts.^[22] A seminal result in this area is the exponential size lower bound for computing the permanent polynomial using monotone arithmetic circuits. Jerrum and Snir proved that any such circuit requires at least n(2^{n-1} - 1) multiplication gates to compute the permanent of an n \times n matrix over the non-negative reals, establishing an exponential separation from non-monotone circuits, which can compute the permanent in polynomial size. This bound highlights the inherent difficulty of permanent computation without cancellations, as the monotone model aligns closely with the #P-hardness of the problem in combinatorial settings.^[23] Monotone arithmetic circuits find applications in combinatorial optimization, particularly for problems with non-negative weights, such as matching or path counting, where the monotonicity restriction mirrors the positivity constraints in optimization formulations. For example, lower bounds on monotone circuits for the perfect matching function provide insights into the complexity of optimizing over bipartite graphs with positive edge weights, improving prior subexponential bounds to $2^{\Omega(n)} size requirements. These connections underscore how monotone models bridge algebraic complexity with practical optimization challenges like resource allocation or network design.^[24]^[25] Recent advances from 2020 to 2025 have strengthened lower bounds in the monotone setting, including superlogarithmic depth requirements for circuits computing clique functions and improved size bounds for related combinatorial polynomials. Notably, de Rezende's survey at STACS 2025 highlights breakthroughs via query-to-communication lifting theorems, achieving optimal $2^{\Omega(n)} lower bounds for monotone Boolean formulas and better size separations for clique computations, alongside superlogarithmic depth lower bounds for connectivity in monotone circuits. These results extend classical separations and inform ongoing efforts to understand monotone analogues of parallel computation classes like NC. Additionally, progress on monotone matrix powers has yielded improved lower bounds, linking rigidity arguments to exponential separations under non-negativity assumptions.^[26]^[27]

Recent Developments

In 2021, significant progress was made in understanding the arithmetic circuit complexity of division and truncation operations. Researchers showed that if a rational function f = g/h is expressed with g and h computable by circuits of size s, then f can be computed by a circuit of size \poly(s, \deg(h)), improving prior bounds that depended on the degree of f. For truncation, the degree-d truncation of a rational function g/h with circuit size s for g can be computed in size \poly(s, \deg(h), \log d), with hardness results linking truncation to problems like integer factoring. These results provide new insights into algebraic operations within circuits, though lower bounds via partial derivatives were not directly established in this work. Advancing reconstruction algorithms, a 2025 breakthrough introduced the first quasi-polynomial time algorithm for reconstructing depth-3 arithmetic circuits (denoted \Sigma \Pi \Sigma^{(3)}) with top fan-in 3 over fields like \mathbb{R} and \mathbb{C}. Given black-box access to an n-variate polynomial f of degree d computed by such a circuit of size s, the randomized algorithm runs in time (nd)^{O(\log d)} \cdot \poly(s) (accounting for bit complexity) and succeeds with probability $1 - o(1), outputting an equivalent circuit under rank conditions on the gates or a generalized form otherwise. This employs techniques like random linear isomorphisms and vanishing subspaces, marking a subexponential advance for this restricted model. Connections between proof complexity and arithmetic circuits deepened in 2025 through enhanced lower bounds on the Ideal Proof System (IPS). Superpolynomial IPS lower bounds over finite fields imply \VNP \neq \VP, with new results establishing such bounds for constant-depth multilinear IPS fragments using knapsack instances modulo primes p \geq 5, yielding sizes $2^{\Omega(n)} for refuting specific circuit identities. These advancements extend prior roABP-IPS bounds to finite fields and provide translation lemmas linking algebraic proofs to CNF encodings, potentially impacting deeper separations in algebraic complexity. At STACS 2025, breakthroughs in monotone circuit complexity included improved lower bounds for the clique function via query-to-communication lifting theorems with colorful sunflowers, enhancing prior superlogarithmic bounds to stronger exponential separations for monotone circuits computing the clique polynomial on n-vertex graphs. Similar techniques yielded better monotone lower bounds for other graph polynomials, such as matching, requiring sizes $2^{n^{\Omega(1)}}, driven by advancements in lifting protocols that bridge communication and circuit models. Despite these advances, no superpolynomial lower bounds exist for explicit polynomials in \VNP relative to \VP, remaining a central open question in arithmetic circuit complexity. However, progress in black-box Polynomial Identity Testing (PIT) derandomization has accelerated, with 2024-2025 results providing randomized polynomial-time black-box PIT algorithms for small-depth +-regular non-commutative circuits of any constant depth, running in time s^{O(d^2)} where s is circuit size and d depth, succeeding with high probability via hitting set generators.

References

[1]
[PDF] Arithmetic Circuits: a survey of recent results and open questions
Arithmetic circuits are a model for computing polynomials, used to study the complexity of such computations in symbolic computation.
[2]
[PDF] A survey of lower bounds in arithmetic circuit complexity
This survey covers recent activity on lower bounds in arithmetic circuit complexity, aiming to help people familiarize with known bounds and develop tools.
[3]
[PDF] Arithmetic Circuits, Structured Matrices and (not so) Deep Learning
Oct 31, 2022 · 1 Introduction. This survey shows how concepts in arithmetic circuit complexity and structured matrices can be used to solve a (theoretical) ...
[4]
[PDF] Arithmetic Complexity - A Survey Lecturer: Avi Wigderson * Scribe
Feb 7, 2002 · We describe the state of the art in the computational complexity of natural polynomials,. e.g. symmetric functions, determinant, matrix ...
[5]
[PDF] on computing the determinant in small parallel time using a small ...
Mar 30, 1984 · Berkowitz and C. Rackoff, Fast parallel computation of polynomials using few processors,. SIAM J. Comput. (1982) submitted for publication. S ...
[6]
[PDF] FPRAS Approximation of the Matrix Permanent in Practice - arXiv
Dec 6, 2020 · Ryser's algorithm for the matrix permanent was published by H.J. Ryser in 1963 [20]. A theoretical description and big-Oh probabilistic analysis ...
[7]
[PDF] The Complexity of Iterated Multiplication
The upper left n n corner of Ax will consist of the matrix given by the formula (x i j). This is achieved as follows. First let Ex be the product of n n3 n3.
[8]
[PDF] Non-Commutative Arithmetic Circuits with Division
Dec 20, 2015 · In Section 3 we prove the circuit size upper bound on matrix inverse, and in Section 4 the formula size lower bound for it, via a general.
[9]
Die Berechnungskomplexität von elementarsymmetrischen ...
Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten. Published: June 1973. Volume 20, pages 238–251, (1973) ...
[10]
The complexity of partial derivatives - ScienceDirect.com
Strassen. Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten. Numer. Math., 20 (1973), pp. 238-251. View in ...<|control11|><|separator|>
[11]
Exponential Lower Bounds for Depth 3 Arithmetic Circuits in ...
We prove an exponential complexity lower bound on depth 3 arithmetic circuits computing some natural symmetric functions over a finite field F. Also, we study ...
[12]
The complexity of computing the permanent - ScienceDirect.com
It is shown that the permanent function of (0, 1)-matrices is a complete problem for the class of counting problems associated with nondeterministic ...
[13]
Completeness classes in algebra - ACM Digital Library
The aim of this paper is to demonstrate that for both algebraic and combinatorial problems this phenomenon exists in a form that is purely algebraic.
[14]
[PDF] Parameterized Valiant's Classes - DROPS
The permanent family (pern) is complete for VNP under p-projections (over fields of characteristic distinct from two) and the problem of computing the ...<|control11|><|separator|>
[15]
[PDF] Toda's theorem - real and complex - Purdue Math
Feb 15, 2010 · In order to develop an “algebraic” version of complexity theory ... k 6= VNP y k problem for k = R or C. Saugata Basu. Toda's theorem ...
[16]
On the Parallel Evaluation of Multivariate Polynomials - SIAM.org
3. Laurent Hyafil, The power of commutativity, 18th Annual Symposium on ... Constant-Depth Arithmetic Circuits for Linear Algebra Problems. 2024 IEEE ...
[17]
Fast Parallel Computation of Polynomials Using Few Processors
It is shown that any multivariate polynomial of degree d that can be computed sequentially in C steps can be computed in parallel in $O((\log d)(\log C + ...
[18]
On computing the determinant in small parallel time using a small ...
30 March 1984, Pages 147-150. Information Processing Letters. On computing the determinant in small parallel time using a small number of processors. Author ...
[19]
[PDF] On the power of homogeneous depth 4 arithmetic circuits
n log n) on the size of homogeneous depth 4 circuits computing a polynomial ... Arithmetic Circuits: An arithmetic circuit over a field F and a set of ...
[20]
Notes on Monotone Arithmetic Circuits
The proofs of most known lower bounds on the size of monotone arithmetic (+,×) circuits ignore the actual values of their coefficients, and only rely on the ...
[21]
Monotone Circuit Lower Bounds from Robust Sunflowers - PMC - NIH
A real arithmetic circuit is said to be monotone if it uses only positive numbers as coefficients. A polynomial P is said to be multilinear if the degree of ...
[22]
Monotone Arithmetic Circuit Lower Bounds Via Communication ...
Feb 15, 2021 · Valiant (1980) showed that general arithmetic circuits with negation can be exponentially more powerful than monotone ones.<|separator|>
[23]
[PDF] QUADRATIC LOWER BOUND FOR PERMANENT VS ...
Feb 24, 2010 · Jerrum & Snir (1982) showed that any monotone arithmetic circuit family that computes permanent must have exponential size. For depth-three ...
[24]
Lower bounds for monotone counting circuits - ScienceDirect.com
Nov 20, 2016 · As observed by Jerrum and Snir [10], every ( + , × ) circuit producing a polynomial f can be easily transformed into a circuit producing f le or ...
[25]
[PDF] Monotone Circuit Complexity of Matching - arXiv
Jul 23, 2025 · The perfect matching function on n-vertex graphs requires monotone circuits of size at least 2nΩ(1), improving on the previous nΩ(log n) bound.
[26]
Some Recent Advancements in Monotone Circuit Complexity ...
Feb 24, 2025 · Monotone circuits for connectivity require super-logarithmic depth. ... Lower bounds for the monotone complexity of some Boolean functions.
[27]
[PDF] Monotone Circuit Size, Matrix Rigidity, and Tensor Rank Under ...
Apr 4, 2025 · Our first result shows how to get 2Ω(n/ log n) monotone circuit lower bounds (improving best known bounds of the form 2Ω(√n)) under an ...Missing: powers | Show results with:powers