We investigate the phenomenon of depth-reduction in commutative and non-commutative
arithmetic circuits. We prove that in the commutative setting, uniform semi-unbounded …

When programming with sublinear space constraints one often needs to use special
implementation techniques even for simple tasks, such as function composition. In this …

This issue's expert guest column is by Eric Allender, who has just taken over the Structural
Complexity Column in the Bulletin of the EATCS. Regarding" Journals to Die For"(SIGACT …

We lay out a refined framework to discuss various approximation algorithms for
combinatorial optimization problems residing inside the optimization class PO. We are …

Maximal word functions occur in data retrieval applications and have connections with
ranking problems, which in turn were first investigated in relation to data compression [21] …

We review some of the known results about the complexity of computing solutions or proofs
of membership for problems in NP. Trying to capture the complexity of this problem, we …

P-printable sets were defined by Hartmanis and Yesha and have been investigated by
several researchers. The analogous notion of L-printable sets was defined by Fortnow et al.; …

The hairpin completion is an operation on formal languages which is inspired by the hairpin
formation in biochemistry. Hairpin formations occur naturally within DNA-computing. It has …

It is known that polynomial size polynomial degree Boolean circuits have equivalent semi-
unbounded logarithmic depth circuits. For arithmetic circuits, the additional property of …

The (bounded) hairpin completion, the hairpin lengthening, and their iterated versions are
operations on formal languages which have been inspired by the hairpin formation in DNA …