There are some open questions on the relations between the complexity classes in the
machine-dependent theory of computational complexity. A lot of them are closely related to …

We prove that for some constant a> 1, for all k≤ a, MATIME [n^{k+ o (1)}]/1⊄ SIZE [O (n^ k)],
for some specific o (1) function. This is a super linear polynomial circuit lower bound …

We study the complexity of model expansion (MX), which is the problem of expanding a
given finite structure with additional relations to produce a finite model of a given formula …

We show that every circuit with AND,OR,NOT, and MOD_m gates, m∈Z^+, of polynomial
size and depth d can be reduced to a depth-2, SYM∘AND, circuit of size 2^(\logn)^O(d). This …

We study the expressive power of fragments of inclusion and independence logic defined by
restricting the number k of universal quantifiers in formulas. Assuming the so-called strict …

This paper deals with descriptive complexity of picture languages of any dimension by
fragments of existential second-order logic: 1) We generalize to any dimension the …

Separation theorems are essential in complexity theory: looking for strict lower and upper
bounds makes sense only in the context of a hierarchy theorem. For probabilistic complexity …

It is unknown whether Cook reducibility of a set A to a set B—that is reduction of A to B via a
Turing machine operating in polynomial time with “free” procedural calls to an algorithm for …

Fuzzy relational equations play an important role as a platform in various applications of
fuzzy sets and systems. The resolution and optimization of fuzzy relational equations are of …