Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Defining Equations:
TR20-063 | 29th April 2020
Prerona Chatterjee, Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse

On the Existence of Algebraically Natural Proofs

Revisions: 1

For every constant c > 0, we show that there is a family {P_{N,c}} of polynomials whose degree and algebraic circuit complexity are polynomially bounded in the number of variables, and that satisfies the following properties:
* For every family {f_n} of polynomials in VP, where f_n is an n ... more >>>

ISSN 1433-8092 | Imprint