{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T00:11:14Z","timestamp":1756858274483,"version":"3.44.0"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","funder":[{"name":"Luxembourg National Research Fund (FNR)","award":["INTER\/FNRS\/2-0\/1507-7233\/Scaling Up Variability\/Cordy, C23\/IS\/18177547\/VARIANCE, and AFR Grant 17047437"],"award-info":[{"award-number":["INTER\/FNRS\/2-0\/1507-7233\/Scaling Up Variability\/Cordy, C23\/IS\/18177547\/VARIANCE, and AFR Grant 17047437"]}]},{"DOI":"10.13039\/501100002661","name":"Fonds De La Recherche Scientifique - FNRS","doi-asserted-by":"publisher","award":[""],"award-info":[{"award-number":[""]}],"id":[{"id":"10.13039\/501100002661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,9]]},"DOI":"10.1145\/3744915.3748473","type":"proceedings-article","created":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T14:54:43Z","timestamp":1756565683000},"page":"149-160","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Exploring the Computational Complexity of Uniform Random Sampling and SAT Counting with Phase Transitions"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0378-5643","authenticated-orcid":false,"given":"Olivier","family":"Zeyen","sequence":"first","affiliation":[{"name":"Interdisciplinary Centre for Security, Reliability and Trust, Univirsity of Luxembourg, Luxembourg, Luxembourg"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8312-1358","authenticated-orcid":false,"given":"Maxime","family":"Cordy","sequence":"additional","affiliation":[{"name":"Interdisciplinary Centre for Security, Reliability and Trust, University of Luxembourg, Luxembourg, Luxembourg"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8431-0377","authenticated-orcid":false,"given":"Gilles","family":"Perrouin","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science, PReCISE, University of Namur, Namur, Belgium"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1483-3858","authenticated-orcid":false,"given":"Mathieu","family":"Acher","sequence":"additional","affiliation":[{"name":"INSA, Univ Rennes, Inria, CNRS, IRISA, Rennes, France"}]}],"member":"320","published-online":{"date-parts":[[2025,8,31]]},"reference":[{"key":"e_1_3_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3461002.3473070"},{"key":"e_1_3_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-94144-8_9"},{"key":"e_1_3_3_1_4_2","doi-asserted-by":"publisher","unstructured":"Tasniem\u00a0Nasser Alyahya Mohamed El\u00a0Bachir Menai and Hassan Mathkour. 2022. On the Structure of the Boolean Satisfiability Problem: A Survey. ACM Comput. Surv. 55 3 Article 46 (mar 2022) 34\u00a0pages.10.1145\/3491210","DOI":"10.1145\/3491210"},{"key":"e_1_3_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31612-8_31"},{"key":"e_1_3_3_1_6_2","first-page":"157","volume-title":"AAAI\/IAAI","author":"Bayardo\u00a0Jr Roberto\u00a0J","year":"2000","unstructured":"Roberto\u00a0J Bayardo\u00a0Jr and Joseph\u00a0Daniel Pehoushek. 2000. Counting models using connected components. In AAAI\/IAAI. 157\u2013162."},{"key":"e_1_3_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/11431855_34"},{"key":"e_1_3_3_1_8_2","doi-asserted-by":"crossref","unstructured":"Elazar Birnbaum and Eliezer\u00a0L Lozinskii. 1999. The good old Davis-Putnam procedure helps counting models. Journal of Artificial Intelligence Research 10 (1999) 457\u2013477.","DOI":"10.1613\/jair.601"},{"key":"e_1_3_3_1_9_2","doi-asserted-by":"crossref","unstructured":"Ulrik Brandes Daniel Delling Marco Gaertler Robert G\u00f6rke Martin Hoefer Zoran Nikoloski and Dorothea Wagner. 2008. On Modularity Clustering. IEEE Transactions on Knowledge and Data Engineering 20 (2008) 172\u2013188.","DOI":"10.1109\/TKDE.2007.190689"},{"key":"e_1_3_3_1_10_2","doi-asserted-by":"crossref","unstructured":"Shaowei Cai Chuan Luo and Kaile Su. 2014. Scoring Functions Based on Second Level Score for k-SAT with Long Clauses. J. Artif. Intell. Res. 51 (2014) 413\u2013441. https:\/\/api.semanticscholar.org\/CorpusID:16385185","DOI":"10.1613\/jair.4480"},{"key":"e_1_3_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46681-0_25"},{"key":"e_1_3_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2593069.2593097"},{"key":"e_1_3_3_1_13_2","doi-asserted-by":"crossref","unstructured":"Sheng Chen and Martin Erwig. 2011. Optimizing the Product Derivation Process. 2011 15th International Software Product Line Conference (2011) 35\u201344.","DOI":"10.1109\/SPLC.2011.47"},{"key":"e_1_3_3_1_14_2","doi-asserted-by":"crossref","unstructured":"Gilles Dequen and Olivier Dubois. 2006. An Efficient Approach to Solving Random k-SAT Problems. Journal of Automated Reasoning 37 (2006) 261\u2013276. https:\/\/api.semanticscholar.org\/CorpusID:25414864","DOI":"10.1007\/s10817-006-9025-2"},{"key":"e_1_3_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3180155.3180248"},{"key":"e_1_3_3_1_16_2","first-page":"502","volume-title":"SAT\u201903","author":"E\u00e9n Niklas","year":"2003","unstructured":"Niklas E\u00e9n and Niklas S\u00f6rensson. 2003. An Extensible SAT-solver. In SAT\u201903.Springer, 502\u2013518."},{"key":"e_1_3_3_1_17_2","unstructured":"Guillaume Escamocher and Barry O\u2019Sullivan. 2022. Generation and Prediction of Difficult Model Counting Instances. ArXiv abs\/2212.02893 (2022)."},{"key":"e_1_3_3_1_18_2","doi-asserted-by":"crossref","unstructured":"Johannes\u00a0Klaus Fichte Markus Hecher and Florim Hamiti. 2020. The Model Counting Competition 2020. Journal of Experimental Algorithmics (JEA) 26 (2020) 1\u201326.","DOI":"10.1145\/3459080"},{"key":"e_1_3_3_1_19_2","first-page":"547\u2014563","volume-title":"Beyond the worst-case analysis of algorithms","author":"Ganesh Vijay","year":"2021","unstructured":"Vijay Ganesh and Moshe\u00a0Y. Vardi. 2021. On The Unreasonable Effectiveness of SAT Solvers. In Beyond the worst-case analysis of algorithms,Tim Roughgarden (Ed.).Cambridge University Press, 547\u2014563."},{"key":"e_1_3_3_1_20_2","doi-asserted-by":"crossref","unstructured":"Jian Gao Ruizhi Li and Minghao Yin. 2017. A randomized diversification strategy for solving satisfiability problem with long clauses. Science China Information Sciences 60 (2017) 1\u201311. https:\/\/api.semanticscholar.org\/CorpusID:13219850","DOI":"10.1007\/s11432-016-0258-4"},{"key":"e_1_3_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-21581-0_31"},{"key":"e_1_3_3_1_22_2","first-page":"105","volume-title":"European Conference on Artificial Intelligence","volume":"94","author":"Gent Ian\u00a0P.","year":"1994","unstructured":"Ian\u00a0P. Gent and Toby Walsh. 1994. The SAT Phase Transition. In European Conference on Artificial Intelligence, Vol.\u00a094. PITMAN, 105\u2013109."},{"key":"e_1_3_3_1_23_2","volume-title":"International Joint Conference on Artificial Intelligence","author":"Gir\u00e1ldez-Cru Jes\u00fas","year":"2015","unstructured":"Jes\u00fas Gir\u00e1ldez-Cru and Jordi Levy. 2015. A Modularity-Based Random SAT Instances Generator. In International Joint Conference on Artificial Intelligence.AAAI Press."},{"key":"e_1_3_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-58475-7_21"},{"key":"e_1_3_3_1_25_2","doi-asserted-by":"publisher","unstructured":"Axel Halin Alexandre Nuttinck Mathieu Acher Xavier Devroey Gilles Perrouin and Benoit Baudry. 2018. Test them all is it worth it? Assessing configuration sampling on the JHipster Web development stack. Empirical Software Engineering (17 Jul 2018).10.1007\/s10664-018-9635-4","DOI":"10.1007\/s10664-018-9635-4"},{"key":"e_1_3_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/11527695_13"},{"key":"e_1_3_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.5555\/2050655.2050721"},{"key":"e_1_3_3_1_28_2","doi-asserted-by":"crossref","unstructured":"Maurice\u00a0G Kendall. 1938. A new measure of rank correlation. Biometrika 30 1-2 (1938) 81\u201393.","DOI":"10.1093\/biomet\/30.1-2.81"},{"key":"e_1_3_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.29.5"},{"key":"e_1_3_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.5555\/3171642.3171738"},{"key":"e_1_3_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2791060.2791070"},{"key":"e_1_3_3_1_32_2","unstructured":"R. Mateescu. 2011. Treewidth in Industrial SAT Benchmarks."},{"key":"e_1_3_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.5555\/1753235.1753267"},{"key":"e_1_3_3_1_34_2","first-page":"231","volume-title":"SPLC\u201909","author":"Mendonca Marcilio","year":"2009","unstructured":"Marcilio Mendonca, Andrzej Wasowski, and Krzysztof Czarnecki. 2009. SAT-based analysis of feature models is easy. In SPLC\u201909 (San Francisco, California).IEEE, 231\u2013240."},{"key":"e_1_3_3_1_35_2","first-page":"459","volume-title":"AAAI Conference on Artificial Intelligence","volume":"92","author":"Mitchell David\u00a0G.","year":"1992","unstructured":"David\u00a0G. Mitchell, Bart Selman, and Hector\u00a0J. Levesque. 1992. Hard and Easy Distributions of SAT Problems. In AAAI Conference on Artificial Intelligence, Vol.\u00a092. 459\u2013465."},{"key":"e_1_3_3_1_36_2","doi-asserted-by":"crossref","unstructured":"R\u00e9mi Monasson Riccardo Zecchina Scott Kirkpatrick Bart Selman and Lidror Troyansky. 1999. Determining computational complexity from characteristic \u2018phase transitions\u2019. Nature 400 6740 (1999) 133\u2013137.","DOI":"10.1038\/22055"},{"key":"e_1_3_3_1_37_2","volume-title":"International Joint Conference on Artificial Intelligence","author":"Mu Zongxu","year":"2015","unstructured":"Zongxu Mu and Holger\u00a0H. Hoos. 2015. On the Empirical Time Complexity of Random 3-SAT at the Phase Transition. In International Joint Conference on Artificial Intelligence. https:\/\/api.semanticscholar.org\/CorpusID:17251755"},{"key":"e_1_3_3_1_38_2","doi-asserted-by":"crossref","unstructured":"Mark E.\u00a0J. Newman and Michelle Girvan. 2003. Finding and evaluating community structure in networks. Physical review. E Statistical nonlinear and soft matter physics 69 2 Pt 2 (2003) 026113.","DOI":"10.1103\/PhysRevE.69.026113"},{"key":"e_1_3_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3106237.3106273"},{"key":"e_1_3_3_1_40_2","volume-title":"Scalable Uniform Sampling for Real-World Software Product Lines","author":"Oh Jeho","year":"2020","unstructured":"Jeho Oh, Paul Gazzillo, Don Batory, Marijn Heule, and Margaret Myers. 2020. Scalable Uniform Sampling for Real-World Software Product Lines. Technical Report TR-20-01."},{"key":"e_1_3_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3336294.3342359"},{"key":"e_1_3_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICST.2019.00032"},{"key":"e_1_3_3_1_43_2","unstructured":"Yash Pote Saurabh Joshi and Kuldeep\u00a0S. Meel. 2019. Phase Transition Behavior of Cardinality and XOR Constraints. ArXiv abs\/1910.09755 (2019). https:\/\/api.semanticscholar.org\/CorpusID:199465708"},{"key":"e_1_3_3_1_44_2","doi-asserted-by":"crossref","unstructured":"Marko Samer and Stefan Szeider. 2007. Algorithms for propositional model counting. J. Discrete Algorithms 8 (2007) 50\u201364.","DOI":"10.1016\/j.jda.2009.06.002"},{"key":"e_1_3_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.10449477"},{"key":"e_1_3_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-53288-8_22"},{"key":"e_1_3_3_1_47_2","doi-asserted-by":"crossref","unstructured":"Joshua Sprey Chico Sundermann Sebastian Krieter Michael Nieke Jacopo Mauro Thomas Th\u00fcm and Ina Schaefer. 2020. SMT-based variability analyses in FeatureIDE. Proceedings of the 14th International Working Conference on Variability Modelling of Software-Intensive Systems (2020) 1\u20139.","DOI":"10.1145\/3377024.3377036"},{"key":"e_1_3_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3646548.3672590"},{"key":"e_1_3_3_1_49_2","doi-asserted-by":"crossref","unstructured":"Chico Sundermann Tobias He\u00df Michael Nieke Paul\u00a0Maximilian Bittner Jeffrey\u00a0M. Young Thomas Th\u00fcm and Ina Schaefer. 2023. Evaluating state-of-the-art # SAT solvers on industrial configuration spaces. Empirical Software Engineering 28 2 (2023) 29.","DOI":"10.1007\/s10664-022-10265-9"},{"key":"e_1_3_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/11814948_38"},{"key":"e_1_3_3_1_51_2","unstructured":"Olivier Zeyen. 2025. URS Phase Transitions. https:\/\/github.com\/serval-uni-lu\/urs_phase_transitions https:\/\/doi.org\/10.5281\/zenodo.15807056."},{"key":"e_1_3_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3644033.3644371"}],"event":{"name":"SPLC-A '25: 29th ACM International Systems and Software Product Line Conference - Volume A","sponsor":["SIGSOFT ACM Special Interest Group on Software Engineering"],"location":"A Coru\u00f1a Spain","acronym":"SPLC-A '25"},"container-title":["Proceedings of the 29th ACM International Systems and Software Product Line Conference - Volume A"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3744915.3748473","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,2]],"date-time":"2025-09-02T16:07:30Z","timestamp":1756829250000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3744915.3748473"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,31]]},"references-count":51,"alternative-id":["10.1145\/3744915.3748473","10.1145\/3744915"],"URL":"https:\/\/doi.org\/10.1145\/3744915.3748473","relation":{},"subject":[],"published":{"date-parts":[[2025,8,31]]},"assertion":[{"value":"2025-08-31","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}