Le papier suivant sera présenté au 40ème symposium annuel ACM/IEEE de logique en informatique (Logic In Computer Science, LICS) en juin 2025 :

Max Bannach, Erik D. Demaine, Timothy Gomez and Markus Hecher: #P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?

Résumé de la contribution :

It establishes a substantially more fine-grained view on counting, showing that while #2CNF/#2DNF is not hard alone (one-shot reduction), if you can do two of these counting calls, then you easily reach #P. In fact you can then also do both calls in a single call and allow a bit of arithmetic postprocessing (to pull out the results via division/modulo and do subtraction afterwards). This even works for restricted variants of #Monotone2DNF without negation. Essentially, one-shot calls are insufficient, but already arithmetic on top of counting is the reason for hardness. This provides substantial progress and yields interesting lower bounds for structural measures like treewidth, consequences like fine-grained versions of Toda’s theorem, as well as sparsification for #2DNF.