All reports by Author Markus Holzer:

__
TR20-079
| 15th May 2020
__

Hermann Gruber , Markus Holzer, Simon Wolfsteiner#### On Minimizing Regular Expressions Without Kleene Star

__
TR08-077
| 23rd May 2008
__

Felix Brandt, Felix Fischer, Markus Holzer#### On Iterated Dominance, Matrix Elimination, and Matched Paths

__
TR07-136
| 28th November 2007
__

Felix Brandt, Felix Fischer, Markus Holzer#### Equilibria of Graphical Games with Symmetries

__
TR06-091
| 29th May 2006
__

Felix Brandt, Felix Fischer, Markus Holzer#### Symmetries and the Complexity of Pure Nash Equilibrium

__
TR06-027
| 22nd February 2006
__

Hermann Gruber, Markus Holzer#### Finding Lower Bounds for Nondeterministic State Complexity is Hard

__
TR00-036
| 29th May 2000
__

Carsten Damm, Markus Holzer, Pierre McKenzie#### The Complexity of Tensor Calculus

Hermann Gruber , Markus Holzer, Simon Wolfsteiner

Finite languages lie at the heart of literally every regular expression. Therefore, we investigate the approximation complexity of minimizing regular expressions without Kleene star, or, equivalently, regular expressions describing finite languages. On the side of approximation hardness, given such an expression of size~$s$, we prove that it is impossible to ... more >>>

Felix Brandt, Felix Fischer, Markus Holzer

We study computational problems that arise in the context of iterated dominance in anonymous games, and show that deciding whether a game can be solved by means of iterated weak dominance is NP-hard for anonymous games with three actions. For the case of two actions, this problem can be reformulated ... more >>>

Felix Brandt, Felix Fischer, Markus Holzer

We study graphical games where the payoff function of each player satisfies one of four types of symmetries in the actions of his neighbors. We establish that deciding the existence of a pure Nash equilibrium is NP-hard in graphical games with each of the four types of symmetry. Using a ... more >>>

Felix Brandt, Felix Fischer, Markus Holzer

Strategic games may exhibit symmetries in a variety of ways. A common aspect of symmetry, enabling the compact representation of games even when the number of players is unbounded, is that players cannot (or need not) distinguish between the other players. We define four classes of symmetric games by considering ... more >>>

Hermann Gruber, Markus Holzer

We investigate the following lower bound methods for regular

languages: The fooling set technique, the extended fooling set

technique, and the biclique edge cover technique. It is shown that

the maximal attainable lower bound for each of the above mentioned

techniques can be algorithmically deduced from ...
more >>>

Carsten Damm, Markus Holzer, Pierre McKenzie

Tensor calculus over semirings is shown relevant to complexity

theory in unexpected ways. First, evaluating well-formed tensor

formulas with explicit tensor entries is shown complete for $\olpus\P$,

for $\NP$, and for $\#\P$ as the semiring varies. Indeed the

permanent of a matrix is shown expressible as ...
more >>>