Copertina

Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Li, Shuangle, Lin, Bingkai, Liu, Yuwei
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH
di: Gupta, Rishav, et al.
Pubblicazione: (2026)

PCP-free APX-Hardness of Nearest Codeword and Minimum Distance
di: Bhattiprolu, Vijay, et al.
Pubblicazione: (2025)

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

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

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

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

Treewidth Inapproximability and Tight ETH Lower Bound
di: Bonnet, Édouard
Pubblicazione: (2024)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
di: Foucaud, Florent, et al.
Pubblicazione: (2023)

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

Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation
di: Bringmann, Karl, et al.
Pubblicazione: (2024)

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

Structural Parameterizations for Two Bounded Degree Problems Revisited
di: Lampis, Michael, et al.
Pubblicazione: (2023)

Improved Lower Bounds for QAC0
di: Joshi, Malvika Raj, et al.
Pubblicazione: (2025)

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

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
di: Banik, Aritra, et al.
Pubblicazione: (2025)

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

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

Parameterized Complexity of the Star Decomposition Problem
di: Hajebi, Sahab, et al.
Pubblicazione: (2024)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
di: Wang, Yichuan
Pubblicazione: (2024)

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

Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing
di: Mao, Xinyu, et al.
Pubblicazione: (2024)

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

Improved Circuit Lower Bounds and Quantum-Classical Separations
di: Grewal, Sabee, et al.
Pubblicazione: (2024)

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

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

Lower Bounds on Relative Error Quantum Compression and Classical Shadows
di: Sankar, Kaushik
Pubblicazione: (2025)

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

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

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

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

A Quadratic Lower Bound for Noncommutative Circuits
di: Shastri, Pratik
Pubblicazione: (2026)

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

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

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

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

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

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

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

Lower Bounds for Subset Sum in Resolution with Modular Counting
di: Part, Fedor
Pubblicazione: (2022)