Seminars

View all Seminars  |  Download ICal for this event

Equivalence Test for Read-Once Arithmetic Formulas

Series: Bangalore Theory Seminars

Speaker: Bhargav Thankey Indian Institute of Science Bangalore

Date/Time: Feb 10 11:00:00

Location: CSA Lecture Hall (Room No. 117, Ground Floor)

Abstract:
We study the polynomial equivalence problem for orbits of read-once arithmetic formulas (ROFs). Read-once formulas have received considerable attention in both algebraic and Boolean complexity and have served as a testbed for developing effective tools and techniques for analyzing circuits. Two n-variate polynomials f,g??F[x] are equivalent, denoted as f?g, if there is an A??GL(n,F) such that f=g(Ax). The orbit of f is the set of all polynomials equivalent to f. We investigate the complexity of the following two natural problems on ROFs:

1. Equivalence test for ROFs: Given black-box access to f, check if it is in the orbit of an ROF. If yes, output an ROF C and an A??GL(n,F) such that f=C(Ax).
2. Polynomial equivalence for orbits of ROFs: Given black-box access to f and g in the orbits of two unknown ROFs, check if f?g. If yes, output an A??GL(n,F) such that f=g(Ax).

These problems are significant generalizations of two well-studied problems in algebraic complexity, namely reconstruction of ROFs and quadratic form equivalence. In this work, we give the first randomized polynomial-time algorithms (with oracle access to quadratic form equivalence) to solve the two problems. The equivalence test works for general ROFs; it also implies an efficient learning algorithm for random arithmetic formulas of unbounded depth and fan-in (in the high number of variables setting). The algorithm for the second problem, which invokes the equivalence test, works for mildly restricted ROFs, namely additive-constant-free ROFs.

The equivalence test is based on a novel interplay between the factors and the essential variables of the Hessian determinant of an ROF, the essential variables of the ROF, and certain special structures in the ROF that we call