Reconstructing arithmetic formulas using lower bound proof techniques

Neeraj Kayal
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)...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.