Cover Image

PCP-free APX-Hardness of Nearest Codeword and Minimum Distance

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bhattiprolu, Vijay, Guruswami, Venkatesan, Ren, Xuandi
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices
by: Bhattiprolu, Vijay, et al.
Published: (2024)

PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs
by: Guruswami, Venkatesan, et al.
Published: (2025)

Baby PIH: Parameterized Inapproximability of Min CSP
by: Guruswami, Venkatesan, et al.
Published: (2023)

Strong Inapproximability for a Promise Rank Problem
by: Guruswami, Venkatesan, et al.
Published: (2026)

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

Scheduling Problems with Constrained Rejections
by: Davies, Sami, et al.
Published: (2025)

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
by: Guruswami, Venkatesan, et al.
Published: (2024)

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)

Hardness of Learning Boolean Functions from Label Proportions
by: Guruswami, Venkatesan, et al.
Published: (2024)

Structure Theorems (and Fast Algorithms) for List Recovery of Subspace-Design Codes
by: Goyal, Rohan, et al.
Published: (2025)

New constructions of pseudorandom codes
by: Ghentiyala, Surendra, et al.
Published: (2024)

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
by: Alrabiah, Omar, et al.
Published: (2024)

Punctured Low-Bias Codes Behave Like Random Linear Codes
by: Guruswami, Venkatesan, et al.
Published: (2021)

Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH
by: Li, Shuangle, et al.
Published: (2024)

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

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
by: Brakensiek, Joshua, et al.
Published: (2026)

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

Explicit Constant-Alphabet Subspace Design Codes
by: Goyal, Rohan, et al.
Published: (2026)

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
by: Guruswami, Venkatesan, et al.
Published: (2025)

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
by: Guruswami, Venkatesan, et al.
Published: (2024)

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
by: Gharibian, Sevag, et al.
Published: (2021)

Communication with Imperfectly Shared Randomness
by: Canonne, Clément L., et al.
Published: (2014)

The PCP-like Theorem for Sub-linear Time Inapproximability
by: Ma, Hengzhao, et al.
Published: (2021)

A Zero-Knowledge PCP Theorem
by: Gur, Tom, et al.
Published: (2024)

The status of the quantum PCP conjecture (games version)
by: Natarajan, Anand, et al.
Published: (2024)

Explicit optimal-length locally repairable codes of distance 5
by: Beemer, Allison, et al.
Published: (2018)

Quasi-quantum states and the quasi-quantum PCP theorem
by: Arad, Itai, et al.
Published: (2024)

The Richness of CSP Non-redundancy
by: Brakensiek, Joshua, et al.
Published: (2025)

Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash
by: Babichenko, Yakov, et al.
Published: (2015)

Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD
by: Deligkas, Argyrios, et al.
Published: (2026)

Nearest Neighbor Complexity and Boolean Circuits
by: DiCicco, Mason, et al.
Published: (2024)

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

Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture
by: Weggemans, Jordi, et al.
Published: (2023)

A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem
by: Li, Zhengyu, et al.
Published: (2023)

Finding Minimum Matching Cuts in $H$-free Graphs
by: Lucke, Felicia, et al.
Published: (2025)

Finding Minimum Distance Preservers: A Parameterized Study
by: Simonov, Kirill, et al.
Published: (2026)

Maximizing Minimum Cycle Bases Intersection
by: Watel, Dimitri, et al.
Published: (2024)

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)

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)