18 citations · 45 across the 8 of their papers we have counts for
8 papers
An Exponential Lower Bound for Zadeh's pivot rule
Yann Disser, Oliver Friedmann, Alexander V. Hopp
The question whether the Simplex Algorithm admits an efficient pivot rule remains one of the most important open questions in discrete optimization. While many natural, determinist…
Errata for: A subexponential lower bound for the Random Facet algorithm for Parity Games
Oliver Friedmann, Thomas Dueholm Hansen, Uri Zwick
In Friedmann, Hansen, and Zwick (2011) we claimed that the expected number of pivoting steps performed by the Random-Facet algorithm of Kalai and of Matousek, Sharir, and Welzl is…
Random-Facet and Random-Bland require subexponential time even for shortest paths
Oliver Friedmann, Thomas Dueholm Hansen, Uri Zwick
The Random-Facet algorithm of Kalai and of Matousek, Sharir and Welzl is an elegant randomized algorithm for solving linear programs and more general LP-type problems. Its expected…
Satisfiability Games for Branching-Time Logics
Oliver Friedmann, Martin Lange, Markus Latte
The satisfiability problem for branching-time temporal logics like CTL*, CTL and CTL+ has important applications in program specification and verification. Their computational comp…
An exponential lower bound for Cunningham's rule
David Avis, Oliver Friedmann
In this paper we give an exponential lower bound for Cunningham's least recently considered (round-robin) rule as applied to parity games, Markhov decision processes and linear pro…
An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms
Oliver Friedmann
This paper presents a new exponential lower bound for the two most popular deterministic variants of the strategy improvement algorithms for solving parity, mean payoff, discounted…
Local Strategy Improvement for Parity Game Solving
Oliver Friedmann, Martin Lange
The problem of solving a parity game is at the core of many problems in model checking, satisfiability checking and program synthesis. Some of the best algorithms for solving parit…
A Super-Polynomial Lower Bound for the Parity Game Strategy Improvement Algorithm as We Know it
Oliver Friedmann
This paper presents a new lower bound for the discrete strategy improvement algorithm for solving parity games due to Voege and Jurdziski. First, we informally show which structure…