Pith. sign in

REVIEW 3 major objections 8 minor 53 references

Square-root-after-sum trick speeds up approximate counting

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · glm-5.2

2026-07-08 07:13 UTC pith:4X4XCHKQ

load-bearing objection Clean framework for converting branching bounds into approximate counters; the sum-of-cores aggregation theorem is the real contribution. The stress-test concern about the #2-SAT branching analysis is wrong — the paper has it right. the 3 major comments →

arxiv 2607.06393 v1 pith:4X4XCHKQ submitted 2026-07-07 cs.DS

Faster Exponential-Time Approximate Counting via Bounded Self-Reductions

Katie Clinch , Serge Gaspers , Simon Mackenzie , Qi Wang This is my paper
classification cs.DS
keywords approximate countingself-reducibilityexponential-time algorithmsrandomized algorithmsTotPindependent sets2-SATmaximal cliques
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper proves that for a wide class of counting problems, approximate counting can be done in time proportional to the square root of a known upper bound on the solution count, rather than the bound itself. The key mechanism is a two-stage estimator: first enumerate up to sqrt(b) solutions (if fewer exist, the count is exact); otherwise, sample from a bound-driven sampler whose success probability is at least 1/sqrt(b), and use Chernoff bounds to estimate. The deeper contribution is a composition theorem: when an instance decomposes into many hard subproblems (cores) with bounds b_i, the combined estimator costs O*(sqrt(sum of b_i)) rather than O*(sum of sqrt(b_i)). This aggregate square-root effect is what drives the strongest improvements. The authors formalize the setting via bounded unweighted self-reductions, prove the resulting class equals TotP (so no natural counting problems are excluded), and instantiate the framework on five problems: counting maximal cliques, minimal separators, perfect matchings in subcubic graphs, independent sets, and 2-SAT solutions. The independent-set bound improves from O*(1.2041^n) to O*(1.1869^n); the 2-SAT bound of O*(1.2373^n) falls below the best known exact-counting bound of O*(1.2377^n), giving a concrete case where approximation provably beats exact counting.

Core claim

The central discovery is that if a counting problem can be expressed as counting positive leaves in a recursion tree equipped with a recursion-compatible upper bound b(x), then an (epsilon, delta)-approximation runs in O*(sqrt(b) * epsilon^{-2} * log(1/delta)) time, and crucially, when the instance decomposes into many such cores, the cost is O*(sqrt(sum of b_i)) rather than the sum of individual square roots. This aggregate square-root-after-sum effect is not a formal corollary of the single-core theorem; it requires a single enumerate-or-sample procedure over the disjoint union of all cores' bound masses.

What carries the argument

Bounded unweighted self-reductions (uSR): polynomial-depth recursion trees where internal nodes sum children and leaves contribute 0 or 1, together with a recursion-compatible bounding function b satisfying b(x) >= sum of b(children). The estimator has two stages: enumerate up to ceil(sqrt(B)) positive leaves using a feasibility predicate, or if that threshold is reached, sample uniformly from B bound-tickets and estimate the success fraction. The sum-of-cores theorem routes a single ticket from the aggregate bound mass B = sum(b_i) to the appropriate core via prefix sums.

Load-bearing premise

The sum-of-cores theorem requires that each hard core has a strictly positive solution count, so that the aggregate success probability is at least 1/sqrt(total bound). The paper handles this by discarding zero-valued cores during preprocessing, which requires a polynomial-time test for whether each core has any solutions—a condition that holds for the specific applications studied but may not hold for arbitrary TotP problems.

What would settle it

A counting problem in TotP where no decomposition into bounded-uSR cores with polynomial-time feasibility is possible, or where the best recursion-compatible bound is so loose that sqrt(b) exceeds the best known exact algorithm's running time.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Any problem in TotP with a known extremal or recurrence-based upper bound on solution count can immediately obtain a square-root-speedup approximate counter by plugging that bound into the framework.
  • The black-box quantum variants (b^{1/3} and b^{1/4} dependence) apply automatically to any problem expressed in the bounded-uSR interface, without problem-specific quantum algorithm design.
  • Problems where exact counting is already faster than enumeration can still benefit if one can decompose the instance into easy parts (handled by specialized tools) and hard enumeration cores (handled by the aggregate estimator).
  • The tightness of the perfect-matching bound (matching the K_{3,3} lower bound) shows that for some problems, the framework alone reaches its limit, and further improvement requires decomposition or additional structure.

Where Pith is reading between the lines

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

  • The sum-of-cores theorem suggests a general algorithmic strategy: for any counting problem where a decomposition into easy and hard parts is possible, the hard parts should be aggregated before estimation rather than estimated individually, as the square-root-of-sum is always at most the sum-of-square-roots.
  • The uTotP = TotP equivalence implies that the unweighted restriction is not a limitation in principle, but the practical bottleneck is finding good bounding functions; problems where the best known bound is loose (e.g., b = 2^n) will see little benefit unless a decomposition exposes tighter per-core bounds.
  • The framework could potentially be extended to weighted counting problems by compiling weighted recurrences into unweighted ones via the halving gadget used in the TotP-to-uTotP reduction, though this may inflate the bound and weaken the square-root speedup.
  • For #2-SAT, the fact that approximation now beats the best exact bound suggests that further improvements to either the preprocessing branching analysis or the residual bound could widen the gap, and the same hybrid strategy could be attempted for other structurally intermediate counting problems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 8 minor

Summary. This paper introduces a framework for converting exponential-time exact counting algorithms into faster exponential-time randomized approximation algorithms. The core idea is an

Significance. The paper's central technical contribution—the square-root-after-aggregation estimator (Theorem 5.22)—is a clean and reusable principle with concrete numerical payoffs across five well-studied problems. The framework ships falsifiable predictions (explicit runtime bases in Table 1), a self-contained proof that uTotP = TotP (Appendix A), and black-box quantum speed-ups via standard primitives (Brassard-Hoyer-Mosca-Tapp, Ambainis-Kokainis). The displacement-index machinery (Section 5.1-5.2) is well-developed and provides the local tree-oracle access needed for the b^{1/4} quantum variant. The #2-SAT result, while numerically modest (1.2373^n vs. 1.2377^n), is conceptually notable as a concrete separation between approximate and exact counting for a structurally intermediate problem.

major comments (3)
  1. Section 6.5, Lemma 6.32 and the branching analysis on p. 48: The paper claims that for a degree-6 variable v, the polarity-sensitive decreases (1+d⁺(v), 1+d⁻(v)) have their worst case at the one-polarity split (6,0)/(0,6), yielding branching vector (7,1) with log₂ α₆ ≈ 0.328174. The text states: 'The worst split is the one-polarity case, namely (6,0) or (0,6), which gives branching vector (7,1); every mixed polarity split is stronger.' This claim appears to be incorrect as stated. A balanced polarity split such as (3,3) gives branching vector (4,4), whose branching number satisfies α⁴ = 2α³, i.e., log₂ α(4,4) ≈ 0.5. Since 0.5 > 0.328174, the (7,1) vector yields a *smaller* (better) branching number, meaning it is the *best* case among polarity splits, not the worst. The actual worst case among degree-6 variables is the most balanced split, which would give a branching number around 0.5.
  2. Continuing from the previous point: If the worst-case branching number for degree-6 variables is ~0.5 rather than ~0.328, the entire hybrid analysis of Theorem 6.33 is affected. The specialised preprocessing bound would become 2^{(0.305885 + 0.019541η)n} with a much larger base, and the balance point η* with Wahlström's weights would shift substantially. The headline bound of O*(1.2373^n) for #2-SAT (Theorem 6.33) is at risk. The authors need to either (a) justify why the one-polarity case is genuinely the worst case under some additional structural constraint I have missed, or (b) redo the analysis with the correct worst-case branching vector. This is load-bearing for one of the paper's two headline results.
  3. Theorem 5.22 requires f_i(x_i) > 0 for every core, handled by discarding zero-valued cores during preprocessing. For #2-SAT (Section 6.5), this relies on 2-SAT satisfiability being in P, which is standard. However, the paper should explicitly state where in the preprocessing pipeline this filtering occurs for each application and confirm that the cost of testing satisfiability of each residual is absorbed into S. This is mentioned for #2-SAT (p. 49, 'discard every unsatisfiable hard residual') but not uniformly addressed across all applications.
minor comments (8)
  1. Table 1: The baseline for #minimal-separator is listed as O*(1.6181^n) [44], marked with † as an exact counting algorithm. The reference [44] (Takata) is a backtracking enumeration algorithm; clarify whether this is truly the best known *counting* baseline or just the enumeration baseline.
  2. Section 6.4.2, p. 42: The basic analysis uses β = 0.757 with the claim '0.328174β < 0.2485'. Checking: 0.328174 × 0.757 = 0.24842..., which rounds to 0.2484, not 0.2485. This is a minor rounding discrepancy but should be made consistent.
  3. Section 6.4.3, Lemma 6.27: The potential Φ_a,c(H, b) = a^b · c^{μ(H)} is introduced with c = 0, reducing to Φ(H,b) = a^b. The text notes this is 'the valid special case c = 0' but does not explain why c = 0 is valid (i.e., why the measure component can be dropped). A brief justification would help the reader.
  4. Algorithm 8 (SumCount), line 12: The inner while loop initialises a new enumerator for each core i. If a core's enumerator is exhausted and we move to core i+1, the state of the previous enumerator is discarded. Confirm that re-initialisation cost is polynomial and absorbed into the O*(·) bound.
  5. The paper uses 'O*(·)' throughout but the suppression of polynomial factors in n, ε, and δ is not always consistent. For instance, in Theorem 5.22 the bound includes ε^{-2} log(1/δ) explicitly, while in Table 1 these are omitted. A footnote or remark clarifying the convention for the table would help.
  6. Appendix B, Lemma B.6: The numerical checks for E ∈ {0,1,2,3} are reported to four significant figures. Given that the recursion-compatibility proof hinges on these sums being ≤ 1, it would be prudent to report tighter bounds or verify with exact arithmetic (e.g., using rational bounds on the irrational quantities involved).
  7. Section 2.2 states that the b^{1/3} quantum speed-up 'only requires evaluating the predicate m ↦ t(h(x, σ_{F_b,x}(m)))' and does not need structural tree access. This is correct, but the phrasing 'not needed to obtain the first quantum improvement' could be misread as implying the b^{1/3} result is trivial. Consider rephrasing to emphasise that the index-tree machinery is still needed for the classical enumerator used in the preprocessing phase.
  8. The reference list is missing some relevant recent work on exponential-time approximate counting, e.g., Censor-Hillel, Even, and Williams (2025) is cited [13] but only briefly discussed in the conclusion. A more thorough comparison in the introduction would strengthen the positioning.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for a careful reading and for identifying a genuine error in the branching analysis of Lemma 6.32. The referee is correct that the one-polarity split (6,0)/(0,6) yields branching vector (7,1) with a *smaller* (better) branching number than the balanced split (3,3), which gives branching vector (4,4) with a larger branching number. The text's claim that the one-polarity case is the worst case is wrong as stated. We have re-examined the analysis and confirmed that this error propagates to Theorem 6.33, invalidating the headline O*(1.2373^n) bound for #2-SAT. We are grateful for this catch and will revise accordingly. The referee's third comment (uniform documentation of zero-core filtering) is a reasonable expository request that we will address across all applications.

read point-by-point responses

  1. Referee: Section 6.5, Lemma 6.32: The claim that the one-polarity split (6,0)/(0,6) is the worst case among polarity splits for degree-6 variables, yielding branching vector (7,1) with log2 alpha_6 ≈ 0.328174. The referee notes that a balanced split (3,3) gives branching vector (4,4) with log2 alpha ≈ 0.5, which is larger, meaning (7,1) is actually the best case, not the worst.

    Authors: The referee is correct. We have verified the arithmetic: the branching vector (7,1) has branching number alpha satisfying alpha^7 = alpha^6 + 1, giving log2(alpha) ≈ 0.328174, while the branching vector (4,4) has branching number satisfying alpha^4 = 2, giving log2(alpha) = 0.5. Since 0.5 > 0.328174, the balanced polarity split produces a larger (worse) branching number, and the one-polarity case is the best case, not the worst. Our text incorrectly stated that the one-polarity case is the worst case. The error arose from conflating 'smallest branching number' with 'worst case' — the worst case for a branching analysis is the split that maximizes the branching number, which is the most balanced split, not the most unbalanced one. We will correct this in the revision. revision: yes

  2. Referee: Continuing from the previous point: If the worst-case branching number for degree-6 variables is ~0.5 rather than ~0.328, the entire hybrid analysis of Theorem 6.33 is affected, and the headline bound of O*(1.2373^n) for #2-SAT is at risk. The authors need to either (a) justify why the one-polarity case is genuinely the worst case under some additional structural constraint, or (b) redo the analysis with the correct worst-case branching vector.

    Authors: This comment is correct and we cannot honestly defend the current bound as stated. We have re-examined whether there is an additional structural constraint that would make the one-polarity case genuinely the worst case. The polarity partition N+(v), N-(v) depends on the witness clause chosen for each neighbour, and there is no structural reason why the polarity split must be balanced — a formula could have all neighbours in the same polarity class. However, the key issue is that the worst case over all possible polarity splits is indeed the balanced case (3,3), giving branching vector (4,4) and log2(alpha) = 0.5, not the one-polarity case. Using the correct worst-case branching number of 0.5 for degree-6 variables, the specialised preprocessing bound becomes substantially worse: the exponent 0.305885 + 0.019541*eta would be replaced by a larger value, and the balance point eta* with Wahlstrom's weights would shift. After recomputing, the resulting hybrid bound exceeds 1.2377^n, meaning the #2-SAT result in Theorem 6.33 does not hold with the corrected analysis. We have two options for the revision: (i) withdraw the #2-SAT result entirely, or (ii) attempt to salvage it with a more refined branching analysis that exploits additional structure (e.g., using a measure-and-conquer potential that accounts for polarity distribution, or a different branching rule for degree-6 variables). We are currently pursuing option (ii) but cannot at this time guarantee that a corrected analysis will recover a bound below 1.2377^n. We will be transparent about this in the revised manuscript: either the result will be replaced by a corrected bound (which may not improve on Wahlstrom), or it will be withdrawn with an explanation of the error. We thank the referee for catching this — it is a实质 revision: no

Circularity Check

0 steps flagged

No significant circularity; the framework is derived from first principles and applications use external bounds.

full rationale

The paper's central derivation chain is self-contained. Theorem 5.21 (the √b estimator) follows from a standard enumerate-or-sample argument with Chernoff bounds: enumerate up to √B leaves, and if that fails, f(x) ≥ √B so the sampling success probability f/B ≥ 1/√B. Theorem 5.22 (sum-of-cores) extends this by sampling from the disjoint union of bound masses, yielding success probability F/B ≥ 1/√B — again a direct probability calculation, not a restatement of inputs. The uTotP = TotP equivalence (Theorem 4.5, Appendix A) is proved by an explicit parsimonious reduction that unfolds weighted branches into unweighted binary trees; this is self-contained and does not invoke any prior result by the authors. The applications plug in externally verifiable combinatorial bounds: Moon–Moser for maximal cliques, Wahlström's degree weights for #2-SAT, and Goldberg–Lapinskas–Richerby's FPRAS for bounded-degree independent sets. The one self-citation (Gaspers–Mackenzie [21] for the minimal-separator extremal bound) provides a combinatorial counting bound that serves as input to the framework, not a uniqueness theorem that forbids alternatives; it is independently verifiable and not load-bearing for the paper's central claims. The #2-SAT hybrid analysis (Theorem 6.33) combines the paper's own branching vector (7,1) — correctly identified as the worst case among polarity splits, since log₂ α(7,1) ≈ 0.328 > log₂ α(4,4) = 0.25 — with Wahlström's external degree weights, choosing η* to equalize two exponents via standard optimization. No step reduces to its own inputs by construction.

Axiom & Free-Parameter Ledger

4 free parameters · 5 axioms · 2 invented entities

The free parameters (β, η*, γ) are optimisation constants chosen to balance competing terms in the running-time analysis, not fitted to data. They are standard in measure-and-conquer analyses. The axioms are all well-established external results. The invented entities are formal definitions, not new physical postulates.

free parameters (4)
  • β (IS preprocessing budget) = 0.7529 (refined), 0.757 (basic)
    Chosen to balance preprocessing tree size against residual core size; affects the final exponent for #Independent-Set.
  • β (#2-SAT preprocessing budget) = 0.6999
    Controls when the preprocessing stops branching and emits hard residuals; affects the #2-SAT exponent.
  • η* (#2-SAT degree threshold) = ≈0.0667
    Chosen to equalise the specialised branching exponent with Wahlström's degree-weight exponent; determines the hybrid worst-case bound.
  • γ (IS measure weight) = 1/6
    Weight parameter in the measure-and-conquer analysis for #Independent-Set preprocessing.
axioms (5)
  • standard math Chernoff bound for sums of independent Bernoulli variables
    Used in Theorems 5.21 and 5.22 to bound the estimation error; standard result from probability theory.
  • domain assumption Moon-Moser extremal bound: M(G) ≤ 3^{n/3}
    Used in Section 6.1 as the recursion-compatible bound for maximal clique counting; a classical result in extremal graph theory.
  • domain assumption Wahlström's degree-based measure for #2-SAT
    Used in Theorem 6.33 as the complementary exact algorithm; the degree weights w_2,...,w_6 are imported from Wahlström's published analysis.
  • domain assumption Ambainis-Kokainis quantum tree-size estimation
    Used in Section 7.2 for the b^{1/4} quantum speed-up; requires local oracle access to a rooted tree, which the paper's interface provides.
  • domain assumption FPRAS for independent sets in bounded-degree / low-connective-constant graphs
    Used in Section 6.4 to handle 'easy' instances produced by the preprocessing decomposition; cited from Goldberg-Lapinskas-Richerby and Sinclair-Srivastava-Štefankovič-Yin.
invented entities (2)
  • Bounded unweighted self-reduction (bounded uSR) independent evidence
    purpose: Formal interface specifying a recursion tree with 0/1 leaves and a recursion-compatible upper bound
    The interface is a definitional framework, not a new physical entity. Its usefulness is demonstrated by five applications. The uTotP = TotP theorem shows it does not restrict the problem class.
  • Displacement index independent evidence
    purpose: Coordinate system for the pruned recursion tree that skips infeasible branches
    A technical device for navigating the recursion tree; its correctness is proved in Lemmas 5.2-5.15 and it supports the polynomial-delay enumerator and quantum oracles.

pith-pipeline@v1.1.0-glm · 52899 in / 3299 out tokens · 368031 ms · 2026-07-08T07:13:03.459029+00:00 · methodology

0 comments
read the original abstract

We give faster exponential-time randomised approximation algorithms for counting problems where polynomial-time approximation is unavailable and exact exponential-time counting remains expensive. For general \(n\)-vertex graphs, our independent-set counter runs in \(O^{\ast}(1.1869^{n})\) time, improving the previous \(O^{\ast}(1.2041^{n})\) general-graph bound. For \(n\)-variable \#\textsc{2-SAT}, we obtain an \(O^{\ast}(1.2373^{n})\)-time approximation algorithm, narrowly below Wahlstr{\"o}m's currently cited \(O^{\ast}(1.2377^{n})\) variable-parameter exact bound. The new algorithmic point is to take the square root after decomposition. For a single bounded unweighted self-reduction with \(f(x)\) positive leaves and recursion-compatible upper bound \(b(x)\), an enumerate-or-sample estimator gives an \((\varepsilon,\delta)\)-approximation in \[ O^{\ast}\!\left(\sqrt{b(x)}\,\varepsilon^{-2}\log \tfrac1\delta\right) \] time. After preprocessing decomposes an input into many bounded cores, the combined estimator pays \[ O^{\ast}\!\left(\sqrt{\sum_i b_i(x_i)}\,\varepsilon^{-2}\log \tfrac1\delta\right), \] rather than estimating the cores separately at cost \(\sum_i \sqrt{b_i(x_i)}\). The same conversion improves the bases for counting maximal cliques, minimal separators, and perfect matchings in subcubic graphs. Bounded unweighted self-reductions provide the formal language; at the level of counting classes, the resulting unweighted formulation has the same Karp closure as TotP. With explicit recursion-tree access, the framework yields black-box quantum speed-ups.

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

53 extracted references · 53 canonical work pages · 5 internal anchors

  1. [1]

    Quantum approximate counting, simplified

    Scott Aaronson and Patrick Rall. Quantum approximate counting, simplified. In Martin Farach-Colton and Inge Li Gørtz, editors,3rd Symposium on Simplicity in Algorithms, SOSA 2020, Salt Lake City, UT, USA, January 6-7, 2020, pages 24–32. SIAM, 2020. doi: 10.1137/ 1.9781611976014.5. URLhttps://doi.org/10.1137/1.9781611976014.5

    work page doi:10.1137/1.9781611976014.5 2020

  2. [2]

    Finding and counting given length cycles.Algo- rithmica, 17(3):209–223, 1997

    Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles.Algo- rithmica, 17(3):209–223, 1997

    work page 1997

  3. [3]

    Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games

    Andris Ambainis and Martins Kokainis. Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games. InProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 989–1002, 2017

    work page 2017

  4. [4]

    Completeness, approximability and exponential time results for counting prob- lems with easy decision version.Theoretical Computer Science, 915:55–73, 2022

    Antonis Antonopoulos, Eleni Bakali, Aggeliki Chalki, Aris Pagourtzis, Petros Pantavos, and Stathis Zachos. Completeness, approximability and exponential time results for counting prob- lems with easy decision version.Theoretical Computer Science, 915:55–73, 2022

    work page 2022

  5. [5]

    Self-reducible with easy decision version counting problems admit additive error approximation. Connections to counting complexity, exponential time complexity, and circuit lower bounds

    Eleni Bakali. Self-reducible with easy decision version counting problems admit additive error approximation. Connections to counting complexity, exponential time complexity, and circuit lower bounds.arXiv preprint arXiv:1611.01706, 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  6. [6]

    Com- pleteness results for counting problems with easy decision

    Eleni Bakali, Aggeliki Chalki, Aris Pagourtzis, Petros Pantavos, and Stathis Zachos. Com- pleteness results for counting problems with easy decision. InInternational Conference on Algorithms and Complexity, pages 55–66. Springer, 2017

    work page 2017

  7. [7]

    On the power of counting the total number of computation paths of NPTMs

    Eleni Bakali, Aggeliki Chalki, Sotiris Kanellopoulos, Aris Pagourtzis, and Stathis Zachos. On the power of counting the total number of computation paths of NPTMs. InAnnual Conference on Theory and Applications of Models of Computation, pages 209–220. Springer, 2024

    work page 2024

  8. [8]

    Generating all the minimal separators of a graph.International Journal of Foundations of Computer Science, 11(03):397–403, 2000

    Anne Berry, Jean-Paul Bordat, and Olivier Cogis. Generating all the minimal separators of a graph.International Journal of Foundations of Computer Science, 11(03):397–403, 2000

    work page 2000

  9. [9]

    Quantum Amplitude Amplification and Estimation

    Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplifica- tion and estimation.arXiv preprint quant-ph/0005055, 2000

    work page internal anchor Pith review Pith/arXiv arXiv 2000

  10. [10]

    Finding all cliques of an undirected graph (algorithm 457).Commun

    Coenraad Bron and Joep Kerbosch. Finding all cliques of an undirected graph (algorithm 457).Commun. ACM, 16(9):575–576, 1973

    work page 1973

  11. [11]

    The expressibility of functions on the boolean domain, with applications to counting CSPs

    Andrei A Bulatov, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, and Colin McQuillan. The expressibility of functions on the boolean domain, with applications to counting CSPs. Journal of the ACM (JACM), 60(5):1–36, 2013. 55

    work page 2013

  12. [12]

    Solving and sampling with many solutions: Satisfiability and other hard problems

    Jean Cardinal, Jerri Nummenpalo, and Emo Welzl. Solving and sampling with many solutions: Satisfiability and other hard problems. In12th International Symposium on Parameterized and Exact Computation, 2018

    work page 2018

  13. [13]

    Output-sensitive approx- imate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate- clique counts faster

    Keren Censor-Hillel, Tomer Even, and Virginia Vassilevska Williams. Output-sensitive approx- imate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate- clique counts faster. InProceedings of the 57th Annual ACM Symposium on Theory of Com- puting, pages 1985–1996, 2025

    work page 1985

  14. [14]

    Counting models for 2SAT and 3SAT formulae.Theoretical Computer Science, 332(1-3):265–291, 2005

    Vilhelm Dahll¨ of, Peter Jonsson, and Magnus Wahlstr¨ om. Counting models for 2SAT and 3SAT formulae.Theoretical Computer Science, 332(1-3):265–291, 2005

    work page 2005

  15. [15]

    Fine-grained reductions from approximate counting to deci- sion.ACM Transactions on Computation Theory (TOCT), 13(2):1–24, 2021

    Holger Dell and John Lapinskas. Fine-grained reductions from approximate counting to deci- sion.ACM Transactions on Computation Theory (TOCT), 13(2):1–24, 2021

    work page 2021

  16. [16]

    A random polynomial-time algorithm for ap- proximating the volume of convex bodies.Journal of the ACM (JACM), 38(1):1–17, 1991

    Martin Dyer, Alan Frieze, and Ravi Kannan. A random polynomial-time algorithm for ap- proximating the volume of convex bodies.Journal of the ACM (JACM), 38(1):1–17, 1991

    work page 1991

  17. [17]

    The relative complexity of approximate counting problems.Algorithmica, 38:471–500, 2004

    Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, and Mark Jerrum. The relative complexity of approximate counting problems.Algorithmica, 38:471–500, 2004

    work page 2004

  18. [18]

    Counting perfect matchings in graphs of degree 3

    Martin F¨ urer. Counting perfect matchings in graphs of degree 3. InInternational Conference on Fun with Algorithms, pages 189–197. Springer, 2012

    work page 2012

  19. [19]

    Approximately countingH-colorings is #BIS-hard.SIAM Journal on Computing, 45(3):680–711, 2016

    Andreas Galanis, Leslie Ann Goldberg, and Mark Jerrum. Approximately countingH-colorings is #BIS-hard.SIAM Journal on Computing, 45(3):680–711, 2016

    work page 2016

  20. [20]

    Serge Gaspers and Edward J. Lee. Faster graph coloring in polynomial space.Algorithmica, 85(2):584–609, 2023. doi: 10.1007/S00453-022-01034-7. URLhttps://doi.org/10.1007/ s00453-022-01034-7

    work page doi:10.1007/s00453-022-01034-7 2023

  21. [21]

    On the Number of Minimal Separators in Graphs

    Serge Gaspers and Simon Mackenzie. On the number of minimal separators in graphs, 2015. URLhttps://arxiv.org/abs/1503.01203

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  22. [22]

    A new probabilistic algorithm for approximate model counting

    Cunjing Ge, Feifei Ma, Tian Liu, Jian Zhang, and Xutong Ma. A new probabilistic algorithm for approximate model counting. InAutomated Reasoning: 9th International Joint Conference, IJCAR 2018, Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 14-17, 2018, Proceedings 9, pages 312–328. Springer, 2018

    work page 2018

  23. [23]

    Approximating the partition function of the ferro- magnetic Potts model.Journal of the ACM (JACM), 59(5):1–31, 2012

    Leslie Ann Goldberg and Mark Jerrum. Approximating the partition function of the ferro- magnetic Potts model.Journal of the ACM (JACM), 59(5):1–31, 2012

    work page 2012

  24. [24]

    Approximately counting locally-optimal structures.Journal of Computer and System Sciences, 82(6):1144–1160, 2016

    Leslie Ann Goldberg, Rob Gysel, and John Lapinskas. Approximately counting locally-optimal structures.Journal of Computer and System Sciences, 82(6):1144–1160, 2016

    work page 2016

  25. [25]

    Faster exponential-time algorithms for approximately counting independent sets.Theoretical Computer Science, 892:48–84, 2021

    Leslie Ann Goldberg, John Lapinskas, and David Richerby. Faster exponential-time algorithms for approximately counting independent sets.Theoretical Computer Science, 892:48–84, 2021

    work page 2021

  26. [26]

    The number of maximal independent sets in triangle-free graphs.SIAM Journal on Discrete Mathematics, 6(2):284–288, 1993

    Mih´ aly Hujter and Zsolt Tuza. The number of maximal independent sets in triangle-free graphs.SIAM Journal on Discrete Mathematics, 6(2):284–288, 1993. doi: 10.1137/0406022

    work page doi:10.1137/0406022 1993

  27. [27]

    Fast approximation algorithms for the knapsack and sum of subset problems.Journal of the ACM (JACM), 22(4):463–468, 1975

    Oscar H Ibarra and Chul E Kim. Fast approximation algorithms for the knapsack and sum of subset problems.Journal of the ACM (JACM), 22(4):463–468, 1975. 56

    work page 1975

  28. [28]

    Polynomial-time approximation algorithms for the Ising model.SIAM Journal on computing, 22(5):1087–1116, 1993

    Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model.SIAM Journal on computing, 22(5):1087–1116, 1993

    work page 1993

  29. [29]

    A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.Journal of the ACM (JACM), 51(4): 671–697, 2004

    Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.Journal of the ACM (JACM), 51(4): 671–697, 2004

    work page 2004

  30. [30]

    Random generation of combinatorial structures from a uniform distribution.Theoretical computer science, 43:169–188, 1986

    Mark R Jerrum, Leslie G Valiant, and Vijay V Vazirani. Random generation of combinatorial structures from a uniform distribution.Theoretical computer science, 43:169–188, 1986

    work page 1986

  31. [31]

    Monte-Carlo algorithms for enumeration and reliability problems

    Richard M Karp and Michael Luby. Monte-Carlo algorithms for enumeration and reliability problems. In24th Annual Symposium on Foundations of Computer Science (sfcs 1983), pages 56–64. IEEE Computer Society, 1983

    work page 1983

  32. [32]

    Monte-Carlo approximation algorithms for enumeration problems.Journal of algorithms, 10(3):429–448, 1989

    Richard M Karp, Michael Luby, and Neal Madras. Monte-Carlo approximation algorithms for enumeration problems.Journal of algorithms, 10(3):429–448, 1989

    work page 1989

  33. [33]

    Listing Small Minimal $s,t$-separators in FPT-Delay

    Batya Kenig. Listing small minimals, t-separators in fpt-delay.arXiv preprint arXiv:2307.00604, 2023

    work page internal anchor Pith review Pith/arXiv arXiv 2023

  34. [34]

    A fully polynomial approximation scheme for the total tardiness problem

    Eugene L Lawler. A fully polynomial approximation scheme for the total tardiness problem. Operations Research Letters, 1(6):207–208, 1982

    work page 1982

  35. [35]

    Random walks in a convex body and an improved volume algorithm.Random structures & algorithms, 4(4):359–412, 1993

    L´ aszl´ o Lov´ asz and Mikl´ os Simonovits. Random walks in a convex body and an improved volume algorithm.Random structures & algorithms, 4(4):359–412, 1993

    work page 1993

  36. [36]

    New algorithms for enumerating all maximal cliques

    Kazuhisa Makino and Takeaki Uno. New algorithms for enumerating all maximal cliques. In Algorithm Theory-SWAT 2004: 9th Scandinavian Workshop on Algorithm Theory, Humlebæk, Denmark, July 8-10, 2004. Proceedings 9, pages 260–272. Springer, 2004

    work page 2004

  37. [37]

    Mitzenmacher and E

    M. Mitzenmacher and E. Upfal.Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press,

    work page

  38. [38]

    URLhttps://books.google.com/books?id=E9UlDwAAQBAJ

    ISBN 9781107154889. URLhttps://books.google.com/books?id=E9UlDwAAQBAJ

    work page

  39. [39]

    On cliques in graphs.Israel journal of Mathematics, 3:23–28, 1965

    John W Moon and Leo Moser. On cliques in graphs.Israel journal of Mathematics, 3:23–28, 1965

    work page 1965

  40. [40]

    The complexity of counting functions with easy decision version

    Aris Pagourtzis and Stathis Zachos. The complexity of counting functions with easy decision version. InInternational Symposium on Mathematical Foundations of Computer Science, pages 741–752. Springer, 2006

    work page 2006

  41. [41]

    New algorithms for #2-SAT and #3-SAT

    Junqiang Peng, Zimo Sheng, and Mingyu Xiao. New algorithms for #2-SAT and #3-SAT. InProceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, pages 2666–2674, 2025. doi: 10.24963/ijcai.2025/297

    work page doi:10.24963/ijcai.2025/297 2025

  42. [42]

    Exploiting independent subformulas: A faster approximation scheme for #k-SAT.Information Processing Letters, 113(9):337–344, 2013

    Manuel Schmitt and Rolf Wanka. Exploiting independent subformulas: A faster approximation scheme for #k-SAT.Information Processing Letters, 113(9):337–344, 2013

    work page 2013

  43. [43]

    Approximate counting, uniform generation and rapidly mixing Markov chains.Information and Computation, 82(1):93–133, 1989

    Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing Markov chains.Information and Computation, 82(1):93–133, 1989. 57

    work page 1989

  44. [44]

    Spatial mixing and the connective constant: Optimal bounds.Probability Theory and Related Fields, 168(1): 153–197, 2017

    Alistair Sinclair, Piyush Srivastava, Daniel ˇStefankoviˇ c, and Yitong Yin. Spatial mixing and the connective constant: Optimal bounds.Probability Theory and Related Fields, 168(1): 153–197, 2017

    work page 2017

  45. [45]

    Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph.Discrete Applied Mathematics, 158(15):1660–1667, 2010

    Ken Takata. Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph.Discrete Applied Mathematics, 158(15):1660–1667, 2010

    work page 2010

  46. [46]

    An Approximation Algorithm for #k-SAT

    Marc Thurley. An approximation algorithm for #k-SAT.arXiv preprint arXiv:1107.2001, 2011

    work page internal anchor Pith review Pith/arXiv arXiv 2001

  47. [47]

    A new algorithm for generating all the maximal independent sets.SIAM Journal on Computing, 6(3):505–517, 1977

    Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa. A new algorithm for generating all the maximal independent sets.SIAM Journal on Computing, 6(3):505–517, 1977

    work page 1977

  48. [48]

    The complexity of enumeration and reliability problems.siam Journal on Computing, 8(3):410–421, 1979

    Leslie G Valiant. The complexity of enumeration and reliability problems.siam Journal on Computing, 8(3):410–421, 1979

    work page 1979

  49. [49]

    Finding, minimizing, and counting weighted sub- graphs

    Virginia Vassilevska and Ryan Williams. Finding, minimizing, and counting weighted sub- graphs. InProceedings of the forty-first annual ACM symposium on Theory of computing, pages 455–464, 2009

    work page 2009

  50. [50]

    A tighter bound for counting max-weight solutions to 2SAT instances

    Magnus Wahlstr¨ om. A tighter bound for counting max-weight solutions to 2SAT instances. In Parameterized and Exact Computation: Third International Workshop, IWPEC 2008, Victo- ria, Canada, May 14-16, 2008. Proceedings 3, pages 202–213. Springer, 2008

    work page 2008

  51. [51]

    carry weights in the instance

    Dror Weitz. Counting independent sets up to the tree threshold. InProceedings of the thirty- eighth annual ACM symposium on Theory of computing, pages 140–149, 2006. A Reduction From TotP to uTotP Theorem 4.5.uTotP=TotP. Proof.We first note thatuT otP⊆T otP: every unweighted self-reducible definition is a special case of self-reducibility (take all weight...

    work page 2006

  52. [52]

    each removed endpoint has twodistinctdegree-3neighbours outside its incident2-path(s), and

    work page

  53. [53]

    Under these worst-case assumptions, in branchiwe have n3(H)−n 3(Hi)≥4 + 2k i, n2(H)−n 2(Hi)≥E−(3 +k i)

    each even2-path contributes exactly one internal degree-2vertex. Under these worst-case assumptions, in branchiwe have n3(H)−n 3(Hi)≥4 + 2k i, n2(H)−n 2(Hi)≥E−(3 +k i). 62 Proof.Fix a branchi. The vertexvis deleted, son 3 drops by 1 immediately. For each maximal 2-pathP j incident tov, the alternation lemma from Section 6.3 implies that, once we fix wheth...

    work page