LIPIcs, Volume 24
FSTTCS 2013, December 12-14, 2013, Guwahati, India
Editors: Anil Seth and Nisheeth K. Vishnoi
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Mitali Bafna and Dor Minzer. Solving Unique Games over Globally Hypercontractive Graphs. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bafna_et_al:LIPIcs.CCC.2024.3, author = {Bafna, Mitali and Minzer, Dor}, title = {{Solving Unique Games over Globally Hypercontractive Graphs}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {3:1--3:15}, 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.3}, URN = {urn:nbn:de:0030-drops-203996}, doi = {10.4230/LIPIcs.CCC.2024.3}, annote = {Keywords: unique games, approximation algorithms} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Peter Bürgisser, Mahmut Levent Doğan, Visu Makam, Michael Walter, and Avi Wigderson. Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 14:1-14:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{burgisser_et_al:LIPIcs.CCC.2024.14, author = {B\"{u}rgisser, Peter and Do\u{g}an, Mahmut Levent and Makam, Visu and Walter, Michael and Wigderson, Avi}, title = {{Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {14:1--14:48}, 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.14}, URN = {urn:nbn:de:0030-drops-204100}, doi = {10.4230/LIPIcs.CCC.2024.14}, annote = {Keywords: computational invariant theory, geometric complexity theory, orbit problems, abc-conjecture, closest vector problem} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Omkar Baraskar, Agrim Dewan, Chandan Saha, and Pulkit Sinha. NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{baraskar_et_al:LIPIcs.ICALP.2024.16, author = {Baraskar, Omkar and Dewan, Agrim and Saha, Chandan and Sinha, Pulkit}, title = {{NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {16:1--16:21}, 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.16}, URN = {urn:nbn:de:0030-drops-201598}, doi = {10.4230/LIPIcs.ICALP.2024.16}, annote = {Keywords: Equivalence testing, MCSP, sparse polynomials, 3SAT} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Charlie Carlson, Ewan Davies, Alexandra Kolla, and Aditya Potukuchi. A Spectral Approach to Approximately Counting Independent Sets in Dense Bipartite Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 35:1-35:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{carlson_et_al:LIPIcs.ICALP.2024.35, author = {Carlson, Charlie and Davies, Ewan and Kolla, Alexandra and Potukuchi, Aditya}, title = {{A Spectral Approach to Approximately Counting Independent Sets in Dense Bipartite Graphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {35:1--35: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.35}, URN = {urn:nbn:de:0030-drops-201782}, doi = {10.4230/LIPIcs.ICALP.2024.35}, annote = {Keywords: approximate counting, independent sets, bipartite graphs, graph containers} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Leonid Gurvits, Nathan Klein, and Jonathan Leake. From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 79:1-79:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{gurvits_et_al:LIPIcs.ICALP.2024.79, author = {Gurvits, Leonid and Klein, Nathan and Leake, Jonathan}, title = {{From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {79:1--79: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.79}, URN = {urn:nbn:de:0030-drops-202229}, doi = {10.4230/LIPIcs.ICALP.2024.79}, annote = {Keywords: traveling salesman problem, strongly Rayleigh distributions, polynomial capacity, probability lower bounds, combinatorial lower bounds} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yaowei Long and Yunfan Wang. Better Decremental and Fully Dynamic Sensitivity Oracles for Subgraph Connectivity. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 109:1-109:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{long_et_al:LIPIcs.ICALP.2024.109, author = {Long, Yaowei and Wang, Yunfan}, title = {{Better Decremental and Fully Dynamic Sensitivity Oracles for Subgraph Connectivity}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {109:1--109: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.109}, URN = {urn:nbn:de:0030-drops-202523}, doi = {10.4230/LIPIcs.ICALP.2024.109}, annote = {Keywords: connectivity, sensitivity} }
Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)
Nisheeth K. Vishnoi. Algorithms in the Presence of Biased Inputs (Invited Talk). In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 5:1-5:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{vishnoi:LIPIcs.FSTTCS.2023.5, author = {Vishnoi, Nisheeth K.}, title = {{Algorithms in the Presence of Biased Inputs}}, booktitle = {43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)}, pages = {5:1--5:2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-304-1}, ISSN = {1868-8969}, year = {2023}, volume = {284}, editor = {Bouyer, Patricia and Srinivasan, Srikanth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.5}, URN = {urn:nbn:de:0030-drops-193788}, doi = {10.4230/LIPIcs.FSTTCS.2023.5}, annote = {Keywords: Algorithmic Bias} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, and Christopher Williamson. Approximate Degree, Secret Sharing, and Concentration Phenomena. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 71:1-71:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bogdanov_et_al:LIPIcs.APPROX-RANDOM.2019.71, author = {Bogdanov, Andrej and Mande, Nikhil S. and Thaler, Justin and Williamson, Christopher}, title = {{Approximate Degree, Secret Sharing, and Concentration Phenomena}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {71:1--71:21}, 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.71}, URN = {urn:nbn:de:0030-drops-112869}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.71}, annote = {Keywords: approximate degree, dual polynomial, pseudorandomness, polynomial approximation, secret sharing} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Suvrit Sra, Nisheeth K. Vishnoi, and Ozan Yildiz. On Geodesically Convex Formulations for the Brascamp-Lieb Constant. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{sra_et_al:LIPIcs.APPROX-RANDOM.2018.25, author = {Sra, Suvrit and Vishnoi, Nisheeth K. and Yildiz, Ozan}, title = {{On Geodesically Convex Formulations for the Brascamp-Lieb Constant}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {25:1--25:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-085-9}, ISSN = {1868-8969}, year = {2018}, volume = {116}, editor = {Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.25}, URN = {urn:nbn:de:0030-drops-94296}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.25}, annote = {Keywords: Geodesic convexity, positive definite cone, geodesics, Brascamp-Lieb constant} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
L. Elisa Celis, Damian Straszak, and Nisheeth K. Vishnoi. Ranking with Fairness Constraints. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{celis_et_al:LIPIcs.ICALP.2018.28, author = {Celis, L. Elisa and Straszak, Damian and Vishnoi, Nisheeth K.}, title = {{Ranking with Fairness Constraints}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {28:1--28: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.28}, URN = {urn:nbn:de:0030-drops-90329}, doi = {10.4230/LIPIcs.ICALP.2018.28}, annote = {Keywords: Ranking, Fairness, Optimization, Matching, Approximation Algorithms} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Rohit Gurjar, Thomas Thierauf, and Nisheeth K. Vishnoi. Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 74:1-74:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{gurjar_et_al:LIPIcs.ICALP.2018.74, author = {Gurjar, Rohit and Thierauf, Thomas and Vishnoi, Nisheeth K.}, title = {{Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {74:1--74:14}, 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.74}, URN = {urn:nbn:de:0030-drops-90782}, doi = {10.4230/LIPIcs.ICALP.2018.74}, annote = {Keywords: Derandomization, Isolation Lemma, Total unimodularity, Near-shortest vectors in Lattices, Regular matroids} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Yuval Peres, Mohit Singh, and Nisheeth K. Vishnoi. Random Walks in Polytopes and Negative Dependence. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 50:1-50:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{peres_et_al:LIPIcs.ITCS.2017.50, author = {Peres, Yuval and Singh, Mohit and Vishnoi, Nisheeth K.}, title = {{Random Walks in Polytopes and Negative Dependence}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {50:1--50:10}, 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.50}, URN = {urn:nbn:de:0030-drops-81464}, doi = {10.4230/LIPIcs.ITCS.2017.50}, annote = {Keywords: Random walks, Matroid, Polytope, Brownian motion, Negative dependence} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
L. Elisa Celis, Amit Deshpande, Tarun Kathuria, Damian Straszak, and Nisheeth K. Vishnoi. On the Complexity of Constrained Determinantal Point Processes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 36:1-36:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{celis_et_al:LIPIcs.APPROX-RANDOM.2017.36, author = {Celis, L. Elisa and Deshpande, Amit and Kathuria, Tarun and Straszak, Damian and Vishnoi, Nisheeth K.}, title = {{On the Complexity of Constrained Determinantal Point Processes}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {36:1--36:22}, 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.36}, URN = {urn:nbn:de:0030-drops-75851}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.36}, annote = {Keywords: determinantal point processes, constraints, matroids, sampling and counting, polynomials, mixed discriminant} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Ioannis Panageas and Nisheeth K. Vishnoi. Mixing Time of Markov Chains, Dynamical Systems and Evolution. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{panageas_et_al:LIPIcs.ICALP.2016.63, author = {Panageas, Ioannis and Vishnoi, Nisheeth K.}, title = {{Mixing Time of Markov Chains, Dynamical Systems and Evolution}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {63:1--63:14}, 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.63}, URN = {urn:nbn:de:0030-drops-62213}, doi = {10.4230/LIPIcs.ICALP.2016.63}, annote = {Keywords: Markov chains, Mixing time, Dynamical Systems, Evolutionary dynamics, Language evolution} }
Feedback for Dagstuhl Publishing