#hardness of approximation
5 papers match
On the Computational Complexity of (Extended) Threshold Dimension and (Semi-)Ladder Index
Pasin Manurangsi
The paper investigates the difficulty of computing the threshold dimension and extended threshold dimension of hypothesis classes, proving NP‑hardness, co‑NP‑hardness, and strong h…
Tight UGC Thresholds for Geometric Stabbing Problems
Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray
The paper proves tight hardness thresholds under the Unique Games Conjecture for several geometric stabbing problems by linking integrality‑gap instances of covering LPs to matchin…
Explicit Separations for One-Query Unitary Synthesis
Fangqi Dong, Alex Lombardi, Fermi Ma
The paper studies how hard it is to construct specific quantum gates using only a single query to a classical oracle, proving lower bounds for certain explicit unitaries and showin…
ETH-Hardness of Learning Monotone Circuits and Approximating Their Size
Bruno Cavalar, Susanna F. de Rezende, Matthew Gray +1
The paper proves that, assuming the Randomised Exponential-Time Hypothesis, both PAC-learning monotone formulas and multiplicatively approximating the minimum monotone circuit size…
Hierarchical -Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs
MichaÅ Szyfelbein, Dariusz Dereniowski
The paper studies hierarchical clustering where the recursion stops once clusters belong to a specified graph class (trees or bounded‑diameter graphs), providing poly‑time logarith…