BIRS Workshop Lecture Videos
Reconstructing arithmetic formulas using lower bound proof techniques Kayal, Neeraj
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 Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International