Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits.

An Algebraic Circuit for a multivariate polynomial P is a computational model for constructing the polynomial P using only additions and multiplications. It is a syntactic model of computation, as opposed to the Boolean Circuit model, and hence lower bounds for this model are widely expected to be e...

Full description

Bibliographic Details

Published in:	Communications of the ACM Vol. 67; no. 2; pp. 101 - 109
Main Authors:	Limaye, Nutan, Srinivasan, Srikanth, Tavenas, Sébastien
Format:	Article
Published:	Association for Computing Machinery Feb2024
Subjects:	Algebra Polynomials Circuit complexity Algorithms Directed acyclic graphs Logic circuits
Online Access:	View this record in EBSCOhost