{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T04:04:10Z","timestamp":1747541050842,"version":"3.40.5"},"publisher-location":"Cham","reference-count":64,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031929311","type":"print"},{"value":"9783031929328","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-92932-8_18","type":"book-chapter","created":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T07:47:23Z","timestamp":1747468043000},"page":"276-291","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Two Simple[st] Learning Tasks"],"prefix":"10.1007","author":[{"given":"Omrit","family":"Filtser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kien","family":"Huynh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anastasia","family":"Lemetti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph","family":"Mitchell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tatiana","family":"Polishchuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valentin","family":"Polishchuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,18]]},"reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"Afshani, P., Arge, L., Larsen, K.G.: Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model. In: Symposium on Computational Geometry, pp. 323\u2013332 (2012)","DOI":"10.1145\/2261250.2261299"},{"issue":"2","key":"18_CR2","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/1150334.1150338","volume":"2","author":"PK Agarwal","year":"2006","unstructured":"Agarwal, P.K., Aronov, B., Koltun, V.: Efficient algorithms for bichromatic separability. ACM Trans. Algorithms (TALG) 2(2), 209\u2013227 (2006)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Edelsbrunner, H., Schwarzkopf, O., Welzl, E.: Euclidean minimum spanning trees and bichromatic closest pairs. Discret. Comput. Geom. 6(5), 407\u2013422 (1991). Preliminary version: SoCG 1990","DOI":"10.1007\/BF02574698"},{"issue":"4","key":"18_CR4","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF01293483","volume":"13","author":"PK Agarwal","year":"1995","unstructured":"Agarwal, P.K., Matou\u0161ek, J.: Dynamic half-space range reporting and its applications. Algorithmica 13(4), 325\u2013345 (1995)","journal-title":"Algorithmica"},{"issue":"4","key":"18_CR5","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1145\/299917.299918","volume":"30","author":"PK Agarwal","year":"1998","unstructured":"Agarwal, P.K., Sharir, M.: Efficient algorithms for geometric optimization. ACM Comput. Surv. (CSUR) 30(4), 412\u2013458 (1998)","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"18_CR6","unstructured":"Aggarwal, C.C.: Data Classification: Algorithms and Applications. Chapman and Hall\/CRC (2014)"},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Antal, B.B., Chesebro, A.G., Strey, H.H., Mujica-Parodi, L.R., Weistuch, C.: Achieving occam\u2019s razor: deep learning for optimal model reduction (2023)","DOI":"10.1371\/journal.pcbi.1012283"},{"issue":"10\u201311","key":"18_CR8","doi-asserted-by":"publisher","first-page":"1441","DOI":"10.1016\/j.dam.2012.03.009","volume":"160","author":"B Aronov","year":"2012","unstructured":"Aronov, B., Garijo, D., N\u00fa\u00f1ez-Rodr\u00edguez, Y., Rappaport, D., Seara, C., Urrutia, J.: Minimizing the error of linear separators on linearly inseparable data. Discret. Appl. Math. 160(10\u201311), 1441\u20131452 (2012)","journal-title":"Discret. Appl. Math."},{"key":"18_CR9","unstructured":"Ben-Hur, A., Horn, D., Siegelmann, H.T., Vapnik, V.: Support vector clustering. J. Mach. Learn. Res. (2001)"},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"Bille, P., G\u00f8rtz, I.L., Stordalen, T.: Predecessor on the ultra-wide word ram. Algorithmica (2024)","DOI":"10.1007\/s00453-023-01193-1"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Bonawitz, E.B., Chang, I.Y., Clark, C., Lombrozo, T.: Ockham\u2019s razor as inductive bias in preschooler\u2019s causal explanations. In: 2008 7th IEEE International Conference on Development and Learning, pp. 7\u201312. IEEE (2008)","DOI":"10.1109\/DEVLRN.2008.4640797"},{"key":"18_CR12","unstructured":"Callahan, P.B., Kosaraju, S.R.: Faster algorithms for some geometric graph problems in higher dimensions. In: SODA, vol. 93, pp. 291\u2013300 (1993)"},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: On enumerating and selecting distances. In: Proceedings of the Fourteenth Annual Symposium on Computational Geometry, pp. 279\u2013286 (1998)","DOI":"10.1145\/276884.276916"},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Larsen, K.G., P\u0103tra\u015fcu, M.: Orthogonal range searching on the ram, revisited. In: Symposium on Computational Geometry, pp. 1\u201310 (2011)","DOI":"10.1145\/1998196.1998198"},{"key":"18_CR15","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Zheng, D.W.: Hopcroft\u2019s problem, log-star shaving, 2D fractional cascading, and decision trees. ACM Trans. Algorithms (2022)","DOI":"10.1137\/1.9781611977073.10"},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L.: More output-sensitive geometric algorithms. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 695\u2013702. IEEE (1994)","DOI":"10.1109\/SFCS.1994.365723"},{"issue":"3","key":"18_CR17","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/BF00994018","volume":"20","author":"C Cortes","year":"1995","unstructured":"Cortes, C., Vapnik, V.: Support-vector networks. Mach. Learn. 20(3), 273\u2013297 (1995)","journal-title":"Mach. Learn."},{"key":"18_CR18","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Lynch, J., Mirano, G.J., Tyagi, N.: Energy-efficient algorithms. In: ITCS 2016, pp. 321\u2013332 (2016)","DOI":"10.1145\/2840728.2840756"},{"key":"18_CR19","first-page":"373","volume":"19","author":"TK Dey","year":"1998","unstructured":"Dey, T.K.: Improved bounds for planar k-sets and related problems. DCG 19, 373\u2013382 (1998)","journal-title":"DCG"},{"key":"18_CR20","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1023\/A:1009868929893","volume":"3","author":"P Domingos","year":"1999","unstructured":"Domingos, P.: The role of occam\u2019s razor in knowledge discovery. Data Min. Knowl. Disc. 3, 409\u2013425 (1999)","journal-title":"Data Min. Knowl. Disc."},{"issue":"1","key":"18_CR21","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1137\/0215019","volume":"15","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Welzl, E.: Constructing belts in two-dimensional arrangements with applications. SIAM J. Comput. 15(1), 271\u2013284 (1986)","journal-title":"SIAM J. Comput."},{"key":"18_CR22","doi-asserted-by":"crossref","unstructured":"Eppstein, D.: Dynamic euclidean minimum spanning trees and extrema of binary functions In: DCG (1995)","DOI":"10.1007\/BF02574030"},{"key":"18_CR23","doi-asserted-by":"crossref","unstructured":"Eppstein, D.: Finding relevant points for nearest-neighbor classification. In: Symposium on Simplicity in Algorithms (SOSA), pp. 68\u201378. SIAM (2022)","DOI":"10.1137\/1.9781611977066.6"},{"key":"18_CR24","unstructured":"Esmeir, S., Markovitch, S.: Occam\u2019s razor just got sharper. In: IJCAI, pp. 768\u2013773. Citeseer (2007)"},{"key":"18_CR25","doi-asserted-by":"crossref","unstructured":"Ezugwu, A.E., et al.: A comprehensive survey of clustering algorithms: State-of-the-art machine learning applications, taxonomy, challenges, and future research prospects. Eng. Appl. Artif. Intell. (2022)","DOI":"10.1016\/j.engappai.2022.104743"},{"key":"18_CR26","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability. Feeman, San Francisco (1979)"},{"key":"18_CR27","unstructured":"Glazenburg, E., Staals, F., van Kreveld, M.: Robust classification of dynamic bichromatic point sets in R2. arXiv preprint arXiv:2406.19161 (2024)"},{"key":"18_CR28","unstructured":"Glazenburg, E., van\u00a0der Horst, T., Peters, T., Speckmann, B., Staals, F.: Robust bichromatic classification using two lines. arXiv preprint arXiv:2401.02897 (2024)"},{"key":"18_CR29","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T.: Geometric partitioning made easier, even in parallel. In: Proceedings of the Ninth Annual Symposium on Computational Geometry, pp. 73\u201382 (1993)","DOI":"10.1145\/160985.161002"},{"key":"18_CR30","volume-title":"Concrete Mathematics","author":"RL Graham","year":"1989","unstructured":"Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics. Addison-Wesley, Reading (1989)"},{"key":"18_CR31","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Koltun, V.: Separability with outliers. In: International Symposium on Algorithms and Computation, pp. 28\u201339. Springer, Cham (2005)","DOI":"10.1007\/11602613_5"},{"key":"18_CR32","doi-asserted-by":"crossref","unstructured":"Hershberger, J.: Stable snap rounding. CGTA (2013)","DOI":"10.1016\/j.comgeo.2012.02.011"},{"issue":"4","key":"18_CR33","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1002\/(SICI)1097-0037(199612)28:4<221::AID-NET6>3.0.CO;2-N","volume":"28","author":"DS Hochbaum","year":"1996","unstructured":"Hochbaum, D.S., Pathria, A.: The bottleneck graph partition problem. Networks 28(4), 221\u2013225 (1996)","journal-title":"Networks"},{"issue":"2","key":"18_CR34","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0166-218X(93)90057-U","volume":"45","author":"MF Houle","year":"1993","unstructured":"Houle, M.F.: Algorithms for weak and wide separation of sets. Discret. Appl. Math. 45(2), 139\u2013159 (1993)","journal-title":"Discret. Appl. Math."},{"key":"18_CR35","doi-asserted-by":"crossref","unstructured":"Kahan, S., Snoeyink, J.: On the bit complexity of minimum link paths: superquadratic algorithms for problems solvable in linear time. In: Symposium on Computational Geometry, pp. 151\u2013158 (1996)","DOI":"10.1145\/237218.237342"},{"issue":"5","key":"18_CR36","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1137\/S0097539794268649","volume":"26","author":"MJ Katz","year":"1997","unstructured":"Katz, M.J., Sharir, M.: An expander-based approach to geometric optimization. SIAM J. Comput. 26(5), 1384\u20131408 (1997)","journal-title":"SIAM J. Comput."},{"key":"18_CR37","volume-title":"The Computational Complexity of Machine Learning","author":"MJ Kearns","year":"1990","unstructured":"Kearns, M.J.: The Computational Complexity of Machine Learning. MIT Press, Cambridge (1990)"},{"issue":"3","key":"18_CR38","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3329863","volume":"15","author":"K Koiliaris","year":"2019","unstructured":"Koiliaris, K., Xu, C.: Faster pseudopolynomial time algorithms for subset sum. TALG 15(3), 1\u201320 (2019)","journal-title":"TALG"},{"key":"18_CR39","unstructured":"Kostitsyna, I., L\u00f6ffler, M., Polishchuk, V., Staals, F.: The complexity of minlink path problems. In: SGG 2016, pp. 1\u201316 (2016)"},{"issue":"9","key":"18_CR40","first-page":"65","volume":"2","author":"V Krishnaiah","year":"2014","unstructured":"Krishnaiah, V., Narsimha, G., Chandra, N.S.: Survey of classification techniques in data mining. Int. J. Comput. Sci. Eng. 2(9), 65\u201374 (2014)","journal-title":"Int. J. Comput. Sci. Eng."},{"issue":"4","key":"18_CR41","first-page":"446","volume":"6","author":"D Krznaric","year":"1999","unstructured":"Krznaric, D., Levcopoulos, C., Nilsson, B.J.: Minimum spanning trees in d dimensions. Nordic J. Comput. 6(4), 446\u2013461 (1999)","journal-title":"Nordic J. Comput."},{"issue":"1","key":"18_CR42","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1109\/TED.2018.2879821","volume":"66","author":"D Kwon","year":"2018","unstructured":"Kwon, D., et al.: Adaptive weight quantization method for nonlinear synaptic devices. IEEE Trans. Electron Devices 66(1), 395\u2013401 (2018)","journal-title":"IEEE Trans. Electron Devices"},{"issue":"4","key":"18_CR43","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra Jr","year":"1983","unstructured":"Lenstra, H.W., Jr.: Integer programming with a fixed number of variables. Math OR 8(4), 538\u2013548 (1983)","journal-title":"Math OR"},{"key":"18_CR44","doi-asserted-by":"crossref","unstructured":"Liu, F., Liu, C.: Towards accurate and high-speed spiking neuromorphic systems with data quantization-aware deep networks. In: Design Automation Conference, pp. 1\u20136 (2018)","DOI":"10.1145\/3195970.3196131"},{"issue":"2","key":"18_CR45","doi-asserted-by":"publisher","first-page":"1093","DOI":"10.1007\/s11135-023-01681-0","volume":"58","author":"C Mari","year":"2024","unstructured":"Mari, C., Mari, E.: Occam\u2019s razor, machine learning and stochastic modeling of complex systems: the case of the Italian energy market. Qual. Quant. 58(2), 1093\u20131111 (2024)","journal-title":"Qual. Quant."},{"key":"18_CR46","unstructured":"Matheny, M., Phillips, J.M.: Approximate maximum halfspace discrepancy. In: 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Schloss-Dagstuhl-Leibniz Zentrum f\u00fcr Informatik (2021)"},{"key":"18_CR47","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J.: Approximations and optimal geometric divide-and-conquer. In: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, pp. 505\u2013511 (1991)","DOI":"10.1145\/103418.103470"},{"issue":"1","key":"18_CR48","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N Megiddo","year":"1984","unstructured":"Megiddo, N.: Linear programming in linear time when the dimension is fixed. JACM 31(1), 114\u2013127 (1984)","journal-title":"JACM"},{"key":"18_CR49","doi-asserted-by":"crossref","unstructured":"Mertens, S.: The easiest hard problem: Number partitioning. In: Percus, A., Istrate, G., Moore, C. (eds.) Computational Complexity and Stat Physics. Oxford University Press (2006)","DOI":"10.1093\/oso\/9780195177374.003.0012"},{"issue":"7","key":"18_CR50","first-page":"6439","volume":"56","author":"GJ Oyewole","year":"2023","unstructured":"Oyewole, G.J., Thopil, G.A.: Data clustering: application and trends. AI Rev. 56(7), 6439\u20136475 (2023)","journal-title":"AI Rev."},{"key":"18_CR51","doi-asserted-by":"crossref","unstructured":"Packer, E.: Iterated snap rounding with bounded drift. In: Symposium on Computational Geometry, pp. 367\u2013376 (2006)","DOI":"10.1145\/1137856.1137910"},{"key":"18_CR52","unstructured":"Packer, E.: Controlled perturbation of sets of line segments in R2 with smart processing order. CGTA (2011)"},{"key":"18_CR53","unstructured":"Polya, G.: How to Solve It. Princeton Press (2004)"},{"key":"18_CR54","doi-asserted-by":"crossref","unstructured":"Rockett, A.M., et\u00a0al.: Continued Fractions. World Scientific (1992)","DOI":"10.1142\/1725"},{"issue":"1","key":"18_CR55","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/0020-0190(89)90166-X","volume":"30","author":"JS Salowe","year":"1989","unstructured":"Salowe, J.S.: L-infinity interdistance selection by parametric search. Inf. Process. Lett. 30(1), 9\u201314 (1989)","journal-title":"Inf. Process. Lett."},{"key":"18_CR56","unstructured":"Seara, C.: On geometric separability. Ph.D. thesis, Universitat Polit\u00e8cnica de Catalunya, Barcelona (2002)"},{"key":"18_CR57","doi-asserted-by":"crossref","unstructured":"Song, C., Liu, B., Wen, W., Li, H., Chen, Y.: A quantization-aware regularized learning method in multilevel memristor-based neuromorphic computing system. In: NVMSA, pp. 1\u20136 (2017)","DOI":"10.1109\/NVMSA.2017.8064465"},{"key":"18_CR58","unstructured":"https:\/\/math.stackexchange.com\/questions\/2086285\/did-p%C3%B3lya-say-can-or-cannot"},{"key":"18_CR59","unstructured":"Sun, K., Nielsen, F.: A geometric modeling of occam\u2019s razor in deep learning. arXiv preprint arXiv:1905.11027 (2019)"},{"key":"18_CR60","doi-asserted-by":"crossref","unstructured":"Van\u00a0Engelen, J.E., Hoos, H.H.: A survey on semi-supervised learning. Mach. Learn. (2020)","DOI":"10.1007\/s10994-019-05855-6"},{"key":"18_CR61","unstructured":"Wang, H.: Unit-disk range searching and applications. In: Czumaj, A., Xin, Q. (eds.) 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), vol. 227, pp. 32:1\u201332:17, Dagstuhl, Germany (2022). Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik"},{"key":"18_CR62","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1613\/jair.228","volume":"4","author":"GI Webb","year":"1996","unstructured":"Webb, G.I.: Further experimental evidence against the utility of occam\u2019s razor. J. Artif. Intell. Res. 4, 397\u2013417 (1996)","journal-title":"J. Artif. Intell. Res."},{"key":"18_CR63","doi-asserted-by":"crossref","unstructured":"Yang, Q., Li, H., Wu, Q.: A quantized training method to enhance accuracy of reram-based neuromorphic systems. In: ISCAS, pp. 1\u20135. IEEE (2018)","DOI":"10.1109\/ISCAS.2018.8351327"},{"key":"18_CR64","volume-title":"Introduction to Semi-supervised Learning","author":"X Zhu","year":"2022","unstructured":"Zhu, X., Goldberg, A.B.: Introduction to Semi-supervised Learning. Springer, Cham (2022)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-92932-8_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T07:47:39Z","timestamp":1747468059000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-92932-8_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031929311","9783031929328"],"references-count":64,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-92932-8_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"18 May 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rome","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/easyconferences.eu\/ciac2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}