Cover Image

A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Burke, Kyle, Ferland, Matthew, Huntemann, Svenja, Teng, Shang-Hua
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Combinatorics 91A46 F.1.3; G.2; F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Battle Sheep is PSPACE-complete
by: Burke, Kyle, et al.
Published: (2025)

Col is PSPACE-complete on Triangular Grids
by: Burke, Kyle, et al.
Published: (2025)

Hive is PSPACE-Hard
by: Andel, Daniël, et al.
Published: (2025)

Quoridor is PSPACE-Complete
by: Drop, Marius, et al.
Published: (2026)

Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs
by: Burke, Kyle, et al.
Published: (2025)

Two-player Domino games
by: de Menibus, Benjamin Hellouin, et al.
Published: (2023)

Direct Sums for Parity Decision Trees
by: Besselman, Tyler, et al.
Published: (2024)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
by: Conneryd, Jonas, et al.
Published: (2025)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
by: de Rezende, Susanna F., et al.
Published: (2024)

Polynomial-time Tractable Problems over the $p$-adic Numbers
by: Fehm, Arno, et al.
Published: (2025)

Certificate-Sensitive Subset Sum: Realizing Instance Complexity
by: Salas, Jesus
Published: (2025)

Maximum Nim and Josephus Problem
by: Takahashi, Shoei, et al.
Published: (2024)

PosSLP and Sum of Squares
by: Bläser, Markus, et al.
Published: (2024)

Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity
by: Knop, Dušan, et al.
Published: (2017)

On the Complexity of Determinations
by: Hellerstein, Joseph M.
Published: (2026)

Immutability Does Not Guarantee Trust: A Formal and Logical Refutation
by: Wright, Craig S
Published: (2025)

NP-Completeness Proofs of Puzzles using the T-Metacell Framework
by: Kiatchaipipat, Nattapol, et al.
Published: (2025)

When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
by: Fritsch, Timo, et al.
Published: (2026)

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
by: Gupta, Chetan, et al.
Published: (2025)

Fast Simulation of Cellular Automata by Self-Composition
by: Natal, Joseph, et al.
Published: (2024)

A Polynomial Time Algorithm for 3SAT
by: Quigley, Robert
Published: (2024)

Approximate all-pairs Hamming distances and 0-1 matrix multiplication
by: Kowaluk, Miroslaw, et al.
Published: (2025)

Proving Unsatisfiability with Hitting Formulas
by: Filmus, Yuval, et al.
Published: (2023)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
by: Conneryd, Jonas, et al.
Published: (2025)

Subquadratic Algorithms and Hardness for Attention with Any Temperature
by: Gupta, Shreya, et al.
Published: (2025)

A universal bound on the space complexity of Directed Acyclic Graph computations
by: Bilardi, Gianfranco, et al.
Published: (2024)

On bounded depth proofs for Tseitin formulas on the grid; revisited
by: Håstad, Johan, et al.
Published: (2022)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
by: de Rezende, Susanna F., et al.
Published: (2026)

Supercritical Tradeoffs for Monotone Circuits
by: Göös, Mika, et al.
Published: (2024)

Thin Tree Verification is coNP-Complete
by: Moayyedi, Alice
Published: (2025)

Sum-of-squares lower bounds for Non-Gaussian Component Analysis
by: Diakonikolas, Ilias, et al.
Published: (2024)

Algorithmic hardness of the partition function for nucleic acid strands
by: Ducloz, Gwendal, et al.
Published: (2025)

A Variant of Game of Sliding Coins
by: Miyadera, Ryohei, et al.
Published: (2025)

Liquid Amortization: Proving Amortized Complexity with LiquidHaskell (Functional Pearl)
by: van Brügge, Jan
Published: (2024)

Mind the gap: A real-valued distance on combinatorial games
by: Burke, Kyle, et al.
Published: (2026)

A dimension-free discrete Remez-type inequality on the polytorus
by: Slote, Joseph, et al.
Published: (2023)

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

The complexity of finding coset-generating polymorphisms and the promise metaproblem
by: Bodirsky, Manuel, et al.
Published: (2026)

A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds
by: Lagerkvist, Victor, et al.
Published: (2025)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
by: Saha, Barna, et al.
Published: (2024)