Information-based complexity (IBC) studies how many pieces of information are required to solve a (numerical) problem up to a prescribed error tolerance. The problems considered include function approximation and learning, numerical integration, optimization, or the solution of PDEs and SDEs. It is of particular interest how the complexity increases with the dimensionality of the problem (cf. curse of dimensionality versus tractability) and with the desired accuracy (cf. rate of convergence). The IBC workshop interacts naturally with several other workshops, including “Foundations of Data science and Machine Learning”, “Approximation Theory”, or “Stochastic Computation” as we study similar topics but from other perspectives. The two semi-plenary talks that we plan to include shall introduce the most important aspects of the field also to researchers from other communities.
Organizers
University of Passau
RPTU Kaiserslautern-Landau
Czech Technical University
Speakers
Semi-plenary speakers
University of Passau
Chemnitz University of Technology & Institute of Mathematics of the National Academy of Sciences of Ukraine
Invited speakers
University of New South Wales
Brown University
Texas A&M University
The University of Tokyo
Osnabrück University
RPTU Kaiserslautern-Landau
Centre de Recerca Matemàtica Barcelona
RICAM Linz
University of New South Wales
University of Alberta
University of Bonn
KU Leuven
JKU Linz
AGH University of Krakow
University of New South Wales
University of Münster
University of Vienna
JKU Linz
University of Passau
University of Graz
Thursday, 9 July
![[HS 08 – 1st Floor]](https://focm2026.univie.ac.at/wp-content/uploads/2026/06/HS08.png){kind=link}
14:00-14:30
Alexander Litvak (University of Alberta)
We provide upper and lower bounds on random diameters of high dimensional convex bodies. We apply our results to bound random diameters of $p$-ellipsoids (images of $\ell_p$ balls under diagonal operators), improving previously known results and obtaining sharp bounds in many cases. This is a joint work with O.Guedon, K.Tatarko, and B.Vritsiou.
14:30-15:00
Mathias Sonnleitner (University of Münster & University of Bielefeld)
We study the approximation of functions from samples taken on a smooth convex surface. The quality of a sampling set is governed by the interplay between prior assumptions on the function, the geometry of the sampling set, and the curvature of the surface. Key characteristics include the average and maximal size of holes, i.e., regions not covered by sample points. We propose a discrete formulation based on the induced Delaunay triangulation and analyze the optimality of random sampling. This leads to a connection with the problem of approximating the surface by the convex hull of the sample points, for which we obtain new results. In particular, we analyze regimes with an optimal curvature-dependent sampling density, and show that the number of gaps exhibits Gaussian fluctuations around a mean that grows superexponentially with the dimension.
15:00-15:30
Friedrich Pillichshammer (JKU Linz)
There are different types of discrepancy with regard to different classes of test sets as well as with regard to different norms. In all cases, these are quantitative measures of the irregularity of the distribution of point sets, and often a discrepancy is related to the worst-case error of a quasi-Monte Carlo rule for the numerical integration of functions from suitable function spaces. Prominent examples are the star $L_p$ discrepancy, the extreme $L_p$ discrepancy, the periodic $L_p$ discrepancy, the anchored $L_p$ discrepancy, the quadrant (or centered) $L_p$ discrepancy, and others. The inverse of a discrepancy for dimension $d$ and error threshold $\varepsilon \in (0,1)$ is the minimal number of points in $[0,1)^d$ required such that the minimal discrepancy is less or equal an $\varepsilon$ share of the initial discrepancy. For applications of QMC to high-dimensional problems, it is of great importance whether the inverse grows exponentially with the dimension (the curse of dimensionality) or not (tractability). Numerous authors have achieved many results in this area over the last three decades. Most of these concern $L_2$ and $L_\infty$ discrepancies. The general $L_p$ case remained elusive. Recently, together with Erich Novak, we developed a method that makes it possible to handle $L_p$ discrepancies as well. In this talk, we present our method and some new results, and summarize all known results and open questions in a comprehensive overview. Joint work with Erich Novak (FSU Jena).
15:30-16:00
Marcin Wnuk (University of Passau)
In the talk we discuss a method of generating (0,m,2)-nets in base b providing an insight into their important structural properties. In particular, we calculate the number of (appropriately discretized) nets and investigate the action of the group of scramblings on the nets, focusing mainly on the following questions:
1. When is this action transitive?
2. What is the structure of the orbits of this action?
3. When is this action faithful?
16:00-16:30 Coffee Break
16:30-17:00
Stefan Heinrich (RPTU Kaiserslautern-Landau)
This talk is concerned with the quantum setting of Information-Based Complexity (IBC). We continue the study of parametric integration in Sobolev spaces. What makes this problem interesting for IBC is that it is intermediate between integration and approximation. Under the embedding condition partial solutions were obtained by Wiegand. Here we present some generalizations with or without the embedding condition. We compare the rates with those in the randomized setting and discuss open problems.
17:00-17:30
Frances Kuo (University of New South Wales)
The Fourier Neural Operator (FNO) is a neural network architecture that learns mappings between function spaces. Its efficient implementation is based on the multi-dimensional Fourier transform. By deriving general regularity bounds for the FNO with respect to both the spatial and parametric variables, we prove that the generalization error of the FNO can be improved by replacing spatial tensor product grids with purpose-built rank-1 lattice points, and by using a second lattice carefully constructed as training points in the parametric space. We achieve more accurate and efficient approximations from fewer network parameters, fewer spatial points, and fewer training samples. In addition, the architecture is simplified, because the high-dimensional Fourier transform on rank-1 lattices requires only a one-dimensional fast Fourier transform, and we can use a hyperbolic cross frequency index set with lattice points. We also prove the universal approximation theorem for our “lattice-based hyperbolic-cross FNOs”.
This is based on joint works with Alexander Keller (NVIDIA), Jakob Dilen and Dirk Nuyens (KU Leuven).
17:30-18:00
Dirk Nuyens (KU Leuven)
Multi‑fidelity Monte Carlo (MFMC) has been successfully applied in many settings where a collection of models with varying cost and accuracy
are combined to reduce variance at fixed computational budget. Building on this idea, we introduce a multi‑fidelity variant of randomized quasi‑Monte Carlo (MFQMC) that couples surrogate models with embedded lattice rules while preserving the unbiasedness and proven convergence properties of QMC.
18:00-18:30
Ian Sloan (University of New South Wales)
Kernel interpolation has an interesting approximation property: if the kernel is the repoducing kernel of a Hilbert space for which the worst-case $L_2$ error of $N$-point interpolation is of order $N^{-\beta}$, then the same approximation applied to a smooth function can have double the rate of convergence, namely $N^{-2\beta}$. This was shown in joint work with Vesa Kaarnioja (BIT Numerical Mathematics 2025), and applied there to the approximation with respect to parameters in a parametric partial differential equation. The result has been extended to $L_p$ approximation for $p \in [1, \infty)$ in recent work with Felix Bartel, Alec Gilbert, Michael Griebel and Frances Kuo.
Friday, 10 July
14:30-15:00
Takashi Goda (The University of Tokyo)
We study multivariate approximation in weighted function spaces, focusing on algorithms based on multiple rank-1 lattices. For periodic functions in weighted Korobov spaces, we present recent results that extend the optimality of these algorithms (in the L-infinity error sense) to the low-smoothness regime between 1/2 and 1 and to general weight structures. Furthermore, we discuss our ongoing work to extend these multiple lattice-based constructions to non-periodic settings, while preserving their computational efficiency and tractability in more general function spaces.
15:00-16:00 semi-plenary talk
Kateryna Pozharska (Chemnitz University of Technology & Institute of Mathematics of the National Academy of Sciences of Ukraine)
In the talk, we will discuss function recovery methods based on different types of data: function values (samples) versus general linear measurements. Here one usually distinguishes linear and non-linear reconstruction methods. So, we consider a (weighted) least squares method for sampling recovery as one of the typical linear reconstruction approaches, and discuss square-root Lasso (rLasso), Orthogonal Matching Pursuit (OMP), and Compressive Sampling Matching Pursuit (CoSaMP) as the effective non-linear decoders. The last ones arise from compressive sensing and sparse recovery. For these methods, we present theoretical guarantees, compare their performance, and analyze their optimality in various model settings.
16:00-16:30 Coffee Break
16:30-17:00
Matthieu Dolbeault (Université de Nantes)
In their paper “Twice-Ramanujan sparsifiers”, Batson, Spielman and Srivastava show that, given a sum of rank-one n x n matrices, one can find O(n) terms whose sum, once appropriately reweighted, has the same spectral properties as the original matrix. We prove a generalization of this result in infinite dimension, and discuss the implications in terms of discretization of L_p norms and least-squares approximation in Reproducing Kernel Hilbert Spaces.
This is joint work with Abdellah Chkifa, David Krieg and Mario Ullrich.
17:00-17:30
Josef Dick (University of New South Wales)
We discuss an algorithm for function approximation in a weighted Korobov space based on shifted rank-1 lattice rules. To mitigate aliasing errors inherent in lattice-based Fourier coefficient estimation, we employ good shifts and recover each Fourier coefficient via a least-squares procedure. We show that the resulting approximation achieves the optimal convergence rate for the approximation error in the supremum norm in the worst-case setting. Moreover, by incorporating random shifts, the algorithm attains the optimal rate for the L two norm approximation error in the randomized setting.
17:30-18:00
Peter Kritzer (RICAM Linz)
We propose a median lattice-based algorithm, inspired by median integration rules, which have attracted significant attention in the theory of quasi-Monte Carlo methods. Our algorithm approximates the Fourier coefficients associated with a suitably chosen frequency index set, where each coefficient is estimated by taking the median over approximations from randomly shifted rank-1 lattice rules with independently chosen generating vectors. We prove that the algorithm achieves, with high probability, a convergence rate of the $L_2$-approximation error that is arbitrarily close to optimal with respect to the number of function evaluations. Furthermore, we show that the error bound depends only polynomially on the dimension, or is even independent of the dimension, under certain summability conditions on the weights. We also include the discussion of a “universal” variant of the algorithm, where we do not need prior information on smoothness and weights.
This talk is based on joint work with Takashi Goda (University of Tokyo) and Zexin Pan (Zhejiang University).
18:00-18:30
Gregor Maier (University of Bonn)
The approximation of operators acting between infinite-dimensional spaces has attracted increasing research attention in recent years. Approximate operators, learned from finite data, show promise to serve as efficient surrogate models for problems in computational science and engineering, complementing traditional numerical methods. A central challenge is to identify relevant classes of operators which can be learned efficiently. Previous research efforts have revealed a broad spectrum of operator classes with regards to their sample complexities: On the one side, holomorphic operators admit worst-case errors that decay algebraically with the reciprocal of the number of training samples. On the other side, Lipschitz and finitely Fréchet differentiable operators exhibit only subalgebraic approximation rates, reflecting an inherent curse of sample complexity. In this talk, we discuss Gaussian Sobolev operators of mixed regularity as an intermediate class between these two regimes. Although mixed Sobolev regularity with respect to an underlying Gaussian measure comprises non-smooth operators, we show that this class still admits an algebraic sample complexity and operators from it can thus be learned efficiently.
Saturday, 11 July
14:00-14:30
Simon Foucart (Texas A&M University)
While it is familiar that a linear functional of an object from a convex set can be estimated optimally (in a worst-case sense) by an affine functional of its linear observations, the following question attracted fewer attention: can other simple functionals be estimated optimally by simple functionals of the observations? In this talk, I will give a positive answer to this question in two cases. In the first case, the functionals are supremum-infimum of linear functionals and the optimal estimation functionals share a similar structure. The main tool is an unusual refinement of the analytical Hahn–Banach theorem. In the second case, the functionals are quadratic forms and the optimal estimation functionals are also quadratic. The main tool is a refinement of Sion’s minimax theorem. In both cases, observation errors modeled deterministically can be integrated. Moreover, the existence results translate into realizable computational constructions of the optimal estimation functionals.
14:30-15:00
Mario Ullrich (JKU Linz)
We show that there is a Riesz basis of Sobolev spaces and Barron classes with smoothness smaller one that consists of ‘small’ ReLU neural networks. We apply this fact to re-prove some recent results on the approximation of functions by deep neural networks. Our proof method avoids using local approximations and allows us to track also the implicit constants.
15:00-15:30
Matěj Trödler (University of Vienna)
We analyze the complexity of training tanh neural networks under uniform accuracy guarantees, building on Berner, Grohs, and Voigtlaender (2022). Our approach is based on a novel construction of sharply localized bump functions via iterated tanh activations. Using this mechanism, we show that, in a finite-precision setting and under mild assumptions, no training algorithm based on finitely many samples can guarantee uniform approximation of the zero function with exponentially small error unless the number of samples grows exponentially in the dimension and depth.
15:30-16:00
Michael Gnewuch (Osnabrück University)
The mean squared error and regularized versions of it are standard loss functions in supervised machine learning. However, calculating these losses for large data sets can be computationally demanding. Modifying an approach of J. Dick and M. Feischl (Journal of Complexity, 2021) we present algorithms to reduce extensive data sets to a smaller size with the help of point sets based on rank-1 lattices.
The compression strategy in the preprocessing step assigns every of those points a pair of weights depending on the original data and responses, representing its relative importance. As a result, the compressed data makes iterative loss calculations in optimization steps much faster.
We analyze the errors of our QMC-data compression algorithms and the cost of the preprocessing step for functions whose Fourier coefficients decay sufficiently fast so that they lie in certain Wiener algebras or Korobov spaces. In particular, we prove that our approach can lead to arbitrary high convergence rates as long as the functions are sufficiently smooth.
The talk is based on the papern[M. Gnewuch, K. Harsha, M. Wnuk, Mathematics of Computation 2026 (preprint version: arXiv:2409.13453v2)] and on recent work together with D. Krieg and M. Wnuk.
16:00-16:30 Coffee Break
16:30-17:00
Larisa Yaroslavtseva (University of Graz)
We study strong approximation of the solution of a scalar stochastic differential equation (SDE) dX_t = \mu(X_t) \, dt + dW_t, t\in [0,1], X_0 = x_0 at the final time point $1$ in the case that the drift coefficient $\mu$ is bounded and $\alpha$-H\”older continuous with $\alpha\in(0, 1]$. Recently, it was shown in [1] that for such SDEs the equidistant Euler approximation achieves an $L^p$-error rate of at least $(1+\alpha)/2$, up to an arbitrary small $\varepsilon$, in terms of the number of evaluations of the driving Brownian motion $W$. In this talk, we show that for such SDEs, an $L^p$-error rate better than $(1+\alpha)/2$ can not be achieved in general by no numerical method based on finitely many evaluations of $W$ and its integrals at fixed time points. In particular, Wagner–Platen type schemes are not superior to the Euler scheme with respect to the $L^p$-error rate in this setting in general. For the proof of this result we choose $\mu$ to be the Weierstrass function and we employ the coupling of noise technique recently introduced in [2]. This is the first lower bound in the literature for the $L^p$-approximation of the solution of an SDE at the final time point by numerical methods based on finitely many evaluations of $W$ and its integrals. [1]. Butkovsky, O., Dareiotis, K., Gerencs\’er, M. (2021). Approximation of SDEs: a stochastic sewing appproach. Probab. Theory Related Fields, \textbf{181}, 975–1034.
[2] Müller-Gronbach, T., Yaroslavtseva, L. (2023). Sharp lower error bounds for strong approximation of SDEs with discontinuous drift coefficient by coupling of noise. Ann. Appl. Probab. \textbf{33}, 902–-935.
17:00-17:30
Paweł Przybyłowicz (AGH University of Krakow)
The talk presents a new methodology, called stochastic PINNs (StPINNs), for approximating sample paths of stochastic differential equations (SDEs) using artificial neural networks. The method is based on a Doss–Sussman transformation of the initial SDE into a random ordinary differential equation (RODE). The approach targets pathwise accuracy, highlights practical training strategies, and is demonstrated on benchmark SDE models. The talk is based on: arxiv.org/abs/2512.14258.
17:30-18:30 semi-plenary talk
Thomas Müller-Gronbach (University of Passau)
We study the complexity of pathwise approximation in p-th mean of the solution of a stochastic differential equation at a single time. We mainly discuss methods based on finitely many evaluations of the driving Brownian motion. First, we briefly review the case of equations with globally Lipschitz continuous coefficients, for which an error rate of at least 1/2 in terms of the number of evaluations of the driving Brownian motion is always guaranteed by using the equidistant Euler-Maruyama scheme. Then we illustrate that giving up global Lipschitz continuity may lead to arbitrary low error rates for the Euler-Maruyama scheme or even for any method based on finitely many evaluations of the driving Brownian motion. Finally, we turn to recent complexity results in the case of equations with a drift coefficient that is not globally Lipschitz continuous. Here we focus on scalar equations with a Lipschitz continuous diffusion coefficient and a drift coefficient that satisfies piecewise smoothness assumptions or has fractional Sobolev regularity or is Hölder continuous.
Posters
![[PZ08 – 1st Floor]](https://focm2026.univie.ac.at/wp-content/uploads/2026/06/poster_zones_1-stock.png){kind=link}
Jakob Eggl
(JKU Linz)
(joint work with Elias Mindlberger and Mario Ullrich)
We study polynomial approximation on a -cube, where is large, and compare interpolation on sparse grids, aka Smolyak’s algorithm (SA), with a simple least squares method based on randomly generated points (LS) using standard benchmark functions. Our main motivation is the influential paper [Barthelmann, Novak, Ritter: High dimensional polynomial interpolation on sparse grids, Adv. Comput. Math. 12, 2000]. We repeat and extend their theoretical analysis and numerical experiments for SA and compare to LS in dimensions up to 100. Our extensive experiments demonstrate that LS, even with only slight oversampling, consistently matches the accuracy of SA in low dimensions. In high dimensions, however, LS shows clear superiority.
Yannick Meiners
(University of Osnabrück)
We study the integration problem over the s-dimensional unit cube on spaces of fractional smoothness 0 < α < 1 in the sense of Riemann-Liouville. Previously upper error bounds for the worst case error of QMC-quadrature rules based on (t, m, s)-nets were proved for these spaces [1]. We show via suitable function space embeddings that these error bounds cannot be improved and that these QMC-quadrature rules are indeed optimal. In particular, we establish that the fractional spaces are equal to the Bessel potential spaces with the same parameters in the sense of equivalent norms. A substantial part of the talk is based on [2].
[1] Gnewuch, M., Dick, J., Markhasin, L. & Sickel, W. (2024). QMC integration based on arbitrary (t, m, s)-nets yields optimal convergence rates on several scales of function spaces, arXiv: 2409.12879v1.
[2] Meiners, Y. (2025). Räume von fraktionaler Glattheit im Sinne von Riemann-Liouville und Bessel-Potential-Räume, Master’s Thesis, University of Osnabrück.
Elias Mindlberger
(JKU Linz)
We study polynomial approximation on a d-cube, where d is large, and compare interpolation on sparse grids, aka Smolyak’s algorithm (SA), with a simple least squares method based on randomly generated points (LS) using standard benchmark functions. Our main motivation is the influential paper [Barthelmann, Novak, Ritter: High dimensional polynomial interpolation on sparse grids, Adv. Comput. Math. 12, 2000]. We repeat and extend their theoretical analysis and numerical experiments for SA and compare to LS in dimensions up to 100. Our extensive experiments demonstrate that LS, even with only slight oversampling, consistently matches the accuracy of SA in low dimensions. In high dimensions, however, LS shows clear superiority.
Nicolas Nagel
(RICAM Linz)
We consider the problem of optimal sample nodes for QMC integration in the two-dimensional torus. It is known that a certain, simple construction, called Fibonacci lattices, achieves the asymptotically optimal rate for the corresponding worst-case error. Recently, it has been observed that these Fibonacci lattices actually seem to be the globally optimal point configuration in certain situations. This leads us to the question of the precise asymptotic behavior of these Fibonacci lattices with exact constants. We show that this is given (up to a normalization) by $C n + D + o(1)$ where the constants $C$ and $D$ can be determined via certain infinite series related to Dedekind zeta functions. In special cases we even get simple closed-form expressions for the worst-case error. In this sense the determination of optimal sample points in the two-dimensional torus for QMC integration is exactly solvable in some situations, an unexpected phenomenon which only occurs rarely in approximation theory.
Mateusz Perlik
(University Of Warsaw)
We consider the worst case Lp approximation of piecewise smooth functions with unknown singular points. Allowable approximations use function values contaminated with random noise. The previously known adaptive algorithm, which is optimal for the case of deterministic and bounded noise, turns out to be optimal also for random noise, provided that the noise is small relative to inverse of the number of samples. In the case of large noise, the algorithm has to be modified to cope with overfitting. Our results show in particular that the presence of singularities does not deteriorate the convergence rate compared to the rate for globally smooth functions.
Jan Zimmermann
(Austrian Academy Of Sciences)
We give explicit upper bounds for the $L^\infty$-discrepancy of admissible lattices (e.g. Frolov lattices) with respect to axes-parallel boxes. In particular, we recover a result of Skriganov, which states that said discrepancy is bounded by a constant times a log-power of the volume of the axes-parallel box. Our approach provides an explicit formula for such a constant for the first time, allowing us to observe how the discrepancy bound depends on the dimension of the space and the specific admissible lattice. As it turns out, for certain dimensions there exist lattice constructions, for which this constant possesses a super-exponential decay in the dimension. Since our discrepancy bound holds for small boxes, too, we also obtain statements about the pre-asymptotic regime.