@article{Miltersen_Variyam_Watanabe_1999, title={Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy}, volume={6}, url={https://tidsskrift.dk/brics/article/view/20116}, DOI={10.7146/brics.v6i46.20116}, abstractNote={Lower bounds on circuit size were previously established for functions<br /> in Sigma^p_2, ZPP^NP, Sigma^exp_2, ZPEXP^NP and MA_exp. We investigate<br />the general question: Given a time bound f(n). What is the best circuit<br /> size lower bound that can be shown for the classes MA-TIME[f],<br />ZP-TIME^NP[f], . . . using the techniques currently known? For the<br />classes MA_exp, ZPEXP^NP, and Sigma^exp_2 , the answer we get is <br />"half-exponential". Informally, a function f is said to be half-exponential if<br />f composed with itself is exponential}, number={46}, journal={BRICS Report Series}, author={Miltersen, Peter Bro and Variyam, Vinodchandran N. and Watanabe, Osamu}, year={1999}, month={Dec.} }