This thesis is making contributions to three strands of descriptive complexity theory. First, we
adapt a representation-invariant, singly exponential-time graph canonization algorithm of …

Effectively documenting data services is a crucial issue in any organization, not only for
governing data but also for interoperation purposes. Indeed, in order to fully realize the …

In this work we prove the first Fixed-depth Size-Hierarchy Theorem for uniform AC 0 [⊕]. In
particular, we show that for any fixed d, the class C d, k of functions that have uniform AC 0 …

In this article we review recent results on expressivity and complexity of first-order, modal,
and propositional dependence logic and some of its variants such as independence and …

Different techniques have been used to prove several transference theorems of the form"
nontrivial algorithms for a circuit class C yield circuit lower bounds against C". In this survey …

This paper originates from the observation that many classical NP graph problems, including
some NP-complete problems, are actually of very low nondeterministic time complexity. In …

We propose a framework for modelling and solving search problems using logic, and
describe a project whose goal is to produce practically effective, general purpose tools for …

The $ diagonalization $$ technique $ was invented by Georg Cantor to show that there are
more real numbers than algebraic numbers and is very important in $ theoretical …

In 1982, Kannan showed that Sigma P 2 does not have n k-sized circuits for any k. Do
smaller classes also admit such circuit lower bounds? Despite several improvements of …

It has long been known that deterministic 1-way counter machines recognize exactly all re
sets. Here we investigate counter machines with general recursive bounds on counter …