ABSTRACT. Generalising similar notions from the literature, we introduce the model of recurrent arithmetic circuits, which can be seen as arithmetic analogues of sequential or logical circuits. These circuits utilise so-called \emph{memory gates} which are used to store data between iterations of the recurrent circuit. We introduce a notion of complexity classes for this model and show under which circumstances the newfound hierarchy of theses classes collapses.

ABSTRACT. Many important computational problems can be defined as modification problems. These problems provide an elegant framework for problem definitions and several Algorithmic Meta Theorems are known for them, providing a rich algorithmic toolbox. We study the expressive power of graph modification problems by providing non-expressibility proofs for particular problems and presenting foundational results that can be used as a basis for a more systematic study of the computational aspects of graph modification problems.

ABSTRACT. Polylogarithmic time delineates a relevant notion of feasibility on several classical computational models such as Boolean circuits or parallel random access machines. As far as the quantum paradigm is concerned, this notion yields the complexity class FBQPOLYLOG of functions approximable in polylogarithmic time with a quantum random access Turing machine. We introduce a quantum programming language with first-order recursive procedures, which provides the first programming language-based characterization of FBQPOLYLOG. Each program computes a function in FBQPOLYLOG (soundness) and, conversely, each function of this complexity class is computed by a program (completeness). We also provide a compilation strategy from programs to uniform families of quantum circuits of polylogarithmic depth and polynomial size, whose set of computed functions is known as QNC, and recover the well-known separation result FBQPOLYLOG ⊊ QNC.

ABSTRACT. This paper establishes and proves complexity results for entailment for cumulative propositional dependence logic and for cumulative propositional logic with team semantics. As recently shown, cumulative logics are famously characterised by System C and exactly captured by the cumulative models of Kraus, Lehmann and Magidor. This gives rise to the entailment problem via relational models, which is specifically considered here.

ABSTRACT. There are a lot of varying results on the expressivity of transformers. Many of them even seem contradicting. This work aims to organize this body of results in a systematic way and consider a notion of uniformity in transformer models, as many expressivity results rely on the existence of a transformer for input length $n$ even though in practice, transformers are viewed as a model that works for variable input lengths up to a maximum input length $N$.

ABSTRACT. We study the minimum number of clauses required to encode a boolean function $f$ into a CNF formula with auxiliary variables. This problem is practically relevant to SAT solving and also of theoretical interest due to its connections with other complexity measures such as nondeterministic circuit size. We first show that any function $f \colon \{0,1\}^n \to \{0, 1\}$ can be encoded with $O(\sqrt{2^n})$ clauses, which is information-theoretically tight. Next, we show a connection between space- and time-efficient data structures and compact CNF encodings. Namely, modeling preprocessed data structures as computation with advice, we obtain the following result: if a boolean function $f$ can be evaluated in nondeterministic time $t$ (in the RAM model) with $m$ bits of advice, then it admits a CNF encoding with $\widetilde{O}(\sqrt{mt} + t)$ clauses. This constitutes a non-uniform generalization of Robson's variant of the Cook--Levin theorem, which encodes RAM computations with runtime $t$ (without advice) using $\widetilde{O}(t)$ clauses. By derandomizing a data structure devised by Larsen and Williams for evaluating $k$-CNF functions, we use our non-uniform Cook--Levin result to show that every $k$-CNF function on $n$ inputs can be encoded with $\frac{n^k}{2^{\Omega_k(\sqrt{\lg n})}}$ clauses. This is notable because if we restrict our attention to encodings that are themselves $k$-CNF, it is known that the minimum number of clauses required to encode $k$-CNF functions is $\Theta_k(n^{k}/\lg n)$ in the worst case. Thus, perhaps surprisingly, clauses of unbounded width are helpful for encoding $k$-CNF functions.

ABSTRACT. At the lower end of the hierarchy of complexity classes we find, represented by the word problem of the Dyck language D1 and the boolean formula value problem, respectively, the complexity classes TC0 and NC1, which are still not known to coincide or to be different. Aim of this note is to “approximate” the boolean formula value problem by TC0-computable predicates. This is done by using the string representation of trees instead of using pointers. This allows for the quantification along the nodes of a path which usually requires logspace-complete techniques. Now it could be tempting to believe the boolean formula value problem to be TC0, Which would have surprising consequences like the collapse of the counting hierarchy and its equality with PSPACE! We introduce the TC0-computable predicates Pos and Neg which share many symmetries and dualities of the boolean case and shed some light on this possibility.