A model-theoretic characterization of constant-depth arithmetic circuits

We study the class ${\mathrm{\#}\text{AC}}^0$ of functions computed by constant-depth polynomial-size arithmetic circuits of unbounded fan-in addition and multiplication gates. No model-theoretic characterization for arithmetic circuit classes is known so far. Inspired by Immerman's characterization of the Boolean circuit class ${\text{AC}}^0$, we remedy this situation and develop such a characterization of ${\mathrm{\#}\text{AC}}^0$. Our characterization can be interpreted as follows: Functions in ${\mathrm{\#}\text{AC}}^0$ are exactly those functions counting winning strategies in first-order model checking games. A consequence of our results is a new model-theoretic characterization of ${\text{TC}}^0$, the class of languages accepted by constant-depth polynomial-size majority circuits.     

The strength of compactness in Computability Theory and Nonstandard Analysis

Compactness is one of the core notions of analysis: it connects local properties to global ones and makes limits well-behaved. We study the computational properties of the compactness of Cantor space $2^{\mathbb{N}}$ for uncountable covers. The most basic question is: how hard is it to compute a finite sub-cover from such a cover of $2^{\mathbb{N}}$? Another natural question is: how hard is it to compute a sequence that covers $2^{\mathbb{N}}$ minus a measure zero set from such a cover? The special and weak fan functionals respectively compute such finite sub-covers and sequences. In this paper, we establish the connection between these new fan functionals on one hand, and various well-known comprehension axioms on the other hand, including arithmetical comprehension, transfinite recursion, and the Suslin functional. In the spirit of Reverse Mathematics, we also analyse the logical strength of compactness in Nonstandard Analysis. Perhaps surprisingly, the results in the latter mirror (often perfectly) the computational properties of the special and weak fan functionals. In particular, we show that compactness (nonstandard or otherwise) readily brings us to the outer edges of Reverse Mathematics (namely ${\mathrm{\Pi }}_2^1{\text{-}\mathsf{\text{CA}}}_0$), and even into Schweber's higher-order framework (namely ${\mathrm{\Sigma }}_1^2$-separation).     

On the power of standard information for tractability for L∞ approximation of periodic functions in the worst case setting

We study multivariate approximation of periodic functions in the worst case setting with the error measured in the $L_{\infty }$ norm. We consider algorithms that use standard information ${\mathrm{\Lambda }}^{\mathrm{std}}$ consisting of function values or general linear information ${\mathrm{\Lambda }}^{\mathrm{all}}$ consisting of arbitrary continuous linear functionals. We investigate equivalences of various notions of algebraic and exponential tractability for ${\mathrm{\Lambda }}^{\mathrm{std}}$ and ${\mathrm{\Lambda }}^{\mathrm{all}}$ under the absolute or normalized error criterion, and show that the power of ${\mathrm{\Lambda }}^{\mathrm{std}}$ is the same as the one of ${\mathrm{\Lambda }}^{\mathrm{all}}$ for various notions of algebraic and exponential tractability. Our results can be applied to weighted Korobov spaces and Korobov spaces with exponential weights. This gives a special solution to Open Problem 145 as posed by Novak and Woźniakowski (2012) [40].