{"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":1747541050948,"version":"3.40.5"},"publisher-location":"Cham","reference-count":30,"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_11","type":"book-chapter","created":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T07:47:21Z","timestamp":1747468041000},"page":"153-169","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Certifying Algorithms for\u00a0Linear Classification"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9038-6901","authenticated-orcid":false,"given":"Vincenzo","family":"Bonifaci","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-6643-727X","authenticated-orcid":false,"given":"Sara","family":"Galatro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,18]]},"reference":[{"issue":"2","key":"11_CR1","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s00454-020-00172-5","volume":"64","author":"K Adiprasito","year":"2020","unstructured":"Adiprasito, K., B\u00e1r\u00e1ny, I., Mustafa, N.H., Terpai, T.: Theorems of Carath\u00e9odory, Helly, and Tverberg without dimension. Discrete Comput. Geom. 64(2), 233\u2013258 (2020). https:\/\/doi.org\/10.1007\/s00454-020-00172-5","journal-title":"Discrete Comput. Geom."},{"key":"11_CR2","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley (1974)"},{"issue":"6","key":"11_CR3","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1524\/itit.2011.0655","volume":"53","author":"E Alkassar","year":"2011","unstructured":"Alkassar, E., B\u00f6hme, S., Mehlhorn, K., Rizkallah, C., Schweitzer, P.: An introduction to certifying algorithms. it - Inf. Technol. 53(6), 287\u2013293 (2011). https:\/\/doi.org\/10.1524\/itit.2011.0655","journal-title":"it - Inf. Technol."},{"issue":"3","key":"11_CR4","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1137\/15M1050574","volume":"47","author":"S Barman","year":"2018","unstructured":"Barman, S.: Approximating Nash equilibria and dense subgraphs via an approximate version of Carath\u00e9odory\u2019s theorem. SIAM J. Comput. 47(3), 960\u2013981 (2018). https:\/\/doi.org\/10.1137\/15M1050574","journal-title":"SIAM J. Comput."},{"issue":"1","key":"11_CR5","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1145\/200836.200880","volume":"42","author":"M Blum","year":"1995","unstructured":"Blum, M., Kannan, S.: Designing programs that check their work. J. ACM 42(1), 269\u2013291 (1995). https:\/\/doi.org\/10.1145\/200836.200880","journal-title":"J. ACM"},{"key":"11_CR6","doi-asserted-by":"publisher","unstructured":"Boser, B.E., Guyon, I., Vapnik, V.: A training algorithm for optimal margin classifiers. In: Haussler, D. (ed.) Proceedings of the Fifth Annual ACM Conference on Computational Learning Theory, COLT 1992, Pittsburgh, PA, USA, July 27-29, 1992, pp. 144\u2013152. ACM (1992). https:\/\/doi.org\/10.1145\/130385.130401","DOI":"10.1145\/130385.130401"},{"issue":"1","key":"11_CR7","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BF01449883","volume":"64","author":"C Carath\u00e9odory","year":"1907","unstructured":"Carath\u00e9odory, C.: \u00dcber den Variabilit\u00e4tsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen. Math. Ann. 64(1), 95\u2013115 (1907). https:\/\/doi.org\/10.1007\/BF01449883","journal-title":"Math. Ann."},{"key":"11_CR8","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd Edition. MIT Press, Cambridge (2009). http:\/\/mitpress.mit.edu\/books\/introduction-algorithms"},{"issue":"3","key":"11_CR9","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1109\/PGEC.1965.264137","volume":"14","author":"TM Cover","year":"1965","unstructured":"Cover, T.M.: Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE Trans. Electron. Comput. 14(3), 326\u2013334 (1965). https:\/\/doi.org\/10.1109\/PGEC.1965.264137","journal-title":"IEEE Trans. Electron. Comput."},{"key":"11_CR10","unstructured":"Dhiflaoui, M., et al.: Certifying and repairing solutions to large LPs \u2013 How good are LP-solvers? In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA. pp. 255\u2013256. ACM\/SIAM (2003). http:\/\/dl.acm.org\/citation.cfm?id=644108.644152"},{"key":"11_CR11","doi-asserted-by":"publisher","unstructured":"Georgiadis, L., Tarjan, R.E.: Dominator tree certification and divergent spanning trees. ACM Trans. Algorithms 12(1), 11:1\u201311:42 (2016). https:\/\/doi.org\/10.1145\/2764913","DOI":"10.1145\/2764913"},{"key":"11_CR12","doi-asserted-by":"publisher","unstructured":"Haghighatkhah, P., Meulemans, W., Speckmann, B., Urhausen, J., Verbeek, K.: Obstructing classification via projection. In: Bonchi, F., Puglisi, S.J. (eds.) 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0202, pp. 56:1\u201356:19. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2021). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2021.56","DOI":"10.4230\/LIPIcs.MFCS.2021.56"},{"key":"11_CR13","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/BF01445182","volume":"57","author":"P Kirchberger","year":"1903","unstructured":"Kirchberger, P.: \u00dcber Tchebychefsche Ann\u00e4herungsmethoden. Math. Ann. 57, 509\u2013540 (1903). https:\/\/doi.org\/10.1007\/BF01445182","journal-title":"Math. Ann."},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/BF01594942","volume":"50","author":"M Kojima","year":"1991","unstructured":"Kojima, M., Mizuno, S., Yoshise, A.: An $${O}(\\sqrt{n} {L})$$ iteration potential reduction algorithm for linear complementarity problems. Math. Program. 50, 331\u2013342 (1991). https:\/\/doi.org\/10.1007\/BF01594942","journal-title":"Math. Program."},{"issue":"2","key":"11_CR15","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1137\/S0097539703437855","volume":"36","author":"D Kratsch","year":"2006","unstructured":"Kratsch, D., McConnell, R.M., Mehlhorn, K., Spinrad, J.P.: Certifying algorithms for recognizing interval graphs and permutation graphs. SIAM J. Comput. 36(2), 326\u2013353 (2006). https:\/\/doi.org\/10.1137\/S0097539703437855","journal-title":"SIAM J. Comput."},{"issue":"10","key":"11_CR16","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1145\/3233231","volume":"61","author":"ZC Lipton","year":"2018","unstructured":"Lipton, Z.C.: The mythos of model interpretability. Commun. ACM 61(10), 36\u201343 (2018). https:\/\/doi.org\/10.1145\/3233231","journal-title":"Commun. ACM"},{"key":"11_CR17","doi-asserted-by":"crossref","unstructured":"Mangasarian, O.L.: Linear and nonlinear separation of patterns by linear programming. Oper. Res. 13(3), 444\u2013452 (1965). https:\/\/www.jstor.org\/stable\/167808","DOI":"10.1287\/opre.13.3.444"},{"key":"11_CR18","volume-title":"Understanding and Using Linear Programming","author":"J Matou\u0161ek","year":"2007","unstructured":"Matou\u0161ek, J., G\u00e4rtner, B.: Understanding and Using Linear Programming. Springer, Heidelberg (2007)"},{"issue":"2","key":"11_CR19","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.cosrev.2010.09.009","volume":"5","author":"RM McConnell","year":"2011","unstructured":"McConnell, R.M., Mehlhorn, K., N\u00e4her, S., Schweitzer, P.: Certifying algorithms. Comput. Sci. Rev. 5(2), 119\u2013161 (2011). https:\/\/doi.org\/10.1016\/j.cosrev.2010.09.009","journal-title":"Comput. Sci. Rev."},{"key":"11_CR20","unstructured":"Mehlhorn, K., N\u00e4her, S.: LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (1999). http:\/\/www.mpi-sb.mpg.de\/%7Emehlhorn\/LEDAbook.html"},{"key":"11_CR21","unstructured":"Mirrokni, V.S., Leme, R.P., Vladu, A., Wong, S.C.: Tight bounds for approximate Carath\u00e9odory and beyond. In: Precup, D., Teh, Y.W. (eds.) Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017. Proceedings of Machine Learning Research, vol.\u00a070, pp. 2440\u20132448. PMLR (2017). http:\/\/proceedings.mlr.press\/v70\/mirrokni17a.html"},{"key":"11_CR22","unstructured":"Mohri, M., Rostamizadeh, A., Talwalkar, A.: Foundations of Machine Learning. Adaptive Computation and Machine Learning, MIT Press, Cambridge (2012)"},{"issue":"1\u20133","key":"11_CR23","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/BF01587075","volume":"44","author":"R Monteiro","year":"1989","unstructured":"Monteiro, R., Adler, I.: Interior path following primal-dual algorithms. Part I: Linear Program. Math. Program. 44(1\u20133), 27\u201341 (1989). https:\/\/doi.org\/10.1007\/BF01587075","journal-title":"Part I: Linear Program. Math. Program."},{"issue":"1","key":"11_CR24","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0022-247X(65)90150-2","volume":"10","author":"JB Rosen","year":"1965","unstructured":"Rosen, J.B.: Pattern separation by convex programming. J. Math. Anal. Appl. 10(1), 123\u2013134 (1965). https:\/\/doi.org\/10.1016\/0022-247X(65)90150-2","journal-title":"J. Math. Anal. Appl."},{"issue":"2","key":"11_CR25","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1137\/110848311","volume":"42","author":"JM Schmidt","year":"2013","unstructured":"Schmidt, J.M.: Contractions, removals, and certifying 3-connectivity in linear time. SIAM J. Comput. 42(2), 494\u2013535 (2013). https:\/\/doi.org\/10.1137\/110848311","journal-title":"SIAM J. Comput."},{"key":"11_CR26","unstructured":"Schrijver, A.: Combinatorial Optimization. Springer (2004)"},{"issue":"7","key":"11_CR27","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/3503914","volume":"65","author":"SA Seshia","year":"2022","unstructured":"Seshia, S.A., Sadigh, D., Sastry, S.S.: Toward verified artificial intelligence. Commun. ACM 65(7), 46\u201355 (2022). https:\/\/doi.org\/10.1145\/3503914","journal-title":"Commun. ACM"},{"key":"11_CR28","doi-asserted-by":"publisher","unstructured":"Vershynin, R.: High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge (2018). https:\/\/doi.org\/10.1017\/9781108231596","DOI":"10.1017\/9781108231596"},{"issue":"2","key":"11_CR29","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1017\/S1446788700012957","volume":"15","author":"D Watson","year":"1973","unstructured":"Watson, D.: A refinement of theorems of Kirchberger and Carath\u00e9odory. J. Aust. Math. Soc. 15(2), 190\u2013192 (1973). https:\/\/doi.org\/10.1017\/S1446788700012957","journal-title":"J. Aust. Math. Soc."},{"issue":"1","key":"11_CR30","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0022-247X(83)90286-X","volume":"92","author":"RJ Webster","year":"1983","unstructured":"Webster, R.J.: Another simple proof of Kirchberger\u2019s theorem. J. Math. Anal. Appl. 92(1), 299\u2013300 (1983). https:\/\/doi.org\/10.1016\/0022-247X(83)90286-X","journal-title":"J. Math. Anal. Appl."}],"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_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T07:47:29Z","timestamp":1747468049000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-92932-8_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031929311","9783031929328"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-92932-8_11","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":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"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"}}]}}