FoCM 2014 conference
Workshop B5 - Information Based Complexity
December 17, 15:30 ~ 16:00 - Room B23
A refined classification of problems with (sub)exponential information complexity
Markus Weimar
Philipps-University Marburg, Germany - weimar@mathematik.uni-marburg.de
In the last 20 years a whole hierarchy of notions of tractability was proposed and analyzed by several authors. These notions are used to classify the computational hardness of continuous numerical problems in terms of the behavior of their information complexity $n(\varepsilon, d)$ as a function of the accuracy $\varepsilon$ and the dimension $d$. By now a lot of effort was spend on either proving quantitative positive results (such as, e.g., the concrete dependence on $\varepsilon$ and $d$ within the well-established framework of polynomial tractability), or on qualitative negative results (which, e.g., state that a given problem suffers from the so-called curse of dimensionality). Although several weaker types of tractability were introduced recently, the theory of information-based complexity still lacks a notion which allows to quantify the exact (sub-/super-)exponential dependence of $n(\varepsilon,d)$ on both parameters $\varepsilon$ and $d$.
In this talk we present the notion of $(s,t)$-weakly tractable problems which attempts to fill this gap. Within this framework the parameters $s$ and $t$ are used to quantitatively refine the huge class of polynomially intractable problems. For compact operators between Hilbert spaces we provide characterizations of $(s,t)$-weak tractability (w.r.t. various settings) in terms of singular values. In addition, our new notion will be illustrated by examples such as embedding problems of Sobolev spaces (as studied recently by Kühn, Sickel, and Ullrich). In particular, we complete the characterization of weak tractability for these problems.
Joint work with Pawel Siedlecki (University of Warsaw, Poland).