 Library Home /
 Search Collections /
 Open Collections /
 Browse Collections /
 BIRS Workshop Lecture Videos /
 Efficient Construction of Rigid Matrices Using an NP...
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Efficient Construction of Rigid Matrices Using an NP Oracle Alman, Josh
Description
If H is a matrix over a field F, then the rankr 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 circuitanalysis 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 eps>0, there is a P^NP machine M such that, for infinitely many N's, M(1^N) outputs a matrix H_N in {0,1}^{N times N} with rigidity R_{H_N}(2^{(log N)^{1/4  eps}}) >= delta N^2 over F_q. Using known connections between matrix rigidity and a number of different areas of complexity theory, we derive several consequences of our constructions, including:  There is a function f in TIME[2^{(log n)^{omega(1)}}]^NP such that f notin PH^cc. Previously, it was even open whether E^NP subset PH^cc.  For all eps>0, there is a P^NP machine M such that, for infinitely many N's, M(1^N) outputs an N times N matrix H_N in {0,1}^{N times N} whose linear transformation requires depth2 F_qlinear circuits of size Omega(N 2^{(log N)^{1/4  eps}}). The previous best lower bound for an explicit family of N \times N matrices was only Omega(N log^2 N / log log N), for superconcentrator graphs. Joint work with Lijie Chen to appear in FOCS 2019.
Item Metadata
Title 
Efficient Construction of Rigid Matrices Using an NP Oracle

Creator  
Publisher 
Banff International Research Station for Mathematical Innovation and Discovery

Date Issued 
20190709T13:32

Description 
If H is a matrix over a field F, then the rankr 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 circuitanalysis 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 eps>0, there is a P^NP machine M such that, for infinitely many N's, M(1^N) outputs a matrix H_N in {0,1}^{N times N} with rigidity R_{H_N}(2^{(log N)^{1/4  eps}}) >= delta N^2 over F_q.
Using known connections between matrix rigidity and a number of different areas of complexity theory, we derive several consequences of our constructions, including:
 There is a function f in TIME[2^{(log n)^{omega(1)}}]^NP such that f notin PH^cc. Previously, it was even open whether E^NP subset PH^cc.
 For all eps>0, there is a P^NP machine M such that, for infinitely many N's, M(1^N) outputs an N times N matrix H_N in {0,1}^{N times N} whose linear transformation requires depth2 F_qlinear circuits of size Omega(N 2^{(log N)^{1/4  eps}}). The previous best lower bound for an explicit family of N \times N matrices was only Omega(N log^2 N / log log N), for superconcentrator graphs.
Joint work with Lijie Chen to appear in FOCS 2019.

Extent 
51.0 minutes

Subject  
Type  
File Format 
video/mp4

Language 
eng

Notes 
Author affiliation: MIT

Series  
Date Available 
20200106

Provider 
Vancouver : University of British Columbia Library

Rights 
AttributionNonCommercialNoDerivatives 4.0 International

DOI 
10.14288/1.0387498

URI  
Affiliation  
Peer Review Status 
Unreviewed

Scholarly Level 
Graduate

Rights URI  
Aggregated Source Repository 
DSpace

Item Media
Item Citations and Data
Rights
AttributionNonCommercialNoDerivatives 4.0 International