Cover Image

From Alternation to FPRAS: Toward a Complexity Classification of Approximate Counting

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hecher, Markus, Lanzinger, Matthias
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Epistemic Logic Programs: Non-Ground and Counting Complexity
by: Eiter, Thomas, et al.
Published: (2025)

A faster FPRAS for #NFA
by: Meel, Kuldeep S., et al.
Published: (2023)

FPT Parameterisations of Fractional and Generalised Hypertree Width
by: Lanzinger, Matthias, et al.
Published: (2025)

Structure-Guided Automated Reasoning
by: Bannach, Max, et al.
Published: (2023)

Structure-Aware Encodings of Argumentation Properties for Clique-width
by: Mahmood, Yasir, et al.
Published: (2025)

Diversity of Extensions in Abstract Argumentation
by: Fichte, Johannes K., et al.
Published: (2026)

Rejection in Abstract Argumentation: Harder Than Acceptance?
by: Fichte, Johannes K., et al.
Published: (2024)

The Complexity of Logarithmic Space Bounded Counting Classes
by: Vijayaraghavan, T. C.
Published: (2025)

Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems
by: Yamakami, Tomoyuki
Published: (2024)

The Complexity of Counting Turns in the Line-Based Dial-a-Ride Problem
by: Lauerbach, Antonio, et al.
Published: (2024)

Algorithmic Structure in Subset Sum: Deterministic In-Bound Navigation and the Counting Complexity Divide
by: Nkosi, Thami
Published: (2025)

The Complexity of Finding and Counting Subtournaments
by: Döring, Simon, et al.
Published: (2025)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
by: Wang, Yichuan
Published: (2024)

Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
by: Focke, Jacob, et al.
Published: (2021)

Complexity of the Guarded Two-Variable Fragment with Counting Quantifiers
by: Pratt-Hartmann, Ian
Published: (2006)

On the Principal Minor Expansion and Complexity of the Symmetrized Determinant
by: Agarwal, Sanyam, et al.
Published: (2026)

The Complexity of Counting Small Sub-Hypergraphs
by: Bressan, Marco, et al.
Published: (2025)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
by: Grossman, Ofer, et al.
Published: (2023)

From Proof Complexity to Circuit Complexity via Interactive Protocols
by: Arteche, Noel, et al.
Published: (2024)

The Communication Complexity of Approximating Matrix Rank
by: Sherstov, Alexander A., et al.
Published: (2024)

From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy
by: Dörfler, Julian, et al.
Published: (2024)

Symmetric Parameterised Holants on Hypergraphs: Towards a Classification for Parameterised VCSPs
by: Aivasiliotis, Panagiotis, et al.
Published: (2025)

Scheme-Theoretic Approach to Computational Complexity. IV. A New Perspective on Hardness of Approximation
by: Çivril, Ali
Published: (2023)

The Counting General Dominating Set Framework
by: Zheng, Jiayi, et al.
Published: (2026)

Low Sets and Closure Properties of Counting Function Classes
by: Ivanashev, Yaroslav
Published: (2025)

Lower Bounds for Subset Sum in Resolution with Modular Counting
by: Part, Fedor
Published: (2022)

The Complexity of Symmetry Breaking Beyond Lex-Leader
by: Anders, Markus, et al.
Published: (2024)

Hilbert's Nullstellensatz is in the Counting Hierarchy
by: Andrews, Robert, et al.
Published: (2026)

Counting Martingales for Measure and Dimension in Complexity Classes
by: Hitchcock, John M., et al.
Published: (2025)

Complexity Classification of Product State Problems for Local Hamiltonians
by: Kallaugher, John, et al.
Published: (2024)

Counting Triangulations of Fixed Cardinal Degrees
by: Chambers, Erin, et al.
Published: (2025)

New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
by: Fan, Austen, et al.
Published: (2026)

Learning DFAs from Positive Examples Only via Word Counting
by: Bordais, Benjamin, et al.
Published: (2025)

On the Counting Complexity of the Skolem Problem
by: Jindal, Gorav, et al.
Published: (2024)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
by: Assadi, Sepehr, et al.
Published: (2024)

On Approximability of Satisfiable k-CSPs: V
by: Bhangale, Amey, et al.
Published: (2024)

Approximate Degree Composition for Recursive Functions
by: Chakraborty, Sourav, et al.
Published: (2024)

Lower Bounds for Approximate Sign Rank
by: Bindua, Riju, et al.
Published: (2026)

On the Complexity of Identification in Linear Structural Causal Models
by: Dörfler, Julian, et al.
Published: (2024)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
by: Baril, Ambroise, et al.
Published: (2024)