{"ID":6023629,"CreatedAt":"2026-07-08T01:00:23.257252134Z","UpdatedAt":"2026-07-10T15:16:26.541449957Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.06393","arxiv_id":"2607.06393","title":"Faster Exponential-Time Approximate Counting via Bounded Self-Reductions","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{ö}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,δ)\\)-approximation in \\[ O^{\\ast}\\!\\left(\\sqrt{b(x)}\\,\\varepsilon^{-2}\\log \\tfrac1δ\\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δ\\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.","short_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 \\...","url_abs":"https://arxiv.org/abs/2607.06393","url_pdf":"https://arxiv.org/pdf/2607.06393v1","authors":"[\"Katie Clinch\",\"Serge Gaspers\",\"Simon Mackenzie\",\"Qi Wang\"]","published":"2026-07-07T15:25:53Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}