:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Grüne, Christoph, Pfaue, Femke
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2511.04308
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Exploring the Reductions Between SSP-NP-complete Problems and Developing a Compendium Website Displaying the Results
by: Pfaue, Femke
Published: (2024)

The Complexity Classes of Hamming Distance Recoverable Robust Problems
by: Grüne, Christoph
Published: (2022)

Continuous Defensive Domination Problems
by: Grüne, Christoph, et al.
Published: (2026)

The Complexity of Blocking All Solutions
by: Grüne, Christoph, et al.
Published: (2025)

Completeness in the Polynomial Hierarchy for many natural Problems in Bilevel and Robust Optimization
by: Grüne, Christoph, et al.
Published: (2023)

On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
by: Grüne, Christoph, et al.
Published: (2024)

Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
by: Grüne, Christoph, et al.
Published: (2026)

A Compendium of Subset Search Problems and Reductions relating to the Parsimonious Property
by: Bartlett, Celina Janet
Published: (2025)

The Complexity of Graph Exploration Games
by: Fuchs, Janosch, et al.
Published: (2023)

The Complexity of Stackelberg Pricing Games
by: Grüne, Christoph, et al.
Published: (2025)

The Existential Theory of the Reals as a Complexity Class: A Compendium
by: Schaefer, Marcus, et al.
Published: (2024)

Recovery Reductions, Conjectures, and Barriers
by: Nareddy, Tejas, et al.
Published: (2025)

A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results
by: Arvind, Vikraman, et al.
Published: (2024)

Reductions Between Code Equivalence Problems
by: Cheraghchi, Mahdi, et al.
Published: (2025)

A New Reduction Method from Multivariate Polynomials to Univariate Polynomials
by: Wang, Cancan, et al.
Published: (2024)

Indefiniteness makes lattice reduction easier
by: Joux, Antoine
Published: (2025)

What Juris Hartmanis taught me about Reductions
by: Immerman, Neil
Published: (2024)

A Subexponential Reduction from Product Partition to Subset Sum
by: Costandin, Marius
Published: (2024)

Lower Bounds on Cardinality of Reducts for Decision Tables from Closed Classes
by: Ostonov, Azimkhon, et al.
Published: (2024)

Finding quantum partial assignments by search-to-decision reductions
by: Weggemans, Jordi
Published: (2024)

StoqMA vs. MA: the power of error reduction
by: Aharonov, Dorit, et al.
Published: (2020)

Local consistency as a reduction between constraint satisfaction problems
by: Dalmau, Victor, et al.
Published: (2023)

BQP, meet NP: Search-to-decision reductions and approximate counting
by: Gharibian, Sevag, et al.
Published: (2024)

Non-signalling parallel repetition using de Finetti reductions
by: Arnon, Rotem, et al.
Published: (2014)

Minimum cost flow decomposition on arc-coloured networks
by: Neto, Claudio Carvalho, et al.
Published: (2025)

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

Specification and Automatic Verification of Computational Reductions
by: Grange, Julien, et al.
Published: (2024)

Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
by: Agarwal, Avantika, et al.
Published: (2024)

The computational power of discrete chemical reaction networks with bounded executions
by: Doty, David, et al.
Published: (2024)

Proof Systems Based on Structured Circuits
by: Micun, Matthäus, et al.
Published: (2026)

The geodesic cover problem for butterfly networks
by: Manuel, Paul, et al.
Published: (2022)

Gap Preserving Reductions Between Reconfiguration Problems
by: Ohsaka, Naoto
Published: (2022)

Information Redistribution Under Reductions in NP Search
by: Wei, Jing-Yuan
Published: (2026)

Hausdorff Reductions and the Exponential Hierarchies
by: Malizia, Enrico
Published: (2024)

An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem
by: Yang, Yang
Published: (2025)

Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians
by: Buhrman, Harry, et al.
Published: (2024)

Expected Complexity of Persistence Barcode Computation via Matrix Reduction
by: Giunti, Barbara, et al.
Published: (2021)

Automatizing Software Cognitive Complexity Reduction through Integer Linear Programming
by: Saborido, Rubén, et al.
Published: (2024)

A characterization of efficiently compilable constraint languages
by: Berkholz, Christoph, et al.
Published: (2023)

Gap-preserving reductions and RE-completeness of independent set games
by: Mančinska, Laura, et al.
Published: (2025)