Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Michael Ludwig:

TR17-019 | 8th February 2017
Andreas Krebs, Nutan Limaye, Michael Ludwig

A Unified Method for Placing Problems in Polylogarithmic Depth

Revisions: 2

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

TR14-177 | 14th December 2014
Andreas Krebs, Klaus-Joern Lange, Michael Ludwig

Visibly Counter Languages and Constant Depth Circuits

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

ISSN 1433-8092 | Imprint