TY - ELEC
AU - Neeraj Kayal
PY - 2019
TI - Reconstructing arithmetic formulas using lower bound proof techniques
LA - eng
M3 - Moving Image
AB - 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.
N2 - 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.
UR - https://open.library.ubc.ca/collections/48630/items/1.0388215
ER - End of Reference