Computational Complexity of Learning Read-Once Formulas over Different Bases

TitleComputational Complexity of Learning Read-Once Formulas over Different Bases
Publication TypeTechnical Report
Year of Publication1991
AuthorsHellerstein, L., & Karpinski M.
Other Numbers644
KeywordsComputational Complexity, learning algorithms, Queries, Read-Once Formulas
Abstract

We study computational complexity of learning read-once formulas over different boolean bases. In particular we design a polynomial time algorithm for learning read-once formulas over a threshold basis. The algorithm works in time O(n**3) using O(n**3) membership queries. By the result of [Angluin, Hellerstein, Karpinski, 1989] on the corresponding unate class of boolean functions, this gives a polynomial time learning algorithm for arbitrary read-once formulas over a threshold basis with negation using membership and equivalence queries. Furthermore we study the structural notion of nondegeneracy in the threshold formulas generalizing the result of [Heiman, Newman, Wigderson, 1990] on the uniqueness of read-once formulas over different boolean bases and derive a negative result on learnability of nondegenerate read-once formulas over the basis (AND, XOR).

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1991/tr-91-014.pdf
Bibliographic Notes

ICSI Technical Report TR-91-014

Abbreviated Authors

L. Hellerstein and M. Karpinski

ICSI Publication Type

Technical Report