Computational Complexity of Learning Read-Once Formulas over Different Bases
Title | Computational Complexity of Learning Read-Once Formulas over Different Bases |
Publication Type | Technical Report |
Year of Publication | 1991 |
Authors | Hellerstein, L., & Karpinski M. |
Other Numbers | 644 |
Keywords | Computational 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). |
URL | http://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 |