Project

Funding: FWF
Funding period: Sep 2021 - Aug 2025
Project number: P34808

Team

  • Peter Kritzer (PI, project leader, RICAM, since Sep 2021)
  • Aicke Hinrichs (PI, national research partner, JKU, Sep 2021 - Dec 2022)
  • Mathias Sonnleitner (PhD student, JKU, Sep 2021)
  • Vishnupriya Anupindi (PostDoc, RICAM, since Aug 2022)
  • Florian Aichinger (PhD student, RICAM, since Feb 2023)

Abstract

The topic of the project is in the field of Information-Based Complexity (IBC), which is a sub-field of mathematics concerned with the following questions: if a mathematical problem depends on a large number of variables, how much information about the problem is required to solve it approximately, but not exceeding a certain error threshold? How does the amount of required information change if the number of variables and/or the error threshold change?

To quantify the dependence of a problem on the number of variables and the error threshold, this can be done by using a concept called tractability, and studying the tractability of various computational problems is among the core questions of IBC. Various notions of tractability, quantifying the dependence on the number of variables and the threshold, exist in the literature.

This project is devoted to the study of IBC, and, in particular tractability, in frameworks that have so far not been studied extensively. Doing so, we hope to push the boundaries of the research field further, and to make make the theory more useful for applications. To give an example, we plan to consider problems where we allow the number of variables to be unbounded, which is an additional challenge in comparison to the standard settings. This and all other problems that shall be dealt with in the course of the project are motivated by recent publications of experts in the field of IBC.

 

Publications

  • P. Kritzer. Selected aspects of tractability analysis. Submitted, 2024. https://arxiv.org/abs/2402.02396 
  • D. Krieg, P. Kritzer. Homogeneous algorithms and solvable problems on cones. J. Complexity 83, 101840, 2024. https://arxiv.org/abs/2311.15767 
  • J. Dick, A. Ebert, L. Herrmann, P. Kritzer, M. Longo. The fast reduced QMC matrix-vector product. J. Comput. Appl. Math. 440, 115642, 2024. https://arxiv.org/abs/2305.11645
  • O. Emenike, F.J. Hickernell, P. Kritzer. A unified treatment of tractability for approximation problems defined on Hilbert spaces. Submitted, 2023. https://arxiv.org/abs/2310.17777
  • M. Gnewuch, P. Kritzer, A.B. Owen, Z. Pan. Computable error bounds for quasi-Monte Carlo using points with non-negative local discrepancy. Submitted, 2023. https://arxiv.org/abs/2309.04209
  • C. Laudage, F. Aichinger, S. Desmettre. A comparative study of factor models for different periods of the electricity spot price market. Submitted, 2023. https://arxiv.org/abs/2306.07731
  • A. Ebert, P. Kritzer, F. Pillichshammer. Tractability of approximation in the weighted Korobov spaces in the worst-case setting. In: Z. Botev et. al (eds.). Advances in Modeling and Simulation, 131-150, Springer, Cham, 2022. https://arxiv.org/abs/2201.09940
  • M. Gnewuch, M. Hefter, A. Hinrichs, K. Ritter. Countable tensor products of Hermite spaces and spaces of Gaussian kernels. J. Complexity 71, 101654, 2022. https://arxiv.org/abs/2110.05778
  • A. Hinrichs, J. Prochno, M. Sonnleitner. Random sections of $\ell_p$-ellipsoids, optimal recovery and Gelfand numbers of diagonal operators. J. Approximation Th. 293, 105919, 2023. https://arxiv.org/abs/2109.14504
  • D. Krieg, M. Sonnleitner. Function recovery on manifolds using scattered data. Submitted, 2022. https://arxiv.org/abs/2109.04106
  • P. Kritzer. A note on the CBC-DBD construction of lattice rules with general positive weights. J. Complexity 78, 101721, 2023. https://arxiv.org/abs/2208.13610
  • P. Kritzer, O. Osisiogu. On a reduced component-by-component digit-by-digit construction of lattice point sets. Uniform Distribution Theory 18 (1), 97-140, 2023. https://arxiv.org/abs/2211.13237

Talks

  • F. Aichinger. Pricing of geometric Asian options in the Volterra-Heston model. Stochastic Models and Control (SMC) 2024, Feb. 27, 2024, Graz, Austria.
  • P. Kritzer. What lattice rules can do for you. RICAM Colloquium, Jan. 18, 2024, Linz, Austria.
  • V. Anupindi. Reduced digital nets. Linz Algebra Research Day, Dec. 12, 2023, Linz, Austria.
  • P. Kritzer. Quasi-Monte Carlo using points with non-negative local discrepancy. Colloquium on the occasion of Johann Brauchart's 50th Birthday, Oct. 20, 2023, Graz, Austria.
  • P. Kritzer. Tractability analysis (invited overview talk). Dagstuhl Seminar on Algorithms and Complexity for Continuous Problems. Aug. 28, 2023, Dagstuhl, Germany.
  • P. Kritzer. Homogeneous algorithms for linear (?) problems. Foundations of Computational Mathematics. Jun. 20, 2023. Paris, France.
  • V. Anupindi (Poster presentation). Pseudorandom numbers from curves of genus 2. Foundations of Computational Mathematics. Jun. 12-14, 2023. Paris, France.
  • P. Kritzer. Lattice point sets for matrix-matrix products. Workshop on the Occasion of the 20th Anniversary of RICAM. Mar. 28, 2023. Linz, Austria.
  • F. Aichinger. Modeling large spot price deviations in electricity markets. German Probability and Statistics Days 2023 (GPSD). Mar. 8, 2023. Essen, Germany.
  • P. Kritzer. Fast computation of matrix-vector products using reduced lattice points. 9th Workshop on High-Dimensional Integration (HDA 2023). Feb. 20, 2023. Canberra, Australia.
  • P. Kritzer. The fast reduced QMC matrix-vector multiplication. Workshop on Approximation and Geometry. Oct. 13, 2022. Bedlewo, Poland.
  • P. Kritzer. Various search algorithms for good lattice rules. SIAM Conference on Uncertainty Quantification. Apr. 13, 2022. Atlanta (virtually), USA.
  • P. Kritzer. Digit-by-digit constructions of good lattice rules. ESI-Workshop on Adaptivity, High-Dimensionality, and Randomness. Apr. 8, 2022. Vienna, Austria.
  • M. Sonnleitner. Random sections of p-ellipsoids and optimal recovery. Austrian Stochastics Days. Sep. 10, 2021. Leoben, Austria.