Equivalence Test for Read-Once Arithmetic Formulas

Nikhil Gupta, Chandan Saha, Bhargav Thankey

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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: • 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). • 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 “skewed paths”. To our knowledge, the Hessian of a general ROF (or even a depth-4 ROF) has not been analyzed before. Analyzing the Hessian and combining the knowledge gained from it with the skewed paths to recursively discover formulas in the orbits of sub-ROFs of lower depth (without incurring an exponential blow-up due to unbounded depth) constitute the main technical contributions of this work.

Original languageEnglish (US)
Title of host publication34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
PublisherAssociation for Computing Machinery
Number of pages68
ISBN (Electronic)9781611977554
StatePublished - 2023
Event34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 - Florence, Italy
Duration: Jan 22 2023Jan 25 2023

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Conference34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

ASJC Scopus subject areas

  • Software
  • Mathematics(all)


Dive into the research topics of 'Equivalence Test for Read-Once Arithmetic Formulas'. Together they form a unique fingerprint.

Cite this