- 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 (s-1). 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 |
2019-07-12T09: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 (s-1).
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 |
2020-01-09
|
| Provider |
Vancouver : University of British Columbia Library
|
| Rights |
Attribution-NonCommercial-NoDerivatives 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
Attribution-NonCommercial-NoDerivatives 4.0 International