 Library Home /
 Search Collections /
 Open Collections /
 Browse Collections /
 BIRS Workshop Lecture Videos /
 Reconstructing arithmetic formulas using lower bound...
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Reconstructing arithmetic formulas using lower bound proof techniques Kayal, Neeraj
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 (s1). Based on joint works with Chandan Saha and Ankit Garg.
Item Metadata
Title 
Reconstructing arithmetic formulas using lower bound proof techniques

Creator  
Publisher 
Banff International Research Station for Mathematical Innovation and Discovery

Date Issued 
20190712T09:52

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 (s1).
Based on joint works with Chandan Saha and Ankit Garg.

Extent 
56.0 minutes

Subject  
Type  
File Format 
video/mp4

Language 
eng

Notes 
Author affiliation: MSR India

Series  
Date Available 
20200109

Provider 
Vancouver : University of British Columbia Library

Rights 
AttributionNonCommercialNoDerivatives 4.0 International

DOI 
10.14288/1.0388215

URI  
Affiliation  
Peer Review Status 
Unreviewed

Scholarly Level 
Faculty

Rights URI  
Aggregated Source Repository 
DSpace

Item Media
Item Citations and Data
Rights
AttributionNonCommercialNoDerivatives 4.0 International