Article

Free access

On learning arithmetic read-once formulas with exponentiation (extended abstract)

Authors:

Daoud Bshouty,

Nader H. BshoutyAuthors Info & Claims

COLT '94: Proceedings of the seventh annual conference on Computational learning theory

Pages 311 - 317

https://doi.org/10.1145/180139.181163

Published: 16 July 1994 Publication History

PDF eReader

Abstract

A formula is a read-once formula if each variable appears at most once in it. An arithmetic read-once formula (AROF) with exponentiation is one in which the operations are addition, subtraction, multiplication, division and exponentiation to an arbitrary integer. We present a polynomial time algorithm for interpolating AROF with exponentiation using randomized substitutions. We then nonconstructively show the existence of a nonuniform deterministic algorithm.

Interpolating AROF without exponentiation is studied in [Bshouty, Hancock and Hellerstein, STOC 92]. To add the exponentiation operation to the basis we develop a new technique.

References

[1]

M. Ben-Or and P. Tiwari. A deterministic algorithm for sparse multivariate polynomial interpolation. In Proceedings of the 20th Annual ACM Symposium on the Theory of Computing, pages 301- 309, 1988.

Digital Library

Google Scholar

[2]

A. Borodin and P. Tiwari. On the decidability of sparse univariate polynomials. In Proceedings of the 31st Symposium on the Foundations of Computer Science, 1990.

Google Scholar

[3]

N. H. Bshouty, T. R. Hancock, and L. Hellerstein. Learning arithmetic read-once formulas. In Proceedings of the Twenty Fourth Annual ACM Symposium on Theory of Computing, pages 370-381, May 1992. To appear in SIAM J. Comp.

Digital Library

Google Scholar

[4]

D.Y. Grigoriev, M. Karpinski, and M. F. Singer. Interpolation of sparse rational functions without knowing bounds on the exponent. In Proceedings of the 31st Symposium on Foundations of Computer Science, 1990.

Digital Library

Google Scholar

[5]

D.Y. Grigoriev, M. Karpinski, and M. F. Singer. Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields. Technical report, Research Report No. 8523-C5, University of Bonn (1988), 1988. To appear in SIAM J. Comp.

Digital Library

Google Scholar

[6]

J. Heintz and C. P. Schnorr. Testing polynomials that are easy to compute. In Proceedings of the l~th Annual ACM Symposium on the Theory o f Computing, pages 262-272, 1980.

Digital Library

Google Scholar

[7]

M. Ron Roth and G. Benedek. Interpolation and approximation of sparse multivariate polynomials over Gr(2). SIAM J. Computing, 20(2):291-314, 1991.

Digital Library

Google Scholar

[8]

R. E. Schapire and L. M. Sellie. Learning sparse multivariate polynomials over a field with queries and counterexamples. In Proceedings of the Sizth Annual Workshop on Computational Learning Theory, pages 17-26, 1993.

Digital Library

Google Scholar

[9]

J.T. Schwartz. Fast polynomial algorithms for verification of polynomial identities . Journal of the Association for Computing Machinery, 27(4):701- 707, 1980.

Digital Library

Google Scholar

[10]

Y. Mansour. Randomized approximation and interpolation of sparse polynomials. To appear in SIAM Journal on Computing.

Digital Library

Google Scholar

Cited By

View all

Raghavendra RJayalal S(2022)Isomorphism testing of read-once functions and polynomialsInformation and Computation10.1016/j.ic.2022.104921(104921)Online publication date: May-2022
https://doi.org/10.1016/j.ic.2022.104921
Washio TMotoda H(1997)Discovering admissible models of complex systems based on scale-types and identity constraintsProceedings of the Fifteenth international joint conference on Artifical intelligence - Volume 210.5555/1622270.1622273(810-817)Online publication date: 23-Aug-1997
https://dl.acm.org/doi/10.5555/1622270.1622273

Index Terms

On learning arithmetic read-once formulas with exponentiation (extended abstract)
1. Computing methodologies
  1. Machine learning
2. Theory of computation
  1. Models of computation
    1. Abstract machines

Recommendations

On Interpolating Arithmetic Read-Once Formulas with Exponentiation

A formula is a read-once formula if each variable appears at most once in it. An arithmetic read-once formula (AROF) with exponentiation is one in which the operations are addition, substraction, multiplication, division and exponentiation to an ...
Learning Arithmetic Read-Once Formulas

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 algorithms for exact learning of ...
Learning arithmetic read-once formulas
STOC '92: Proceedings of the twenty-fourth annual ACM symposium on Theory of Computing

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

COLT '94: Proceedings of the seventh annual conference on Computational learning theory

July 1994

376 pages

ISBN:0897916557

DOI:10.1145/180139

Chairman:
Manfred Warmuth
Univ. of California, Santa Cruz

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 July 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

7COLT94

Sponsor:

7COLT94: 7th Annual Conference on Computational Learning Theory

July 12 - 15, 1994

New Jersey, New Brunswick, USA

Acceptance Rates

Overall Acceptance Rate 35 of 71 submissions, 49%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
16
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)2

Reflects downloads up to 04 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Raghavendra RJayalal S(2022)Isomorphism testing of read-once functions and polynomialsInformation and Computation10.1016/j.ic.2022.104921(104921)Online publication date: May-2022
https://doi.org/10.1016/j.ic.2022.104921
Washio TMotoda H(1997)Discovering admissible models of complex systems based on scale-types and identity constraintsProceedings of the Fifteenth international joint conference on Artifical intelligence - Volume 210.5555/1622270.1622273(810-817)Online publication date: 23-Aug-1997
https://dl.acm.org/doi/10.5555/1622270.1622273

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

On Interpolating Arithmetic Read-Once Formulas with Exponentiation

Learning Arithmetic Read-Once Formulas

Learning arithmetic read-once formulas