arxiv: 2605.08797 · v1 · submitted 2026-05-09 · 💻 cs.CC

Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH

Rishav Gupta , Bingkai Lin , Xin Zheng This is my paper

Pith reviewed 2026-05-12 00:59 UTC · model grok-4.3

classification 💻 cs.CC

keywords Exponential Time HypothesisMaximum Likelihood DecodingParameterized ComplexityInapproximabilityCover FamilyLower BoundsNearest Codeword ProblemGap-MAXLIN

0 comments

The pith

Assuming ETH, approximating parameterized Maximum Likelihood Decoding within a constant factor requires n to the power of Omega(k) time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that under the Exponential Time Hypothesis there is no n to the o of k time algorithm for approximating the parameterized Maximum Likelihood Decoding problem to within any fixed constant factor. The same tight bound holds for the Nearest Codeword Problem. The argument begins from the known ETH hardness of approximating Gap-MAXLIN and uses a new combinatorial object called a cover family to build a deterministic reduction that preserves the gap. This removes the need for stronger randomized assumptions such as Gap-ETH and improves the exponent from the previous n to the Omega of k over poly log k.

Core claim

We present a simple deterministic reduction which, assuming the Exponential Time Hypothesis (ETH), yields tight lower bounds for approximating the parameterized Maximum Likelihood Decoding problem (MLD) and the parameterized Nearest Codeword Problem (NCP) within some fixed constant factor. Our starting point is the ETH-based exponential-time hardness of (c,s)-Gap-MAXLIN. We transform a (c,s)-Gap-MAXLIN instance into an instance of gamma-Gap k-MLD via a novel combinatorial object that we call a cover family. We provide both a randomized construction of the required cover families and a subsequent derandomization.

What carries the argument

A cover family, the novel combinatorial object that maps Gap-MAXLIN instances into Gap-MLD instances while preserving the approximation gap.

If this is right

Constant-factor approximation of parameterized MLD requires n to the Omega of k time under ETH.
The same n to the Omega of k lower bound applies to constant-factor approximation of the Nearest Codeword Problem.
Derandomization of cover families produces a fully deterministic reduction.
The approach gives a direct path from Gap-MAXLIN hardness without intermediate 2-CSP problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Cover families may simplify reductions for other parameterized inapproximability questions in coding theory.
The result suggests that moderate values of the parameter k already force superpolynomial time even for crude approximations.
If similar objects exist for other source problems, the technique could tighten ETH bounds across additional parameterized approximation tasks.

Load-bearing premise

The Exponential Time Hypothesis implies that Gap-MAXLIN cannot be solved in subexponential time.

What would settle it

An algorithm that approximates parameterized MLD to within a fixed constant factor in n to the o of k time for every k, or a refutation of the Exponential Time Hypothesis.

read the original abstract

We present a simple deterministic reduction which, assuming the Exponential Time Hypothesis ($\mathsf{ETH}$), yields tight lower bounds for approximating the parameterized Maximum Likelihood Decoding problem ($\mathsf{MLD}$) and the parameterized Nearest Codeword Problem ($\mathsf{NCP}$) within some fixed constant factor. Our starting point is the ETH-based exponential-time hardness of $(c,s)$-Gap-$\mathsf{MAXLIN}$ established in [BHI+24]. We transform a $(c,s)$-Gap-$\mathsf{MAXLIN}$ instance into an instance of $\gamma$-Gap $k$-$\mathsf{MLD}$ via a novel combinatorial object that we call a cover family. We provide both a randomized construction of the required cover families and a subsequent derandomization. Prior to our work, $n^{\Omega(k)}$ hardness for constant-factor approximation was only shown under the randomized Gap Exponential Time Hypothesis Gap-$\mathsf{ETH}$ [Man20], which is a much stronger assumption than $\mathsf{ETH}$. Under $\mathsf{ETH}$, the strongest known lower bound was $n^{\Omega(k/\operatorname{poly} \log k)}$ due to [BKM25]. Unlike previous approaches that rely on reductions from the hardness of approximating $2$-$\mathsf{CSP}$, our reduction provides a more direct and conceptually simpler route to achieving the optimal lower bounds.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives a direct deterministic reduction from Gap-MAXLIN that finally gets the tight n^Omega(k) ETH lower bound for constant-factor approximation of parameterized MLD and NCP.

read the letter

The core advance is a new combinatorial object called a cover family that lets them embed a Gap-MAXLIN instance into a gamma-Gap k-MLD instance while keeping the gap constant and independent of k. They give a randomized construction for the families and then derandomize it in polynomial time. This produces the optimal exponent under plain ETH, improving on the n^Omega(k / polylog k) bound from BKM25 and removing the need for Gap-ETH that Man20 required. The route is also more direct than prior reductions that went through 2-CSP approximation hardness, which makes the argument easier to follow at a high level. The starting point from BHI+24 is external and standard, so there is no circularity in the hardness transfer. The parameter k and instance size blowup stay controlled, and the derandomization step is claimed to preserve the necessary properties without extra logarithmic factors. That said, the soundness ultimately rests on verifying that the cover families satisfy the exact covering and gap-preservation properties after derandomization; the abstract outlines the steps cleanly but the full proof details would need checking to confirm no hidden loss in the constant gamma. This work is aimed at researchers in fine-grained complexity and coding theory who care about ETH-based approximation lower bounds for parameterized problems. Anyone following the line of results on MLD/NCP hardness will find the new gadget and the tightened exponent useful. The paper shows clear thinking and honest engagement with the prior literature, so it deserves a serious referee even if some technical steps require careful scrutiny in review.

Referee Report

1 major / 2 minor

Summary. The paper claims a deterministic reduction, assuming ETH, from the ETH-hard (c,s)-Gap-MAXLIN problem to constant-factor γ-Gap k-MLD (and similarly for NCP). The reduction uses a new combinatorial object called a cover family, constructed first randomly and then derandomized in polynomial time. This yields tight n^Ω(k) lower bounds for constant-factor approximation of the parameterized MLD and NCP problems, improving on prior n^Ω(k/poly log k) bounds under ETH and on results requiring the stronger Gap-ETH assumption.

Significance. If correct, the result is significant: it closes the gap between ETH and Gap-ETH for these parameterized approximation problems via a direct and conceptually simpler route than prior 2-CSP reductions. The explicit randomized construction plus derandomization of cover families, together with the parameter-preserving property, would constitute a clean technical contribution to ETH-based hardness in coding theory.

major comments (1)

§3 (Construction of cover families): The randomized construction is claimed to produce a cover family with the required density and gap-preservation properties with high probability; however, the precise probability bound and the dependence on the Gap-MAXLIN parameters (c,s) are not stated explicitly enough to verify that the subsequent derandomization step (via conditional expectations or limited-independence hashing) runs in poly(n) time while keeping the blow-up independent of k.

minor comments (2)

The notation for the cover family (Definition 2.3) uses several parameters (m, t, r) whose roles in the gap transfer are introduced only in the proof of Lemma 3.4; a short table summarizing the parameter mapping from Gap-MAXLIN to γ-Gap k-MLD would improve readability.
Theorem 1.1 states the final lower bound as n^Ω(k); it would be helpful to make explicit the hidden constant in the exponent and confirm it is independent of the approximation factor γ.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading, the positive assessment of the result's significance, and the recommendation for minor revision. We address the single major comment below.

read point-by-point responses

Referee: §3 (Construction of cover families): The randomized construction is claimed to produce a cover family with the required density and gap-preservation properties with high probability; however, the precise probability bound and the dependence on the Gap-MAXLIN parameters (c,s) are not stated explicitly enough to verify that the subsequent derandomization step (via conditional expectations or limited-independence hashing) runs in poly(n) time while keeping the blow-up independent of k.

Authors: We agree that the success probability and its dependence on (c,s) should be stated more explicitly. In the revised version we will add a self-contained lemma in §3 that bounds the failure probability by 1/n (via a standard Chernoff + union-bound argument over the O(n) equations of the Gap-MAXLIN instance). The bound depends on c and s only through the choice of the cover-family size m = poly(n), which is independent of the parameter k. Consequently the derandomization (conditional expectations or limited-independence hashing) runs in poly(n) time and introduces no additional blow-up in k or in the instance size. The technical content of the reduction remains unchanged. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's derivation consists of a deterministic reduction from the external ETH-hardness of (c,s)-Gap-MAXLIN (cited from [BHI+24]) to constant-factor γ-Gap k-MLD, using a newly introduced combinatorial object (cover families) whose randomized construction and derandomization are explicitly provided. No step reduces by definition or construction to the target result itself; the cover family is defined and built independently to embed the gap-preserving mapping, and the ETH transfer relies on the cited prior hardness rather than any self-referential fitting, ansatz smuggling, or uniqueness theorem from the authors' own prior work. The central lower-bound claim therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the ETH assumption and the prior Gap-MAXLIN hardness result; the cover family is a newly defined combinatorial object whose properties are established via randomized and derandomized constructions in the paper.

axioms (1)

domain assumption Exponential Time Hypothesis (ETH)
Starting hardness assumption for the Gap-MAXLIN problem as established in the cited [BHI+24]

invented entities (1)

cover family no independent evidence
purpose: Combinatorial object used to transform a (c,s)-Gap-MAXLIN instance into a gamma-Gap k-MLD instance
Newly introduced object with both randomized construction and subsequent derandomization provided in the paper

pith-pipeline@v0.9.0 · 5543 in / 1270 out tokens · 47682 ms · 2026-05-12T00:59:43.609911+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

[1]

51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) , pages=

Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems Under ETH , author=. 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) , pages=. 2024 , organization=

work page 2024
[2]

2017 , publisher=

Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis , author=. 2017 , publisher=

work page 2017
[3]

Proceedings of the twenty-ninth annual ACM symposium on Theory of computing , pages=

Algorithmic complexity in coding theory and the minimum distance problem , author=. Proceedings of the twenty-ninth annual ACM symposium on Theory of computing , pages=

work page
[4]

SIAM Journal on Computing , volume=

The parametrized complexity of some fundamental problems in coding theory , author=. SIAM Journal on Computing , volume=. 1999 , publisher=

work page 1999
[5]

Impagliazzo, Russell and Paturi, Ramamohan , title =. J. Comput. Syst. Sci. , month = mar, pages =. 2001 , issue_date =. doi:10.1006/jcss.2000.1727 , abstract =

work page doi:10.1006/jcss.2000.1727 2001
[6]

Tovey , abstract =

Craig A. Tovey , abstract =. A simplified NP-complete satisfiability problem , journal =. 1984 , issn =. doi:https://doi.org/10.1016/0166-218X(84)90081-7 , url =

work page doi:10.1016/0166-218x(84)90081-7 1984
[7]

and Wu, David J

Bitansky, Nir and Harsha, Prahladh and Ishai, Yuval and Rothblum, Ron D. and Wu, David J. , booktitle=. Dot-Product Proofs and Their Applications , year=

work page
[8]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC) , pages=

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all l_p Norms , author=. Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC) , pages=

work page
[9]

Journal of the ACM (JACM) , volume=

Parameterized Intractability of Even Set and Shortest Vector Problem , author=. Journal of the ACM (JACM) , volume=

work page
[10]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k -Coverage, Unique Set Cover and Related Problems (via t -wise Agreement Testing Theorem) , author=. Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

work page 2020
[11]

Near Optimal Constant Inapproximability under

Mitali Bafna and. Near Optimal Constant Inapproximability under. Proceedings of the 57th Annual. 2025 , url =. doi:10.1145/3717823.3718257 , timestamp =

work page doi:10.1145/3717823.3718257 2025
[12]

Parameterized Complexity , author=

work page
[13]

Journal of Computer and System Sciences , volume=

The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations , author=. Journal of Computer and System Sciences , volume=

work page
[14]

IEEE Transactions on Information Theory , volume=

On the Inherent Intractability of Certain Coding Problems , author=. IEEE Transactions on Information Theory , volume=

work page
[15]

Mildly exponential reduction from gap-3SAT to polynomial-gap label-cover

Irit Dinur. Mildly exponential reduction from gap-3SAT to polynomial-gap label-cover. Electronic colloquium on computational complexity ECCC ; research reports, surveys and books in computational complexity. 2016

work page 2016
[16]

The Cost of Consistency: Submodular Maximization with Constant Recourse , booktitle =

Venkatesan Guruswami and Bingkai Lin and Xuandi Ren and Yican Sun and Kewen Wu , editor =. Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under. Proceedings of the 57th Annual. 2025 , url =. doi:10.1145/3717823.3718130 , timestamp =

work page doi:10.1145/3717823.3718130 2025
[17]

2026 , eprint=

Mind the Gap? Not for SVP Hardness under ETH! , author=. 2026 , eprint=

work page 2026
[18]

39th Computational Complexity Conference (CCC 2024) , pages =

Guruswami, Venkatesan and Ren, Xuandi and Sandeep, Sai , title =. 39th Computational Complexity Conference (CCC 2024) , pages =. 2024 , volume =. doi:10.4230/LIPIcs.CCC.2024.27 , annote =

work page doi:10.4230/lipics.ccc.2024.27 2024
[19]

and Micciancio, D

Dumer, I. and Micciancio, D. and Sudan, M. , journal=. Hardness of approximating the minimum distance of a linear code , year=

work page