Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > STRONG ALGEBRAS:
Reports tagged with strong algebras:
TR26-084 | 20th May 2026
Abhibhav Garg, Rafael Mendes de Oliveira, Akash Sengupta, Nir Shalmon, Amir Shpilka

Rank bounds and polynomial-time PIT for $\Sigma^k \Pi \Sigma \Pi^2$ circuits

A depth-4 algebraic circuit with top fan-in $k$ and bottom fan-in $2$ is a circuit $\Phi$ of the form $\Phi = \sum_{i=1}^k \prod_{j=1}^{m_i} Q_{ij}$, where the polynomials $Q_{ij} \in \mathbb{K}[x_1, \ldots, x_n]$ have degree at most $2$.
The class of all such circuits is denoted by $\Sigma^k \Pi \Sigma ... more >>>




ISSN 1433-8092 | Imprint