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 in ... more >>>

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 the value of a ... more >>>

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 absence ... more >>>