:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Minevich, Igor, Cunningham, Gabe, Karan, Aditya, Gyllinsky, Joshua V.
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Combinatorics
Online Access:	https://arxiv.org/abs/2411.02251
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Graph Powers of Groups II: The RA Matrix
by: Cunningham, Gabe, et al.
Published: (2025)

Graph Powers of Groups
by: Cunningham, Gabe, et al.
Published: (2025)

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

NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
by: Gaspers, Serge, et al.
Published: (2025)

King Chasing Problem in Chinese Chess is NP-hard
by: Li, Chao, et al.
Published: (2026)

Optimal Union Probability Interval Is NP-Hard
by: Kaski, Petteri, et al.
Published: (2026)

Computing the EHZ capacity is NP-hard
by: Leipold, Karla, et al.
Published: (2024)

Determining the Outerthickness of Graphs Is NP-Hard
by: Lee, Pin-Hsian, et al.
Published: (2026)

Real Stability and Log Concavity are coNP-Hard
by: Chin, Tracy
Published: (2024)

Flat origami is Turing Complete
by: Hull, Thomas C., et al.
Published: (2023)

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

NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles
by: Yang, Chao, et al.
Published: (2024)

Classification of Non-redundancy of Boolean Predicates of Arity 4
by: Brakensiek, Joshua, et al.
Published: (2026)

Evolomino is NP-complete
by: Nikolaev, Andrei V.
Published: (2025)

Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
by: Gamarnik, David, et al.
Published: (2026)

Generic Reed-Solomon Codes Achieve List-decoding Capacity
by: Brakensiek, Joshua, et al.
Published: (2022)

Equality cases of the Stanley--Yan log-concave matroid inequality
by: Chan, Swee Hong, et al.
Published: (2024)

Lions and Contamination: Trees and General Graphs
by: Kim, Dohoon, et al.
Published: (2026)

Wataridori is NP-Complete
by: Ruangwises, Suthee
Published: (2026)

Nondango is NP-Complete
by: Ruangwises, Suthee
Published: (2023)

Factorization norms and an inverse theorem for MaxCut
by: Balla, Igor, et al.
Published: (2025)

Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
by: Ikenmeyer, Christian, et al.
Published: (2022)

On a Hierarchy of Spectral Invariants for Graphs
by: Arvind, V., et al.
Published: (2023)

A Note on the Complexity of Directed Clique
by: Gutowski, Grzegorz, et al.
Published: (2026)

A combinatorial view of Holant problems on higher domains
by: Liu, Yin
Published: (2024)

A near-optimal Quadratic Goldreich-Levin algorithm
by: Briët, Jop, et al.
Published: (2025)

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

A criterion for Andrásfai--Erdős--Sós type theorems and applications
by: Hou, Jianfeng, et al.
Published: (2024)

A Hypergraph Container Method on Spread SAT: Approximation and Speedup
by: Han, Zicheng, et al.
Published: (2026)

Flip Distance of Triangulations of Convex Polygons / Rotation Distance of Binary Trees is NP-complete
by: Dorfer, Joseph
Published: (2026)

A parameterized algorithm for $K_r$-factors in graphs of high minimum degree
by: Gan, Luyining, et al.
Published: (2023)

Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
by: Hellmuth, Marc, et al.
Published: (2023)

NP-Completeness of Neighborhood Balanced Colorings
by: Asaeedi, Saeed
Published: (2024)

The 2-Attractor Problem is NP-Complete
by: Fuchs, Janosch, et al.
Published: (2023)

On the Constant-Depth Circuit Complexity of Generating Quasigroups
by: Collins, Nathaniel A., et al.
Published: (2024)

The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs
by: Ahn, Jungho, et al.
Published: (2022)

A General Framework for Low Soundness Homomorphism Testing
by: Mittal, Tushant, et al.
Published: (2025)

Carrying is Hard: Exploring the Gap between Hardness for NP and PSPACE for the Hanano and Jelly no Puzzles
by: Chavrimootoo, Michael C., et al.
Published: (2026)

Low-Degree Polynomials Are Good Extractors
by: Alrabiah, Omar, et al.
Published: (2024)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
by: Basu, Arpon, et al.
Published: (2024)