@prefix vivo: .
@prefix edm: .
@prefix dcterms: .
@prefix dc: .
@prefix skos: .
@prefix ns0: .
vivo:departmentOrSchool "Non UBC"@en ;
edm:dataProvider "DSpace"@en ;
dcterms:creator "Josh Alman"@en ;
dcterms:issued "2020-01-06T09:39:23Z"@en, "2019-07-09T13:32"@en ;
dcterms:description """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 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 depth-2 F_q-linear 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 super-concentrator graphs.
Joint work with Lijie Chen to appear in FOCS 2019."""@en ;
edm:aggregatedCHO "https://circle.library.ubc.ca/rest/handle/2429/73137?expand=metadata"@en ;
dcterms:extent "51.0 minutes"@en ;
dc:format "video/mp4"@en ;
skos:note ""@en, "Author affiliation: MIT"@en ;
dcterms:spatial "Banff (Alta.)"@en ;
edm:isShownAt "10.14288/1.0387498"@en ;
dcterms:language "eng"@en ;
ns0:peerReviewStatus "Unreviewed"@en ;
edm:provider "Vancouver : University of British Columbia Library"@en ;
dcterms:publisher "Banff International Research Station for Mathematical Innovation and Discovery"@en ;
dcterms:rights "Attribution-NonCommercial-NoDerivatives 4.0 International"@en ;
ns0:rightsURI "http://creativecommons.org/licenses/by-nc-nd/4.0/"@en ;
ns0:scholarLevel "Graduate"@en ;
dcterms:isPartOf "BIRS Workshop Lecture Videos (Banff, Alta)"@en ;
dcterms:subject "Mathematics"@en, "Computer Science, Theoretical Computer Science"@en ;
dcterms:title "Efficient Construction of Rigid Matrices Using an NP Oracle"@en ;
dcterms:type "Moving Image"@en ;
ns0:identifierURI "http://hdl.handle.net/2429/73137"@en .