On the Existence of Algebraic Natural Proofs
- 7 August 2026
- journal article
- research article
- Published by Springer Nature in computational complexity
- Vol. 35 (2) , 7
Abstract
No abstract availableKeywords
This publication has 30 references indexed in Scilit:
- Unifying Known Lower Bounds via Geometric Complexity Theorycomputational complexity, 2015
- Über einige Anwendungen diophantischer Approximationen2014
- Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Boundscomputational complexity, 2004
- Natural ProofsJournal of Computer and System Sciences, 1997
- Lower bounds on the size of bounded depth circuits over a complete basis with logical additionMathematical Notes, 1987
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984
- Lower bounds for polynomials with algebraic coefficientsTheoretical Computer Science, 1980
- Probabilistic algorithms for sparse polynomials1979
- A probabilistic remark on algebraic program testingInformation Processing Letters, 1978
- Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von InterpolationskoeffizientenNumerische Mathematik, 1973