TY - JOUR A1 - Kreuzer, Martin A1 - Walsh, Florian T1 - Computing the binomial part of a polynomial ideal JF - Journal of Symbolic Computation (Online ISSN: 1095-855X) N2 - 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. KW - binomial part KW - binomial ideal KW - exponent lattice KW - cellular decomposition Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-18708 VL - 2024 IS - 124 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Frühwirth, Lorenz A1 - Prochno, Joscha T1 - Sanov-type large deviations and conditional limit theorems for high-dimensional Orlicz balls JF - Journal of Mathematical Analysis and Applications (Online ISSN: 1096-0813) N2 - 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é-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é-Maxwell-Borel lemma, and thus the geometric interpretation, undergoes a phase transition depending on the magnitude of the V2-Orlicz radius. KW - Entropy maximization KW - Gibbs conditioning principle KW - Large deviation principle KW - Orlicz space KW - Poincaré-Maxwell-Borel lemma KW - Sanov's theorem Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-18723 VL - 2024 IS - 536,1 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Peña Ferrández, Juan Manuel A1 - Sauer, Thomas T1 - Stabilized recovery and model reduction for multivariate exponential polynomials JF - Journal of Symbolic Computation (Online ISSN: 1095-855X) N2 - 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. KW - Prony's method KW - Gröbner basis KW - Backwards error KW - Model reduction Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-18748 VL - 2024 IS - 125 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Kabluchko, Zakhar A1 - Prochno, Joscha A1 - Sonnleitner, Mathias T1 - A probabilistic approach to Lorentz balls l(^n)(q,1) JF - Journal of Functional Analysis (Online ISSN: 1096-0783) N2 - 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é-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äger type result for the asymptotic volume of intersections of volume normalized l(^n)(q,1) and l(^n)(p) balls. KW - Central limit theorem KW - Concentration of measure KW - Convex body KW - Maximum entropy principle Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-18878 VL - 2025 IS - 288, 1 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Müller-Gronbach, Thomas A1 - Yaroslavtseva, Larisa T1 - On the complexity of strong approximation of stochastic differential equations with a non-Lipschitz drift coefficient JF - Journal of Complexity (Online ISSN: 1090-2708) N2 - 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. KW - Stochastic differential equations KW - Non-Lipschitz drift coefficient KW - Strong approximation in p-th mean KW - Complexity KW - Lower error bounds KW - Error rates Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-18819 VL - 2024 IS - 85 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Epperlein, Jeremias A1 - Wirth, Fabian T1 - The joint spectral radius is pointwise Hölder continuous JF - Linear Algebra and its Applications N2 - We show that the joint spectral radius is pointwise Hölder continuous. In addition, the joint spectral radius is locally Hölder continuous for ε-inflations. In the two-dimensional case, local Hölder continuity holds on the matrix sets with positive joint spectral radius. KW - Joint spectral radius KW - Hölder continuity KW - Extremal norm Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-19140 SN - 1873-1856 VL - 2025 IS - 704 SP - 92 EP - 122 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Glock, Stefan A1 - Munhá Correia, David A1 - Sudakov, Benny T1 - Hamilton cycles in pseudorandom graphs JF - Advances in Mathematics N2 - 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ó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ász. They can also be used to improve a result of Alon and Bourgain on additive patterns in multiplicative subgroups. KW - Hamilton cycle KW - Hamiltonicity KW - Pseudorandom graph KW - Expander graph Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-19151 VL - 2024 IS - 458 B PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Kreuzer, Martin A1 - Linh, Tran N. K. A1 - Long, Le N. T1 - Differential theory of zero-dimensional schemes JF - Journal of Pure and Applied Algebra N2 - To study a 0-dimensional scheme |X in |P^n over a perfect field K, we use the module of Kähler differentials (Omega)(^1)(_{R/K}) of its homogeneous coordinate ring R and its exterior powers, the higher modules of Kä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ä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ähler differentials. As a further application, we characterize uniformity conditions on |X using the Hilbert functions of the Kähler differential modules of |X and its subschemes. KW - Kähler differential module KW - Zero-dimensional scheme KW - Regularity index KW - Hilbert function KW - Curvilinear scheme KW - Fat point scheme Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-19130 SN - 1873-1376 VL - 229 (2025) IS - 1 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Kreuzer, Martin A1 - Miasnikov, Alexei A1 - Walsh, Florian T1 - Decomposing finite Z-algebras JF - Journal of Algebra N2 - 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. KW - Algebra decomposition KW - Directly indecomposable factor KW - Bilinear map KW - Maximal ring of scalars KW - Primitive idempotent KW - Lie ring Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-19184 SN - 1090-266X VL - 2025 IS - 664 B SP - 206 EP - 246 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Gishboliner, Lior A1 - Glock, Stefan A1 - Sgueglia, Amedeo T1 - Tight Hamilton cycles with high discrepancy JF - Combinatorics, Probability and Computing (1469-2163) N2 - 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á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. KW - Discrepancy KW - tight Hamilton cycles KW - random walks KW - nibble method Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-19166 SN - 1469-2163 VL - 34 (2025) IS - 4 SP - 565 EP - 584 PB - Cambridge University Press CY - Cambridge ER - TY - JOUR A1 - Chen, Yijia A1 - Müller, Moritz A1 - Yokoyama, Keita T1 - A parameterized halting problem, Δ0 truth and the MRDP theorem JF - The Journal of Symbolic Logic (ISSN 1943-5886) N2 - 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. KW - bounded arithmetical truth KW - parameterized halting KW - descriptive complexity KW - weak arithmetic KW - MRDP theorem Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-19308 SN - 1943-5886 VL - 90 (2025) IS - 2 SP - 483 EP - 508 PB - Cambridge University Press CY - Cambridge ER - TY - JOUR A1 - Hofstadler, Julian T1 - Optimal convergence rates of MCMC integration for functions with unbounded second moment JF - Journal of Applied Probability N2 - 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 . KW - Markov chain KW - Monte Carlo KW - spectral gap KW - absolute mean error Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-19310 VL - 62 (2025) IS - 3 SP - 1069 EP - 1075 PB - Cambridge University Press CY - Cambridge ER - TY - THES A1 - Henle, Mona T1 - Multi-Leader Congestion Games with an Adversary N2 - 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. KW - Congestion Games KW - Game Theory KW - Adversary KW - Spieltheorie Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-19683 ER - TY - THES A1 - Schiermeier, Kathrin T1 - Multidimensional Wavelets and Neural Networks N2 - 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. KW - Wavelets KW - Filterbanks KW - Convolutional Neural Networks Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-19742 ER - TY - THES A1 - Neuwirth, Daniel T1 - Einbettung und Charakterisierung von aligned bar 1-visibility Graphen und outer fan free Graphen N2 - 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öglichen Einbettungen charakterisiert. Die Reprä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ür bar (1; 2)-visibility, bar (1; 3)-visibility und bar (1; 4)-visibility Graphen und geben einen maximal dünnen Graphen für die Klasse der bar (1;1) visibility Graphen an. Wir zeigen, dass die Klassen der bar (1; j)-visibility Graphen für 1 < j < 1eine unendliche Hierarchie bilden. Abschließend beweisen wir, dass das Erkennungsproblem ob ein Graph eine bar (1;1)-visibility Repräsentation hat, NP-vollständig ist. Die Klasse der aligned bar 1-visibility Graphen (AB1V ) erhält man, indem man die bar (1;1)-visibility Repräsentation um 90 Grad dreht und alle Knoten verlä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ür die Klasse der AB1V Graphen bzgl. ihrer maximalen Dichte, der minimale Grad eines Knotens. Wir fü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ür die Klasse der maximalen Graphen geben wir einen dünnen Graphen und eine untere Schranke bzgl. der Dichte an. Wir geben einen Algorithmus an, welcher eine Bucheinbettung aus einer AB1V Einbettung berechnet. Fü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ür die Klasse der distinkt strong AB1V Graphen, Graphen in der jeder Knoten ein unterschiedliche r-Ordnung hat und maximal für die r-Ordnung ist, geben wir einen Algorithmus an, der in O(n6) eine mögliche Einbettung berechnet. Zum Schluss zeigen wir fü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ä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. KW - Graph Drawing Y1 - 2026 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-19930 ER -