Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma

In this work we prove that there is a function f ∈ E NP such that, for every sufficiently large n and d = √ n/ log n, f n ( f restricted to n-bit inputs) cannot be (1/2 + 2 -d )-approximated by F 2 -polynomials of degree d. We also observe that a minor improvement (e.g., improving d to n 1/2+ε for any ε > 0) over our result will imply E NP cannot be computed by depth-3 AC 0 -circuits of 2 n 1/2+ε size, which is a notoriously hard open question in complexity theory.

Using the same proof techniques, we are also able to construct extremely rigid matrices over F 2 in P NP . More specifically, we show that for every constant ε ∈ (0, 1), there is a

• n 2 , for every sufficiently large n. This improves the recent P NP constructions of rigid matrices in [Alman and Chen, FOCS 2019] and [Bhangale et al., FOCS 2020], which only gives Ω(n 2 ) rigidity.

The key ingredient in the proof of our new results is a new derandomized XOR lemma based on approximate linear sums, which roughly says that given an n-input function f which cannot be 0.99-approximated by certain linear sum of s many functions in F within ℓ 1 -distance, one can construct a new function Amp f with O(n) input bits, which cannot be (1/2 + s Ω(1) )approximated by F -functions. Taking F to be a function collection containing low-degree F 2 -polynomials or low-rank F 2 -matrices, our results are then obtained by first using the algorithmic method to construct a function which is weakly hard against linear sums of F in the above sense, and then apply the derandomized XOR lemma to f . We obtain our new derandomized XOR lemma by giving a generalization of the famous hardcore lemma by Impagliazzo. Our generalization in some sense constructs a non-Boolean hardcore of a weakly hard function f with respect to F -functions, from the weak inapproximability of f by any linear sum of F with bounded ℓ p -norm. This generalization recovers the original hardcore lemma by considering the ℓ ∞ -norm. Surprisingly, when we switch to the ℓ 1 -norm, we immediately rediscover Levin's proof of Yao's XOR Lemma. That is, these first two proofs of Yao's XOR Lemma can be unified with our new perspective. For proving the correlation bounds, our new derandomized XOR lemma indeed works with the ℓ 4/3 -norm.