7 min read
On this page

Algebraic Complexity Theory

Arithmetic Circuits

An arithmetic circuit over a field F computes a polynomial in F[x_1, ..., x_n]. Nodes are:

  • Input gates: Variables x_i or field constants
  • Addition gates: Sum of children (with field-element edge labels for linear combinations)
  • Multiplication gates: Product of children

Size: Number of gates. Depth: Longest path from input to output. Degree: Degree of the computed polynomial.

An arithmetic formula is a circuit where every gate has fan-out at most 1 (equivalently, the underlying graph is a tree).

VP and VNP

Valiant (1979) defined algebraic analogs of P and NP:

VP (Valiant's P): Families of polynomials {f_n} where f_n has poly(n) degree and is computed by arithmetic circuits of poly(n) size.

VNP (Valiant's NP): Families {f_n} where f_n(x_1,...,x_n) = sum over e in {0,1}^{m(n)} of g_n(x_1,...,x_n, e_1,...,e_{m(n)}) where g_n is in VP and m(n) = poly(n).

The summation over exponentially many terms (the "existential quantifier" of algebraic complexity) mirrors the nondeterministic computation of NP.

Determinant vs Permanent

The determinant of an n x n matrix A: det(A) = sum over sigma in S_n of sgn(sigma) * product of A[i, sigma(i)]

The permanent of an n x n matrix A: perm(A) = sum over sigma in S_n of product of A[i, sigma(i)]

Despite their syntactic similarity (differing only in the sign), their computational complexities are vastly different:

  • Determinant is in VP: computable by O(n^3) arithmetic operations (Gaussian elimination), or by circuits of poly(n) size and O(log^2 n) depth.
  • Permanent is VNP-complete (Valiant, 1979): the hardest problem in VNP under polynomial projections.

Valiant's Conjecture

Conjecture: VP != VNP. Equivalently, the permanent of an n x n matrix cannot be computed as the determinant of a poly(n) x poly(n) matrix.

This is the algebraic analog of P != NP. Over finite fields, the permanent is #P-complete (Valiant, 1979). Over the rationals, VP != VNP would imply (a strong form of) P != NP.

Best known: The permanent requires determinants of size 2^{Omega(sqrt{n})} (Mignon-Ressayre over characteristic != 2, strengthened by Cai-Chen-Li).

Lower Bounds

General Arithmetic Circuits

Baur-Strassen (1983): Any arithmetic circuit computing a degree-d polynomial in n variables requires Omega(n log d) size. This gives Omega(n log n) for the polynomial x_1^n + ... + x_n^n.

This is essentially the best known general lower bound -- proving omega(n log n) for an explicit polynomial would be a breakthrough.

Arithmetic Formulas

Kalorkoti (1985): The determinant requires arithmetic formulas of size Omega(n^3).

Nisan (1991): Over non-commutative computation, the permanent requires formulas of exponential size. (This does not transfer to the commutative setting.)

Depth Reduction

Theorem (Valiant-Skyum-Berkowitz-Rackoff, 1983): Any poly(n)-size arithmetic circuit of poly(n) degree can be converted to depth O(log n log(degree)) with polynomial size increase.

Theorem (Agrawal-Vinay, 2008; Koiran, 2012; Tavenas, 2013): Any poly(n)-size arithmetic circuit computing a degree-d polynomial can be converted to a depth-4 circuit (Sigma-Pi-Sigma-Pi) of size 2^{O(sqrt{d} log n)}.

Consequence: Proving a 2^{omega(sqrt{n})} lower bound for depth-4 circuits computing an explicit polynomial would imply VP != VNP. This is the depth-4 barrier and the current frontier for algebraic lower bounds.

Restricted Models

Significant lower bounds exist for restricted circuit classes:

  • Monotone circuits: The permanent requires 2^{Omega(n)} size over monotone arithmetic circuits
  • Homogeneous depth-4 circuits: Superpolynomial lower bounds for the iterated matrix multiplication polynomial (Kayal-Limaye-Saha-Srinivasan, 2014; Kumar-Saraf, 2017)
  • Constant-depth multilinear circuits: Exponential lower bounds (Raz-Yehudayoff, 2009)
  • Non-commutative circuits: Exponential lower bounds (Nisan, 1991)

Polynomial Identity Testing (PIT)

PIT problem: Given an arithmetic circuit C, determine whether C computes the identically zero polynomial.

Randomized PIT: Schwartz-Zippel

Lemma (Schwartz, 1980; Zippel, 1979): If f is a nonzero polynomial of degree d over field F, and S is a subset of F, then Pr_{r in S^n}[f(r) = 0] <= d/|S|.

This gives an efficient randomized algorithm: evaluate C at a random point. If C is zero, it always evaluates to 0; if not, it evaluates to nonzero with high probability. PIT is in coRP.

Deterministic PIT: Open Problem

Derandomizing PIT (making it deterministic in polynomial time) is a major open problem. Its resolution is deeply connected to circuit lower bounds.

Theorem (Kabanets-Impagliazzo, 2004): If PIT is in P (deterministically), then either:

  • NEXP does not have polynomial-size arithmetic circuits, OR
  • The permanent cannot be computed by polynomial-size arithmetic circuits

Thus, derandomizing PIT implies proving circuit lower bounds. Conversely, strong enough circuit lower bounds yield PIT derandomization (via Nisan-Wigderson generators).

Hitting Set Generators

A hitting set generator for degree-d, size-s circuits maps a seed of length polylog(s, d, n) to n field elements such that any nonzero polynomial computed by such a circuit is nonzero on at least one image point.

Constructing explicit hitting set generators for general circuits would derandomize PIT. Known constructions exist for restricted models:

  • Read-once oblivious branching programs (Nisan, 1992)
  • Depth-3 diagonal circuits (Saxena-Seshadhri, 2012)
  • Sparse polynomials (Klivans-Spielman, 2001)

Tensor Rank and Matrix Multiplication

Tensor Rank

A 3-dimensional tensor T in F^{a x b x c} has rank r if r is the minimum number of rank-1 tensors (outer products u tensor v tensor w) summing to T.

Connection to bilinear complexity: The number of multiplications needed to compute a bilinear map (like matrix multiplication) equals the rank of the corresponding tensor.

Matrix Multiplication Exponent

The exponent of matrix multiplication omega is defined as: omega = inf{tau : two n x n matrices can be multiplied using O(n^tau) arithmetic operations}

Known bounds: 2 <= omega < 2.372 (current best: omega < 2.3719, by Duan-Wu-Zhou, 2023, using the laser method and combinatorial bounds).

Key milestones:

  • Strassen (1969): omega < 2.808 (the 2x2 case uses 7 multiplications instead of 8)
  • Pan (1980): omega < 2.796
  • Coppersmith-Winograd (1990): omega < 2.376
  • Le Gall (2014): omega < 2.3729
  • Alman-Vassilevska Williams (2021): omega < 2.3728

Conjecture: omega = 2 (matrix multiplication can be done in essentially quadratic time). Evidence: the "group-theoretic approach" (Cohn-Umans) constructs fast algorithms from groups with specific properties.

The Laser Method

Strassen's laser method (1986), refined by Coppersmith-Winograd, works by:

  1. Start with a small base tensor T (e.g., Coppersmith-Winograd tensor)
  2. Take large tensor powers T^{tensor k}
  3. Extract a "useful" sub-tensor corresponding to matrix multiplication
  4. Optimize the extraction using asymptotic rank analysis

The method has inherent limitations: it cannot prove omega = 2 using the Coppersmith-Winograd tensor family (Ambainis-Filmus-Le Gall, 2015).

Algebraic Complexity Classes

| Class | Description | Key Members | |---|---|---| | VP | Poly-size circuits, poly-degree | Determinant, symmetric functions | | VNP | Exponential sum over VP | Permanent, Hamiltonian cycle polynomial | | VBP | Poly-size branching programs (ABPs) | Determinant, iterated matrix mult | | VF | Poly-size formulas | Smaller than VP (depth O(log n)) | | VP_e | VP without degree bound | May differ from VP |

Containments: VF is in VBP is in VP is in VNP. The first two separations are known over sufficiently large fields. VP vs VNP is open (Valiant's conjecture).

The Permanent and Counting

Theorem (Valiant, 1979): Computing the permanent over GF(2) is #P-complete (counts perfect matchings in bipartite graphs).

Theorem (Toda, 1991): PH is contained in P^{#P}. Thus the permanent (via #P) is at least as hard as the polynomial hierarchy.

Ryser's formula: perm(A) = (-1)^n * sum over S of (-1)^{|S|} * product over i of sum over j in S of a_{ij}. This gives an O(2^n * n) algorithm, better than the naive O(n! * n).

GCT: Geometric Complexity Theory

Mulmuley and Sohoni (2001) proposed using algebraic geometry and representation theory to prove VP != VNP.

Key idea: The determinant and permanent define orbits under group actions (GL_n acting on polynomials). Separating VP from VNP reduces to showing that certain orbit closures are distinct, which can be established by finding obstructions -- representation-theoretic objects (specific highest-weight vectors) present in one orbit closure but not the other.

Status: GCT is a long-term program. While it has produced deep mathematics, it has not yet yielded new complexity separations. A key barrier: the required obstructions may not exist in the "easiest" cases (Burgisser-Ikenmeyer-Panova, 2019).

Open Problems

  • VP vs VNP (Valiant's conjecture) -- the central question
  • Is omega = 2? What is the exact value of omega?
  • Deterministic PIT in polynomial time
  • Prove superpolynomial lower bounds for general arithmetic circuits (for explicit polynomials)
  • Does depth-4 circuit lower bound approach lead to VP != VNP?
  • Can GCT provide concrete lower bounds?
  • What is the formula complexity of the determinant? (Known: Omega(n^3) and O(n^{O(log n)}))