{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:32:40Z","timestamp":1725489160410},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540735441"},{"type":"electronic","value":"9783540735458"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-73545-8_30","type":"book-chapter","created":{"date-parts":[[2007,8,17]],"date-time":"2007-08-17T13:44:11Z","timestamp":1187358251000},"page":"296-306","source":"Crossref","is-referenced-by-count":1,"title":["When Does Greedy Learning of Relevant Attributes Succeed?"],"prefix":"10.1007","author":[{"given":"Jan","family":"Arpe","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R\u00fcdiger","family":"Reischuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"30_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1007\/3-540-61332-3_163","volume-title":"Computing and Combinatorics","author":"T. Akutsu","year":"1996","unstructured":"Akutsu, T., Bao, F.: Approximating Minimum Keys and Optimal Substructure Screens. In: Cai, J.-Y., Wong, C.K. (eds.) COCOON 1996. LNCS, vol.\u00a01090, pp. 290\u2013299. Springer, Heidelberg (1996)"},{"issue":"3-4","key":"30_CR2","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1089\/106652700750050817","volume":"7","author":"T. Akutsu","year":"2000","unstructured":"Akutsu, T., Miyano, S., Kuhara, S.: Algorithms for Identifying Boolean Networks and Related Biological Networks Based on Matrix Multiplication and Fingerprint Function. J. Comput. Biology\u00a07(3-4), 331\u2013343 (2000)","journal-title":"J. Comput. Biology"},{"issue":"2","key":"30_CR3","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1016\/S0304-3975(02)00183-4","volume":"292","author":"T. Akutsu","year":"2003","unstructured":"Akutsu, T., Miyano, S., Kuhara, S.: A Simple Greedy Algorithm for Finding Functional Relations: Efficient Implementation and Average Case Analysis. Theoret. Comput. Sci.\u00a0292(2), 481\u2013495 (2003)","journal-title":"Theoret. Comput. Sci."},{"issue":"1-2","key":"30_CR4","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/0004-3702(94)90084-1","volume":"69","author":"H. Almuallim","year":"1994","unstructured":"Almuallim, H., Dietterich, T.G.: Learning Boolean Concepts in the Presence of Many Irrelevant Features. Artificial Intelligence\u00a069(1-2), 279\u2013305 (1994)","journal-title":"Artificial Intelligence"},{"key":"30_CR5","series-title":"Wiley-Intersci. Ser. Discrete Math. Optim.","volume-title":"The Probabilistic Method.","author":"N. Alon","year":"1992","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method. Wiley-Intersci. Ser. Discrete Math. Optim. John Wiley and Sons, Chichester (1992)"},{"key":"30_CR6","unstructured":"Arpe, J.: Learning Concepts with Few Unknown Relevant Attributes from Noisy Data. PhD thesis, Institut f\u00fcr Theoretische Informatik, Universit\u00e4t zu L\u00fcbeck (2006)"},{"key":"30_CR7","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/978-3-540-39624-6_10","volume-title":"Algorithmic Learning Theory","author":"J. Arpe","year":"2003","unstructured":"Arpe, J., Reischuk, R.: Robust Inference of Relevant Attributes. In: Gavald\u00e1, R., Jantke, K.P., Takimoto, E. (eds.) ALT 2003. LNCS (LNAI), vol.\u00a02842, pp. 99\u2013113. Springer, Heidelberg (2003)"},{"key":"30_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/11750321_37","volume-title":"Theory and Applications of Models of Computation","author":"J. Arpe","year":"2006","unstructured":"Arpe, J., Reischuk, R.: Learning Juntas in the Presence of Noise. In: Cai, J.-Y., Cooper, S.B., Li, A. (eds.) TAMC 2006. LNCS, vol.\u00a03959, pp. 387\u2013398. Springer, Heidelberg, Invited to appear in special issue of TAMC 2006 in Theoret. Comput. Sci., Series A (2006)"},{"key":"30_CR9","unstructured":"Arpe, J., Reischuk, R.: When Does Greedy Learning of Relevant Attributes Succeed?\u2014A Fourier-based Characterization. Technical Report ECCC TR06-065, Electronic Colloquium on Computational Complexity (2006)"},{"key":"30_CR10","first-page":"158","volume-title":"Studies in Item Analysis and Prediction","author":"R.R. Bahadur","year":"1961","unstructured":"Bahadur, R.R.: A Representation of the Joint Distribution of Responses to n Dichotomous Items. In: Solomon, H. (ed.) Studies in Item Analysis and Prediction, pp. 158\u2013168. Stanford University Press, Stanford (1961)"},{"key":"30_CR11","unstructured":"Bernasconi, A.: Mathematical Techniques for the Analysis of Boolean Functions. PhD thesis, Universit\u00e0 degli Studi di Pisa, Dipartimento di Ricerca in Informatica (1998)"},{"key":"30_CR12","doi-asserted-by":"crossref","unstructured":"Blum, A., Furst, M., Jackson, J.C., Kearns, M., Mansour, Y., Rudich, S.: Weakly Learning DNF and Characterizing Statistical Query Learning Using Fourier Analysis. In: Proc. 26th STOC 1994, pp. 253\u2013262 (1994)","DOI":"10.1145\/195058.195147"},{"issue":"1-2","key":"30_CR13","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/S0004-3702(97)00063-5","volume":"97","author":"A. Blum","year":"1997","unstructured":"Blum, A., Langley, P.: Selection of Relevant Features and Examples in Machine Learning. Artificial Intelligence\u00a097(1-2), 245\u2013271 (1997)","journal-title":"Artificial Intelligence"},{"issue":"6","key":"30_CR14","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1016\/0020-0190(87)90114-1","volume":"24","author":"A. Blumer","year":"1987","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.K.: Occam\u2019s Razor. Inform. Process. Lett.\u00a024(6), 377\u2013380 (1987)","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"30_CR15","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1023\/A:1024653703689","volume":"39","author":"E. Boros","year":"2003","unstructured":"Boros, E., Horiyama, T., Ibaraki, T., Makino, K., Yagiura, M.: Finding Essential Attributes from Binary Data. Ann. Math. Artif. Intell.\u00a039(3), 223\u2013257 (2003)","journal-title":"Ann. Math. Artif. Intell."},{"issue":"3","key":"30_CR16","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: A Greedy Heuristic for the Set Covering Problem. Math. Oper. Res.\u00a04(3), 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"30_CR17","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A Threshold of ln n for Approximating Set Cover. J. ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"30_CR18","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/j.ipl.2004.09.017","volume":"93","author":"D. Fukagawa","year":"2005","unstructured":"Fukagawa, D., Akutsu, T.: Performance Analysis of a Greedy Algorithm for Inferring Boolean Functions. Inform. Process. Lett.\u00a093(1), 7\u201312 (2005)","journal-title":"Inform. Process. Lett."},{"key":"30_CR19","doi-asserted-by":"crossref","unstructured":"Furst, M.L., Jackson, J.C., Smith, S.W.: Improved Learning of AC\n                        0 Functions. In: Proc. 4th COLT 1991, pp. 317\u2013325","DOI":"10.1016\/B978-1-55860-213-7.50032-8"},{"issue":"3","key":"30_CR20","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation Algorithms for Combinatorial Problems. J. Comput. System Sci.\u00a09(3), 256\u2013278 (1974)","journal-title":"J. Comput. System Sci."},{"key":"30_CR21","volume-title":"Algorithm Design","author":"J. Kleinberg","year":"2005","unstructured":"Kleinberg, J., Tardos, \u00c9.: Algorithm Design. Addison-Wesley, Reading (2005)"},{"issue":"3","key":"30_CR22","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1145\/174130.174138","volume":"40","author":"N. Linial","year":"1993","unstructured":"Linial, N., Mansour, Y., Nisan, N.: Constant Depth Circuits, Fourier Transform, and Learnability. J. ACM\u00a040(3), 607\u2013620 (1993)","journal-title":"J. ACM"},{"key":"30_CR23","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1007\/978-1-4615-2696-4_11","volume-title":"Theoretical Advances in Neural Computation and Learning","author":"Y. Mansour","year":"1994","unstructured":"Mansour, Y.: Learning Boolean Functions via the Fourier Transform. In: Roychodhury, V., Siu, K.-Y., Orlitsky, A. (eds.) Theoretical Advances in Neural Computation and Learning, pp. 391\u2013424. Kluwer Academic Publishers, Dordrecht (1994)"},{"issue":"3","key":"30_CR24","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1016\/j.jcss.2004.04.002","volume":"69","author":"E. Mossel","year":"2004","unstructured":"Mossel, E., O\u2019Donnell, R.W., Servedio, R.A.: Learning functions of k relevant variables. J. Comput. System Sci.\u00a069(3), 421\u2013434 (2004)","journal-title":"J. Comput. System Sci."},{"issue":"4","key":"30_CR25","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/S0304-3975(99)00237-6","volume":"240","author":"R. Reischuk","year":"2000","unstructured":"Reischuk, R.: Can Large Fanin Circuits Perform Reliable Computations in the Presence of Noise? Theoretical Comput. Sci.\u00a0240(4), 319\u2013335 (2000)","journal-title":"Theoretical Comput. Sci."},{"key":"30_CR26","unstructured":"Shamir, R., Dietrich, B.: Characterization and Algorithms for Greedily Solvable Transportation Problems. In: Proc. 1st SODA 1990, pp. 358\u2013366 (1990)"},{"key":"30_CR27","doi-asserted-by":"crossref","unstructured":"Slav\u00edk, P.: A Tight Analysis of the Greedy Algorithm for Set Cover. In: Proc. 28th STOC 1996, pp. 435\u2013441 (1996)","DOI":"10.1145\/237814.237991"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73545-8_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T16:38:23Z","timestamp":1578501503000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73545-8_30"}},"subtitle":["\u2014 A Fourier-Based Characterization \u2014"],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540735441","9783540735458"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73545-8_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}