"Non UBC"@en .
"DSpace"@en .
"Neeraj Kayal"@en .
"2020-01-09T09:41:47Z"@en .
"2019-07-12T09:52"@en .
"What is the smallest formula computing a given multivariate polynomial f(x)=\n In this talk I will present a paradigm for translating the known lower\nbound proofs for various subclasses of formulas into efficient proper learn=\ning algorithms for the same subclass.\n\nMany lower bounds proofs for various subclasses of arithmetic formulas redu=\nce the problem to showing that any expression for f(x) as a sum of =93simpl=\ne=94 polynomials T_i(x):\n f(x) =3D T_1(x) + T_2(x) + =85 + T_s(x),\nthe number s of simple summands is large. For example, each simple summand =\nT_i could be a product of linear forms or a power of a low degree polynomia=\nl and so on.\nThe lower bound consists of constructing a vector space of linear maps M, e=\nach L in M being a linear map from the set of polynomials F[x] to some vect=\nor space W\n(typically W is F[X] itself) with the following two properties:\n\n(i) For every simple polynomial T, dim(M*T) is small, say =\nthat dim(M*T) <=3D r.\n\n(ii) For the candidate hard polynomial f, dim(M*f) is large,=\n say that dim(M*f) >=3D R.\nThese two properties immediately imply a lower bound: s >=3D R/r.\n\nThe corresponding reconstruction/proper learning problem is the following: =\ngiven f(x) we want to find the simple summands T_1(x), T_2(x), =85, T_s(x) =\nwhich add up to f(x).\nWe will see how such a lower bound proof can often be used to solve the rec=\nonstruction problem. Our main tool will be an efficient algorithmic solutio=\nn\nto the problem of decomposing a pair of vector spaces (U, V) under the simu=\nltaneous action of a vector space of linear maps from U to V.\n\nAlong the way we will also obtain very precise bounds on the size of formul=\nas computing certain explicit polynomials. For example, we will obtain for =\nevery s, an explicit\npolynomial f(x) that can be computed by a depth three formula of size s but=\n not by any depth three formula of size (s-1).\n\nBased on joint works with Chandan Saha and Ankit Garg."@en .
"https://circle.library.ubc.ca/rest/handle/2429/73237?expand=metadata"@en .
"56.0 minutes"@en .
"video/mp4"@en .
""@en .
"Author affiliation: MSR India"@en .
"Banff (Alta.)"@en .
"10.14288/1.0388215"@en .
"eng"@en .
"Unreviewed"@en .
"Vancouver : University of British Columbia Library"@en .
"Banff International Research Station for Mathematical Innovation and Discovery"@en .
"Attribution-NonCommercial-NoDerivatives 4.0 International"@en .
"http://creativecommons.org/licenses/by-nc-nd/4.0/"@en .
"Faculty"@en .
"BIRS Workshop Lecture Videos (Banff, Alta)"@en .
"Mathematics"@en .
"Computer Science, Theoretical Computer Science"@en .
"Reconstructing arithmetic formulas using lower bound proof techniques"@en .
"Moving Image"@en .
"http://hdl.handle.net/2429/73237"@en .