Title :
Effect of operators on straight line complexity
Author :
Boneh, Dan ; Lipton, Richard J.
Author_Institution :
Bellcore, USA
Abstract :
This paper concerns lower bounds on the straight line complexity of multi-variate polynomials. We obtain a conditional result showing that certain explicit linear operators must greatly increase the complexity of some polynomials. We do so by showing that if these operators roughly preserve the complexity of all polynomials then, co-NP is in AM. We show that certain explicit operators must vastly increase the straight line complexity of certain polynomials
Keywords :
computational complexity; polynomials; theorem proving; conditional result; explicit linear operators; lower bounds; multivariate polynomials; straight line complexity; Polynomials; Sampling methods;
Conference_Titel :
Theory of Computing and Systems, 1997., Proceedings of the Fifth Israeli Symposium on
Conference_Location :
Ramat-Gan
Print_ISBN :
0-8186-8037-7
DOI :
10.1109/ISTCS.1997.595151
