:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Bordais, Benjamin, Neider, Daniel
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2511.08431
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A framework for computing upper bounds in passive learning settings
by: Bordais, Benjamin, et al.
Published: (2025)

Learning Branching-Time Properties in CTL and ATL via Constraint Solving
by: Bordais, Benjamin, et al.
Published: (2024)

The Complexity of Learning Temporal Properties
by: Bordais, Benjamin, et al.
Published: (2024)

Learning Tree Pattern Transformations
by: Neider, Daniel, et al.
Published: (2024)

Counting Small Induced Subgraphs: Hardness via Fourier Analysis
by: Curticapean, Radu, et al.
Published: (2024)

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

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

Hilbert's Nullstellensatz is in the Counting Hierarchy
by: Andrews, Robert, 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)

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

Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial
by: Curticapean, Radu, et al.
Published: (2025)

From Alternation to FPRAS: Toward a Complexity Classification of Approximate Counting
by: Hecher, Markus, et al.
Published: (2025)

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)

Modular Counting CSP: Reductions and Algorithms
by: Kazeminia, Amirhossein, et al.
Published: (2025)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
by: Döring, Simon, et al.
Published: (2024)

Review of Automaton Learning Algorithms with Polynomial Complexity -- Completely Solved Examples
by: Haneef, Farah
Published: (2024)

Counting Subgraphs in Somewhere Dense Graphs
by: Bressan, Marco, et al.
Published: (2022)

Model Counting for Dependency Quantified Boolean Formulas
by: Fung, Long-Hin, et al.
Published: (2025)

Finite Variable Counting Logics with Restricted Requantification
by: Raßmann, Simon, et al.
Published: (2024)

Computing the Elementary Symmetric Polynomials in Positive Characteristics
by: Orzel, Ian
Published: (2025)

Frontier Space-Time Algorithms Using Only Full Memory
by: Chmel, Petr, et al.
Published: (2026)

Work-Efficient Parallel Counting via Sampling
by: Liu, Hongyang, et al.
Published: (2024)

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

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

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
by: Focke, Jacob, et al.
Published: (2022)

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

Positive Univariate Polynomials: SOS certificates, algorithms, bit complexity, and T-systems
by: Bender, Matías, 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)

Compilation and Fast Model Counting beyond CNF
by: de Colnet, Alexis, et al.
Published: (2025)

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

Multiquadratic Sum-of-Squares Lower Bounds Imply VNC$^1$ $\neq$ VNP
by: Rossman, Benjamin, et al.
Published: (2025)

The Computational Complexity of Counting Linear Regions in ReLU Neural Networks
by: Stargalla, Moritz, et al.
Published: (2025)

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

Counting Locally Optimal Tours in the TSP
by: Manthey, Bodo, et al.
Published: (2024)

The Word Problem for Products of Symmetric Groups
by: Simon, Hans U.
Published: (2025)

Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
by: Baril, Ambroise, et al.
Published: (2025)

Symmetric Distributions from Shallow Circuits
by: Kane, Daniel M., et al.
Published: (2025)