1 citations · 1 across the 5 of their papers we have counts for
4 papers · 1 filter
From Finite-Valued Nondeterministic Transducers to Deterministic Two-Tape Automata
Elisabet Burjons, Fabian Frei, Martin Raszyk
The question whether P equals NP revolves around the discrepancy between active production and mere verification by Turing machines. In this paper, we examine the analogous problem…
Complexity of Stability
Fabian Frei, Edith Hemaspaandra, Jörg Rothe
Graph parameters such as the clique number, the chromatic number, and the independence number are central in many areas, ranging from computer networks to linguistics to computatio…
Efficient Circuit Simulation in MapReduce
Fabian Frei, Koichi Wada
The MapReduce framework has firmly established itself as one of the most widely used parallel computing platforms for processing big data on tera- and peta-byte scale. Approaching…
Finding Optimal Solutions With Neighborly Help
Elisabet Burjons, Fabian Frei, Edith Hemaspaandra +2
Can we efficiently compute optimal solutions to instances of a hard problem from optimal solutions to neighboring (i.e., locally modified) instances? For example, can we efficientl…