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)
Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Optimal Electrical Oblivious Routing on Expanders. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 65:1-65:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{florescu_et_al:LIPIcs.ICALP.2024.65, author = {Florescu, Cella and Kyng, Rasmus and Gutenberg, Maximilian Probst and Sachdeva, Sushant}, title = {{Optimal Electrical Oblivious Routing on Expanders}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {65:1--65: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.65}, URN = {urn:nbn:de:0030-drops-202083}, doi = {10.4230/LIPIcs.ICALP.2024.65}, annote = {Keywords: Expanders, Oblivious routing for 𝓁\underlinep, Electrical flow routing} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Sushant Sachdeva, Anvith Thudi, and Yibin Zhao. Better Sparsifiers for Directed Eulerian Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 119:1-119:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{sachdeva_et_al:LIPIcs.ICALP.2024.119, author = {Sachdeva, Sushant and Thudi, Anvith and Zhao, Yibin}, title = {{Better Sparsifiers for Directed Eulerian Graphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {119:1--119: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.119}, URN = {urn:nbn:de:0030-drops-202628}, doi = {10.4230/LIPIcs.ICALP.2024.119}, annote = {Keywords: Graph algorithms, Linear algebra and computation, Discrepancy theory} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Michael B. Cohen, Aaron Sidford, and Kevin Tian. Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 62:1-62:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{cohen_et_al:LIPIcs.ITCS.2021.62, author = {Cohen, Michael B. and Sidford, Aaron and Tian, Kevin}, title = {{Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {62:1--62:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.62}, URN = {urn:nbn:de:0030-drops-136011}, doi = {10.4230/LIPIcs.ITCS.2021.62}, annote = {Keywords: Variational inequalities, minimax optimization, acceleration, 𝓁\underline∞ regression} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Zeyuan Allen-Zhu and Lorenzo Orecchia. Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{allenzhu_et_al:LIPIcs.ITCS.2017.3, author = {Allen-Zhu, Zeyuan and Orecchia, Lorenzo}, title = {{Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {3:1--3:22}, 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.3}, URN = {urn:nbn:de:0030-drops-81850}, doi = {10.4230/LIPIcs.ITCS.2017.3}, annote = {Keywords: linear coupling, gradient descent, mirror descent, acceleration} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Zeyuan Allen-Zhu, Zhenyu Liao, and Yang Yuan. Optimization Algorithms for Faster Computational Geometry. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 53:1-53:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{allenzhu_et_al:LIPIcs.ICALP.2016.53, author = {Allen-Zhu, Zeyuan and Liao, Zhenyu and Yuan, Yang}, title = {{Optimization Algorithms for Faster Computational Geometry}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {53:1--53:6}, 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.53}, URN = {urn:nbn:de:0030-drops-63325}, doi = {10.4230/LIPIcs.ICALP.2016.53}, annote = {Keywords: maximum inscribed balls, minimum enclosing balls, approximation algorithms} }
Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)
Zeyuan Allen-Zhu, Rati Gelashvili, and Ilya Razenshteyn. Restricted Isometry Property for General p-Norms. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 451-460, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{allenzhu_et_al:LIPIcs.SOCG.2015.451, author = {Allen-Zhu, Zeyuan and Gelashvili, Rati and Razenshteyn, Ilya}, title = {{Restricted Isometry Property for General p-Norms}}, booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}, pages = {451--460}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-83-5}, ISSN = {1868-8969}, year = {2015}, volume = {34}, editor = {Arge, Lars and Pach, J\'{a}nos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.451}, URN = {urn:nbn:de:0030-drops-51273}, doi = {10.4230/LIPIcs.SOCG.2015.451}, annote = {Keywords: compressive sensing, dimension reduction, linear algebra, high-dimensional geometry} }