Algebraic Complexity Classes

In this section we will thoroughly discuss the definitions of the main complexity classes in algebraic complexity theory, their connections to other problems in computer science and mathematics, and some of their applications.

General Definitions

VP

VNP

VNC

VBP

Restricted Circuit Classes

Depth 2

Depth 3

Waring Rank (or diagonal depth 3)

This class of circuits, denoted by $\Sigma \wedge \Sigma$ is the class of circuits computing polynomials of the form $$f = \sum_{i=1}^s \ell_i^d$$ where the $\ell_i$ are linear forms. The size of the circuit is the number of linear forms $s$.

If $f$ is a polynomial in $n$ variables of degree $d$, which can be computed by a circuit of size $s$, we say $f \in \Sigma \wedge \Sigma(n, d, s)$.

Bounded Top Fan-in

Theorem [DS'22]: $\overline{\Sigma^{[k]} \Pi \Sigma}(\mathrm{poly}(n)) \subset \textrm{VP}$.

Is the above also true for the closure of depth 4 circuits with bounded top fanin?

Depth 4

References

[DS'22]: Dutta, P., Saxena, N. (2022). Separated borders: exponential-gap fanin-hierarchy theorem for approximative depth-3 circuits.