@article{KreuzerWalsh2024, author = {Kreuzer, Martin and Walsh, Florian}, title = {Computing the binomial part of a polynomial ideal}, series = {Journal of Symbolic Computation (Online ISSN: 1095-855X)}, volume = {2024}, journal = {Journal of Symbolic Computation (Online ISSN: 1095-855X)}, number = {124}, publisher = {Elsevier}, address = {Amsterdam}, doi = {10.1016/j.jsc.2024.102298}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-18708}, pages = {30 Seiten}, year = {2024}, abstract = {Given an ideal I in a polynomial ring K[x1,...,xn] over a field K, we present a complete algorithm to compute the binomial part of I, i.e., the subideal Bin(I) of I generated by all monomials and binomials in I. This is achieved step-by-step. First we collect and extend several algorithms for computing exponent lattices in different kinds of fields. Then we generalize them to compute exponent lattices of units in 0-dimensional K-algebras, where we have to generalize the computation of the separable part of an algebra to non-perfect fields in characteristic p. Next we examine the computation of unit lattices in finitely generated K-algebras, as well as their associated characters and lattice ideals. This allows us to calculate Bin(I) when I is saturated with respect to the indeterminates by reducing the task to the 0-dimensional case. Finally, we treat the computation of Bin(I) for general ideals by computing their cellular decomposition and dealing with finitely many special ideals called (s,t)-binomial parts. All algorithms have been implemented in SageMath.}, language = {en} } @article{FruehwirthProchno2024, author = {Fr{\"u}hwirth, Lorenz and Prochno, Joscha}, title = {Sanov-type large deviations and conditional limit theorems for high-dimensional Orlicz balls}, series = {Journal of Mathematical Analysis and Applications (Online ISSN: 1096-0813)}, volume = {2024}, journal = {Journal of Mathematical Analysis and Applications (Online ISSN: 1096-0813)}, number = {536,1}, publisher = {Elsevier}, address = {Amsterdam}, doi = {10.1016/j.jmaa.2024.128169}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-18723}, pages = {25 Seiten}, year = {2024}, abstract = {In this paper, we prove a Sanov-type large deviation principle for the sequence of empirical measures of vectors chosen uniformly at random from an Orlicz ball. From this level-2 large deviation result, in a combination with Gibbs conditioning, entropy maximization and an Orlicz version of the Poincar{\´e}-Maxwell-Borel lemma, we deduce a conditional limit theorem for high-dimensional Orlicz balls. In more geometric parlance, the latter shows that if V1 and V2 are Orlicz functions, then random points in the V1-Orlicz ball, conditioned on having a small V2-Orlicz radius, look like an appropriately scaled V2-Orlicz ball. In fact, we show that the limiting distribution in our Poincar{\´e}-Maxwell-Borel lemma, and thus the geometric interpretation, undergoes a phase transition depending on the magnitude of the V2-Orlicz radius.}, language = {en} } @article{PenaFerrandezSauer2024, author = {Pe{\~n}a Ferr{\´a}ndez, Juan Manuel and Sauer, Thomas}, title = {Stabilized recovery and model reduction for multivariate exponential polynomials}, series = {Journal of Symbolic Computation (Online ISSN: 1095-855X)}, volume = {2024}, journal = {Journal of Symbolic Computation (Online ISSN: 1095-855X)}, number = {125}, publisher = {Elsevier}, address = {Amsterdam}, doi = {10.1016/j.jsc.2024.102313}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-18748}, pages = {20 Seiten}, year = {2024}, abstract = {Recovery of multivariate exponential polynomials, i.e., the multivariate version of Prony's problem, can be stabilized by using more than the minimally needed multiinteger samples of the function. We present an algorithm that takes into account this extra information and prove a backward error estimate for the algebraic recovery method SMILE. In addition, we give a method to approximate data by an exponential polynomial sequence of a given structure as a step in the direction of multivariate model reduction.}, language = {en} } @article{KabluchkoProchnoSonnleitner2024, author = {Kabluchko, Zakhar and Prochno, Joscha and Sonnleitner, Mathias}, title = {A probabilistic approach to Lorentz balls l(^n)(q,1)}, series = {Journal of Functional Analysis (Online ISSN: 1096-0783)}, volume = {2025}, journal = {Journal of Functional Analysis (Online ISSN: 1096-0783)}, number = {288, 1}, publisher = {Elsevier}, address = {Amsterdam}, doi = {10.1016/j.jfa.2024.110682}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-18878}, pages = {32 Seiten}, year = {2024}, abstract = {We develop a probabilistic approach to study the volumetric and geometric properties of unit balls |B(^n)(q,1) of finite-dimensional Lorentz sequence spaces l(^n)(q,1). More precisely, we show that the empirical distribution of a random vector X^(n) uniformly distributed on its volume normalized unit ball converges weakly to a compactly supported symmetric probability distribution with explicitly given density; as a consequence we obtain a weak Poincar{\´e}-Maxwell-Borel principle for any fixed number k in |N of coordinates of X^(n) as n grows infinitly. Moreover, we prove a central limit theorem for the largest coordinate of X^(n), demonstrating a quite different behavior than in the case of the l(^n)(q) balls, where a Gumbel distribution appears in the limit. Finally, we prove a Schechtman-Schmuckenschl{\"a}ger type result for the asymptotic volume of intersections of volume normalized l(^n)(q,1) and l(^n)(p) balls.}, language = {en} } @article{MuellerGronbachYaroslavtseva2024, author = {M{\"u}ller-Gronbach, Thomas and Yaroslavtseva, Larisa}, title = {On the complexity of strong approximation of stochastic differential equations with a non-Lipschitz drift coefficient}, series = {Journal of Complexity (Online ISSN: 1090-2708)}, volume = {2024}, journal = {Journal of Complexity (Online ISSN: 1090-2708)}, number = {85}, publisher = {Elsevier}, address = {Amsterdam}, doi = {10.1016/j.jco.2024.101870}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-18819}, pages = {17 Seiten}, year = {2024}, abstract = {We survey recent developments in the field of complexity of pathwise approximation in p-th mean of the solution of a stochastic differential equation at the final time 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 the global Lipschitz continuity of the coefficients may lead to a non-polynomial decay of the error for the Euler-Maruyama scheme or even to an arbitrary slow decay of the smallest possible error that can be achieved on the basis of finitely many evaluations of the driving Brownian motion. Finally, we turn to recent positive results for 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 and we present corresponding complexity results.}, language = {en} } @article{EpperleinWirth2024, author = {Epperlein, Jeremias and Wirth, Fabian}, title = {The joint spectral radius is pointwise H{\"o}lder continuous}, series = {Linear Algebra and its Applications}, volume = {2025}, journal = {Linear Algebra and its Applications}, number = {704}, publisher = {Elsevier}, address = {Amsterdam}, issn = {1873-1856}, doi = {10.1016/j.laa.2024.09.016}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19140}, pages = {92 -- 122}, year = {2024}, abstract = {We show that the joint spectral radius is pointwise H{\"o}lder continuous. In addition, the joint spectral radius is locally H{\"o}lder continuous for ε-inflations. In the two-dimensional case, local H{\"o}lder continuity holds on the matrix sets with positive joint spectral radius.}, language = {en} } @article{GlockMunhaCorreiaSudakov2024, author = {Glock, Stefan and Munh{\´a} Correia, David and Sudakov, Benny}, title = {Hamilton cycles in pseudorandom graphs}, series = {Advances in Mathematics}, volume = {2024}, journal = {Advances in Mathematics}, number = {458 B}, publisher = {Elsevier}, address = {Amsterdam}, doi = {10.1016/j.aim.2024.109984}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19151}, pages = {45 Seiten}, year = {2024}, abstract = {Finding general conditions which ensure that a graph is Hamiltonian is a central topic in graph theory. An old and well-known conjecture in the area states that any d-regular n-vertex graph G whose second largest eigenvalue in absolute value λ(G) is at most d/C, for some universal constant C > 0, has a Hamilton cycle. In this paper, we obtain two main results which make substantial progress towards this problem. Firstly, we settle this conjecture in full when the degree d is at least a small power of n. Secondly, in the general case we show that λ(G) ≤ d/C(log n)1/3 implies the existence of a Hamilton cycle, improving the 20-year old bound of d/ log1-o(1) n of Krivelevich and Sudakov. We use in a novel way a variety of methods, such as a robust P{\´o}sa rotation-extension technique, the Friedman-Pippenger tree embedding with rollbacks and the absorbing method, combined with additional tools and ideas. Our results have several interesting applications. In particular, they imply the currently best-known bounds on the number of generators which guarantee the Hamiltonicity of random Cayley graphs, which is an important partial case of the well known Hamiltonicity conjecture of Lov{\´a}sz. They can also be used to improve a result of Alon and Bourgain on additive patterns in multiplicative subgroups.}, language = {en} } @article{KreuzerLinhLong2024, author = {Kreuzer, Martin and Linh, Tran N. K. and Long, Le N.}, title = {Differential theory of zero-dimensional schemes}, series = {Journal of Pure and Applied Algebra}, volume = {229 (2025)}, journal = {Journal of Pure and Applied Algebra}, number = {1}, publisher = {Elsevier}, address = {Amsterdam}, issn = {1873-1376}, doi = {10.1016/j.jpaa.2024.107815}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19130}, pages = {31 Seiten}, year = {2024}, abstract = {To study a 0-dimensional scheme |X in |P^n over a perfect field K, we use the module of K{\"a}hler differentials (Omega)(^1)(_{R/K}) of its homogeneous coordinate ring R and its exterior powers, the higher modules of K{\"a}hler differentials (Omega)(^m)(_{R/K}). One of our main results is a characterization of weakly curvilinear schemes |X by the Hilbert polynomials of the modules (Omega)(^m)(_{R/K}) which allows us to check this property algorithmically without computing the primary decomposition of the vanishing ideal of |X. Further main achievements are precise formulas for the Hilbert functions and Hilbert polynomials of the modules (Omega)(^m)(_{R/K}) for a fat point scheme |X which extend and settle previous partial results and conjectures. Underlying these results is a novel method: we first embed the homogeneous coordinate ring R into its truncated integral closure ~R. Then we use the corresponding map from the module of K{\"a}hler differentials (Omega)(^1)(_{R/K}) to (Omega)(^1)(_{~R/K}) to find a formula for the Hilbert polynomial HP((Omega)(^1)(_{R/K})) and a sharp bound for the regularity index ri((Omega)(^1)(_{R/K})). Next we extend this to formulas for the Hilbert polynomials HP((Omega)(^m)(_{R/K})) and bounds for the regularity indices of the higher modules of K{\"a}hler differentials. As a further application, we characterize uniformity conditions on |X using the Hilbert functions of the K{\"a}hler differential modules of |X and its subschemes.}, language = {en} } @article{KreuzerMiasnikovWalsh2024, author = {Kreuzer, Martin and Miasnikov, Alexei and Walsh, Florian}, title = {Decomposing finite Z-algebras}, series = {Journal of Algebra}, volume = {2025}, journal = {Journal of Algebra}, number = {664 B}, publisher = {Elsevier}, address = {Amsterdam}, issn = {1090-266X}, doi = {10.1016/j.jalgebra.2024.10.027}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19184}, pages = {206 -- 246}, year = {2024}, abstract = {For a finite Z-algebra R, i.e., for a ring which is not necessarily associative or unitary, but whose additive group is finitely generated, we construct a decomposition of R/Ann(R) into directly indecomposable factors under weak hypotheses. The method is based on constructing and decomposing a ring of scalarsS, and then lifting the decomposition ofSto the bilinear map given by the multiplication of R, and finally to R/Ann(R). All steps of the construction are given as explicit algorithms and it is shown that the entire procedure has a probabilistic polynomial time complexity in the bit size of the input, except for the possible need to calculate the prime factorization of an integer. In particular, in the case when Ann(R)=0, these algorithms compute direct decompositions of R into directly indecomposable factors.}, language = {en} } @article{GishbolinerGlockSgueglia2025, author = {Gishboliner, Lior and Glock, Stefan and Sgueglia, Amedeo}, title = {Tight Hamilton cycles with high discrepancy}, series = {Combinatorics, Probability and Computing (1469-2163)}, volume = {34 (2025)}, journal = {Combinatorics, Probability and Computing (1469-2163)}, number = {4}, publisher = {Cambridge University Press}, address = {Cambridge}, issn = {1469-2163}, doi = {10.1017/S0963548325000057}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19166}, pages = {565 -- 584}, year = {2025}, abstract = {In this paper, we study discrepancy questions for spanning subgraphs of k-uniform hypergraphs. Our main result is that, for any integers k ≥ 3 and r ≥ 2, any r-colouring of the edges of a k-uniform n-vertex hypergraph G with minimum (k-1)-degree δ(G) ≥ (1/2+o(1))n contains a tight Hamilton cycle with high discrepancy, that is, with at least n/r +� (n) edges of one colour. The minimum degree condition is asymptotically best possible and our theorem also implies a corresponding result for perfect matchings. Our tools combine various structural techniques such as Tur{\´a}n-type problems and hypergraph shadows with probabilistic techniques such as random walks and the nibble method. We also propose several intriguing problems for future research.}, language = {en} } @article{ChenMuellerYokoyama2024, author = {Chen, Yijia and M{\"u}ller, Moritz and Yokoyama, Keita}, title = {A parameterized halting problem, Δ0 truth and the MRDP theorem}, series = {The Journal of Symbolic Logic (ISSN 1943-5886)}, volume = {90 (2025)}, journal = {The Journal of Symbolic Logic (ISSN 1943-5886)}, number = {2}, publisher = {Cambridge University Press}, address = {Cambridge}, issn = {1943-5886}, doi = {10.1017/jsl.2024.44}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19308}, pages = {483 -- 508}, year = {2024}, abstract = {We study the parameterized complexity of the problem to decide whether a given natural number n satisfies a given Δ0-formula ϕ(x); the parameter is the size of ϕ. This parameterization focusses attention on instances where n is large compared to the size of ϕ.We show unconditionally that this problem does not belong to the parameterized analogue of AC0. From this we derive that certain natural upper bounds on the complexity of our parameterized problem imply certain separations of classical complexity classes. This connection is obtained via an analysis of a parameterized halting problem. Some of these upper bounds follow assuming that IΔ0 proves the MRDP theorem in a certain weak sense.}, language = {en} } @article{Hofstadler2025, author = {Hofstadler, Julian}, title = {Optimal convergence rates of MCMC integration for functions with unbounded second moment}, series = {Journal of Applied Probability}, volume = {62 (2025)}, journal = {Journal of Applied Probability}, number = {3}, publisher = {Cambridge University Press}, address = {Cambridge}, doi = {10.1017/jpr.2024.108}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19310}, pages = {1069 -- 1075}, year = {2025}, abstract = {We study the Markov chain Monte Carlo estimator for numerical integration for func- tions that do not need to be square integrable with respect to the invariant distribution. For chains with a spectral gap we show that the absolute mean error for L^p functions, with p ∈ (1, 2), decreases like n^(1/p)-1 , which is known to be the optimal rate. This improves currently known results where an additional parameter δ > 0 appears and the convergence is of order n^((1+δ)/p)-1 .}, language = {en} } @phdthesis{Henle2025, author = {Henle, Mona}, title = {Multi-Leader Congestion Games with an Adversary}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19683}, school = {Universit{\"a}t Passau}, pages = {112 Seiten}, year = {2025}, abstract = {In this thesis, we introduced a congestion game with multiple leaders and a single follower (adversary) which is motivated by security applications with congestion effects. Our objective was to understand the result and the impact of selfish acting individuals in these games. In this regard, we analyzed the existence, the computation and the quality of (approximate) pure Nash equilibria. First, we observed that an exact pure Nash equilibrium always exists in the resulting strategic game among the leaders if the resource cost coefficients are identical and the underlying congestion game is a matroid congestion game. If one of these two conditions is not fulfilled, the existence of PNE is not ensured anymore in general. Consequently, we focused on approximate equilibria. For the case of symmetric singleton strategies, one of our main result established that K ≈ 1.1974, the unique solution of a cubic polynomial equation, is the smallest possible factor such that the existence of a K-approximate equilibrium is guaranteed for all instances of the game. To this end, we presented an efficient algorithm which computes a K-approximate PNE. Furthermore, we showed that the factor K is tight by providing an instance where no α-approximate PNE with α < K exists. However, for a specific symmetric singleton instance there might be a better α-approximate PNE, i.e., with α < K. A given instance could even admit an exact PNE. We provided therefore a polynomial time procedure that computes a best approximate PNE of a given instance. In particular, this procedure can verify the existence of an exact PNE in a given instance efficiently and, if it exists, can also determine the corresponding load vector. Finally, for symmetric singleton instances with two resources, we compared the total cost of a best (cheapest) and worst (most expensive) PNE to the total cost of an optimal outcome, termed by the price of stability and the price of anarchy, respectively. In particular, we verified that the PoS and the PoA are 4/3.}, subject = {Spieltheorie}, language = {en} } @phdthesis{Schiermeier2025, author = {Schiermeier, Kathrin}, title = {Multidimensional Wavelets and Neural Networks}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19742}, school = {Universit{\"a}t Passau}, pages = {xx, 168 Seiten}, year = {2025}, abstract = {The construction of scaling functions and wavelets in multiple dimensions and for arbitrary scaling matrices is a challenging task entailing some complexities. Existing approaches mainly focus on the two-dimensional case using dyadic or quincunx sampling. This thesis aims to develop a method to construct multidimensional scaling and wavelet filters yielding orthogonal scaling functions and wavelets under the usage of convolutional neural networks. We start by recalling substantial fundamentals of ideals, modules, Fourier analysis, filterbanks and multiresolution analyses, where the mentioned concepts are already considered in an arbitrary dimensional setting to prepare the proof of the main result. There, we show the connection between multivariate scaling functions and multidimensional filters possessing certain properties. This enables us to construct scaling functions and corresponding wavelets by discrete filter design. Exploiting the link between the discrete wavelet decomposition, filterbanks and neural networks, we utilize the latter to do so. Being the main difficulty of this process, we especially focus on the Cohen criterion, which concerns the zeros of the Fourier transform of the scaling filter in modulus representing a multivariate trigonometric polynomial. After transferring the Bernstein inequality for univariate trigonomic polynomials to multiple dimensions, we present a method to derive a finite set of inequality constraints implying that the Cohen criterion holds true for a given multivariate cosine sum. Afterwards, we introduce neural networks and TensorFlow as the main tools to execute the described approach, formulate the described objective as an optimization problem and present some smaller numerical experiments and their results. A second objective of this thesis is the construction of filters possessing a unimodular modulation vector and therefore the ability to be completed to a perfect reconstruction filterbank. Both - the construction and the filterbank completion - can also be considered in a neural network framework as we will detail in the last section of this thesis alongside with the presentation of corresponding numerical experiments. In the context of filterbank completion, a further observation which allows to complete any given interpolatory filter to a perfect reconstruction filterbank in a very intuitive and simple way is presented. Furthermore, we explain that any given unimodular filter can be rendered interpolatory through prefiltering.}, language = {en} } @phdthesis{Neuwirth2026, author = {Neuwirth, Daniel}, title = {Einbettung und Charakterisierung von aligned bar 1-visibility Graphen und outer fan free Graphen}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19930}, school = {Universit{\"a}t Passau}, pages = {VII, 247 Seiten}, year = {2026}, abstract = {In dieser Arbeit werden drei verschiedene Klassen von Graphen untersucht. Die Klassen sind die bar (1;1)-visibilty Graphen, die aligned bar 1-visibility Graphen und die outer fan free Graphen. Die Klassen werden durch ihre m{\"o}glichen Einbettungen charakterisiert. Die Repr{\"a}sentation der bar (1; j)-visibility Graphen ist, dass jeder Knoten als horizontaler Strich und jede Kante als vertikaler Strich gezeichnet wird. Eine Kante kann einen Knoten genau einmal schneiden und ein Knoten kann j-mal geschnitten werden. Wir erweitern die Ergebnisse von Dean et. al. und geben Beispiele mit einer maximalen Dichte an f{\"u}r bar (1; 2)-visibility, bar (1; 3)-visibility und bar (1; 4)-visibility Graphen und geben einen maximal d{\"u}nnen Graphen f{\"u}r die Klasse der bar (1;1) visibility Graphen an. Wir zeigen, dass die Klassen der bar (1; j)-visibility Graphen f{\"u}r 1 < j < 1eine unendliche Hierarchie bilden. Abschließend beweisen wir, dass das Erkennungsproblem ob ein Graph eine bar (1;1)-visibility Repr{\"a}sentation hat, NP-vollst{\"a}ndig ist. Die Klasse der aligned bar 1-visibility Graphen (AB1V ) erh{\"a}lt man, indem man die bar (1;1)-visibility Repr{\"a}sentation um 90 Grad dreht und alle Knoten verl{\"a}ngert, so dass diese alle mit der y-Koordinate 0 starten. Die relative Position bzgl. der x-Koordinate wird mit der t-Ordnung beschrieben und mit der r-Ordnung die relative Position bzgl. der y-Koordinate. Wir erweitern die Erkenntnisse von Felsner und Massow f{\"u}r die Klasse der AB1V Graphen bzgl. ihrer maximalen Dichte, der minimale Grad eines Knotens. Wir f{\"u}hren die Methode Pfadaddition ein, um anhand deren Abschlusseigenschaften zu unterscheiden, ob ein Graph in einer Klasse liegt oder nicht. Diese Methode nutzen wir, um die Beziehung der Klasse der AB1V Graphen mit anderen Klassen zu untersuchen. F{\"u}r die Klasse der maximalen Graphen geben wir einen d{\"u}nnen Graphen und eine untere Schranke bzgl. der Dichte an. Wir geben einen Algorithmus an, welcher eine Bucheinbettung aus einer AB1V Einbettung berechnet. F{\"u}r die Klassen der optimalen AB1V Graphen geben wir einen Einbettungsalgorithmus an. Wir verbessern den Erkennungsalgorithmus von Felsner und Massow, ob ein Graph mit einer gegebenen t-Ordnung eine AB1V Einbettung besitzt. F{\"u}r die Klasse der distinkt strong AB1V Graphen, Graphen in der jeder Knoten ein unterschiedliche r-Ordnung hat und maximal f{\"u}r die r-Ordnung ist, geben wir einen Algorithmus an, der in O(n6) eine m{\"o}gliche Einbettung berechnet. Zum Schluss zeigen wir f{\"u}r diese Klasse, dass es exponentiell viele verschiedene Einbettungen gibt. Ein Graph hat eine outer fan free Einbettung, wenn alle Knoten inzident zu einer Fl{\"a}che sind und keine Kante von zwei Kanten geschnitten wird, die adjazent zu einem Knoten sind. Wir untersuchen diese Klasse zuerst auf die Dichte. Weiter erforschen wir die Beziehung zwischen den Klassen der AB1V , RAC und k-planaren Graphen. Abschließend geben wir eine Reduktion von NAE-3-SAT auf das Erkennungsproblem von outer fan free Graphen an.}, language = {de} }