Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.04125 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Similar Items
Deterministic Hardness of Approximation For SVP in all Finite $\ell_p$ Norms
by: Hair, Isaac M, et al.
Published: (2026)
by: Hair, Isaac M, et al.
Published: (2026)
Deterministic Hardness of Approximation of Unique-SVP and GapSVP in $\ell_p$ norms for $p>2$
by: Hecht, Yahli, et al.
Published: (2025)
by: Hecht, Yahli, et al.
Published: (2025)
On the NP-Hardness Approximation Curve for Max-2Lin(2)
by: Martinsson, Björn
Published: (2024)
by: Martinsson, Björn
Published: (2024)
Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
by: Riazanov, Artur, et al.
Published: (2025)
by: Riazanov, Artur, 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)
by: Chavrimootoo, Michael C., et al.
Published: (2026)
NP-Hardness and a PTAS for the Pinwheel Problem
by: Kleinberg, Robert, et al.
Published: (2026)
by: Kleinberg, Robert, et al.
Published: (2026)
Determining the Outerthickness of Graphs Is NP-Hard
by: Lee, Pin-Hsian, et al.
Published: (2026)
by: Lee, Pin-Hsian, et al.
Published: (2026)
Optimal Union Probability Interval Is NP-Hard
by: Kaski, Petteri, et al.
Published: (2026)
by: Kaski, Petteri, et al.
Published: (2026)
Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice
by: Digulescu, Mircea-Adrian
Published: (2026)
by: Digulescu, Mircea-Adrian
Published: (2026)
Sumplete is Hard, Even with Two Different Numbers
by: Ruangwises, Suthee
Published: (2023)
by: Ruangwises, Suthee
Published: (2023)
A Brief Note on a Recent Claim About NP-Hard Problems and BQP
by: Chavrimootoo, Michael C.
Published: (2024)
by: Chavrimootoo, Michael C.
Published: (2024)
Universal NP-Hardness of Clustering under General Utilities
by: Majumdar, Angshul
Published: (2026)
by: Majumdar, Angshul
Published: (2026)
On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
by: Guruswami, Venkatesan, et al.
Published: (2023)
by: Guruswami, Venkatesan, et al.
Published: (2023)
Sorting by Strip Swaps is NP-Hard
by: Roy, Swapnoneel, et al.
Published: (2025)
by: Roy, Swapnoneel, et al.
Published: (2025)
Real Stability and Log Concavity are coNP-Hard
by: Chin, Tracy
Published: (2024)
by: Chin, Tracy
Published: (2024)
Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard
by: Krokhin, Andrei, et al.
Published: (2025)
by: Krokhin, Andrei, et al.
Published: (2025)
NP-hardness of SVP in Euclidean Space
by: Wan, Daqing
Published: (2026)
by: Wan, Daqing
Published: (2026)
Reducibility among NP-Hard graph problems and boundary classes
by: Hassan, Syed Mujtaba, et al.
Published: (2024)
by: Hassan, Syed Mujtaba, et al.
Published: (2024)
The 2-Attractor Problem is NP-Complete
by: Fuchs, Janosch, et al.
Published: (2023)
by: Fuchs, Janosch, et al.
Published: (2023)
NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
by: Gaspers, Serge, et al.
Published: (2025)
by: Gaspers, Serge, et al.
Published: (2025)
Hardness of the Binary Covering Radius Problem in Large $\ell_p$ Norms
by: Bennett, Huck, et al.
Published: (2026)
by: Bennett, Huck, et al.
Published: (2026)
When Symmetry Yields NP-Hardness: Affine ML-SAT on S5 Frames
by: Krebs, Andreas, et al.
Published: (2025)
by: Krebs, Andreas, et al.
Published: (2025)
Graph-Based Deterministic Polynomial Framwork for NP Problems
by: Lee, Changryeol
Published: (2025)
by: Lee, Changryeol
Published: (2025)
Near Optimal Hardness of Approximating $k$-CSP
by: Minzer, Dor, et al.
Published: (2025)
by: Minzer, Dor, et al.
Published: (2025)
List Recovery for Random Low-Rate Linear Codes
by: Hair, Isaac M, et al.
Published: (2026)
by: Hair, Isaac M, et al.
Published: (2026)
Public Key Encryption from High-Corruption Constraint Satisfaction Problems
by: Hair, Isaac M, et al.
Published: (2026)
by: Hair, Isaac M, et al.
Published: (2026)
Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms
by: Bennett, Huck, et al.
Published: (2022)
by: Bennett, Huck, et al.
Published: (2022)
P=NP
by: Deng, Zikang
Published: (2024)
by: Deng, Zikang
Published: (2024)
An $Ω( (\log n / \log \log n)^2 )$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures
by: Ko, Young Kun
Published: (2026)
by: Ko, Young Kun
Published: (2026)
Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
by: Gaikwad, Ajinkya, et al.
Published: (2025)
by: Gaikwad, Ajinkya, et al.
Published: (2025)
Freeze-Tag is NP-hard in 2D with $L_1$ distance
by: Silva, Lucas de Oliveira, et al.
Published: (2025)
by: Silva, Lucas de Oliveira, et al.
Published: (2025)
Training Neural Networks is NP-Hard in Fixed Dimension
by: Froese, Vincent, et al.
Published: (2023)
by: Froese, Vincent, et al.
Published: (2023)
Structural Origin and the Minimal Syntax of NP-Hardness: Analysis of SAT from Syntactic Generativity and Compositional Collapse
by: Nishiyama, Yumiko
Published: (2025)
by: Nishiyama, Yumiko
Published: (2025)
On $NP \cap coNP$ proof complexity generators
by: Krajicek, Jan
Published: (2025)
by: Krajicek, Jan
Published: (2025)
Proofs of NP = coNP = PSPACE: Current upgrade
by: Gordeev, Lev, et al.
Published: (2023)
by: Gordeev, Lev, et al.
Published: (2023)
Wataridori is NP-Complete
by: Ruangwises, Suthee
Published: (2026)
by: Ruangwises, Suthee
Published: (2026)