Image de couverture de livre

Col is PSPACE-complete on Triangular Grids

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Burke, Kyle, Tennenhouse, Craig
Format:	Preprint
Publié:	2025
Sujets:	Computational Complexity Combinatorics 91A46 F.1.3; G.2.1; F.2.2
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Battle Sheep is PSPACE-complete
par: Burke, Kyle, et autres
Publié: (2025)

Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs
par: Burke, Kyle, et autres
Publié: (2025)

A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers
par: Burke, Kyle, et autres
Publié: (2024)

Quoridor is PSPACE-Complete
par: Drop, Marius, et autres
Publié: (2026)

Hive is PSPACE-Hard
par: Andel, Daniël, et autres
Publié: (2025)

Mind the gap: A real-valued distance on combinatorial games
par: Burke, Kyle, et autres
Publié: (2026)

The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions
par: Pavlov, Gorgi
Publié: (2026)

On Sampling Lower Bounds for Polynomials
par: Khodabandeh, Mohammad Mahdi, et autres
Publié: (2026)

A Permutation Avoidance Game with Reverse Replies and Monotone Traps
par: Ulfarsson, Henning
Publié: (2026)

Algorithmic hardness of the partition function for nucleic acid strands
par: Ducloz, Gwendal, et autres
Publié: (2025)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
par: Anand, Emile, et autres
Publié: (2024)

Rankwidth of Graphs with Balanced Separations: Expansion for Dense Graphs
par: Anand, Emile
Publié: (2025)

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
par: de Rezende, Susanna F., et autres
Publié: (2019)

On the Complexity of Determinations
par: Hellerstein, Joseph M.
Publié: (2026)

PosSLP and Sum of Squares
par: Bläser, Markus, et autres
Publié: (2024)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
par: Conneryd, Jonas, et autres
Publié: (2025)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
par: Conneryd, Jonas, et autres
Publié: (2025)

On bounded depth proofs for Tseitin formulas on the grid; revisited
par: Håstad, Johan, et autres
Publié: (2022)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
par: de Rezende, Susanna F., et autres
Publié: (2026)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
par: de Rezende, Susanna F., et autres
Publié: (2024)

Supercritical Tradeoffs for Monotone Circuits
par: Göös, Mika, et autres
Publié: (2024)

Block-weighted random graphs: planar and beyond
par: Kang, Mihyun, et autres
Publié: (2026)

Asymptotic Transfer in Critical Recursive Composition Schemes
par: Drmota, Michael, et autres
Publié: (2026)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
par: Lela, Marko
Publié: (2025)

On the Min-Max Star Partitioning Number
par: Feldmann, Sarah, et autres
Publié: (2024)

Small Shadow Partitions
par: Kopparty, Swastik, et autres
Publié: (2024)

Which graph motif parameters count?
par: Bläser, Markus, et autres
Publié: (2025)

Explicit separations between randomized and deterministic Number-on-Forehead communication
par: Kelley, Zander, et autres
Publié: (2023)

On the Satisfaction Probabilities of $k$-CNF Formulas
par: Tantau, Till
Publié: (2022)

Certificate-Sensitive Subset Sum: Realizing Instance Complexity
par: Salas, Jesus
Publié: (2025)

On the Complexity of Problems on Graphs Defined on Groups
par: Das, Bireswar, et autres
Publié: (2025)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
par: Saha, Barna, et autres
Publié: (2024)

When Votes Change and Committees Should (Not)
par: Bredereck, Robert, et autres
Publié: (2020)

New Results on Edge-coloring and Total-coloring of Split Graphs
par: Couto, Fernanda, et autres
Publié: (2023)

Maximizing Index Diversity in Committee Elections
par: Böhm, Paula, et autres
Publié: (2026)

Optimal covering of rectangular grid graphs with tours of constrained length
par: Bereg, Sergey, et autres
Publié: (2025)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
par: Hakoniemi, Tuomas, et autres
Publié: (2024)

Separation of PSPACE and EXP
par: Czerwinski, Reiner
Publié: (2021)

Symmetric Arithmetic Circuits
par: Dawar, Anuj, et autres
Publié: (2020)

Lower Bounds for Symmetric Circuits for the Determinant
par: Dawar, Anuj, et autres
Publié: (2021)