Fine-grained complexity lower bounds for problems in computer aided verification

DOI10.1007/978-3-031-22337-2_14zbMath1528.68225MaRDI QIDQ6113981

Monika R. Henzinger

Publication date: 10 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• From pre-historic to post-modern symbolic model checking
• Algorithms and conditional lower bounds for planning problems
• Symbolic graphs: Linear solutions to connectivity related problems
• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition
• Alternating-time temporal logic
• The Probabilistic Communication Complexity of Set Intersection
• Conditionally Optimal Algorithms for Generalized B\"uchi Games
• Model and Objective Separation with Conditional Lower Bounds
• Communication Complexity
• Improved Set-Based Symbolic Algorithms for Parity Games
• Decremental strongly-connected components and single-source reachability in near-linear time
• Quasipolynomial Set-Based Symbolic Algorithms for Parity Games
• A classification of symbolic transition systems
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Symbolic algorithms for graphs and Markov decision processes with fairness objectives

This page was built for publication: Fine-grained complexity lower bounds for problems in computer aided verification