All reports by Author Andreas Krebs:

__
TR17-072
| 25th April 2017
__

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

Revisions: 1

__
TR17-019
| 8th February 2017
__

Andreas Krebs, Nutan Limaye, Michael Ludwig#### A Unified Method for Placing Problems in Polylogarithmic Depth

Revisions: 2

__
TR16-164
| 25th October 2016
__

Andreas Krebs, Meena Mahajan, Anil Shukla#### Relating two width measures for resolution proofs

__
TR14-183
| 25th December 2014
__

Nikhil Balaji, Andreas Krebs, Nutan Limaye#### Skew Circuits of Small Width

__
TR14-177
| 14th December 2014
__

Andreas Krebs, Klaus-Joern Lange, Michael Ludwig#### Visibly Counter Languages and Constant Depth Circuits

__
TR13-102
| 17th July 2013
__

Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah#### Small Depth Proof Systems

__
TR13-040
| 11th March 2013
__

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

Revisions: 2

__
TR12-186
| 27th December 2012
__

Andreas Krebs, Nutan Limaye#### DLOGTIME-Proof Systems

__
TR12-090
| 2nd July 2012
__

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

__
TR12-079
| 14th June 2012
__

Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer#### Verifying Proofs in Constant Depth

__
TR11-173
| 22nd December 2011
__

Christoph Behle, Andreas Krebs#### Regular Languages in MAJ[<] with three variables

__
TR11-095
| 22nd June 2011
__

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

Revisions: 1

__
TR11-035
| 4th March 2011
__

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid#### Typed Monoids -- An Eilenberg-like Theorem for non regular Languages

__
TR10-103
| 28th June 2010
__

Andreas Krebs, Nutan Limaye, Meena Mahajan#### Counting paths in VPA is complete for \#NC$^1$

__
TR09-085
| 14th September 2009
__

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid#### An Approach to characterize the Regular Languages in TC0 with Linear Wires

Revisions: 1

__
TR06-117
| 31st August 2006
__

Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien#### Languages with Bounded Multiparty Communication Complexity

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 >>>

Andreas Krebs, Nutan Limaye, Michael Ludwig

In this work we consider the term evaluation problem which involves, given a term over some algebra and a valid input to the term, computing the value of the term on that input. This is a classical problem studied under many names such as formula evaluation problem, formula value problem ... more >>>

Andreas Krebs, Meena Mahajan, Anil Shukla

In this short note, we revisit two hardness measures for resolution proofs: width and asymmetric width. It is known that for every unsatisfiable CNF F,

width(F \derives \Box) \le awidth(F \derives \Box) + max{ awidth(F \derives \Box), width(F)}.

We give a simple direct proof of the upper bound, ... more >>>

Nikhil Balaji, Andreas Krebs, Nutan Limaye

A celebrated result of Barrington (1985) proved that polynomial size, width-5 branching programs (BP) are equivalent in power to a restricted form of branching programs -- polynomial sized width-5 permutation branching programs (PBP), which in turn capture all of NC1. On the other hand it is known that width-3 PBPs ... more >>>

Andreas Krebs, Klaus-Joern Lange, Michael Ludwig

We examine visibly counter languages, which are languages recognized by visibly counter automata (a.k.a. input driven counter automata). We are able to effectively characterize the visibly counter languages in AC0, and show that they are contained in FO[+].

more >>>Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

A proof system for a language $L$ is a function $f$ such that Range$(f)$ is exactly $L$. In this paper, we look at proofsystems from a circuit complexity point of view and study proof systems that are computationally very restricted. The restriction we study is: they can be computed by ... 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 >>>

Andreas Krebs, Nutan Limaye

We define DLOGTIME proof systems, DLTPS, which generalize NC0 proof systems.

It is known that functions such as Exact-k and Majority do not have NC0 proof systems. Here, we give a DLTPS for Exact-k (and therefore for Majority) and also for other natural functions such as Reach and k-Clique. Though ...
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 >>>

Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer

In this paper we initiate the study of proof systems where verification of proofs proceeds by NC0 circuits. We investigate the question which languages admit proof systems in this very restricted model. Formulated alternatively, we ask which languages can be enumerated by NC0 functions. Our results show that the answer ... more >>>

Christoph Behle, Andreas Krebs

We consider first order logic over words and show FO+MOD[<] is contained in MAJ[<] with three variables.

It is known that for the classes FO[<], FO+MOD[<], FO+GROUP[<] three variables suffice. In the case of MOD[<] even two variables are sufficient.

As a consequence we know that if TC^ 0 neq ... 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 >>>

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

Based on different concepts to obtain a finer notion of language recognition via finite monoids we develop an algebraic structure called typed monoid.

This leads to an algebraic description of regular and non regular languages.

We obtain for each language a unique minimal recognizing typed monoid, the typed syntactic monoid.

more >>>

Andreas Krebs, Nutan Limaye, Meena Mahajan

We give a \#NC$^1$ upper bound for the problem of counting accepting paths in any fixed visibly pushdown automaton. Our algorithm involves a non-trivial adaptation of the arithmetic formula evaluation algorithm of Buss, Cook, Gupta, Ramachandran (BCGR: SICOMP 21(4), 1992). We also show that the problem is \#NC$^1$ hard. Our ... more >>>

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

We consider the regular languages recognized by weighted threshold circuits with a linear number of wires.

We present a simple proof to show that parity cannot be computed by such circuits.

Our proofs are based on an explicit construction to restrict the input of the circuit such that the value ...
more >>>

Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien

We study languages with bounded communication complexity in the multiparty "input on the forehead" model with worst-case partition. In the two party case, it is known that such languages are exactly those that are recognized by programs over commutative monoids. This can be used to show that these languages can ... more >>>