This work continues the development of hardness magnification. The latter proposes a strategy for showing strong complexity lower bounds by reducing them to a refined analysis of weaker models, where combinatorial techniques might be successful.

We consider gap versions of the meta-computational problems MKtP and MCSP, where one needs to distinguish instances (strings or truth-tables) of complexity s 1 ( N ) from instances of complexity s 2 ( N ) , and N = 2 n denotes the input length. In MCSP, complexity is measured by circuit size, while in MKtP one considers Levin's notion of time-bounded Kolmogorov complexity. (In our results, the parameters s 1 ( N ) and s 2 ( N ) are asymptotically quite close, and the problems almost coincide with their standard formulations without a gap.) We establish that for Gap-MKtP [ s 1 s 2 ] and Gap-MCSP [ s 1 s 2 ] , a marginal improvement over the state-of-the-art in unconditional lower bounds in a variety of computational models would imply explicit super-polynomial lower bounds.

Theorem. There exists a universal constant c 1 for which the following hold. If there exists 0"> 0 such that for every small enough 0"> 0

1. Gap-MCSP [ 2 n cn 2 n ] Circuit [ N 1+ ] , then NP is not contained in Circuit[poly]. 2. Gap-MKtP [ 2 n 2 n + c n ] TC 0 [ N 1+ ] , then EXP is not contained in TC 0 [poly]. 3. Gap-MKtP [ 2 n 2 n + c n ] B 2 -Formula [ N 2+ ] , then EXP is not contained in Formula[poly]. 4. Gap-MKtP [ 2 n 2 n + c n ] U 2 -Formula [ N 3+ ] , then EXP is not contained in Formula[poly]. 5. Gap-MKtP [ 2 n 2 n + c n ] BP [ N 2+ ] , then EXP is not contained in BP[poly]. 6. Gap-MKtP [ 2 n 2 n + c n ] (AC 0 [6])[ N 1+ ] , then EXP is not contained in AC 0 [6] .

These results are complemented by lower bounds for Gap-MCSP and Gap-MKtP against different models. For instance, the lower bound assumed in (1) holds for U 2 -formulas of near-quadratic size, and lower bounds similar to (3)-(5) hold for various regimes of parameters.

Going beyond the standard boolean devices, we identify a natural computational model under which the hardness magnification threshold for Gap-MKtP lies below existing lower bounds: U 2 -formulas that can compute parity functions at the leaves (instead of just literals). As a consequence, if one managed to adapt the existing lower bound techniques against such formulas to work with Gap-MKtP, then EXP is not contained in NC 1 would follow via hardness magnification.