Parameterised counting in logspace
From MaRDI portal
Publication:6093373
DOI10.1007/s00453-023-01114-2arXiv1904.12156WikidataQ123269459 ScholiaQ123269459MaRDI QIDQ6093373
Anselm Haak, Om Prakash, Arne Meier, B. V. Raghavendra Rao
Publication date: 6 October 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1904.12156
Algorithms in computer science (68Wxx) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Graph theory (05Cxx)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Structural tractability of counting of solutions to conjunctive queries
- Machine-based methods in parameterized complexity theory
- The complexity of computing the permanent
- The complexity of counting homomorphisms seen from the other side
- Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\)
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- Relativized alternation and space-bounded computation
- Nondeterministic \(NC^1\) computation
- Gap-definable counting classes
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- Circuits over PP and PL
- Block interpolation: a framework for tight exponential-time counting complexity
- The parameterised complexity of counting even and odd induced subgraphs
- Describing parameterized complexity classes
- The complexity of matrix rank and feasible systems of linear equations
- On the space and circuit complexity of parameterized problems: classes and completeness
- A complexity theory for feasible closure properties
- Parameterized counting of trees, forests and matroid bases
- Parametrized complexity theory.
- Subtractive reductions and complete problems for counting complexity classes
- The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space
- Completeness Results for Parameterized Space Classes
- PP is as Hard as the Polynomial-Time Hierarchy
- Query evaluation via tree-decompositions
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- The PL Hierarchy Collapses
- Color-coding
- Some Lower Bounds in Parameterized AC^0.
- The Parameterized Complexity of Counting Problems
- Relationships among $PL$, $\#L$, and the determinant
- Homomorphisms are a good basis for counting small subgraphs
- Approximate Counting CSP Seen from the Other Side
- Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
- Parameterized Analogues of Probabilistic Computation
- Extensor-coding
- Computational Complexity
- Counting Matchings of Size k Is $\sharp$ W[1-Hard]
- Parameterized approximation algorithms for some location problems in graphs
- Parameterized (Modular) Counting and Cayley Graph Expanders
This page was built for publication: Parameterised counting in logspace
