:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Bennett, Huck, Ly, Peter
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2603.03219
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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)

Deterministic Hardness of Approximation For SVP in all Finite $\ell_p$ Norms
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)

Query-Efficient Fixpoints of $\ell_p$-Contractions
by: Haslebacher, Sebastian, et al.
Published: (2025)

On Approximability of Steiner Tree in $\ell_p$-metrics
by: Fleischmann, Henry, et al.
Published: (2023)

$\ell_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
by: Guruswami, Venkatesan, et al.
Published: (2021)

Improved Hardness of BDD and SVP Under Gap-(S)ETH
by: Bennett, Huck, et al.
Published: (2021)

Hardness of SetCover Reoptimization
by: Jansen, Klaus, et al.
Published: (2025)

On the Hardness of the Drone Delivery Problem
by: Bartlmae, Simon, et al.
Published: (2025)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
by: de Rezende, Susanna F., et al.
Published: (2026)

Hardness of Hypergraph Edge Modification Problems
by: Gishboliner, Lior, et al.
Published: (2025)

Worst-Case and Average-Case Hardness of Hypercycle and Database Problems
by: Fu, Cheng-Hao, et al.
Published: (2025)

Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice
by: Digulescu, Mircea-Adrian
Published: (2026)

Three Hardness Results for Graph Similarity Problems
by: Sun, He, et al.
Published: (2023)

Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More
by: Dalirrooyfard, Mina, et al.
Published: (2025)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
by: Guruswami, Venkatesan, et al.
Published: (2023)

A Brief Note on a Recent Claim About NP-Hard Problems and BQP
by: Chavrimootoo, Michael C.
Published: (2024)

Improved Hardness Results for the Guided Local Hamiltonian Problem
by: Cade, Chris, et al.
Published: (2022)

Fibers and Gleason parts for the maximal ideal space of $\mathcal A_u(B_{\ell_p})$
by: Dimant, Verónica, et al.
Published: (2024)

NP-Hardness and a PTAS for the Pinwheel Problem
by: Kleinberg, Robert, et al.
Published: (2026)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
by: Cavalar, Bruno P., et al.
Published: (2025)

On the Classical Hardness of the Semidirect Discrete Logarithm Problem in Finite Groups
by: Arif, Mohammad Ferry Husnil, et al.
Published: (2025)

SVP$_p$ is Deterministically NP-Hard for all $p > 2$, Even to Approximate Within a Factor of $2^{\log^{1-\varepsilon} n}$
by: Hair, Isaac M., et al.
Published: (2025)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
by: Esmer, Barış Can, et al.
Published: (2024)

AC^0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard
by: Lu, Jiaqi, 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)

On the Hardness of Approximation of the Fair k-Center Problem
by: Thejaswi, Suhas
Published: (2026)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
by: Adriaens, Florian, et al.
Published: (2024)

Meta Theorem for Hardness on FCP-Problem
by: Nagao, Atsuki, et al.
Published: (2025)

Bounds for Hardness Condensation in the Query Model
by: Kayal, Chandrima, et al.
Published: (2026)

Hardness of clique approximation for monotone circuits
by: Błasiok, Jarosław, et al.
Published: (2025)

Hardness Amplification via Group Theory
by: Nareddy, Tejas, et al.
Published: (2024)

Matching Cut and Variants on Bipartite Graphs of Bounded Radius and Diameter
by: Lucke, Felicia
Published: (2025)

Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions
by: Datta, Swarnalipa, et al.
Published: (2023)

Higher Hardness Results for the Reconfiguration of Odd Matchings
by: Dorfer, Joseph
Published: (2026)

Hard-to-Sample Distributions from Robust Extractors
by: Byramji, Farzan, et al.
Published: (2026)

Tetris is Hard with Just One Piece Type
by: MIT Hardness Group, et al.
Published: (2026)

Hard CNF Instances for Ideal Proof Systems
by: Hakoniemi, Tuomas, et al.
Published: (2026)

Are Depth-2 Regular Expressions Hard to Intersect?
by: Ascone, Rocco, et al.
Published: (2025)

Near Optimal Hardness of Approximating $k$-CSP
by: Minzer, Dor, et al.
Published: (2025)