Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Naoto Ohsaka. Alphabet Reduction for Reconfiguration Problems. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 113:1-113:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{ohsaka:LIPIcs.ICALP.2024.113, author = {Ohsaka, Naoto}, title = {{Alphabet Reduction for Reconfiguration Problems}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {113:1--113:17}, 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.113}, URN = {urn:nbn:de:0030-drops-202560}, doi = {10.4230/LIPIcs.ICALP.2024.113}, annote = {Keywords: reconfiguration problems, hardness of approximation, Hadamard codes, alphabet reduction} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Alberto Larrauri and Stanislav Živný. Solving Promise Equations over Monoids and Groups. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 146:1-146:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{larrauri_et_al:LIPIcs.ICALP.2024.146, author = {Larrauri, Alberto and \v{Z}ivn\'{y}, Stanislav}, title = {{Solving Promise Equations over Monoids and Groups}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {146:1--146: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.146}, URN = {urn:nbn:de:0030-drops-202893}, doi = {10.4230/LIPIcs.ICALP.2024.146}, annote = {Keywords: constraint satisfaction, promise constraint satisfaction, equations, minions} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Amey Bhangale, Prahladh Harsha, and Sourya Roy. Mixing of 3-Term Progressions in Quasirandom Groups. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 20:1-20:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bhangale_et_al:LIPIcs.ITCS.2022.20, author = {Bhangale, Amey and Harsha, Prahladh and Roy, Sourya}, title = {{Mixing of 3-Term Progressions in Quasirandom Groups}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {20:1--20:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.20}, URN = {urn:nbn:de:0030-drops-156163}, doi = {10.4230/LIPIcs.ITCS.2022.20}, annote = {Keywords: Quasirandom groups, 3-term arithmetic progressions} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Amey Bhangale and Aleksa Stanković. Max-3-Lin over Non-Abelian Groups with Universal Factor Graphs. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 21:1-21:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bhangale_et_al:LIPIcs.ITCS.2022.21, author = {Bhangale, Amey and Stankovi\'{c}, Aleksa}, title = {{Max-3-Lin over Non-Abelian Groups with Universal Factor Graphs}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {21:1--21:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.21}, URN = {urn:nbn:de:0030-drops-156177}, doi = {10.4230/LIPIcs.ITCS.2022.21}, annote = {Keywords: Universal factor graphs, linear equations, non-abelian groups, hardness of approximation} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Amey Bhangale, Diptarka Chakraborty, and Rajendra Kumar. Hardness of Approximation of (Multi-)LCS over Small Alphabet. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bhangale_et_al:LIPIcs.APPROX/RANDOM.2020.38, author = {Bhangale, Amey and Chakraborty, Diptarka and Kumar, Rajendra}, title = {{Hardness of Approximation of (Multi-)LCS over Small Alphabet}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {38:1--38:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.38}, URN = {urn:nbn:de:0030-drops-126418}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.38}, annote = {Keywords: Longest common subsequence, Hardness of approximation, ETH-hardness, Densest k-subgraph problem} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Amey Bhangale and Subhash Khot. Simultaneous Max-Cut Is Harder to Approximate Than Max-Cut. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bhangale_et_al:LIPIcs.CCC.2020.9, author = {Bhangale, Amey and Khot, Subhash}, title = {{Simultaneous Max-Cut Is Harder to Approximate Than Max-Cut}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {9:1--9:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.9}, URN = {urn:nbn:de:0030-drops-125610}, doi = {10.4230/LIPIcs.CCC.2020.9}, annote = {Keywords: Simultaneous CSPs, Unique Games hardness, Max-Cut} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Orr Paradise. Smooth and Strong PCPs. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 2:1-2:41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{paradise:LIPIcs.ITCS.2020.2, author = {Paradise, Orr}, title = {{Smooth and Strong PCPs}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {2:1--2:41}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.2}, URN = {urn:nbn:de:0030-drops-116875}, doi = {10.4230/LIPIcs.ITCS.2020.2}, annote = {Keywords: Interactive and probabilistic proof systems, Probabilistically checkable proofs, Hardness of approximation} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Venkatesan Guruswami and Sai Sandeep. Rainbow Coloring Hardness via Low Sensitivity Polymorphisms. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{guruswami_et_al:LIPIcs.APPROX-RANDOM.2019.15, author = {Guruswami, Venkatesan and Sandeep, Sai}, title = {{Rainbow Coloring Hardness via Low Sensitivity Polymorphisms}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {15:1--15:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.15}, URN = {urn:nbn:de:0030-drops-112303}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.15}, annote = {Keywords: inapproximability, hardness of approximation, constraint satisfaction, hypergraph coloring, polymorphisms} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Amey Bhangale and Subhash Khot. UG-Hardness to NP-Hardness by Losing Half. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bhangale_et_al:LIPIcs.CCC.2019.3, author = {Bhangale, Amey and Khot, Subhash}, title = {{UG-Hardness to NP-Hardness by Losing Half}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {3:1--3:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.3}, URN = {urn:nbn:de:0030-drops-108258}, doi = {10.4230/LIPIcs.CCC.2019.3}, annote = {Keywords: NP-hardness, Inapproximability, Unique Games Conjecture} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Amey Bhangale. NP-Hardness of Coloring 2-Colorable Hypergraph with Poly-Logarithmically Many Colors. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 15:1-15:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bhangale:LIPIcs.ICALP.2018.15, author = {Bhangale, Amey}, title = {{NP-Hardness of Coloring 2-Colorable Hypergraph with Poly-Logarithmically Many Colors}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {15:1--15:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.15}, URN = {urn:nbn:de:0030-drops-90190}, doi = {10.4230/LIPIcs.ICALP.2018.15}, annote = {Keywords: Hypergraph coloring, Inapproximability, Schrijver graph} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Amey Bhangale, Subhash Khot, and Devanathan Thiruvenkatachari. An Improved Dictatorship Test with Perfect Completeness. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 15:1-15:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bhangale_et_al:LIPIcs.FSTTCS.2017.15, author = {Bhangale, Amey and Khot, Subhash and Thiruvenkatachari, Devanathan}, title = {{An Improved Dictatorship Test with Perfect Completeness}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {15:1--15:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.15}, URN = {urn:nbn:de:0030-drops-83854}, doi = {10.4230/LIPIcs.FSTTCS.2017.15}, annote = {Keywords: Property Testing, Distatorship Test, Fourier Analysis} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Amey Bhangale, Irit Dinur, and Inbal Livni Navon. Cube vs. Cube Low Degree Test. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 40:1-40:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bhangale_et_al:LIPIcs.ITCS.2017.40, author = {Bhangale, Amey and Dinur, Irit and Livni Navon, Inbal}, title = {{Cube vs. Cube Low Degree Test}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {40:1--40:31}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.40}, URN = {urn:nbn:de:0030-drops-81748}, doi = {10.4230/LIPIcs.ITCS.2017.40}, annote = {Keywords: Low Degree Test, Probabilistically Checkable Proofs, Locally Testable Codes} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Amey Bhangale, Rajiv Gandhi, Mohammad Taghi Hajiaghayi, Rohit Khandekar, and Guy Kortsarz. Bicovering: Covering Edges With Two Small Subsets of Vertices. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{bhangale_et_al:LIPIcs.ICALP.2016.6, author = {Bhangale, Amey and Gandhi, Rajiv and Hajiaghayi, Mohammad Taghi and Khandekar, Rohit and Kortsarz, Guy}, title = {{Bicovering: Covering Edges With Two Small Subsets of Vertices}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {6:1--6:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.6}, URN = {urn:nbn:de:0030-drops-62728}, doi = {10.4230/LIPIcs.ICALP.2016.6}, annote = {Keywords: Bi-covering, Unique Games, Max Bi-clique} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Amey Bhangale, Ramprasad Saptharishi, Girish Varma, and Rakesh Venkat. On Fortification of Projection Games. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 497-511, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{bhangale_et_al:LIPIcs.APPROX-RANDOM.2015.497, author = {Bhangale, Amey and Saptharishi, Ramprasad and Varma, Girish and Venkat, Rakesh}, title = {{On Fortification of Projection Games}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {497--511}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.497}, URN = {urn:nbn:de:0030-drops-53204}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.497}, annote = {Keywords: Parallel Repetition, Fortification} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
Amey Bhangale, Prahladh Harsha, and Girish Varma. A Characterization of Hard-to-cover CSPs. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 280-303, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{bhangale_et_al:LIPIcs.CCC.2015.280, author = {Bhangale, Amey and Harsha, Prahladh and Varma, Girish}, title = {{A Characterization of Hard-to-cover CSPs}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {280--303}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-81-1}, ISSN = {1868-8969}, year = {2015}, volume = {33}, editor = {Zuckerman, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.280}, URN = {urn:nbn:de:0030-drops-50574}, doi = {10.4230/LIPIcs.CCC.2015.280}, annote = {Keywords: CSPs, Covering Problem, Hardness of Approximation, Unique Games, Invariance Principle} }