Symmetric Exponential Time Requires Near-Maximum Circuit Size

We show that there is a language in S2E/1 (symmetric exponential time with one bit of advice) with circuit complexity at least 2n/n. In particular, the above also implies the same near-maximum circuit lower bounds for the classes Σ2E, (Σ2E∩Π2E)/1, and ZPENP/1. Previously, only ”half-exponential” circuit lower bounds for these complexity classes were known, and the smallest complexity class known to require exponential circuit complexity was Δ3E = EΣ2P (Miltersen, Vinodchandran, and Watanabe COCOON’99).