Cover Image

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Guruswami, Venkatesan, Lin, Bingkai, Ren, Xuandi, Sun, Yican, Wu, Kewen
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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

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

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

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)

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

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

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
by: S., Karthik C., et al.
Published: (2021)

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

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
by: Alrabiah, Omar, 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)

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

Near Optimal Hardness of Approximating $k$-CSP
by: Minzer, Dor, et al.
Published: (2025)

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

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

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

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

Hardness of Learning Boolean Functions from Label Proportions
by: Guruswami, Venkatesan, 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)

$\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)

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

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
by: Conneryd, Jonas, et al.
Published: (2025)

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

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

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
by: Chen, Yijia, et al.
Published: (2023)

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

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

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
by: S., Karthik C., et al.
Published: (2024)

Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique
by: Gamarnik, David, et al.
Published: (2023)

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

Optimal Monotone Depth-Three Circuit Lower Bounds for Majority
by: Gurumukhani, Mohit, et al.
Published: (2026)

Optimal Lower Bounds for Symmetric Modular Circuits
by: Pago, Benedikt
Published: (2026)

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

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

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