research
∙
09/08/2020
Completeness in Polylogarithmic Time and Space
Complexity theory can be viewed as the study of the relationship between...
share
research
∙
01/07/2020
Behavioural Theory of Reflective Algorithms I: Reflective Sequential Algorithms
We develop a behavioural theory of reflective sequential algorithms (RSA...
research
∙
11/29/2019
Proper Hierarchies in Polylogarithmic Time and Absence of Complete Problems
The polylogarithmic time hierarchy structures sub-linear time complexity...
research
∙
11/29/2019
A Restricted Second-Order Logic for Non-deterministic Poly-Logarithmic Time
We introduce a restricted second-order logic SO^plog for finite structur...
research
∙
03/08/2019
Descriptive Complexity of Deterministic Polylogarithmic Time
We propose a logical characterization of problems solvable in determinis...
research
∙
06/19/2018
The Polylog-Time Hierarchy Captured by Restricted Second-Order Logic
Let SO^plog denote the restriction of second-order logic, where second-o...
research
∙
04/16/2018