Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Venkatesan Guruswami, Xuandi Ren, and Sai Sandeep. Baby PIH: Parameterized Inapproximability of Min CSP. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{guruswami_et_al:LIPIcs.CCC.2024.27, author = {Guruswami, Venkatesan and Ren, Xuandi and Sandeep, Sai}, title = {{Baby PIH: Parameterized Inapproximability of Min CSP}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {27:1--27:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.27}, URN = {urn:nbn:de:0030-drops-204237}, doi = {10.4230/LIPIcs.CCC.2024.27}, annote = {Keywords: Parameterized Inapproximability Hypothesis, Constraint Satisfaction Problems} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Clément Dallard, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Martin Milanič. Computing Tree Decompositions with Small Independence Number. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 51:1-51:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dallard_et_al:LIPIcs.ICALP.2024.51, author = {Dallard, Cl\'{e}ment and Fomin, Fedor V. and Golovach, Petr A. and Korhonen, Tuukka and Milani\v{c}, Martin}, title = {{Computing Tree Decompositions with Small Independence Number}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {51:1--51:18}, 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.51}, URN = {urn:nbn:de:0030-drops-201945}, doi = {10.4230/LIPIcs.ICALP.2024.51}, annote = {Keywords: tree-independence number, approximation, parameterized algorithms} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
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)
@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} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Huairui Chu and Bingkai Lin. FPT Approximation Using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 19:1-19:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chu_et_al:LIPIcs.ISAAC.2023.19, author = {Chu, Huairui and Lin, Bingkai}, title = {{FPT Approximation Using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {19:1--19:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.19}, URN = {urn:nbn:de:0030-drops-193216}, doi = {10.4230/LIPIcs.ISAAC.2023.19}, annote = {Keywords: FPT approximation algorithm, Treewidth, Capacitated vertex cover, Target set selection, Vector dominating set} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Bingkai Lin, Xuandi Ren, Yican Sun, and Xiuhan Wang. On Lower Bounds of Approximating Parameterized k-Clique. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 90:1-90:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{lin_et_al:LIPIcs.ICALP.2022.90, author = {Lin, Bingkai and Ren, Xuandi and Sun, Yican and Wang, Xiuhan}, title = {{On Lower Bounds of Approximating Parameterized k-Clique}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {90:1--90:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.90}, URN = {urn:nbn:de:0030-drops-164317}, doi = {10.4230/LIPIcs.ICALP.2022.90}, annote = {Keywords: parameterized complexity, k-clique, hardness of approximation} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Bingkai Lin. A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 81:1-81:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{lin:LIPIcs.ICALP.2019.81, author = {Lin, Bingkai}, title = {{A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {81:1--81:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.81}, URN = {urn:nbn:de:0030-drops-106573}, doi = {10.4230/LIPIcs.ICALP.2019.81}, annote = {Keywords: set cover, FPT inapproximability, gap-producing reduction, (n, k)-universal set} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Ian Mertz, Toniann Pitassi, and Yuanhao Wei. Short Proofs Are Hard to Find. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 84:1-84:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{mertz_et_al:LIPIcs.ICALP.2019.84, author = {Mertz, Ian and Pitassi, Toniann and Wei, Yuanhao}, title = {{Short Proofs Are Hard to Find}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {84:1--84:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.84}, URN = {urn:nbn:de:0030-drops-106605}, doi = {10.4230/LIPIcs.ICALP.2019.84}, annote = {Keywords: automatizability, Resolution, SAT solvers, proof complexity} }