TY - GEN

T1 - Learning boolean read-once formulas with arbitrary symmetric and constant fan-in gates

AU - Bshouty, Nader H.

AU - Hancock, Thomas R.

AU - Hellerstein, Lisa

PY - 1992

Y1 - 1992

N2 - 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, 1}1≤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 Bqq{f : {0, 1}1≤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.

AB - 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, 1}1≤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 Bqq{f : {0, 1}1≤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.

UR - http://www.scopus.com/inward/record.url?scp=0026976842&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026976842&partnerID=8YFLogxK

U2 - 10.1145/130385.130386

DO - 10.1145/130385.130386

M3 - Conference contribution

AN - SCOPUS:0026976842

SN - 089791497X

SN - 9780897914970

T3 - Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory

SP - 1

EP - 15

BT - Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory

PB - Publ by ACM

T2 - Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory

Y2 - 27 July 1992 through 29 July 1992

ER -