@prefix vivo: .
@prefix edm: .
@prefix dcterms: .
@prefix dc: .
@prefix skos: .
@prefix ns0: .
vivo:departmentOrSchool "Non UBC"@en ;
edm:dataProvider "DSpace"@en ;
dcterms:creator "Neeraj Kayal"@en ;
dcterms:issued "2020-01-09T09:41:47Z"@en, "2019-07-12T09:52"@en ;
dcterms:description """What is the smallest formula computing a given multivariate polynomial f(x)=
In this talk I will present a paradigm for translating the known lower
bound proofs for various subclasses of formulas into efficient proper learn=
ing algorithms for the same subclass.
Many lower bounds proofs for various subclasses of arithmetic formulas redu=
ce the problem to showing that any expression for f(x) as a sum of =93simpl=
e=94 polynomials T_i(x):
f(x) =3D T_1(x) + T_2(x) + =85 + T_s(x),
the number s of simple summands is large. For example, each simple summand =
T_i could be a product of linear forms or a power of a low degree polynomia=
l and so on.
The lower bound consists of constructing a vector space of linear maps M, e=
ach L in M being a linear map from the set of polynomials F[x] to some vect=
or space W
(typically W is F[X] itself) with the following two properties:
(i) For every simple polynomial T, dim(M*T) is small, say =
that dim(M*T) <=3D r.
(ii) For the candidate hard polynomial f, dim(M*f) is large,=
say that dim(M*f) >=3D R.
These two properties immediately imply a lower bound: s >=3D R/r.
The corresponding reconstruction/proper learning problem is the following: =
given f(x) we want to find the simple summands T_1(x), T_2(x), =85, T_s(x) =
which add up to f(x).
We will see how such a lower bound proof can often be used to solve the rec=
onstruction problem. Our main tool will be an efficient algorithmic solutio=
n
to the problem of decomposing a pair of vector spaces (U, V) under the simu=
ltaneous action of a vector space of linear maps from U to V.
Along the way we will also obtain very precise bounds on the size of formul=
as computing certain explicit polynomials. For example, we will obtain for =
every s, an explicit
polynomial f(x) that can be computed by a depth three formula of size s but=
not by any depth three formula of size (s-1).
Based on joint works with Chandan Saha and Ankit Garg."""@en ;
edm:aggregatedCHO "https://circle.library.ubc.ca/rest/handle/2429/73237?expand=metadata"@en ;
dcterms:extent "56.0 minutes"@en ;
dc:format "video/mp4"@en ;
skos:note ""@en, "Author affiliation: MSR India"@en ;
dcterms:spatial "Banff (Alta.)"@en ;
edm:isShownAt "10.14288/1.0388215"@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 "Faculty"@en ;
dcterms:isPartOf "BIRS Workshop Lecture Videos (Banff, Alta)"@en ;
dcterms:subject "Mathematics"@en, "Computer Science, Theoretical Computer Science"@en ;
dcterms:title "Reconstructing arithmetic formulas using lower bound proof techniques"@en ;
dcterms:type "Moving Image"@en ;
ns0:identifierURI "http://hdl.handle.net/2429/73237"@en .