{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T21:44:52Z","timestamp":1648763092131},"reference-count":23,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2001,8]]},"abstract":"<jats:p> We employ the Always Approximately Correct or AAC model defined in [35], to prove learnability results for classes of Boolean functions over arbitrary finite Abelian groups. This model is an extension of Angluin's Query model of exact learning. The Boolean functions we consider belong to approximation classes, i.e. functions that are approximable (in various norms) by few Fourier basis functions, or irreducible characters of the domain Abelian group. We contrast our learnability results to previous results for similar classes in the PAC model of learning with and without membership queries. <\/jats:p><jats:p> In addition, we discuss new, natural issues and questions that arise when the AAC model is used. One such question is whether a uniform training set is available for learning any function in a given approximation class. No analogous question seems to have been studied in the context of Angluin's Query model. Another question is whether the training set can be found quickly if the approximation class of the function is completely unknown to the learner, or only partial information about the approximation class is given to the learner (in addition to the answers to membership queries). <\/jats:p><jats:p> In order to prove the learnability results in this paper we require new techniques for efficiently sampling Boolean functions using the character theory of finite Abelian groups, as well as the development of algebraic algorithms. The techniques result in other natural applications closely related to learning, for example, query complexity of deterministic algorithms for testing linearity, efficient pseudorandom generators, and estimating VC dimensions for classes of Boolean functions over finite Abelian groups. <\/jats:p>","DOI":"10.1142\/s0129054101000618","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T10:59:39Z","timestamp":1027767579000},"page":"491-516","source":"Crossref","is-referenced-by-count":0,"title":["DERANDOMIZED LEARNING OF BOOLEAN FUNCTIONS OVER FINITE ABELIAN GROUPS"],"prefix":"10.1142","volume":"12","author":[{"given":"M.","family":"SITHARAM","sequence":"first","affiliation":[{"name":"Computer and Information Science and Engineering Department, University of Florida, CSE Building, P.O Box 11-6120, Gainesville, Florida 32605, USA"}]},{"given":"TIMOTHY","family":"STRANEY","sequence":"additional","affiliation":[{"name":"Department of Math and CS, Kent State University, Kent, Ohio 44242, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90052-6"},{"key":"p_2","first-page":"147","volume":"9","author":"Angluin D.","year":"1992","journal-title":"Machine Learning"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1145\/138027.138061"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267823"},{"key":"p_6","first-page":"301","author":"Ben-Or M.","year":"1988","journal-title":"Proceedings of the 20t\/l Annual ACM Symposium on Theory of Computing"},{"key":"p_7","first-page":"73","author":"Blum M.","year":"1990","journal-title":"Proceedings of the 22nd Annual ACM Symposium on Theory of Computing"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1145\/225298.225349"},{"key":"p_9","first-page":"302","author":"Bshouty N. H.","year":"1993","journal-title":"Proceedings of the 34th IEEE Symposium on the Foundations of Computer Science"},{"key":"p_10","first-page":"219","author":"Bshouty N. H.","year":"1995","journal-title":"Proceedings of the 21th Annual ACM Symposium on Theory of Computing"},{"key":"p_11","first-page":"304","author":"Bshouty N.","year":"1995","journal-title":"Proceedings of the 36th IEEE Symposium on the Foundations of Computer Science"},{"key":"p_18","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/B978-1-55860-213-7.50032-8","author":"Furst M.","year":"1991","journal-title":"Proceedings of COLT"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(92)90060-8"},{"key":"p_24","first-page":"99","author":"Hajnal A.","year":"1987","journal-title":"Proceedings of the 2%th IEEE Symposium on Foundations of Computer Science"},{"key":"p_26","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365706"},{"key":"p_27","first-page":"48","author":"Krause P.","year":"1994","journal-title":"Proceedings of the 2\u00a7th Symposium on Theory of Computing"},{"key":"p_28","first-page":"682","author":"Krause P.","year":"1995","journal-title":"l IEEE Symposium on Foundations of Computer Science"},{"key":"p_29","first-page":"777","author":"Krause S.","year":"1991","journal-title":"Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science"},{"key":"p_30","first-page":"455","author":"Kushilevitz E.","year":"1991","journal-title":"Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science"},{"key":"p_31","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63537"},{"key":"p_32","first-page":"462","author":"Nisan N.","year":"1992","journal-title":"Proceedings of the 2Ath Annual ACM Symposium on Theory of Computing"},{"key":"p_33","first-page":"2","author":"Nisan N.","year":"1988","journal-title":"Proceedings of the 2\u00a7th IEEE Symposium on Foundations of Computer Science"},{"key":"p_34","first-page":"468","author":"Paturi R.","year":"1992","journal-title":"Proceedings of 24th Annual ACM Symposium on Theory of Computing"},{"key":"p_35","first-page":"17","author":"Schapire R.","year":"1993","journal-title":"Proceedings of the 6th Workshop on Computational Learning Theory"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054101000618","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:46:38Z","timestamp":1565138798000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054101000618"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,8]]},"references-count":23,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2001,8]]}},"alternative-id":["10.1142\/S0129054101000618"],"URL":"https:\/\/doi.org\/10.1142\/s0129054101000618","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,8]]}}}