Search Results

Documents authored by Li, Shuangle

Document
DOI: 10.4230/LIPIcs.STACS.2025.65
On Average Baby PIH and Its Applications

Authors: Yuwei Liu, Yijia Chen, Shuangle Li, Bingkai Lin, and Xin Zheng

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
The Parameterized Inapproximability Hypothesis (PIH) asserts that no FPT algorithm can decide whether a given 2CSP instance parameterized by the number of variables is satisfiable, or at most a constant fraction of its constraints can be satisfied simultaneously. In a recent breakthrough, Guruswami, Lin, Ren, Sun, and Wu (STOC 2024) proved the PIH under the Exponential Time Hypothesis (ETH). However, it remains a major open problem whether the PIH can be established assuming only W[1]≠FPT. Towards this goal, Guruswami, Ren, and Sandeep (CCC 2024) showed a weaker version of the PIH called the Baby PIH under W[1]≠FPT. In addition, they proposed one more intermediate assumption known as the Average Baby PIH, which might lead to further progress on the PIH. As the main contribution of this paper, we prove that the Average Baby PIH holds assuming W[1]≠FPT. Given a 2CSP instance where the number of its variables is the parameter, the Average Baby PIH states that no FPT algorithm can decide whether (i) it is satisfiable or (ii) any multi-assignment that satisfies all constraints must assign each variable more than r values on average for any fixed constant r > 1. So there is a gap between (i) and (ii) on the average number of values that are assigned to a variable, i.e., 1 vs. r. If this gap occurs in each variable instead of on average, we get the original Baby PIH. So central to our paper is an FPT self-reduction for 2CSP instances that turns the above gap for each variable into a gap on average. By the known W[1]-hardness for the Baby PIH, this proves that the Average Baby PIH holds under W[1] ≠ FPT. As applications, we obtain (i) for the first time, the W[1]-hardness of constant approximating k-ExactCover, and (ii) a tight relationship between running time lower bounds in the Average Baby PIH and approximating the parameterized Nearest Codeword Problem (k-NCP).
Cite as

Yuwei Liu, Yijia Chen, Shuangle Li, Bingkai Lin, and Xin Zheng. On Average Baby PIH and Its Applications. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 65:1-65:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.STACS.2025.65,
  author =	{Liu, Yuwei and Chen, Yijia and Li, Shuangle and Lin, Bingkai and Zheng, Xin},
  title =	{{On Average Baby PIH and Its Applications}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{65:1--65:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.65},
  URN =		{urn:nbn:de:0030-drops-228900},
  doi =		{10.4230/LIPIcs.STACS.2025.65},
  annote =	{Keywords: Average Baby PIH, Parameterized Inapproximability, Constraint Satisfaction Problem, Exact Set Cover, W\lbrack1\rbrack-hardness}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.107
Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems Under ETH

Authors: Shuangle Li, Bingkai Lin, and Yuwei Liu

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
In this paper we present a new gap-creating randomized self-reduction for the parameterized Maximum Likelihood Decoding problem over 𝔽_p (k-MLD_p). The reduction takes a k-MLD_p instance with k⋅ n d-dimensional vectors as input, runs in O(d2^{O(k)}n^{1.01}) time for some computable function f, outputs a (3/2-ε)-Gap-k'-MLD_p instance for any ε > 0, where k' = O(k²log k). Using this reduction, we show that assuming the randomized Exponential Time Hypothesis (ETH), no algorithms can approximate k-MLD_p (and therefore its dual problem k-NCP_p) within factor (3/2-ε) in f(k)⋅ n^{o(√{k/log k})} time for any ε > 0. We then use reduction by Bhattacharyya, Ghoshal, Karthik and Manurangsi (ICALP 2018) to amplify the (3/2-ε)-gap to any constant. As a result, we show that assuming ETH, no algorithms can approximate k-NCP_p and k-MDP_p within γ-factor in f(k)⋅ n^{o(k^{ε_γ})} time for some constant ε_γ > 0. Combining with the gap-preserving reduction by Bennett, Cheraghchi, Guruswami and Ribeiro (STOC 2023), we also obtain similar lower bounds for k-MDP_p, k-CVP_p and k-SVP_p. These results improve upon the previous f(k)⋅ n^{Ω(poly log k)} lower bounds for these problems under ETH using reductions by Bhattacharyya et al. (J.ACM 2021) and Bennett et al. (STOC 2023).
Cite as

Shuangle Li, Bingkai Lin, and Yuwei Liu. Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems Under ETH. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 107:1-107:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ICALP.2024.107,
  author =	{Li, Shuangle and Lin, Bingkai and Liu, Yuwei},
  title =	{{Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems Under ETH}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{107:1--107:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.107},
  URN =		{urn:nbn:de:0030-drops-202500},
  doi =		{10.4230/LIPIcs.ICALP.2024.107},
  annote =	{Keywords: Nearest Codeword Problem, Hardness of Approximations, Fine-grained Complexity, Parameterized Complexity, Minimum Distance Problem, Shortest Vector Problem}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact