On learning read-k-satisfy-j DNF

Avrim Blum; Roni Khardont; Eyal Kushilevitzi; Leonard Pitt; Dan Rothf

doi:10.1145/180139.181051

On learning read-k-satisfy-j DNF

Avrim Blum, Roni Khardont, Eyal Kushilevitzi, Leonard Pitt, Dan Rothf

Siebel School of Computing and Data Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We study the learnability of Read-k-Satisfy-j (RkSj) DNF formulae. These are DNF formulae in which the maximal number of occurrences of a variable is bounded by k, and the number of terms satisfied by any assignment is at most j. We show that this class of functions is learnable in polynomial time, using Equivalence and Membership Queries, as long as k · j = O(log n/log log n)-Learnability was previously known only in case that both k and j are constants. We also present a family of boolean functions that have short (poly(n)) Read-2-Satisfy-1 DNF formulae but require CNF formulae of size 2^φ(√n). Therefore, our result does not seem to follow from the recent learnability result of [Bsh93].

Original language	English (US)
Title of host publication	Proceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994
Publisher	Association for Computing Machinery
Pages	110-117
Number of pages	8
ISBN (Electronic)	0897916557
DOIs	https://doi.org/10.1145/180139.181051
State	Published - Jul 16 1994
Event	7th Annual Conference on Computational Learning Theory, COLT 1994 - New Brunswick, United States Duration: Jul 12 1994 → Jul 15 1994

Publication series

Name	Proceedings of the Annual ACM Conference on Computational Learning Theory
Volume	Part F129415

Other

Other	7th Annual Conference on Computational Learning Theory, COLT 1994
Country/Territory	United States
City	New Brunswick
Period	7/12/94 → 7/15/94

ASJC Scopus subject areas

Software
Theoretical Computer Science
Artificial Intelligence

Online availability

10.1145/180139.181051

Library availability

Discover UIUC Full Text

Cite this

Blum, A., Khardont, R., Kushilevitzi, E., Pitt, L., & Rothf, D. (1994). On learning read-k-satisfy-j DNF. In Proceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994 (pp. 110-117). (Proceedings of the Annual ACM Conference on Computational Learning Theory; Vol. Part F129415). Association for Computing Machinery. https://doi.org/10.1145/180139.181051

On learning read-k-satisfy-j DNF. / Blum, Avrim; Khardont, Roni; Kushilevitzi, Eyal et al.
Proceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994. Association for Computing Machinery, 1994. p. 110-117 (Proceedings of the Annual ACM Conference on Computational Learning Theory; Vol. Part F129415).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Blum, A, Khardont, R, Kushilevitzi, E, Pitt, L & Rothf, D 1994, On learning read-k-satisfy-j DNF. in Proceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994. Proceedings of the Annual ACM Conference on Computational Learning Theory, vol. Part F129415, Association for Computing Machinery, pp. 110-117, 7th Annual Conference on Computational Learning Theory, COLT 1994, New Brunswick, United States, 7/12/94. https://doi.org/10.1145/180139.181051

@inproceedings{208b27b77ee449879b5e147eeb3156a1,

title = "On learning read-k-satisfy-j DNF",

abstract = "We study the learnability of Read-k-Satisfy-j (RkSj) DNF formulae. These are DNF formulae in which the maximal number of occurrences of a variable is bounded by k, and the number of terms satisfied by any assignment is at most j. We show that this class of functions is learnable in polynomial time, using Equivalence and Membership Queries, as long as k · j = O(log n/log log n)-Learnability was previously known only in case that both k and j are constants. We also present a family of boolean functions that have short (poly(n)) Read-2-Satisfy-1 DNF formulae but require CNF formulae of size 2φ(√n). Therefore, our result does not seem to follow from the recent learnability result of [Bsh93].",

author = "Avrim Blum and Roni Khardont and Eyal Kushilevitzi and Leonard Pitt and Dan Rothf",

note = "Publisher Copyright: {\textcopyright} 1994 ACM.; 7th Annual Conference on Computational Learning Theory, COLT 1994 ; Conference date: 12-07-1994 Through 15-07-1994",

year = "1994",

month = jul,

day = "16",

doi = "10.1145/180139.181051",

language = "English (US)",

series = "Proceedings of the Annual ACM Conference on Computational Learning Theory",

publisher = "Association for Computing Machinery",

pages = "110--117",

booktitle = "Proceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994",

address = "United States",

}

TY - GEN

T1 - On learning read-k-satisfy-j DNF

AU - Blum, Avrim

AU - Khardont, Roni

AU - Kushilevitzi, Eyal

AU - Pitt, Leonard

AU - Rothf, Dan

PY - 1994/7/16

Y1 - 1994/7/16

N2 - We study the learnability of Read-k-Satisfy-j (RkSj) DNF formulae. These are DNF formulae in which the maximal number of occurrences of a variable is bounded by k, and the number of terms satisfied by any assignment is at most j. We show that this class of functions is learnable in polynomial time, using Equivalence and Membership Queries, as long as k · j = O(log n/log log n)-Learnability was previously known only in case that both k and j are constants. We also present a family of boolean functions that have short (poly(n)) Read-2-Satisfy-1 DNF formulae but require CNF formulae of size 2φ(√n). Therefore, our result does not seem to follow from the recent learnability result of [Bsh93].

AB - We study the learnability of Read-k-Satisfy-j (RkSj) DNF formulae. These are DNF formulae in which the maximal number of occurrences of a variable is bounded by k, and the number of terms satisfied by any assignment is at most j. We show that this class of functions is learnable in polynomial time, using Equivalence and Membership Queries, as long as k · j = O(log n/log log n)-Learnability was previously known only in case that both k and j are constants. We also present a family of boolean functions that have short (poly(n)) Read-2-Satisfy-1 DNF formulae but require CNF formulae of size 2φ(√n). Therefore, our result does not seem to follow from the recent learnability result of [Bsh93].

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

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

U2 - 10.1145/180139.181051

DO - 10.1145/180139.181051

M3 - Conference contribution

AN - SCOPUS:84943226623

T3 - Proceedings of the Annual ACM Conference on Computational Learning Theory

SP - 110

EP - 117

BT - Proceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994

PB - Association for Computing Machinery

T2 - 7th Annual Conference on Computational Learning Theory, COLT 1994

Y2 - 12 July 1994 through 15 July 1994

ER -

On learning read-k-satisfy-j DNF

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this