DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2026.1

Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding Under ETH

Authors: Rishav Gupta, Bingkai Lin, and Xin Zheng

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract

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 established in [Nir Bitansky et al., 2024]. We transform a (c, s)-Gap MAXLIN instance into an instance of γ-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. Prior to our work, n^{Ω(k)} hardness for constant-factor approximation was only shown under the randomized Gap Exponential Time Hypothesis Gap-ETH [Pasin Manurangsi, 2020], which is a much stronger assumption than ETH. Under ETH, the strongest known lower bound was n^{Ω(k/poly log k)} due to [Mitali Bafna et al., 2025]. Unlike previous approaches that rely on reductions from the hardness of approximating 2-CSP, our reduction provides a more direct and conceptually simpler route to achieving the optimal lower bounds.

Cite as

Rishav Gupta, Bingkai Lin, and Xin Zheng. Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding Under ETH. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 1:1-1:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.CCC.2026.1,
  author =	{Gupta, Rishav and Lin, Bingkai and Zheng, Xin},
  title =	{{Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding Under ETH}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{1:1--1:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.1},
  URN =		{urn:nbn:de:0030-drops-270439},
  doi =		{10.4230/LIPIcs.CCC.2026.1},
  annote =	{Keywords: Maximum Likelihood Decoding, Parameterized Complexity, Hardness of Approximation, Exponential Time Hypothesis}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.8

Mind the Gap? Not for SVP Hardness Under ETH!

Authors: Divesh Aggarwal, Rishav Gupta, Aditya Morolia, and Chuanqi Zhang

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

We prove new hardness results for fundamental lattice problems under the Exponential Time Hypothesis (ETH). Building on a recent breakthrough by Bitansky et al. [BHIRW24], who gave a polynomial-time reduction from 3SAT to the (gap) MAXLIN problem - a class of CSPs with linear equations over finite fields - we derive ETH hardness for several lattice problems. First, we show that for any p ∈ [1, ∞), there exists an explicit constant γ > 1 such that CVP _{p,γ} (the 𝓁_p-norm approximate Closest Vector Problem) does not admit a 2^o(n)-time algorithm unless ETH is false. Our reduction is deterministic and proceeds via a direct reduction from (gap) MAXLIN to CVP _{p,γ}. Our main contribution is a randomized ETH hardness result for SVP _{p,γ} (the 𝓁_p-norm approximate Shortest Vector Problem) for all p ∈ (2, ∞). This result relies on a novel geometric property of the integer lattice ℤⁿ in the 𝓁_p norm, which says that for any p ∈ (2, ∞), the number of lattice vectors close to 1/2 1_n (in the 𝓁_p norm) is exponentially larger than the number of short vectors (namely those close to the origin). We establish this property via a new inequality for the Theta function, which we use to get a randomized reduction from CVP _{p,γ} to SVP _{p,γ'}. Finally, we also use our ideas to give some minor improvements over prior reductions from 3SAT to BDD _{p, α} (the Bounded Distance Decoding Problem), yielding better ETH hardness results for BDD _{p, α} for any p ∈ [1, ∞) and α > α_p^{‡}, where α_p^{‡} is an explicit threshold depending on p.

Cite as

Divesh Aggarwal, Rishav Gupta, Aditya Morolia, and Chuanqi Zhang. Mind the Gap? Not for SVP Hardness Under ETH!. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 8:1-8:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{aggarwal_et_al:LIPIcs.ICALP.2026.8,
  author =	{Aggarwal, Divesh and Gupta, Rishav and Morolia, Aditya and Zhang, Chuanqi},
  title =	{{Mind the Gap? Not for SVP Hardness Under ETH!}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{8:1--8:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.8},
  URN =		{urn:nbn:de:0030-drops-263979},
  doi =		{10.4230/LIPIcs.ICALP.2026.8},
  annote =	{Keywords: Lattices, Fine-Grained Complexity, Exponential Time Hypothesis, Post-Quantum Cryptography}
}

Search Results

Documents authored by Gupta, Rishav

Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding Under ETH

Abstract

Cite as

Mind the Gap? Not for SVP Hardness Under ETH!

Abstract

Cite as

Thanks for your feedback!

Could not send message