ML Anthology

On Learning Arithmetic Read-Once Formulas with Exponentiation (Extended Abstract)

Daoud Bshouty, Nader H. Bshouty
COLT 1994 pp. 311-317
doi:10.1145/180139.181163 /colt/1994/bshouty1994colt-learning/

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.

COLT Semantic Scholar

Cite

Text

Bshouty and Bshouty. "On Learning Arithmetic Read-Once Formulas with Exponentiation (Extended Abstract)." Annual Conference on Computational Learning Theory, 1994. doi:10.1145/180139.181163

Markdown

[Bshouty and Bshouty. "On Learning Arithmetic Read-Once Formulas with Exponentiation (Extended Abstract)." Annual Conference on Computational Learning Theory, 1994.](https://mlanthology.org/colt/1994/bshouty1994colt-learning/) doi:10.1145/180139.181163

BibTeX

@inproceedings{bshouty1994colt-learning,
  title     = {{On Learning Arithmetic Read-Once Formulas with Exponentiation (Extended Abstract)}},
  author    = {Bshouty, Daoud and Bshouty, Nader H.},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {1994},
  pages     = {311-317},
  doi       = {10.1145/180139.181163},
  url       = {https://mlanthology.org/colt/1994/bshouty1994colt-learning/}
}