Learning arithmetic read-once formulas

ABSTRACT

A formula is read-once if each variable appears at most once in it. An arithmetic read-once formula is one in which the operators are addition, subtraction, multiplication, and division. We present polynomial time algorithm for exactly learning (or interpolating) arithmetic read-once formulas computing functions over a field. We present an algorithm that uses randomized membership queries (or substitutions) to identify such formulas over large finite fields and infinite fields. We also present a deterministic algorithm that uses equivalence queries as well as membership queries to identify arithmetic read-once formulas over small finite fields. We then non-constructively show the existence of deterministic membership query (interpolation) algorithms for arbitrary formulas over fields of characteristic 0 and for division-free formulas over large or infinite fields. Our algorithms assume we are able to efficiently perform arithmetic operations on field elements and compute square roots in the field. It is shown that the ability to compute square roots is necessary, in the sense that the problem of computing n – 1 square roots in a field can be reduced to the problem of identifying an arithmetic formula over n variables in that field. Our equivalence queries are of a slightly non-standard form, in which counterexamples are required to not be inputs on which the formula evaluates to 0/0. This assumption is shown to be necessary for fields of size o(n/log n), for which it is shown that there is no polynomial time identification algorithm that uses just membership and standard equivalence queries.

REFERENCES

• AHK89: Dana Angluin , Lisa Hellerstein , Marek Karpinski, Learning read-once formulas with queries, Journal of the ACM (JACM), v.40 n.1, p.185-210, Jan. 1993 [doi>10.1145/138027.138061]
• BOT88: Michael Ben-Or, A deterministic algorithm for sparse multivariate polynomial interpolation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.301-309, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62241]
• BHH92: N. H. Bshouty, T. R. Hancock, and L. Hellerstein. Learning boolean read-once formulas with arbitrary symmetric and constant fan-in gates. Manuscript in Preparation.
• BHHK91: N. H. Bshouty, T. R. Hancock, L. Hellerstein, and M. Karpinski. Read-once threshold formulas, justifying assignments, and transformations. Unpublished Manuscript.
• BT90: A. Borodin , P. Tiwari, On the decidability of sparse univariate polynomial interpolation, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.535-545, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100292]
• GKS90a: S. A. Goldman, M. J. Kearns, and R. E. Schapire. Exact identification of circuits using fixed points of amplification functions. In Proceedings of the 31st Symposium on Foundations of Computer Science, 1990.
• GKS88: Dima Grigoriev , Marek Karpinski , Michael F. Singer, Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolationover Finite Fields, University of Bonn, 1988
• GKS90b: D.Y. Grigoriev, M. Karpinski, and M. Singer. Interpolation of sparse rational functions without knowing bounds on the exponent. In Proceedings of the 31s1 Symposium on Foundations of Computer Science, 1990.
• Han90: T. Hancock. Identifying /u-formula decision trees with queries. Technical report, Harvard University TR- 16-90, 1990.
• HH91: Thomas Hancock , Lisa Hellerstein, Learning read-once formulas over fields and extended bases, Proceedings of the fourth annual workshop on Computational learning theory, p.326-336, August 05-07, 1991, Santa Cruz, California, United States
• HK90: Lisa Hellerstein , Marek Karpinski, Computational Complexity of Learning Read-Once Formulas over Different Bases, University of Bonn, 1990
• HS80: J. Heintz , C. P. Schnorr, Testing polynomials which are easy to compute (Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.262-272, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804674]
• L91: B. Lhotzky. On the computational complexity of some algebraic counting problems. PhD thesis, University of Bonn, 1991.
• RB89: Ron M. Roth , Gyora M. Benedek, Interpolation and approximation of sparse multivariate polynomials over GF(2), SIAM Journal on Computing, v.20 n.2, p.291-314, April 1990 [doi>10.1137/0220019]
• Sch80: J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Performance, Theory