Efficient Construction of Rigid Matrices Using an NP Oracle

Josh Alman
If H is a matrix over a field F, then the rank-r rigidity of H, denoted R_{H}(r), is the minimum Hamming distance from H to a matrix of rank at most r over F. Giving explicit constructions of rigid matrices for a variety of parameter regimes is a central open challenge in complexity theory. In this work, building on Williams' seminal connection between circuit-analysis algorithms and lower bounds [Williams, J. ACM 2014], we give a...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.