Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, and Dor Minzer. Parallel Repetition of k-Player Projection Games. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 54:1-54:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bhangale_et_al:LIPIcs.APPROX/RANDOM.2024.54, author = {Bhangale, Amey and Braverman, Mark and Khot, Subhash and Liu, Yang P. and Minzer, Dor}, title = {{Parallel Repetition of k-Player Projection Games}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {54:1--54:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.54}, URN = {urn:nbn:de:0030-drops-210475}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.54}, annote = {Keywords: Parallel Repetition, Multiplayer games, Projection games} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Fateme Abbasi, Marek Adamczyk, Miguel Bosch-Calvo, Jarosław Byrka, Fabrizio Grandoni, Krzysztof Sornat, and Antoine Tinguely. An O(loglog n)-Approximation for Submodular Facility Location. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{abbasi_et_al:LIPIcs.ICALP.2024.5, author = {Abbasi, Fateme and Adamczyk, Marek and Bosch-Calvo, Miguel and Byrka, Jaros{\l}aw and Grandoni, Fabrizio and Sornat, Krzysztof and Tinguely, Antoine}, title = {{An O(loglog n)-Approximation for Submodular Facility Location}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {5:1--5: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.5}, URN = {urn:nbn:de:0030-drops-201488}, doi = {10.4230/LIPIcs.ICALP.2024.5}, annote = {Keywords: approximation algorithms, facility location, submodular facility location, universal stochastic facility location} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, and Joachim Spoerhase. Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{abbasi_et_al:LIPIcs.ICALP.2024.6, author = {Abbasi, Fateme and Banerjee, Sandip and Byrka, Jaros{\l}aw and Chalermsook, Parinya and Gadekar, Ameet and Khodamoradi, Kamyar and Marx, D\'{a}niel and Sharma, Roohani and Spoerhase, Joachim}, title = {{Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {6:1--6:19}, 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.6}, URN = {urn:nbn:de:0030-drops-201494}, doi = {10.4230/LIPIcs.ICALP.2024.6}, annote = {Keywords: Clustering, approximation algorithms, parameterized complexity} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Yash Khanna and Anand Louis. Planted Models for the Densest k-Subgraph Problem. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{khanna_et_al:LIPIcs.FSTTCS.2020.27, author = {Khanna, Yash and Louis, Anand}, title = {{Planted Models for the Densest k-Subgraph Problem}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {27:1--27:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.27}, URN = {urn:nbn:de:0030-drops-132682}, doi = {10.4230/LIPIcs.FSTTCS.2020.27}, annote = {Keywords: Densest k-Subgraph, Semi-Random models, Planted Models, Semidefinite Programming, Approximation Algorithms, Beyond Worst Case Analysis} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Anand Louis and Rakesh Venkat. Planted Models for k-Way Edge and Vertex Expansion. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{louis_et_al:LIPIcs.FSTTCS.2019.23, author = {Louis, Anand and Venkat, Rakesh}, title = {{Planted Models for k-Way Edge and Vertex Expansion}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {23:1--23:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-131-3}, ISSN = {1868-8969}, year = {2019}, volume = {150}, editor = {Chattopadhyay, Arkadev and Gastin, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.23}, URN = {urn:nbn:de:0030-drops-115857}, doi = {10.4230/LIPIcs.FSTTCS.2019.23}, annote = {Keywords: Vertex Expansion, k-way partitioning, Semi-Random models, Planted Models, Approximation Algorithms, Beyond Worst Case Analysis} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Anand Louis and Rakesh Venkat. Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 101:1-101:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{louis_et_al:LIPIcs.ICALP.2018.101, author = {Louis, Anand and Venkat, Rakesh}, title = {{Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {101:1--101:15}, 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.101}, URN = {urn:nbn:de:0030-drops-91057}, doi = {10.4230/LIPIcs.ICALP.2018.101}, annote = {Keywords: Semi-Random models, Vertex Expansion, Approximation Algorithms, Beyond Worst Case Analysis} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Irit Dinur, Prahladh Harsha, Rakesh Venkat, and Henry Yuen. Multiplayer Parallel Repetition for Expanding Games. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{dinur_et_al:LIPIcs.ITCS.2017.37, author = {Dinur, Irit and Harsha, Prahladh and Venkat, Rakesh and Yuen, Henry}, title = {{Multiplayer Parallel Repetition for Expanding Games}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {37:1--37:16}, 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.37}, URN = {urn:nbn:de:0030-drops-81575}, doi = {10.4230/LIPIcs.ITCS.2017.37}, annote = {Keywords: Parallel Repetition, Multi-player, Expander} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Yuval Rabani and Rakesh Venkat. Approximating Sparsest Cut in Low Rank Graphs via Embeddings from Approximately Low Dimensional Spaces. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{rabani_et_al:LIPIcs.APPROX-RANDOM.2017.21, author = {Rabani, Yuval and Venkat, Rakesh}, title = {{Approximating Sparsest Cut in Low Rank Graphs via Embeddings from Approximately Low Dimensional Spaces}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {21:1--21:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-044-6}, ISSN = {1868-8969}, year = {2017}, volume = {81}, editor = {Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.21}, URN = {urn:nbn:de:0030-drops-75705}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.21}, annote = {Keywords: Metric Embeddings, Sparsest Cut, Negative type metrics, Approximation Algorithms} }
Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Amit Deshpande, Prahladh Harsha, and Rakesh Venkat. Embedding Approximately Low-Dimensional l_2^2 Metrics into l_1. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{deshpande_et_al:LIPIcs.FSTTCS.2016.10, author = {Deshpande, Amit and Harsha, Prahladh and Venkat, Rakesh}, title = {{Embedding Approximately Low-Dimensional l\underline2^2 Metrics into l\underline1}}, booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)}, pages = {10:1--10:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-027-9}, ISSN = {1868-8969}, year = {2016}, volume = {65}, editor = {Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.10}, URN = {urn:nbn:de:0030-drops-68456}, doi = {10.4230/LIPIcs.FSTTCS.2016.10}, annote = {Keywords: Metric Embeddings, Sparsest Cut, Negative type metrics, Approximation Algorithms} }
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 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Amit Deshpande and Rakesh Venkat. Guruswami-Sinop Rounding without Higher Level Lasserre. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 105-114, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{deshpande_et_al:LIPIcs.APPROX-RANDOM.2014.105, author = {Deshpande, Amit and Venkat, Rakesh}, title = {{Guruswami-Sinop Rounding without Higher Level Lasserre}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {105--114}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.105}, URN = {urn:nbn:de:0030-drops-46911}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.105}, annote = {Keywords: Sparsest Cut, Lasserre Hierarchy, Metric embeddings} }
Feedback for Dagstuhl Publishing