{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T22:05:17Z","timestamp":1779919517731,"version":"3.53.1"},"publisher-location":"Cham","reference-count":48,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031863189","type":"print"},{"value":"9783031863196","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-86319-6_11","type":"book-chapter","created":{"date-parts":[[2025,8,5]],"date-time":"2025-08-05T03:01:57Z","timestamp":1754362917000},"page":"125-146","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Polynomial Threshold Functions of Bounded Tree-Width: Some Explainability and Complexity Aspects"],"prefix":"10.1007","author":[{"given":"Karine","family":"Chubarian","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Johnny","family":"Joyce","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gy\u00f6rgy","family":"Tur\u00e1n","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,3,8]]},"reference":[{"issue":"4","key":"11_CR1","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1145\/31846.31852","volume":"34","author":"M Ajtai","year":"1987","unstructured":"Ajtai, M., Gurevich, Y.: Monotone versus positive. J. ACM 34(4), 1004\u20131015, 1987.","journal-title":"J. ACM"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Ankan, A., Panda, A.: pgmpy: probabilistic graphical models using Python. In: Proceedings of the 14th Python in Science Conference (SciPy 2015), vol. 10. Citeseer (2015)","DOI":"10.25080\/Majora-7b98e3ed-001"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Barrington, D.A.M.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC$${^1}$$. J. Comput. Syst. Sci. 38(1), 150\u2013164 (1989)","DOI":"10.1016\/0022-0000(89)90037-8"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Caruana, R., Lou, Y., Gehrke, J., Koch, P., Sturm, M., Elhadad, N.: Intelligible models for healthcare: Predicting pneumonia risk and hospital 30-day readmission. In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1721\u20131730. ACM (2015)","DOI":"10.1145\/2783258.2788613"},{"key":"11_CR5","unstructured":"Chan, H., Darwiche, A.: Reasoning about Bayesian network classifiers. In: UAI \u201903, Proceedings of the 19th Conference in Uncertainty in Artificial Intelligence, pp. 107\u2013115 (2003)"},{"key":"11_CR6","unstructured":"Chubarian, K., Tur\u00e1n, G.: Approximating bounded tree-width Bayesian network classifiers with OBDD. In: Proceedings of Machine Learning Research, vol. 138, pp. 113\u2013124. PMLR (2020)"},{"issue":"1\u20132","key":"11_CR7","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/S0166-218X(00)00221-3","volume":"108","author":"B Courcelle","year":"2001","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discret. Appl. Math. 108(1\u20132), 23\u201352 (2001)","journal-title":"Discret. Appl. Math."},{"key":"11_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511811357","volume-title":"Modeling and Reasoning with Bayesian Networks","author":"A Darwiche","year":"2009","unstructured":"Darwiche, A.: Modeling and Reasoning with Bayesian Networks. Cambridge University Press, Cambridge (2009)"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"Darwiche, A.: Logic for Explainable AI. In 38th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS, pp. 1\u201311. IEEE (2023)","DOI":"10.1109\/LICS56636.2023.10175757"},{"key":"11_CR10","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1613\/jair.989","volume":"17","author":"A Darwiche","year":"2002","unstructured":"Darwiche, A., Marquis, P.: A knowledge compilation map. J. Artif. Intell. Res. 17, 229\u2013264 (2002)","journal-title":"J. Artif. Intell. Res."},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"De, A., Diakonikolas, I., Servedio, R.A.: Deterministic approximate counting for degree-2 polynomial threshold functions (2013). CoRR, abs\/1311.7105","DOI":"10.1109\/CCC.2014.31"},{"key":"11_CR12","first-page":"3158","volume":"2023","author":"A de Colnet","year":"2023","unstructured":"de Colnet, A., Marquis, P.: On translations between ML models for XAI purposes. In: Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, pp. 3158\u20133166 (2023)","journal-title":"In: Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI"},{"key":"11_CR13","first-page":"1834","volume":"2020","author":"A de Colnet","year":"2020","unstructured":"de Colnet, A., Mengel, S.: Lower bounds for approximate knowledge compilation. In: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pp. 1834\u20131840 (2020)","journal-title":"In: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI"},{"issue":"4","key":"11_CR14","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1016\/j.dam.2006.06.020","volume":"156","author":"E Fischer","year":"2008","unstructured":"Fischer, E., Makowsky, J.A., Ravve, E.V.: Counting truth assignments of formulas of bounded tree-width or clique-width. Discret. Appl. Math. 156(4),, 511\u2013529 (2008)","journal-title":"Discret. Appl. Math."},{"issue":"2\u20133","key":"11_CR15","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1023\/A:1007465528199","volume":"29","author":"N Friedman","year":"1997","unstructured":"Friedman, N., Geiger, D., Goldszmidt, M.: Bayesian network classifiers. Mach. Learn. 29(2\u20133), 131\u2013163 (1997)","journal-title":"Mach. Learn."},{"key":"11_CR16","first-page":"817","volume":"2011","author":"P Gopalan","year":"2011","unstructured":"Gopalan, P., Klivans, A.R., Meka, R., Stefankovic, D., Vempala, S., Vigoda,. E.: An FPTAS for #knapsack and related counting problems. In: IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pp. 817\u2013826 (2011)","journal-title":"FOCS"},{"key":"11_CR17","unstructured":"Hagberg, A., Swart, P., Chult, D.S.: Exploring network structure, dynamics, and function using NetworkX. Technical Report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States), 2008"},{"key":"11_CR18","doi-asserted-by":"crossref","unstructured":"Hajnal, P., Liu, Z., Tur\u00e1n, G.: Nearest neighbor representations of Boolean functions. Inf. Comput. 285(Part), 104879 (2022)","DOI":"10.1016\/j.ic.2022.104879"},{"key":"11_CR19","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.ic.2014.09.008","volume":"240","author":"KA Hansen","year":"2015","unstructured":"Hansen, K.A., Podolskii, V.V.: Polynomial threshold functions and Boolean threshold circuits. Inf. Comput. 240, 56\u201373 (2015)","journal-title":"Inf. Comput."},{"issue":"3","key":"11_CR20","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1093\/comjnl\/bxm052","volume":"51","author":"P Hlinen\u00fd","year":"2008","unstructured":"Hlinen\u00fd, P., Oum, S., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. Comput. J. 51(3), 326\u2013362 (2008)","journal-title":"Comput. J."},{"issue":"1\u20132","key":"11_CR21","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0304-3975(97)83807-8","volume":"180","author":"K Hosaka","year":"1997","unstructured":"Hosaka, K., Takenaga, Y., Kaneda, T., Yajima, S.: Size of ordered binary decision diagrams representing threshold functions. Theor. Comput. Sci. 180(1\u20132), 47\u201360 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Jukna, S.: Boolean Function Complexity - Advances and Frontiers. Algorithms and Combinatorics, vol. 27. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-24508-4"},{"issue":"6","key":"11_CR23","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0020-0190(92)90234-M","volume":"42","author":"NG Kinnersley","year":"1992","unstructured":"Kinnersley, N.G.: The vertex separation number of a graph equals its path-width. Inf. Process. Lett. 42(6), 345\u2013350 (1992)","journal-title":"Inf. Process. Lett."},{"key":"11_CR24","volume-title":"Probabilistic Graphical Models - Principles and Techniques","author":"D Koller","year":"2009","unstructured":"Koller, D., Friedman, N.: Probabilistic Graphical Models - Principles and Techniques. MIT Press, Cambridge (2009)"},{"issue":"1","key":"11_CR25","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0166-218X(93)90171-J","volume":"43","author":"E Korach","year":"1993","unstructured":"Korach, E., Solel, N.: Tree-width, path-width, and cutwidth. Discret. Appl. Math. 43(1), 97\u2013101 (1993)","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"11_CR26","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1007\/s000370050015","volume":"7","author":"M Krause","year":"1998","unstructured":"Krause, M., Pudl\u00e1k, P.: Computing Boolean functions by polynomials and threshold circuits. Comput. Complex. 7(4), 346\u2013370 (1998)","journal-title":"Comput. Complex."},{"issue":"2","key":"11_CR27","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1017\/S026988890200019X","volume":"17","author":"C Lacave","year":"2002","unstructured":"Lacave, C., D\u00edez, F.J.: A review of explanation methods for Bayesian networks. Knowl. Eng. Rev. 17(2), 107\u2013127 (2002)","journal-title":"Knowl. Eng. Rev."},{"issue":"10","key":"11_CR28","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)","journal-title":"Commun. ACM"},{"key":"11_CR29","doi-asserted-by":"crossref","unstructured":"Lou, Y., Caruana, R., Gehrke, J.: Intelligible models for classification and regression. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 150\u2013158 (2012)","DOI":"10.1145\/2339530.2339556"},{"key":"11_CR30","first-page":"623","volume":"2013","author":"Y Lou","year":"2013","unstructured":"Lou, Y., Caruana, R., Gehrke, J., Hooker, G.: Accurate intelligible models with pairwise interactions. In: The 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013, pp. 623\u2013631 (2013)","journal-title":"KDD"},{"key":"11_CR31","unstructured":"Madre, J.C., Coudert, O.: A logically complete reasoning maintenance system based on a logical constraint solver. In: Proceedings of the 12th International Joint Conference on Artificial Intelligence, pp. 294\u2013299 (1991)"},{"key":"11_CR32","doi-asserted-by":"crossref","unstructured":"Makowsky, J., Meer, K.: Polynomials of bounded tree-width. In: Formal Power Series and Algebraic Combinatorics, pp. 692\u2013703. Springer, Berlin (2000)","DOI":"10.1007\/978-3-662-04166-6_68"},{"key":"11_CR33","first-page":"211","volume-title":"Foundations of Computational Mathematics, Proceedings of the Smalefest 2000","author":"JA Makowsky","year":"2002","unstructured":"Makowsky, J.A., Meer, K.: Polynomials of bounded tree-width. In: Cucker, F., Rojas, M. (eds.) Foundations of Computational Mathematics, Proceedings of the Smalefest 2000, pp. 211\u2013250. World Scientific, Singapore (2002)"},{"key":"11_CR34","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1109\/JRPROC.1961.287775","volume":"49","author":"M Minsky","year":"1961","unstructured":"Minsky, M.: Steps toward artificial intelligence. Proc. IRE 49, 8\u201330 (1961)","journal-title":"Proc. IRE"},{"key":"11_CR35","unstructured":"Molnar, C.: Interpretable Machine Learning: A Guide for Making Black Box Models Explainable, 2nd edn. Lulu.com (2022). https:\/\/christophm.github.io\/interpretable-ml-book"},{"key":"11_CR36","unstructured":"Nori, H., Jenkins, S., Koch, P., Caruana, R.: InterpretML: A unified framework for machine learning interpretability (2019). CoRR, abs\/1909.09223"},{"key":"11_CR37","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782","volume-title":"Analysis of Boolean Functions","author":"R O\u2019Donnell","year":"2014","unstructured":"O\u2019Donnell, R.: Analysis of Boolean Functions. Cambridge University Press, Cambridge (2014)"},{"issue":"3","key":"11_CR38","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1016\/j.jcss.2007.06.021","volume":"74","author":"R O\u2019Donnell","year":"2008","unstructured":"O\u2019Donnell, R., Servedio, R.A.: Extremal properties of polynomial threshold functions. J. Comput. Syst. Sci. 74(3), 298\u2013312 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"11_CR39","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1137\/0204027","volume":"4","author":"VR Pratt","year":"1975","unstructured":"Pratt, V.R.: The power of negative thinking in multiplying Boolean matrices. SIAM J. Comput. 4(3), 326\u2013330 (1975)","journal-title":"SIAM J. Comput."},{"key":"11_CR40","first-page":"887","volume":"37","author":"AA Razborov","year":"1985","unstructured":"Razborov, A.A.: A lower bound for the monotone network complexity of the logical permanent. Mat. Zametki 37, 887\u2013900 (1985)","journal-title":"Mat. Zametki"},{"key":"11_CR41","first-page":"798","volume":"281","author":"AA Razborov","year":"1985","unstructured":"Razborov, A.A.: Lower bounds on the monotone complexity of some Boolean functions. Doklady Akademii Nauk SSSR 281, 798\u2013801 (1985)","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"11_CR42","unstructured":"Servedio, R.A., Tan, L.-Y.: Deterministic approximate counting of polynomial threshold functions via a derandomized regularity lemma. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2021. LIPIcs, vol. 207, pp. 37:1\u201337:18 (2021)"},{"issue":"12","key":"11_CR43","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0082349","volume":"8","author":"MB Sesen","year":"2013","unstructured":"Sesen, M.B., Nicholson, A.E., Banares-Alcantara, R., Kadir, T., Brady, M.: Bayesian networks for clinical decision support in lung cancer care. PloS One 8(12), e82349 (2013)","journal-title":"PloS One"},{"key":"11_CR44","first-page":"3936","volume":"2016","author":"Y Shen","year":"2016","unstructured":"Shen, Y., Choi, A., Darwiche, A.: Tractable operations for arithmetic circuits of probabilistic models. In: NIPS, 2016, pp. 3936\u20133944 (2016)","journal-title":"In: NIPS"},{"key":"11_CR45","doi-asserted-by":"crossref","unstructured":"Shortliffe, E.H.: A rule-based computer program for advising physicians regarding antimicrobial therapy selection. In: Proceedings of the 1974 ACM Annual Conference, p. 739. ACM (1974)","DOI":"10.1145\/1408800.1408906"},{"issue":"1","key":"11_CR46","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF02122563","volume":"8","author":"\u00c9 Tardos","year":"1988","unstructured":"Tardos, \u00c9.: The gap between monotone and non-monotone circuit complexity is exponential. Combinatorica 8(1), 141\u2013142 (1988)","journal-title":"Combinatorica"},{"key":"11_CR47","first-page":"2725","volume":"16","author":"G Varando","year":"2015","unstructured":"Varando, G., Bielza, C., Larra\u00f1aga, P.: Decision boundary for discrete Bayesian network classifiers. J. Mach. Learn. Res. 16, 2725\u20132749 (2015)","journal-title":"J. Mach. Learn. Res."},{"key":"11_CR48","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719789","volume-title":"Branching Programs and Binary Decision Diagrams","author":"I Wegener","year":"2000","unstructured":"Wegener, I.: Branching Programs and Binary Decision Diagrams. SIAM, Philadelphia (2000)"}],"container-title":["Trends in Mathematics","Model Theory, Computer Science, and Graph Polynomials"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-86319-6_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T21:28:55Z","timestamp":1779917335000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-86319-6_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031863189","9783031863196"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-86319-6_11","relation":{},"ISSN":["2297-0215","2297-024X"],"issn-type":[{"value":"2297-0215","type":"print"},{"value":"2297-024X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"8 March 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}