We study the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$. For $d=1$, this maximum is $3$. For $d=2$, this maximum is $\tilde{\Theta}(N^{1/2})$. Similar (slightly less accurate) statements hold for $d>2$ as well. We discuss the tightness of our methods, and describe ... more >>>

We present a complete classification of the parameterized complexity of all operator fragments of the satisfiability problem in computation tree logic CTL. The investigated parameterization is temporal depth and pathwidth. Our results show a dichotomy between W[1]-hard and fixed-parameter tractable fragments. The two real operator fragments which are in FPT ... more >>>

We define the lower and upper mutual dimensions $mdim(x:y)$ and $Mdim(x:y)$ between any two points $x$ and $y$ in Euclidean space. Intuitively these are the lower and upper densities of the algorithmic information shared by $x$ and $y$. We show that these quantities satisfy the main desiderata for a satisfactory ... more >>>