We establish several ``sharp threshold'' results for computational complexity. For certain tasks, we can prove a resource lower bound of n^c for c \geq 1 (or obtain an efficient circuit-analysis algorithm for n^c size), there is strong intuition that a similar result can be proved for larger functions of n, yet we can also prove that replacing ``n^c'' with ``n^{c+\varepsilon}'' in our results, for any \varepsilon > 0, would imply a breakthrough n^{\omega(1)} lower bound.

We first establish such a result for Hardness Magnification. We prove (among other results) that for some c, the Minimum Circuit Size Problem for (\log n)^c-size circuits on length-n truth tables ({MCSP}[(\log n)^c]) does not have n^{2-o(1)}-size probabilistic formulas. We also prove that an n^{2+\varepsilon} lower bound for {MCSP}[(\log n)^c] (for any \varepsilon > 0 and c \geq 1) would imply major lower bound results, such as {NP} does not have n^k-size formulas for all k, and \#{SAT} does not have log-depth circuits.
Similar results hold for time-bounded Kolmogorov complexity. Note that cubic size lower bounds are known for probabilistic De Morgan formulas (for other functions).

Next we show a sharp threshold for Quantified Derandomization (QD) of probabilistic formulas.
(1) For all \alpha, \varepsilon > 0, there is a deterministic polynomial-time algorithm that finds satisfying assignments to every probabilistic formula of n^{2-2\alpha-\varepsilon} size with at most 2^{n^{\alpha}} falsifying assignments.
(2) If for some \alpha, \varepsilon > 0, there is such an algorithm for probabilistic formulas of n^{2-\alpha+\varepsilon}-size and 2^{n^{\alpha}} unsatisfying assignments, then a full derandomization of {NC}^1 follows: a deterministic poly-time algorithm additively approximating the acceptance probability of any polynomial-size formula. Consequently, {NP} does not have n^k-size formulas, for all k.

Finally we show a sharp threshold result for Explicit Obstructions, inspired by Mulmuley's notion of explicit obstructions from GCT. An explicit obstruction against S(n)-size formulas is a poly-time algorithm A such that A(1^n) outputs a list \{(x_i,f(x_i))\}_{i \in [\mathrm{poly}(n)]} \subseteq \{0,1\}^n \times \{0,1\}, and every S(n)-size formula F is inconsistent with the (partially defined) function f. We prove that for all \varepsilon > 0, there is an explicit obstruction against n^{2-\varepsilon}-size formulas, and prove that there is an explicit obstruction against n^{2+\varepsilon}-size formulas for some \varepsilon > 0 if and only if there is an explicit obstruction against all polynomial-size formulas. This in turn is equivalent to the statement that {E} does not have 2^{o(n)}-size formulas, a breakthrough in circuit complexity.