Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Xi Chen, Yuhao Li, and Mihalis Yannakakis. Reducing Tarski to Unique Tarski (In the Black-Box Model). In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 21:1-21:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chen_et_al:LIPIcs.CCC.2023.21, author = {Chen, Xi and Li, Yuhao and Yannakakis, Mihalis}, title = {{Reducing Tarski to Unique Tarski (In the Black-Box Model)}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {21:1--21:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.21}, URN = {urn:nbn:de:0030-drops-182919}, doi = {10.4230/LIPIcs.CCC.2023.21}, annote = {Keywords: Tarski fixed point, Query complexity, TFNP} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Amol Pasarkar, Christos Papadimitriou, and Mihalis Yannakakis. Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 88:1-88:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{pasarkar_et_al:LIPIcs.ITCS.2023.88, author = {Pasarkar, Amol and Papadimitriou, Christos and Yannakakis, Mihalis}, title = {{Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {88:1--88: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.88}, URN = {urn:nbn:de:0030-drops-175913}, doi = {10.4230/LIPIcs.ITCS.2023.88}, annote = {Keywords: Total Complexity, Extremal Combinatorics, Pigeonhole Principle} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Oliver Korten. Derandomization from Time-Space Tradeoffs. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 37:1-37:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{korten:LIPIcs.CCC.2022.37, author = {Korten, Oliver}, title = {{Derandomization from Time-Space Tradeoffs}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {37:1--37:26}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.37}, URN = {urn:nbn:de:0030-drops-165993}, doi = {10.4230/LIPIcs.CCC.2022.37}, annote = {Keywords: Pseudorandomness, circuit complexity, total functions} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Vijay V. Vazirani and Mihalis Yannakakis. Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 59:1-59:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{vazirani_et_al:LIPIcs.ITCS.2021.59, author = {Vazirani, Vijay V. and Yannakakis, Mihalis}, title = {{Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {59:1--59: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.59}, URN = {urn:nbn:de:0030-drops-135987}, doi = {10.4230/LIPIcs.ITCS.2021.59}, annote = {Keywords: Hyland-Zeckhauser scheme, one-sided matching markets, mechanism design, dichotomous utilities, PPAD, FIXP} }
Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Łukasz Bożyk, Jan Derbisz, Tomasz Krawczyk, Jana Novotná, and Karolina Okrasa. Vertex Deletion into Bipartite Permutation Graphs. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bozyk_et_al:LIPIcs.IPEC.2020.5, author = {Bo\.{z}yk, {\L}ukasz and Derbisz, Jan and Krawczyk, Tomasz and Novotn\'{a}, Jana and Okrasa, Karolina}, title = {{Vertex Deletion into Bipartite Permutation Graphs}}, booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)}, pages = {5:1--5:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-172-6}, ISSN = {1868-8969}, year = {2020}, volume = {180}, editor = {Cao, Yixin and Pilipczuk, Marcin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.5}, URN = {urn:nbn:de:0030-drops-133087}, doi = {10.4230/LIPIcs.IPEC.2020.5}, annote = {Keywords: permutation graphs, comparability graphs, partially ordered set, graph modification problems} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Kousha Etessami, Christos Papadimitriou, Aviad Rubinstein, and Mihalis Yannakakis. Tarski’s Theorem, Supermodular Games, and the Complexity of Equilibria. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{etessami_et_al:LIPIcs.ITCS.2020.18, author = {Etessami, Kousha and Papadimitriou, Christos and Rubinstein, Aviad and Yannakakis, Mihalis}, title = {{Tarski’s Theorem, Supermodular Games, and the Complexity of Equilibria}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {18:1--18:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.18}, URN = {urn:nbn:de:0030-drops-117037}, doi = {10.4230/LIPIcs.ITCS.2020.18}, annote = {Keywords: Tarski’s theorem, supermodular games, monotone functions, lattices, fixed points, Nash equilibria, computational complexity, PLS, PPAD, stochastic games, oracle model, lower bounds} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Sanjana Kolisetty, Linh Le, Ilya Volkovich, and Mihalis Yannakakis. The Complexity of Finding S-Factors in Regular Graphs. 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. 21:1-21:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kolisetty_et_al:LIPIcs.FSTTCS.2019.21, author = {Kolisetty, Sanjana and Le, Linh and Volkovich, Ilya and Yannakakis, Mihalis}, title = {{The Complexity of Finding S-Factors in Regular Graphs}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {21:1--21:12}, 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.21}, URN = {urn:nbn:de:0030-drops-115834}, doi = {10.4230/LIPIcs.FSTTCS.2019.21}, annote = {Keywords: constraint satisfaction problem, Dichotomy theorem, Graph Factors, Regular Graphs} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Mihalis Yannakakis. Fixed Point Computation Problems and Facets of Complexity (Invited Talk). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, p. 5:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{yannakakis:LIPIcs.ICALP.2019.5, author = {Yannakakis, Mihalis}, title = {{Fixed Point Computation Problems and Facets of Complexity}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {5:1--5:1}, 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.5}, URN = {urn:nbn:de:0030-drops-105812}, doi = {10.4230/LIPIcs.ICALP.2019.5}, annote = {Keywords: Fixed Point, Polynomial Time Algorithm, Computational Complexity} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Kousha Etessami, Emanuel Martinov, Alistair Stewart, and Mihalis Yannakakis. Reachability for Branching Concurrent Stochastic Games (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 115:1-115:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{etessami_et_al:LIPIcs.ICALP.2019.115, author = {Etessami, Kousha and Martinov, Emanuel and Stewart, Alistair and Yannakakis, Mihalis}, title = {{Reachability for Branching Concurrent Stochastic Games}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {115:1--115: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.115}, URN = {urn:nbn:de:0030-drops-106917}, doi = {10.4230/LIPIcs.ICALP.2019.115}, annote = {Keywords: stochastic games, multi-type branching processes, concurrent games, minimax-polynomial equations, reachability, almost-sure, limit-sure} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Kousha Etessami. The complexity of analyzing infinite-state Markov chains, Markov decision processes, and stochastic games (Invited Talk). In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{etessami:LIPIcs.STACS.2013.1, author = {Etessami, Kousha}, title = {{The complexity of analyzing infinite-state Markov chains, Markov decision processes, and stochastic games}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {1--2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.1}, URN = {urn:nbn:de:0030-drops-39143}, doi = {10.4230/LIPIcs.STACS.2013.1}, annote = {Keywords: recursive Markov chains, Markov decision processes, stochastic games, monotone systems of nonlinear equations, least fixed points, Newton's method, co} }
Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Orna Kupferman, Yoad Lustig, Moshe Y. Vardi, and Mihalis Yannakakis. Temporal Synthesis for Bounded Systems and Environments. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 615-626, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
@InProceedings{kupferman_et_al:LIPIcs.STACS.2011.615, author = {Kupferman, Orna and Lustig, Yoad and Vardi, Moshe Y. and Yannakakis, Mihalis}, title = {{Temporal Synthesis for Bounded Systems and Environments}}, booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)}, pages = {615--626}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-25-5}, ISSN = {1868-8969}, year = {2011}, volume = {9}, editor = {Schwentick, Thomas and D\"{u}rr, Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.615}, URN = {urn:nbn:de:0030-drops-30481}, doi = {10.4230/LIPIcs.STACS.2011.615}, annote = {Keywords: temporal synthesis} }
Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)
Susanne Albers and Pascal Weil. Preface -- 25th International Symposium on Theoretical Aspects of Computer Science. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{albers_et_al:LIPIcs.STACS.2008.1326, author = {Albers, Susanne and Weil, Pascal}, title = {{Preface -- 25th International Symposium on Theoretical Aspects of Computer Science}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {1--10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1326}, URN = {urn:nbn:de:0030-drops-13263}, doi = {10.4230/LIPIcs.STACS.2008.1326}, annote = {Keywords: Symposium, theoretical computer science, algorithms and data structures, automata and formal languages, computational and structural complexity, logic in computer science, applications} }
Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)
Mihalis Yannakakis. Equilibria, Fixed Points, and Complexity Classes. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 19-38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{yannakakis:LIPIcs.STACS.2008.1311, author = {Yannakakis, Mihalis}, title = {{Equilibria, Fixed Points, and Complexity Classes}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {19--38}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1311}, URN = {urn:nbn:de:0030-drops-13110}, doi = {10.4230/LIPIcs.STACS.2008.1311}, annote = {Keywords: Equilibria, Fixed points, Computational Complexity, Game Theory} }
Feedback for Dagstuhl Publishing