Publications

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 ]