Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy Peter Bro Miltersen Vinodchandran N. Variyam Osamu Watanabe December 1999

### Abstract:

Lower bounds on circuit size were previously established for functions in , , , and . We investigate the general question: Given a time bound . What is the best circuit size lower bound that can be shown for the classes , using the techniques currently known? For the classes , and , the answer we get is half-exponential''. Informally, a function is said to be half-exponential if composed with itself is exponential

Available as PostScript, PDF, DVI.