Efficient Construction of Rigid Matrices Using an NP Oracle

For a matrix H over a field IF, 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 delta > 0 such that, for all constants epsilon > 0, there is a P-NP machine M such that, for infinitely many N's, M(1(N)) outputs a matrix H-N is an element of {0, 1}(NxN) with R-HN (2(log N)(1/4-epsilon)) >= delta . 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 is an element of TIME[2((log n)omega(1))](NP) such that f is not an element of PHcc. Previously, it was open whether E-NP subset of PHcc. For all epsilon > 0, there is a P-NP machine M such that, for infinitely many N's, M(1(N)) outputs an N x N matrix H-N is an element of {0, 1}(NxN) whose linear transformation requires depth-2 F-q-linear circuits of size Omega(N . 2((log N)1/4-epsilon)). The previous best lower bound for an explicit family of N x N matrices over F-q was only Omega(N log(2) N/(log log N)(2)), for asymptotically good error-correcting codes.