Learning Boolean Read-Once Formulas with Arbitrary Symmetric and Constant Fan-in Gates

Abstract

A formula is read-once if each variable appears on at most a single input. Angluin, Hellerstein, and Karpinski have shown that boolean formulas with AND, OR, and NOT gates are exactly identifiable in polynomial time using membership and equivalence queries [AHK89]. Hancock and Hellerstein have generalized this to allow a wider subclass of symmetric basis functions [HH91]. We show a polynomial time algorithm in this model for identifying read-once formulas whose gates compute arbitrary functions of fan-in k or less for some constant k (i.e. any f :0,11≤c≤k → 0,1). We further show that if there is a polynomial time membership and equivalence query algorithm to identify read-once formulas over some set of functions B that meets certain technical conditions, then there is also such an algorithm to identify read-once formulas over Bu{f:0,11≤c≤k → 0,1}. Finally, we extend the previous results to show that there is a polynomial time identification algorithm for read-once formulas over the basis of all symmetric functions (and hence also over the union of arbitrary symmetric and arbitrary constant fan-in gates). Given standard cryptographic assumptions, none of these results are possible for read-twice formulas.