Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Mayank Goswami and Riko Jacob. On Instance-Optimal Algorithms for a Generalization of Nuts and Bolts and Generalized Sorting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 23:1-23:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{goswami_et_al:LIPIcs.APPROX/RANDOM.2024.23, author = {Goswami, Mayank and Jacob, Riko}, title = {{On Instance-Optimal Algorithms for a Generalization of Nuts and Bolts and Generalized Sorting}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {23:1--23:23}, 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.23}, URN = {urn:nbn:de:0030-drops-210168}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.23}, annote = {Keywords: Sorting, Priced Information, Instance Optimality, Nuts and Bolts} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Kuan Cheng, Minghui Ouyang, Chong Shangguan, and Yuanting Shen. When Can an Expander Code Correct Ω(n) Errors in O(n) Time?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 61:1-61:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{cheng_et_al:LIPIcs.APPROX/RANDOM.2024.61, author = {Cheng, Kuan and Ouyang, Minghui and Shangguan, Chong and Shen, Yuanting}, title = {{When Can an Expander Code Correct \Omega(n) Errors in O(n) Time?}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {61:1--61:23}, 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.61}, URN = {urn:nbn:de:0030-drops-210543}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.61}, annote = {Keywords: expander codes, expander graphs, linear-time decoding} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Andreas Galanis, Alkis Kalavasis, and Anthimos Vardis Kandiros. On Sampling from Ising Models with Spectral Constraints. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{galanis_et_al:LIPIcs.APPROX/RANDOM.2024.70, author = {Galanis, Andreas and Kalavasis, Alkis and Kandiros, Anthimos Vardis}, title = {{On Sampling from Ising Models with Spectral Constraints}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {70:1--70:14}, 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.70}, URN = {urn:nbn:de:0030-drops-210638}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.70}, annote = {Keywords: Ising model, spectral constraints, Glauber dynamics, mean-field Ising, random regular graphs} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Junjie Chen, Minming Li, Haifeng Xu, and Song Zuo. Bayesian Calibrated Click-Through Auctions. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chen_et_al:LIPIcs.ICALP.2024.44, author = {Chen, Junjie and Li, Minming and Xu, Haifeng and Zuo, Song}, title = {{Bayesian Calibrated Click-Through Auctions}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {44:1--44: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.44}, URN = {urn:nbn:de:0030-drops-201878}, doi = {10.4230/LIPIcs.ICALP.2024.44}, annote = {Keywords: information design, ad auctions, online advertising, mechanism design} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yiannis Giannakopoulos, Alexander Grosz, and Themistoklis Melissourgos. On the Smoothed Complexity of Combinatorial Local Search. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 72:1-72:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{giannakopoulos_et_al:LIPIcs.ICALP.2024.72, author = {Giannakopoulos, Yiannis and Grosz, Alexander and Melissourgos, Themistoklis}, title = {{On the Smoothed Complexity of Combinatorial Local Search}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {72:1--72: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.72}, URN = {urn:nbn:de:0030-drops-202154}, doi = {10.4230/LIPIcs.ICALP.2024.72}, annote = {Keywords: Smoothed Analysis, local search, better-response dynamics, PLS-hardness, combinatorial local optimization, congestion games, pure Nash equilibria} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Shaofeng H.-C. Jiang, Wenqian Wang, Yubo Zhang, and Yuhao Zhang. Algorithms for the Generalized Poset Sorting Problem. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 92:1-92:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{jiang_et_al:LIPIcs.ICALP.2024.92, author = {Jiang, Shaofeng H.-C. and Wang, Wenqian and Zhang, Yubo and Zhang, Yuhao}, title = {{Algorithms for the Generalized Poset Sorting Problem}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {92:1--92:15}, 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.92}, URN = {urn:nbn:de:0030-drops-202359}, doi = {10.4230/LIPIcs.ICALP.2024.92}, annote = {Keywords: sorting, poset sorting, generalized sorting} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Constantinos Daskalakis, Noah Golowich, Nika Haghtalab, and Abhishek Shetty. Smooth Nash Equilibria: Algorithms and Complexity. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 37:1-37:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{daskalakis_et_al:LIPIcs.ITCS.2024.37, author = {Daskalakis, Constantinos and Golowich, Noah and Haghtalab, Nika and Shetty, Abhishek}, title = {{Smooth Nash Equilibria: Algorithms and Complexity}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {37:1--37:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.37}, URN = {urn:nbn:de:0030-drops-195657}, doi = {10.4230/LIPIcs.ITCS.2024.37}, annote = {Keywords: Nash equilibrium, smoothed analysis, PPAD} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Yujia Jin, Vidya Muthukumar, and Aaron Sidford. The Complexity of Infinite-Horizon General-Sum Stochastic Games. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 76:1-76:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{jin_et_al:LIPIcs.ITCS.2023.76, author = {Jin, Yujia and Muthukumar, Vidya and Sidford, Aaron}, title = {{The Complexity of Infinite-Horizon General-Sum Stochastic Games}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {76:1--76:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.76}, URN = {urn:nbn:de:0030-drops-175791}, doi = {10.4230/LIPIcs.ITCS.2023.76}, annote = {Keywords: complexity, stochastic games, general-sum games, Nash equilibrium} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Constantinos Daskalakis. Equilibrium Computation, Deep Learning, and Multi-Agent Reinforcement Learning (Invited Talk). In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{daskalakis:LIPIcs.ICALP.2022.2, author = {Daskalakis, Constantinos}, title = {{Equilibrium Computation, Deep Learning, and Multi-Agent Reinforcement Learning}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {2:1--2:1}, 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.2}, URN = {urn:nbn:de:0030-drops-163431}, doi = {10.4230/LIPIcs.ICALP.2022.2}, annote = {Keywords: Deep Learning, Multi-Agent (Reinforcement) Learning, Game Theory, Nonconvex Optimization, PPAD} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, and Amir Yehudayoff. Interactive Proofs for Verifying Machine Learning. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 41:1-41:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{goldwasser_et_al:LIPIcs.ITCS.2021.41, author = {Goldwasser, Shafi and Rothblum, Guy N. and Shafer, Jonathan and Yehudayoff, Amir}, title = {{Interactive Proofs for Verifying Machine Learning}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {41:1--41:19}, 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.41}, URN = {urn:nbn:de:0030-drops-135806}, doi = {10.4230/LIPIcs.ITCS.2021.41}, annote = {Keywords: PAC learning, Fourier analysis of boolean functions, Complexity gaps, Complexity lower bounds, Goldreich-Levin algorithm, Kushilevitz-Mansour algorithm, Distribution testing} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Constantinos Daskalakis and Ioannis Panageas. Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{daskalakis_et_al:LIPIcs.ITCS.2019.27, author = {Daskalakis, Constantinos and Panageas, Ioannis}, title = {{Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {27:1--27:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.27}, URN = {urn:nbn:de:0030-drops-101204}, doi = {10.4230/LIPIcs.ITCS.2019.27}, annote = {Keywords: No regret learning, Zero-sum games, Convergence, Dynamical Systems, KL divergence} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Constantinos Daskalakis and Yasushi Kawase. Optimal Stopping Rules for Sequential Hypothesis Testing. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{daskalakis_et_al:LIPIcs.ESA.2017.32, author = {Daskalakis, Constantinos and Kawase, Yasushi}, title = {{Optimal Stopping Rules for Sequential Hypothesis Testing}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {32:1--32:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.32}, URN = {urn:nbn:de:0030-drops-78237}, doi = {10.4230/LIPIcs.ESA.2017.32}, annote = {Keywords: property testing, sequential hypothesis testing, A/B testing} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Aviv Adler, Constantinos Daskalakis, and Erik D. Demaine. The Complexity of Hex and the Jordan Curve Theorem. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{adler_et_al:LIPIcs.ICALP.2016.24, author = {Adler, Aviv and Daskalakis, Constantinos and Demaine, Erik D.}, title = {{The Complexity of Hex and the Jordan Curve Theorem}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {24:1--24: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.24}, URN = {urn:nbn:de:0030-drops-63032}, doi = {10.4230/LIPIcs.ICALP.2016.24}, annote = {Keywords: Jordan, Brouwer, Hex, PPAD, PSPACE} }
Feedback for Dagstuhl Publishing