{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:22:38Z","timestamp":1725664958572},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540635772"},{"type":"electronic","value":"9783540696025"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63577-7_38","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T23:32:49Z","timestamp":1330299169000},"page":"100-115","source":"Crossref","is-referenced-by-count":0,"title":["Derandomized learning of boolean functions"],"prefix":"10.1007","author":[{"given":"Meera","family":"Sitharam","sequence":"first","affiliation":[]},{"given":"Timothy","family":"Straney","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"8_CR1","unstructured":"Alon, N., Vu, V. H.: Threshold gates, coin weighing, and indecomposable hypergraphs. FOGS (1996)"},{"issue":"2","key":"8_CR2","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","volume":"75","author":"D. Angluin","year":"1987","unstructured":"Angluin, D.: Learning regular sets from queries and counterexamples. Information and Computation (Vol. 75(2), 1987) 87\u2013106","journal-title":"Information and Computation"},{"key":"8_CR3","first-page":"147","volume":"9","author":"D. Angluin","year":"1992","unstructured":"Angluin, D., Frazier, M., Pitt, L.: Learning conjunctions of Horn clauses. Machine Learning (Vol. 9, 1992) 147\u2013164","journal-title":"Machine Learning"},{"key":"8_CR4","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1145\/138027.138061","volume":"40","author":"D. Angluin","year":"1993","unstructured":"Angluin, D., Hellerstein, L., Karpinski, M.: Learning read-once formulas with queries Journal of the ACM (Vol. 40, 1993) 185\u2013210","journal-title":"Journal of the ACM"},{"key":"8_CR5","unstructured":"Auer, P., Long, P., Srinivasan, A.: Pseudorandomness and learning of combinatorial rectangles. to appear in STOC (1997)"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Tiwari, P.: A deterministic algorithm for sparse multivariate polynomial interpolation. Proc. 20th Ann. ACM Symp. Theory of Comput. (May 1988) 301\u2013309","DOI":"10.1145\/62212.62241"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"Bshouty, N. H.: Exact learning via the monotone theory. Proceedings of the 34th IEEE Symposium on the Foundations of Computer Science 302\u2013311","DOI":"10.1109\/SFCS.1993.366857"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"Bshouty, N. H., Tamon, C.: On the Fourier spectrum of monotone functions. Proc. 27th Ann. ACM Symp. Theory of Comput. (May 1995) 219\u2013399","DOI":"10.1145\/225058.225125"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Bshouty, N., Mansour, Y.: Simple learning algorithms for decision trees and multivariate polynomials. Proc. 36th Ann. IEEE Symp. Foundations of C.S. (1995) 304\u2013311","DOI":"10.1109\/SFCS.1995.492486"},{"key":"8_CR10","unstructured":"Buck, R. C.: Applications of duality in approximation theory. Approximation of functions, Elsevier, H.L. Garabedian ed. (1964) 27\u201342"},{"key":"8_CR11","unstructured":"Enflo, P., Sitharam, M.: Stability of basis families and complexity lower bounds. ECCC report (Sept. 1996) Preprint also available at: http \/\/nimitz.mcs.kent.edu\/ sitharam"},{"key":"8_CR12","unstructured":"Furst, M., Jackson, J., Smith, S.: Improved learning of AC\u00b0 functions. 4th Conf. on Computational Learning Theory, (1991) 317\u2013325"},{"key":"8_CR13","unstructured":"Goldman, M., Hastad, J., Razborov, A. A.: Majority gates vs. general weighted threshold gates. 32nd Ann. IEEE Symp. Foundations of C.S. (1991)"},{"key":"8_CR14","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1016\/0097-3165(92)90060-8","volume":"61","author":"C. Gotsman","year":"1992","unstructured":"Gotsman, C., Linial, N.: Equivalence of two problems on the cube \u2014 A note. J. Comb. Theory, Ser. A 61 (1992) 142\u2013146","journal-title":"J. Comb. Theory, Ser. A"},{"key":"8_CR15","unstructured":"Grolmusz, V.: Harmonic analysis, real approximation and communication complexity of Boolean functions. Manuscript (1994)"},{"key":"8_CR16","unstructured":"Hastad, J.: Computational limitations of small depth circuits. Ph. D thesis, MIT press (1986)"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Hastad, J.: On the size of weights for threshold gates. SIAM J. Disc. Math. (1994) 484\u2013492","DOI":"10.1137\/S0895480192235878"},{"key":"8_CR18","unstructured":"Hajnal, A., Maass, W., Pudlik, P., Szegedy, M., Turin, G.: Threshold circuits of bounded depth. 28th Ann. IEEE Syrnp. Foundations of C.S. (1987) 99\u2013110"},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"Jackson, J.: An efficient membership query algorithm for learning DNF with respect to the uniform distribution. Proc. 35th Ann. IEEE Symp. Foundations of C.S. (1994) 42\u201353","DOI":"10.1109\/SFCS.1994.365706"},{"key":"8_CR20","unstructured":"Kushilevitz, E., Mansour, Y.: Learning decision trees using the Fourier transform. 32nd Ann. IEEE Syrnp. Foundations of C.S. (1991) 455\u2013464"},{"key":"8_CR21","unstructured":"Linial, N., Mansour, Y., Nisan, N.: Constant depth circuits, Fourier transforms, and learnability. 30th Ann. IEEE Symp. Foundations of C.S. (1989) 574\u2013579"},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"Nisan, N., Szegedy, M.: On the degree of Boolean functions as real polynomials. 24th Ann. ACM Symp. on Theory of Computing (1992) 462\u2013467","DOI":"10.1145\/129712.129757"},{"key":"8_CR23","unstructured":"Paturi, R.: On the degree of polynomials that approximate symmetric Boolean functions. 24th Ann. ACM Symp. on Theory of Computing (1992) 468\u2013474"},{"key":"8_CR24","doi-asserted-by":"crossref","unstructured":"Sitharam, M.: Pseudorandom generators and learning algorithms for AC\u00b0. Ann. ACM Symp. on Theory of Computing (1994) 478\u2013488","DOI":"10.1145\/195058.195236"},{"key":"8_CR25","doi-asserted-by":"crossref","unstructured":"Schapire, R., Sellie, L.: Learning sparse multivariate polynomials over a field with queries and counterexamples. Proceedings of the 6th Workshop on Computational Learning Theory 17\u201326","DOI":"10.1145\/168304.168307"},{"key":"8_CR26","unstructured":"Sitharain, M.: Approximation from spaces of functions over the cube, complexity lower bounds, derandomization, and learning algorithms. See ECCC reports. Preprint also available at: http \/\/nimitz.mcs.kent.edu\/ sitharam"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63577-7_38.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:44:42Z","timestamp":1619574282000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63577-7_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540635772","9783540696025"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-63577-7_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}