pith. sign in

arxiv: 2605.14093 · v2 · pith:ODJK3Z44new · submitted 2026-05-13 · 💻 cs.DS

New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions

Sanjay Jain , Junqiang Peng , Frank Stephan , Haoyun Tang , Mingyu Xiao This is my paper

Pith reviewed 2026-05-19 17:27 UTC · model grok-4.3

classification 💻 cs.DS
keywords Parity-SATbounded-occurrence SATexact algorithmsrandomized algorithmsmodel counting⊕P-completeSAT
0
0 comments X

The pith

Algorithms solve Parity-SAT in sub-2^m time on formulas with bounded variable occurrences.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper develops randomized algorithms for Parity-SAT, the task of deciding whether a CNF formula has an odd number of satisfying assignments. For the restricted case where each variable appears in at most d clauses, the method runs in O^*(2^{m(1-1/O(d))}) time and thereby breaks the 2^m barrier for every fixed d. When d equals 2 the authors obtain sharper bounds of O^*(1.1193^n) or O^*(1.3248^m). The same structural ideas produce an O^*(1.1052^L) algorithm for unrestricted Parity-SAT measured by formula length L. All procedures use only polynomial space and improve on the best known running times for the corresponding exact counting problems.

Core claim

The authors present randomized algorithms that decide Parity-d-occ-SAT in O^*(2^{m(1-1/O(d))}) time for any fixed d, breaking the 2^m barrier that holds under SETH for general instances. For the special case d=2 they obtain O^*(1.1193^n) or O^*(1.3248^m) time via branching, and they lift the underlying reductions to an O^*(1.1052^L) algorithm for general Parity-SAT, all with polynomial space and strictly better than known exact counting bounds.

What carries the argument

Structural reductions and branching rules that track the parity of the number of satisfying assignments while shrinking the instance size.

If this is right

  • Parity-SAT admits faster algorithms than exact model counting when variable occurrences are bounded.
  • The classical 2^m barrier for Parity-SAT is not tight under bounded-occurrence restrictions.
  • Polynomial-space procedures exist that decide parity more efficiently than known counting methods for these restricted formulas.
  • Insights from the d=2 case improve the general algorithm measured by total formula length L.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Parity-tracking reductions may yield similar speed-ups for other ⊕P-complete problems that possess bounded-occurrence structure.
  • The gap between parity and counting could be exploited in additional parameterized settings beyond occurrence bounds.
  • The techniques suggest that length-based measures can sometimes replace variable- or clause-count measures for general instances.

Load-bearing premise

The reductions and branching steps must preserve parity correctly and without introducing hidden exponential costs on all relevant formula classes.

What would settle it

A family of d-occurrence CNF formulas on which every algorithm deciding parity requires Ω(2^m) time would show that the claimed sub-2^m bound does not hold.

read the original abstract

Parity-SAT is the problem of determining whether a given CNF formula has an odd number of satisfying assignments. As a canonical $\oplus$P-complete problem, it represents a fundamental variant of the exact model counting problem (#SAT). Under the Strong Exponential Time Hypothesis (SETH), Parity-SAT admits no $O^*((2-\varepsilon)^n)$-time or $O^*((2-\varepsilon)^m)$-time algorithm for any constant $\varepsilon>0$, where $n$ and $m$ denote the numbers of variables and clauses, respectively. Thus, breaking the $2^n$ or $2^m$ barrier appears impossible in full generality. In this work, we revisit this barrier through structural restrictions and a refined exploitation of parity. We study Parity-$d$-occ-SAT, where each variable appears in at most $d$ clauses, and obtain three main results. First, we design a randomized $O^*(2^{m(1-1/O(d))})$-time algorithm, thereby breaking the $2^m$ barrier for every fixed $d$. Second, for the special case $d=2$, we develop a significantly sharper branching algorithm running in $O^*(1.1193^n)$ time or $O^*(1.3248^m)$ time. Third, leveraging the structural insights underlying the $d=2$ case, we obtain an $O^*(1.1052^L)$-time algorithm for general Parity-SAT, where $L$ denotes the formula length. All algorithms use only polynomial space. Notably, our running-time bounds are better than the best known bounds for the corresponding exact counting counterparts, highlighting a genuine algorithmic advantage of parity over counting. Conceptually, our results demonstrate that parity admits finer structural reductions and more efficient branching than exact model counting, and that bounded occurrence can be systematically leveraged to circumvent classical exponential barriers.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript presents new algorithms for Parity-SAT and its bounded-occurrence variants. It claims a randomized O^*(2^{m(1-1/O(d))})-time algorithm for Parity-d-occ-SAT that breaks the 2^m barrier for every fixed d, a sharper O^*(1.1193^n) or O^*(1.3248^m) branching algorithm for d=2, and an O^*(1.1052^L)-time algorithm for general Parity-SAT (L = formula length), all using only polynomial space and improving on the best known exact counting bounds.

Significance. If the central claims hold, the work is significant for the exact algorithms community: it shows that parity admits strictly finer structural reductions and more efficient branching than #SAT, systematically leveraging bounded occurrence to circumvent SETH-style barriers while remaining polynomial-space. The explicit case analysis on variable occurrences and the isolation-lemma application are strengths that could influence follow-up work on other parity or modular counting problems.

major comments (2)
  1. [§4.2] §4.2, branching recurrence (4): the measure for the d=2 case reports a base of 1.1193, but the analysis must confirm that every reduction outcome (including parity-preserving simplifications) is accounted for in the recurrence; otherwise the claimed exponent may be optimistic.
  2. [Theorem 5.3] Theorem 5.3: the O^*(1.1052^L) bound for general Parity-SAT is derived from the d=2 structural insights; the manuscript should include an explicit statement that the reduction from arbitrary formulas to the bounded-occurrence case incurs only polynomial overhead and preserves parity exactly.
minor comments (2)
  1. [Introduction] The definition of formula length L in the introduction should be stated explicitly (number of literal occurrences) rather than left implicit.
  2. [Table 1] Table 1 comparing running times with #SAT bounds would benefit from an additional column listing the precise polynomial-space usage.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the constructive comments. We address each of the major comments below and will incorporate the suggested clarifications in the revised version.

read point-by-point responses

  1. Referee: [§4.2] §4.2, branching recurrence (4): the measure for the d=2 case reports a base of 1.1193, but the analysis must confirm that every reduction outcome (including parity-preserving simplifications) is accounted for in the recurrence; otherwise the claimed exponent may be optimistic.

    Authors: We thank the referee for pointing this out. Upon re-examination, the branching analysis in Section 4.2 enumerates all reduction outcomes, including parity-preserving simplifications such as unit propagation and clause resolution steps that maintain the parity. The measure is chosen to ensure that each branch decreases the measure sufficiently, and the base of 1.1193 is obtained from solving the recurrence that covers the worst-case branching vectors. To address the concern explicitly, we will add a sentence or short paragraph confirming that no additional cases arise from the parity-preserving rules beyond those already analyzed in the recurrence. revision: yes

  2. Referee: [Theorem 5.3] Theorem 5.3: the O^*(1.1052^L) bound for general Parity-SAT is derived from the d=2 structural insights; the manuscript should include an explicit statement that the reduction from arbitrary formulas to the bounded-occurrence case incurs only polynomial overhead and preserves parity exactly.

    Authors: We agree that making this explicit would enhance the clarity of the proof. The reduction used in the proof of Theorem 5.3 is a standard one that replaces high-occurrence variables by introducing new variables and clauses in a way that preserves the exact parity of the number of satisfying assignments, while increasing the total length L by at most a linear factor in the original size. We will add an explicit statement or a short lemma in the revised manuscript to this effect, right before or within the proof of Theorem 5.3. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper derives its running-time bounds through explicit construction and analysis of structural reductions and parity-preserving branching rules, with recurrences solved directly from case analysis on variable occurrences and clause structures. These steps are independent of the final exponents, use standard tools such as the isolation lemma for randomization, and maintain correctness via exhaustive case handling without reducing any claimed bound to a quantity defined by the same analysis. No self-citations are load-bearing for the core results, and the d=2 insights are leveraged internally without circular redefinition. The algorithms are self-contained against external benchmarks for exact counting.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard algorithmic techniques for CNF formulas and parity tracking with no new free parameters, invented entities, or ad-hoc axioms beyond conventional branching and reduction methods in exponential-time SAT algorithms.

axioms (1)
  • standard math Branching on variables or clauses preserves the parity of satisfying assignments and allows exhaustive case analysis without exponential overhead beyond the stated recurrence.
    Invoked implicitly in the design of the branching algorithms for d=2 and the general case.

pith-pipeline@v0.9.0 · 5885 in / 1380 out tokens · 76002 ms · 2026-05-19T17:27:53.985735+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

48 extracted references · 48 canonical work pages

  1. [1]

    Cook , title =

    Stephen A. Cook , title =. Proceedings of the 3rd Annual. 1971 , doi =

    work page 1971

  2. [2]

    Valiant , title =

    Leslie G. Valiant , title =. Theor. Comput. Sci. , volume =. 1979 , doi =

    work page 1979

  3. [3]

    Proceedings of the 44th Annual Symposium on Foundations of Computer Science (

    Fahiem Bacchus and Shannon Dalmao and Toniann Pitassi , title =. Proceedings of the 44th Annual Symposium on Foundations of Computer Science (. 2003 , doi =

    work page 2003

  4. [4]

    Dan Roth , title =. Artif. Intell. , volume =. 1996 , doi =

    work page 1996

  5. [5]

    Kautz , title =

    Tian Sang and Paul Beame and Henry A. Kautz , title =. Proceedings of the 20th National Conference on Artificial Intelligence (

    work page

  6. [6]

    Mark Chavira and Adnan Darwiche , title =. Artif. Intell. , volume =. 2008 , doi =

    work page 2008

  7. [7]

    Counting-Based Reliability Estimation for Power-Transmission Grids , booktitle =

    Leonardo Due. Counting-Based Reliability Estimation for Power-Transmission Grids , booktitle =. 2017 , doi =

    work page 2017

  8. [8]

    Shrotri and Kuldeep S

    Nina Narodytska and Aditya A. Shrotri and Kuldeep S. Meel and Alexey Ignatiev and Jo. Assessing Heuristic Machine Learning Explanations with Model Counting , booktitle =. 2019 , doi =

    work page 2019

  9. [9]

    Valiant and Vijay V

    Leslie G. Valiant and Vijay V. Vazirani , title =. Theor. Comput. Sci. , volume =. 1986 , doi =

    work page 1986

  10. [10]

    Papadimitriou and Stathis Zachos , title =

    Christos H. Papadimitriou and Stathis Zachos , title =. Proceedings of the 6th. 1983 , doi =

    work page 1983

  11. [11]

    1991 , doi =

    Seinosuke Toda , title =. 1991 , doi =

    work page 1991

  12. [12]

    Russell Impagliazzo and Ramamohan Paturi , title =. J. Comput. Syst. Sci. , volume =. 2001 , doi =

    work page 2001

  13. [13]

    Proceedings of the 23rd Annual

    Russell Impagliazzo and William Matthews and Ramamohan Paturi , title =. Proceedings of the 23rd Annual. 1992 , doi =

    work page 1992

  14. [14]

    Chan and Ryan Williams , title =

    Timothy M. Chan and Ryan Williams , title =. Proceedings of the 27th Annual. 2016 , doi =

    work page 2016

  15. [15]

    A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances , booktitle =

    Magnus Wahlstr. A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances , booktitle =. 2008 , doi =

    work page 2008

  16. [16]

    Fomin and Dieter Kratsch , title =

    Fedor V. Fomin and Dieter Kratsch , title =. 2010 , doi =

    work page 2010

  17. [17]

    Proceedings of the 34th International Joint Conference on Artificial Intelligence (

    Junqiang Peng and Zimo Sheng and Mingyu Xiao , title =. Proceedings of the 34th International Joint Conference on Artificial Intelligence (. 2025 , doi =

    work page 2025

  18. [18]

    Demaine and Timothy Gomez and Markus Hecher , title =

    Max Bannach and Erik D. Demaine and Timothy Gomez and Markus Hecher , title =. Proceedings of the 40th Annual. 2025 , doi =

    work page 2025

  19. [19]

    Demaine and Timothy Gomez and Markus Hecher , title =

    Max Bannach and Erik D. Demaine and Timothy Gomez and Markus Hecher , title =. Proceedings of the 2026 Symposium on Simplicity in Algorithms (. 2026 , doi =

    work page 2026

  20. [20]

    Chris Calabro and Russell Impagliazzo and Valentine Kabanets and Ramamohan Paturi , title =. J. Comput. Syst. Sci. , volume =. 2008 , doi =

    work page 2008

  21. [21]

    Proceedings of the 3rd International Workshop on Parameterized and Exact Computation (

    Patrick Traxler , title =. Proceedings of the 3rd International Workshop on Parameterized and Exact Computation (. 2008 , doi =

    work page 2008

  22. [22]

    On Problems as Hard as

    Marek Cygan and Holger Dell and Daniel Lokshtanov and D. On Problems as Hard as. 2016 , doi =

    work page 2016

  23. [23]

    Burkhard Monien and Robert Preis , title =. J. Discrete Algorithms , volume =. 2006 , doi =

    work page 2006

  24. [24]

    Fomin and Kjartan H

    Fedor V. Fomin and Kjartan H. Pathwidth of cubic graphs and exact algorithms , journal =. 2006 , doi =

    work page 2006

  25. [25]

    Sorkin , title =

    Serge Gaspers and Gregory B. Sorkin , title =. 2017 , doi =

    work page 2017

  26. [26]

    Fomin and Fabrizio Grandoni and Dieter Kratsch , title =

    Fedor V. Fomin and Fabrizio Grandoni and Dieter Kratsch , title =. J. 2009 , doi =

    work page 2009

  27. [27]

    Huairui Chu and Mingyu Xiao and Zhe Zhang , title =. Theor. Comput. Sci. , volume =. 2021 , doi =

    work page 2021

  28. [28]

    Junqiang Peng and Mingyu Xiao , title =. Inf. Comput. , volume =. 2023 , doi =

    work page 2023

  29. [29]

    An improved exponential-time algorithm for

    Ramamohan Paturi and Pavel Pudl. An improved exponential-time algorithm for. J. 2005 , doi =

    work page 2005

  30. [30]

    Satisfiability Coding Lemma , booktitle =

    Ramamohan Paturi and Pavel Pudl. Satisfiability Coding Lemma , booktitle =. 1997 , doi =

    work page 1997

  31. [31]

    A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems , booktitle =

    Uwe Sch. A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems , booktitle =. 1999 , doi =

    work page 1999

  32. [32]

    Proceedings of the 21st Annual

    Chris Calabro and Russell Impagliazzo and Ramamohan Paturi , title =. Proceedings of the 21st Annual. 2006 , doi =

    work page 2006

  33. [33]

    Hirsch , title =

    Evgeny Dantsin and Edward A. Hirsch , title =. Handbook of Satisfiability - Second Edition , publisher =. 2021 , doi =

    work page 2021

  34. [34]

    1989 , doi =

    Kazuo Iwama , title =. 1989 , doi =

    work page 1989

  35. [35]

    Lozinskii , title =

    Eliezer L. Lozinskii , title =. Inf. Process. Lett. , volume =. 1992 , doi =

    work page 1992

  36. [36]

    Proceedings of the 62nd

    Dominik Scheder , title =. Proceedings of the 62nd. 2021 , doi =

    work page 2021

  37. [37]

    Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (

    Sixue Liu , title =. Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (. 2018 , doi =

    work page 2018

  38. [38]

    Kurur , title =

    Vikraman Arvind and Piyush P. Kurur , title =. Inf. Comput. , volume =. 2006 , doi =

    work page 2006

  39. [39]

    Valiant , title =

    Leslie G. Valiant , title =. Proceedings of the 47th Annual. 2006 , doi =

    work page 2006

  40. [40]

    Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (

    Amir Abboud and Shon Feller and Oren Weimann , title =. Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (. 2020 , doi =

    work page 2020

  41. [41]

    Algorithmica , volume =

    Leslie Ann Goldberg and Marc Roth , title =. Algorithmica , volume =. 2024 , doi =

    work page 2024

  42. [42]

    Proceedings of the 29th Annual European Symposium on Algorithms (

    Radu Curticapean and Holger Dell and Thore Husfeldt , title =. Proceedings of the 29th Annual European Symposium on Algorithms (. 2021 , doi =

    work page 2021

  43. [43]

    Proceedings of the 18th International Conference and Workshops on Algorithms and Computation (

    Gordon Hoi and Sanjay Jain and Ammar Fathin Sabili and Frank Stephan , title =. Proceedings of the 18th International Conference and Workshops on Algorithms and Computation (. 2024 , doi =

    work page 2024

  44. [44]

    Proceedings of the 26th International Conference on Principles and Practice of Constraint Programming (

    Gordon Hoi and Sanjay Jain and Frank Stephan , title =. Proceedings of the 26th International Conference on Principles and Practice of Constraint Programming (. 2020 , doi =

    work page 2020

  45. [45]

    The Parity of Directed Hamiltonian Cycles , booktitle =

    Andreas Bj. The Parity of Directed Hamiltonian Cycles , booktitle =. 2013 , doi =

    work page 2013

  46. [46]

    The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems , booktitle =

    Andreas Bj. The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems , booktitle =. 2015 , doi =

    work page 2015

  47. [47]

    Exponential Time Complexity of the Permanent and the Tutte Polynomial , journal =

    Holger Dell and Thore Husfeldt and D. Exponential Time Complexity of the Permanent and the Tutte Polynomial , journal =. 2014 , doi =

    work page 2014

  48. [48]

    CoRR , volume =

    Gordon Hoi and Ammar Fathin Sabili and Frank Stephan , title =. CoRR , volume =. 2022 , url =

    work page 2022