Cover Image

Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gupta, Rishav, Lin, Bingkai, Zheng, Xin
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

Mind the Gap? Not for SVP Hardness under ETH!
by: Aggarwal, Divesh, et al.
Published: (2025)

Treewidth Inapproximability and Tight ETH Lower Bound
by: Bonnet, Édouard
Published: (2024)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
by: Grossman, Ofer, et al.
Published: (2023)

Treedepth Inapproximability and Exponential ETH Lower Bound
by: Bonnet, Édouard, et al.
Published: (2025)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
by: Kisfaludi-Bak, Sándor, et al.
Published: (2020)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
by: Wang, Yichuan
Published: (2024)

Tight Lower Bounds for Block-Structured Integer Programs
by: Hunkenschröder, Christoph, et al.
Published: (2024)

FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set
by: Chu, Huairui, et al.
Published: (2023)

Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
by: Alman, Josh, et al.
Published: (2025)

Lower Bounds for Approximate Sign Rank
by: Bindua, Riju, et al.
Published: (2026)

Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions
by: Blocki, Jeremiah, et al.
Published: (2021)

Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes
by: Block, Alexander R., et al.
Published: (2026)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
by: Basu, Arpon, et al.
Published: (2024)

Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
by: Wang, Qisheng, et al.
Published: (2024)

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
by: Jansen, Klaus, et al.
Published: (2025)

Query Lower Bounds for Correlation Clustering under Memory Constraints
by: Garg, Sumegha, et al.
Published: (2026)

A Framework for Computational Lower Bounds in Nontrivial Norm Approximation
by: Tang, Runshi, et al.
Published: (2026)

Partial Minimum Branching Program Size Problem is ETH-hard
by: Glinskih, Ludmila, et al.
Published: (2024)

Hardness Amplification for (Sparse) LPN
by: Aggarwal, Divesh, et al.
Published: (2026)

Linear Space Streaming Lower Bounds for Approximating CSPs
by: Chou, Chi-Ning, et al.
Published: (2021)

When Majority Fails: Tight Bounds for Correlation Distillation Conjectures
by: Kamath, Pritish, et al.
Published: (2026)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
by: Singer, Noah G., et al.
Published: (2026)

Local Enumeration and Majority Lower Bounds
by: Gurumukhani, Mohit, et al.
Published: (2024)

Spectral Lower Bounds for Local Search
by: Brânzei, Simina, et al.
Published: (2024)

Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
by: Kothari, Pravesh K., et al.
Published: (2024)

Tight Fine-Grained Bounds for Direct Access on Join Queries
by: Bringmann, Karl, et al.
Published: (2022)

A Quadratic Lower Bound for Noncommutative Circuits
by: Shastri, Pratik
Published: (2026)

IPS Lower Bounds for Formulas and Sum of ROABPs
by: Chatterjee, Prerona, et al.
Published: (2025)

Lower Bounds for Set-Multilinear Branching Programs
by: Chatterjee, Prerona, et al.
Published: (2023)

Lower Bounds from Succinct Hitting Sets
by: Chatterjee, Prerona, et al.
Published: (2023)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
by: Li, Qian, et al.
Published: (2025)

Hardness of Maximum Likelihood Learning of DPPs
by: Grigorescu, Elena, et al.
Published: (2022)

Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
by: Byramji, Farzan, et al.
Published: (2025)

Tight Bounds for Quantum Phase Estimation and Related Problems
by: Mande, Nikhil S., et al.
Published: (2023)

Quantum Lovász Local Lemma: Shearer's Bound is Tight
by: He, Kun, et al.
Published: (2018)

Convergent Gate Elimination and Constructive Circuit Lower Bounds
by: Carmosino, Marco, et al.
Published: (2026)

Top-Down Lower Bounds for Depth-Four Circuits
by: Göös, Mika, et al.
Published: (2023)

Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies
by: Gajulapalli, Karthik, et al.
Published: (2025)