Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Algebraic natural proofs:
TR18-064 | 3rd April 2018
Markus Bläser, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov

Generalized Matrix Completion and Algebraic Natural Proofs

Algebraic natural proofs were recently introduced by Forbes, Shpilka and Volk (Proc. of the 49th Annual {ACM} {SIGACT} Symposium on Theory of Computing (STOC), pages {653--664}, 2017) and independently by Grochow, Kumar, Saks and Saraf~(CoRR, abs/1701.01717, 2017) as an attempt to transfer Razborov and Rudich's famous barrier result (J. Comput. ... more >>>

TR23-135 | 14th September 2023
Prerona Chatterjee, Anamay Tengse

On Annihilators of Explicit Polynomial Maps

We study the algebraic complexity of annihilators of polynomials maps. In particular, when a polynomial map is `encoded by' a small algebraic circuit, we show that the coefficients of an annihilator of the map can be computed in PSPACE. Even when the underlying field is that of reals or complex ... more >>>

ISSN 1433-8092 | Imprint