Publication Details
Title: Computational Complexity of Learning Read-Once Formulas over Different Bases
Author: L. Hellerstein and M. Karpinski
Group: ICSI Technical Reports
Date: February 1991
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-014.pdf
Overview:
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).
Author: L. Hellerstein and M. Karpinski
Group: ICSI Technical Reports
Date: February 1991
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-014.pdf
Overview:
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).
Keywords: Computational Complexity, Learning Algorithms, Read-Once Formulas, Queries.
Bibliographic Information:
ICSI Technical Report TR-91-014
Bibliographic Reference:
L. Hellerstein and M. Karpinski. Computational Complexity of Learning Read-Once Formulas over Different Bases. ICSI Technical Report TR-91-014, February 1991