Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > HOMOGENEOUS FORMULAS:
Reports tagged with Homogeneous formulas:
TR23-191 | 2nd December 2023
Hervé Fournier, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

On the Power of Homogeneous Algebraic Formulas

Proving explicit lower bounds on the size of algebraic formulas is a long-standing open problem in the area of algebraic complexity theory. Recent results in the area (e.g. a lower bound against constant-depth algebraic formulas due to Limaye, Srinivasan, and Tavenas (FOCS 2021)) have indicated a way forward for attacking ... more >>>




ISSN 1433-8092 | Imprint