enter search term and/or author name
Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition
Krishnendu Chatterjee, Monika Henzinger
Article No.: 15
The computation of the winning set for Büchi objectives in alternating games on graphs is a central problem in computer-aided verification with a large number of applications. The long-standing best known upper bound for solving the problem...
Merge-and-Shrink Abstraction: A Method for Generating Lower Bounds in Factored State Spaces
Malte Helmert, Patrik Haslum, Jörg Hoffmann, Raz Nissim
Article No.: 16
Many areas of computer science require answering questions about reachability in compactly described discrete transition systems. Answering such questions effectively requires techniques to be able to do so without building the entire system. In...
Given topological spaces X,Y, a fundamental problem of algebraic topology is understanding the structure of all continuous maps X → Y. We consider a computational version, where X,Y are given as...
This article presents the first tight bounds on the time complexity of shared-memory renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct identifiers from a small namespace.
The Cost of Fault Tolerance in Multi-Party Communication Complexity
Binbin Chen, Haifeng Yu, Yuda Zhao, Phillip B. Gibbons
Article No.: 19
Multi-party communication complexity involves distributed computation of a function over inputs held by multiple distributed players. A key focus of distributed computing research, since the very beginning, has been to tolerate failures. It is...