Efficient Construction of Rigid Matrices Using an NP Oracle

Abstract

For a matrix H over a field F, its rank-r rigidity, denoted R_H (r), is the minimum Hamming distance from H to a matrix of rank at most r over F. A central open challenge in complexity theory is to give explicit constructions of rigid matrices for a variety of parameter settings. In this work, building on Williams' seminal connection between circuit-analysis algorithms and lower bounds [Williams, J. ACM 2014], we give a construction of rigid matrices in P^NP. Letting q = p^r be a prime power, we show: • There is an absolute constant δ>0 such that, for all constants ε >0, there is a P^NP machine M such that, for infinitely many N's, M(1^N) outputs a matrix H_N ∊ {0,1}^N×N with R_H_N (2^ (log N)^ 1/4-ε) ≥ δ ⋅ N^2 over F_q. Using known connections between matrix rigidity and other topics in complexity theory, we derive several consequences of our constructions, including: • There is a function f ∊ TIME [2^ (log n)^ ω(1)]^ NP such that f ∉ PH^cc. Previously, it was open whether E^NP ⊂ PH^cc. • For all ε >0, there is a P^NP machine M such that, for infinitely many N's, M(1^N) outputs an N × N matrix H_N ∊ {0,1}^N×N whose linear transformation requires depth-2 F_q-linear circuits of size Ω(N ⋅ 2^ (log N)^ 1/4 - ε). The previous best lower bound for an explicit family of N × N matrices over F_q was only Ω(N log^2 N / (log log N)^2), for asymptotically good error-correcting codes.