IEEE - Institute of Electrical and Electronics Engineers, Inc. - Polynomials with 0-1 coefficients that are hard to evaluate

16th Annual Symposium on Foundations of Computer Science (sfcs 1975)

Author(s): Lipton, Richard J.
Publisher: IEEE - Institute of Electrical and Electronics Engineers, Inc.
Publication Date: 1 October 1975
Conference Location: USA, USA
Conference Date: 13 October 1975
Page(s): 6 - 10
ISSN (Paper): 0272-5428
DOI: 10.1109/SFCS.1975.25
Regular:

We show the existence of polynomials with 0-1 coefficients that are hard to evaluate even when arbitrary preconditioning is allowed. Further we show that there are power series with 0-1... View More

Advertisement