Chatterjee, Krishnendu; Dvořák, Wolfgang; Henzinger, Monika; Svozil, Alexander Algorithms and conditional lower bounds for planning problems. (English) Zbl 1519.68231 Artif. Intell. 297, Article ID 103499, 22 p. (2021). MSC: 68T20 68Q17 68R10 90C40 91A43 91A80 PDFBibTeX XMLCite \textit{K. Chatterjee} et al., Artif. Intell. 297, Article ID 103499, 22 p. (2021; Zbl 1519.68231) Full Text: DOI arXiv Link
Chatterjee, Krishnendu; Dvořák, Wolfgang; Henzinger, Monika; Svozil, Alexander Near-linear time algorithms for streett objectives in graphs and MDPs. (English) Zbl 07649915 Fokkink, Wan (ed.) et al., 30th international conference on concurrency theory, CONCUR 2019, Amsterdam, the Netherlands, August 27–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 140, Article 7, 16 p. (2019). MSC: 68Q85 PDFBibTeX XMLCite \textit{K. Chatterjee} et al., LIPIcs -- Leibniz Int. Proc. Inform. 140, Article 7, 16 p. (2019; Zbl 07649915) Full Text: DOI arXiv
Chatterjee, Krishnendu; Dvořák, Wolfgang; Henzinger, Monika; Svozil, Alexander Quasipolynomial set-based symbolic algorithms for parity games. (English) Zbl 1415.68142 Barthe, Gilles (ed.) et al., LPAR-22. 22nd international conference on logic for programming, artificial intelligence and reasoning, Awassa, Ethiopia, November 17–21, 2018. Selected papers. Manchester: EasyChair. EPiC Ser. Comput. 57, 233-253 (2018). MSC: 68Q60 68W30 PDFBibTeX XMLCite \textit{K. Chatterjee} et al., EPiC Ser. Comput. 57, 233--253 (2018; Zbl 1415.68142) Full Text: DOI arXiv
Chatterjee, Krishnendu; Dvořák, Wolfgang; Henzinger, Monika; Loitzenbauer, Veronika Lower bounds for symbolic computation on graphs: strongly connected components, liveness, safety, and diameter. (English) Zbl 1403.68063 Czumaj, Artur (ed.), Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7–10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-503-1/ebook). 2341-2356 (2018). MSC: 68Q05 68Q10 68Q17 68R10 68W25 68W40 PDFBibTeX XMLCite \textit{K. Chatterjee} et al., in: Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7--10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2341--2356 (2018; Zbl 1403.68063) Full Text: arXiv Link
Chatterjee, Krishnendu; Dvořák, Wolfgang; Henzinger, Monika; Loitzenbauer, Veronika Improved set-based symbolic algorithms for parity games. (English) Zbl 1436.68194 Goranko, Valentin (ed.) et al., 26th EACSL annual conference on computer science logic, CSL 2017, Stockholm, Sweden, August 20–24, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 82, Article 18, 21 p. (2017). MSC: 68Q60 68W30 91A43 PDFBibTeX XMLCite \textit{K. Chatterjee} et al., LIPIcs -- Leibniz Int. Proc. Inform. 82, Article 18, 21 p. (2017; Zbl 1436.68194) Full Text: DOI arXiv
Chatterjee, Krishnendu; Dvořák, Wolfgang; Henzinger, Monika; Loitzenbauer, Veronika Model and objective separation with conditional lower bounds: disjunction is harder than conjunction. (English) Zbl 1401.68189 Proceedings of the 2016 31st annual ACM/IEEE symposium on logic in computer science, LICS 2016, New York City, NY, USA, July 5–8, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4391-6). 197-206 (2016). MSC: 68Q60 05C85 68Q17 68Q25 68Q45 68Q87 PDFBibTeX XMLCite \textit{K. Chatterjee} et al., in: Proceedings of the 2016 31st annual ACM/IEEE symposium on logic in computer science, LICS 2016, New York City, NY, USA, July 5--8, 2016. New York, NY: Association for Computing Machinery (ACM). 197--206 (2016; Zbl 1401.68189) Full Text: DOI arXiv
Chatterjee, Krishnendu; Dvořák, Wolfgang; Henzinger, Monika; Loitzenbauer, Veronika Conditionally optimal algorithms for generalized Büchi games. (English) Zbl 1398.68390 Faliszewski, Piotr (ed.) et al., 41st international symposium on mathematical foundations of computer science, MFCS 2016, Kraków, Poland, August 22–26, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-016-3). LIPIcs – Leibniz International Proceedings in Informatics 58, Article 25, 15 p. (2016). MSC: 68R10 05C85 68W40 91A43 PDFBibTeX XMLCite \textit{K. Chatterjee} et al., LIPIcs -- Leibniz Int. Proc. Inform. 58, Article 25, 15 p. (2016; Zbl 1398.68390) Full Text: DOI arXiv