PCP-free APX-Hardness of Nearest Codeword and Minimum Distance.
Electron. Colloquium Comput. Complex., 2025
Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH.
Electron. Colloquium Comput. Complex., 2024
Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024
Baby PIH: Parameterized Inapproximability of Min CSP.
Electron. Colloquium Comput. Complex., 2023
Parameterized Inapproximability Hypothesis under ETH.
Electron. Colloquium Comput. Complex., 2023
Constant Approximating Parameterized <i>k</i>-SETCOVER is W[2]-hard.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023
Improved Hardness of Approximating k-Clique under ETH.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023
Constant Approximating Parameterized k-SetCover is W[2]-hard.
CoRR, 2022
On Lower Bounds of Approximating Parameterized k-Clique.
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022
A Survey on Parameterized Inapproximability: k-Clique, k-SetCover, and More.
CoRR, 2021
Generalized Sorting with Predictions.
Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021