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...

Descripción completa

Detalles Bibliográficos

Publicado en:	Communications of the ACM Vol. 67; no. 2; pp. 101 - 109
Autores principales:	Limaye, Nutan, Srinivasan, Srikanth, Tavenas, Sébastien
Formato:	Artículo
Publicado:	Association for Computing Machinery Feb2024
Materias:	Algebra Polynomials Circuit complexity Algorithms Directed acyclic graphs Logic circuits
Acceso en línea:	Ver este registro en EBSCOhost