Effect of operators on straight line complexity
Authors: D. Boneh and R. Lipton
Abstract:
We show that certain explicit operators must vastly increase
the straight line complexity of certain polynomials.
Reference:
In proceedings of ISTCS, Ramat-Gan, Israel, 1997
Full paper: gzipped-PostScript [first posted 3/1997 ]