Hardness Magnification

The recent surprising phenomenon of hardness magnification (HM in short) (similar phenomenon was known before, but the interest in them has been revived since [Oliveira-Santhanam’18]) shows that innocent-looking weak circuit lower bounds for specific problems such as MCSP (the Minimum Circuit Size Problem, given a truth-table of a Boolean function and asks what the minimum size of a circuit computing it is) can imply major circuit lower bounds such as NP not in P/poly. For example, if a sparse variant of MCSP does not have \(n \cdot \mathrm{polylog}(n)\) size circuit, then \(\mathsf{NP} \ne \mathsf{P}\) ([McKay-Murray-Williams’19]).

Several of my past papers ([Chen-McKay-Murray-Williams’19], [Chen-Jin-Williams’19], [Chen-Jin-Williams’20], [Chen-Hirahara-Oliveira-Pich-Rajgopal-Santhanam’20], [Chen-Tell’19]) aimed to better understand this phenomenon and are summarized below.

1. What properties of sparse-MCSP enabled such a hardness magnification phenomenon?

• In [Chen-McKay-Murray-Williams’19] and [Chen-Jin-Williams’19], we showed similar HM phenomenona for any \(\mathsf{NP}\) language that is equally sparse as the sparse variants of MCSP studied by previous work. Our results suggest that perhaps the most important properties of these specific problems studied by previous paper on HM are their sparsity.

2. How close are we to use HM theorems to prove new lower bounds?

• To derive breakthrough circuit lower bounds, most previous work on HM requires to prove either super cubic De Morgan formula lower bounds for sparse-MCSP, for which the best known lower bound is quadratic, or an \(n \cdot \mathrm{polylog}(n)\) size circuit lower bound for sparse-MCSP, which seems very hard given the current techniques based on gate elimination.

• In [Chen-Jin-Williams’20], we established several sharp thresholds for HM theorems. For example, we showed that sparse-MCSP cannot be computed by sub-quadratic size randomized De Morgan formulas while improving that to slightly super-quadratic would imply breakthrough lower bounds such as \(\mathsf{PSPACE} \not\subset \mathsf{NC}^1\).

3. What prevents us from proving lower bounds required by the hardness magnification (HM) theorems?

• The natural proof barrier does not seem to apply here since HM theorems only work for special functions (i.e., it avoids the largeness of natural properties). So one natural question stemmed from the hardness magnification phenomenon is to understand whether there is another inherent barrier, which prevents us from using current techniques to prove the lower bounds required by HM theorems.

• In [Chen-Hirahara-Oliveira-Pich-Rajgopal-Santhanam’20], we formulated a concrete barrier called Locality barrier. Roughly speaking, the locality barrier says that if your lower-bound methods are robust enough to handle small-fan-in oracles, then it cannot be used to prove the lower bounds required by most HM theorems. Unfortunately, most lower-bound techniques that we are aware of (random restrictions, approximation method, communication complexity, etc.) are subject to this barrier.

• It is worth mentioning that there are subsequent work [Pich’20] and [Hirahara’20] proving new HM theorems that bypass the locality barrier. It is an interesting question to understand whether these new HM theorems can lead to breakthrough circuit lower bounds, or some different barriers still prevent us from applying them.

4. How close are we to prove super-polynomial \(\mathsf{TC}^{0}\) Lower Bounds?

• One frontier question in circuit complexity is to prove super-polynomial lower bounds against \(\mathsf{TC}^0\) circuits (constant-depth circuits consist entirely of majority gates). \(n^{1+1/\exp(d)}\)-size lower bounds are known for a certain \(\mathsf{NC}^1\)-complete problem \(P_{\mathsf{NC}^1}\) against depth-\(d\) \(\mathsf{TC}^0\) circuits [Impagliazzo-Paturi-Saks’97]. [Allender-Koucký’10] proved that for \(P_{\mathsf{NC}^1}\), if one can show \(n^{1+1/d}\)-size lower bounds against depth-\(d\) \(\mathsf{TC}^0\) circuits, then \(\mathsf{NC}^1 \ne \mathsf{TC}^0\).

• In [Chen-Tell’19], we showed that any \(n^{1+1/\exp(o(d))}\)-size lower bound for \(P_{\mathsf{NC}^1}\) against depth-\(d\) \(\mathsf{TC}^0\) circuits would already imply \(\mathsf{NC}^1 \ne \mathsf{TC}^0\). That is, qualitatively we are very close to the threshold between barely-super-linear hardness and super-polynomial hardness against \(\mathsf{TC}^0\).