Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Rahul Savani. The Complexity of Gradient Descent (Invited Talk). In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 5:1-5:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{savani:LIPIcs.FSTTCS.2021.5, author = {Savani, Rahul}, title = {{The Complexity of Gradient Descent}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {5:1--5:2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.5}, URN = {urn:nbn:de:0030-drops-155167}, doi = {10.4230/LIPIcs.FSTTCS.2021.5}, annote = {Keywords: Computational Complexity, Continuous Optimization, TFNP, PPAD, PLS, CLS, UEOPL} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
John Fearnley and Rahul Savani. A Faster Algorithm for Finding Tarski Fixed Points. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{fearnley_et_al:LIPIcs.STACS.2021.29, author = {Fearnley, John and Savani, Rahul}, title = {{A Faster Algorithm for Finding Tarski Fixed Points}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {29:1--29:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.29}, URN = {urn:nbn:de:0030-drops-136741}, doi = {10.4230/LIPIcs.STACS.2021.29}, annote = {Keywords: query complexity, Tarski fixed points, total function problem} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Argyrios Deligkas, John Fearnley, and Rahul Savani. Tree Polymatrix Games Are PPAD-Hard. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{deligkas_et_al:LIPIcs.ICALP.2020.38, author = {Deligkas, Argyrios and Fearnley, John and Savani, Rahul}, title = {{Tree Polymatrix Games Are PPAD-Hard}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {38:1--38:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.38}, URN = {urn:nbn:de:0030-drops-124458}, doi = {10.4230/LIPIcs.ICALP.2020.38}, annote = {Keywords: Nash Equilibria, Polymatrix Games, PPAD, Brouwer Fixed Points} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. Unique End of Potential Line. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 56:1-56:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{fearnley_et_al:LIPIcs.ICALP.2019.56, author = {Fearnley, John and Gordon, Spencer and Mehta, Ruta and Savani, Rahul}, title = {{Unique End of Potential Line}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {56:1--56:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.56}, URN = {urn:nbn:de:0030-drops-106327}, doi = {10.4230/LIPIcs.ICALP.2019.56}, annote = {Keywords: P-matrix linear complementarity problem, unique sink orientation, contraction map, TFNP, total search problems, continuous local search} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, and Paul G. Spirakis. Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 138:1-138:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{deligkas_et_al:LIPIcs.ICALP.2019.138, author = {Deligkas, Argyrios and Fearnley, John and Melissourgos, Themistoklis and Spirakis, Paul G.}, title = {{Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {138:1--138:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.138}, URN = {urn:nbn:de:0030-drops-107141}, doi = {10.4230/LIPIcs.ICALP.2019.138}, annote = {Keywords: PPA, FIXP, ETR, consensus halving, circuit, reduction, complexity class} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
John Fearnley, Martin Gairing, Matthias Mnich, and Rahul Savani. Reachability Switching Games. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 124:1-124:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{fearnley_et_al:LIPIcs.ICALP.2018.124, author = {Fearnley, John and Gairing, Martin and Mnich, Matthias and Savani, Rahul}, title = {{Reachability Switching Games}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {124:1--124: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.124}, URN = {urn:nbn:de:0030-drops-91282}, doi = {10.4230/LIPIcs.ICALP.2018.124}, annote = {Keywords: Deterministic Random Walks, Model Checking, Reachability, Simple Stochastic Game, Switching Systems} }
Published in: LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012)
Nathalie Bertrand, John Fearnley, and Sven Schewe. Bounded Satisfiability for PCTL. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. 92-106, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{bertrand_et_al:LIPIcs.CSL.2012.92, author = {Bertrand, Nathalie and Fearnley, John and Schewe, Sven}, title = {{Bounded Satisfiability for PCTL}}, booktitle = {Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL}, pages = {92--106}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-42-2}, ISSN = {1868-8969}, year = {2012}, volume = {16}, editor = {C\'{e}gielski, Patrick and Durand, Arnaud}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.92}, URN = {urn:nbn:de:0030-drops-36667}, doi = {10.4230/LIPIcs.CSL.2012.92}, annote = {Keywords: Satisfiability, Temporal Logic, Probabilistic Logic} }
Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
John Fearnley, Markus Rabe, Sven Schewe, and Lijun Zhang. Efficient Approximation of Optimal Control for Continuous-Time Markov Games. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 399-410, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
@InProceedings{fearnley_et_al:LIPIcs.FSTTCS.2011.399, author = {Fearnley, John and Rabe, Markus and Schewe, Sven and Zhang, Lijun}, title = {{Efficient Approximation of Optimal Control for Continuous-Time Markov Games}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)}, pages = {399--410}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-34-7}, ISSN = {1868-8969}, year = {2011}, volume = {13}, editor = {Chakraborty, Supratik and Kumar, Amit}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.399}, URN = {urn:nbn:de:0030-drops-33547}, doi = {10.4230/LIPIcs.FSTTCS.2011.399}, annote = {Keywords: Continuous time Markov decision processes and games, discretisation} }
Feedback for Dagstuhl Publishing