All reports by Author Pierre McKenzie:

__
TR17-109
| 22nd June 2017
__

Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani#### Does Looking Inside a Circuit Help?

__
TR17-072
| 25th April 2017
__

Eric Allender, Andreas Krebs, Pierre McKenzie#### Better Complexity Bounds for Cost Register Machines

Revisions: 1

__
TR13-040
| 11th March 2013
__

MichaĆ«l Cadilhac, Andreas Krebs, Pierre McKenzie#### The Algebraic Theory of Parikh Automata

Revisions: 2

__
TR12-090
| 2nd July 2012
__

Michael Blondin, Andreas Krebs, Pierre McKenzie#### The Complexity of Intersecting Finite Automata Having Few Final States

__
TR11-095
| 22nd June 2011
__

Christoph Behle, Andreas Krebs, Klaus-Joern Lange, Pierre McKenzie#### Low uniform versions of NC1

Revisions: 1

__
TR05-136
| 14th November 2005
__

Anna Gal, Michal Koucky, Pierre McKenzie#### Incremental branching programs

__
TR00-036
| 29th May 2000
__

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

__
TR98-059
| 15th September 1998
__

C. Lautemann, Pierre McKenzie, T. Schwentick, H. Vollmer#### The Descriptive Complexity Approach to LOGCFL

Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani

The Black-Box Hypothesis, introduced by Barak et al. (JACM, 2012), states that any property of boolean functions decided efficiently (e.g., in BPP) with inputs represented by circuits can also be decided efficiently in the black-box setting, where an algorithm is given an oracle access to the input function and an ... more >>>

Eric Allender, Andreas Krebs, Pierre McKenzie

Cost register automata (CRA) are one-way finite automata whose transitions have the side effect that a register is set to the result of applying a state-dependent semiring operation to a pair of registers. Here it is shown that CRAs over the semiring (N,min,+) can simulate polynomial time computation, proving along ... more >>>

MichaĆ«l Cadilhac, Andreas Krebs, Pierre McKenzie

The Parikh automaton model equips a finite automaton with integer registers and imposes a semilinear constraint on the set of their final settings. Here the theory of typed monoids is used to characterize the language classes that arise algebraically. Complexity bounds are derived, such as containment of the unambiguous Parikh ... more >>>

Michael Blondin, Andreas Krebs, Pierre McKenzie

The problem of determining whether several finite automata accept a word in common is closely related to the well-studied membership problem in transformation monoids. We raise the issue of limiting the number of final states in the automata intersection problem. For automata with two final states, we show the problem ... more >>>

Christoph Behle, Andreas Krebs, Klaus-Joern Lange, Pierre McKenzie

In the setting known as DLOGTIME-uniformity,

the fundamental complexity classes

$AC^0\subset ACC^0\subseteq TC^0\subseteq NC^1$ have several

robust characterizations.

In this paper we refine uniformity further and examine the impact

of these refinements on $NC^1$ and its subclasses.

When applied to the logarithmic circuit depth characterization of $NC^1$,

some refinements leave ...
more >>>

Anna Gal, Michal Koucky, Pierre McKenzie

In this paper we propose the study of a new model of restricted

branching programs which we call incremental branching programs.

This is in line with the program proposed by Cook in 1974 as an

approach for separating the class of problems solvable in logarithmic

space from problems solvable ...
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 >>>

C. Lautemann, Pierre McKenzie, T. Schwentick, H. Vollmer

Building upon the known generalized-quantifier-based first-order

characterization of LOGCFL, we lay the groundwork for a deeper

investigation. Specifically, we examine subclasses of LOGCFL arising

from varying the arity and nesting of groupoidal quantifiers. Our

work extends the elaborate theory relating monoidal quantifiers to

NC^1 and its subclasses. In the ...
more >>>