Model and Objective Separation with Conditional Lower Bounds

DOI10.1145/2933575.2935304zbMath1401.68189arXiv1602.02670OpenAlexW2256738662MaRDI QIDQ4635875

Wolfgang Dvořák, Veronika Loitzenbauer, Krishnendu Chatterjee, Monika R. Henzinger

Publication date: 23 April 2018

Published in: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.02670

zbMATH Keywords

Markov decision processesmodel checkinggraph algorithmsconditional lower bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Fine-grained complexity lower bounds for problems in computer aided verification, Unnamed Item, Algorithms and conditional lower bounds for planning problems, The Orthogonal Vectors Conjecture for Branching Programs and Formulas, Unnamed Item