TY - JOUR A1 - Schwartz, Niels T1 - Topology of closure systems in algebraic lattices JF - Algebra universalis N2 - Algebraic lattices are spectral spaces for the coarse lower topology. Closure systems in algebraic lattices are studied as subspaces. Connections between order theoretic properties of a closure system and topological properties of the subspace are explored. A closure system is algebraic if and only if it is a patch closed subset of the ambient algebraic lattice. Every subset X in an algebraic lattice P generates a closure system〈X〉P . The closure system〈Y 〉P generated by the patch closure Y of X is the patch closure of〈X〉P. If X is contained in the set of nontrivial prime elements of P then〈X〉P is a frame and is a coherent algebraic frame if X is patch closed in P. Conversely, if the algebraic lattice P is coherent then its set of nontrivial prime elements is patch closed. KW - Poset KW - Complete lattice KW - Algebraic lattice KW - Frame KW - Closure system KW - Closure operator KW - Spectral space KW - Specialization KW - Coarse lower topology KW - Scott topology KW - Patch topology Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2023090808111682406614 VL - 84 IS - 2 SP - 1 EP - 33 PB - Springer Nature CY - Berlin ER - TY - JOUR A1 - Münch, Miriam A1 - Rutter, Ignaz A1 - Stumpf, Peter T1 - Partial and Simultaneous Transitive Orientations via Modular Decompositions JF - Algorithmica N2 - A natural generalization of the recognition problem for a geometric graph class is the problem of extending a representation of a subgraph to a representation of the whole graph. A related problem is to find representations for multiple input graphs that coin- cide on subgraphs shared by the input graphs. A common restriction is the sunflower case where the shared graph is the same for each pair of input graphs. These problems translate to the setting of comparability graphs where the representations correspond to transitive orientations of their edges. We use modular decompositions to improve the runtime for the orientation extension problem and the sunflower orientation problem to linear time. We apply these results to improve the runtime for the partial represen- tation problem and the sunflower case of the simultaneous representation problem for permutation graphs to linear time. We also give the first efficient algorithms for these problems on circular permutation graphs. KW - Representation extension KW - Simultaneous representation KW - Comparability KW - graph KW - Permutation graph KW - Circular permutation graph KW - Modular decomposition Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2024022914111908687000 VL - 86 IS - 4 SP - 1263 EP - 1292 PB - Springer Nature CY - Berlin ER - TY - JOUR A1 - Frühwirth, Lorenz A1 - Prochno, Joscha T1 - Hölder’s inequality and its reverse — a probabilistic point of view JF - Mathematische Nachrichten N2 - In this article, we take a probabilistic look at Hölder's inequality, considering the ratio of terms in the classical Hölder inequality for random vectors in ℝ𝑛. We prove a central limit theorem for this ratio, which then allows us to reverse the inequality up to a multiplicative constant with high probability. The models of randomness include the uniform distribution on 𝓁𝑛𝑝 balls and spheres. We also provide a Berry–Esseen–type result and prove a large and a moderate deviation principle for the suitably normalized Hölder ratio. KW - Berry–Esseen bound KW - central limit theorem KW - Hölder’s inequality KW - 𝓁 𝑛 𝑝 ball KW - large deviation principle KW - moderate deviation principle KW - reverse inequality Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2023062315175042989607 VL - 296 IS - 12 SP - 5493 EP - 5512 PB - Wiley CY - Hoboken ER - TY - THES A1 - Hofstadler, Julian T1 - Qualitative and quantitative convergence results for randomised integration methods N2 - In this thesis different randomised integration methods based on either, randomised Quasi-Monte Carlo, or (adaptive) Markov chain Monte Carlo methods are studied. Depending on the underlying integration problem we show qualitative and quantitative results, which ensure the asymptotic correctness of an algorithm or provide explicit error bounds. The first problem we consider is Lebesgue integration in the unit cube. We prove that a class of structured randomised integration methods is consistent w.r.t. convergence in mean and probability for any integrable function. Under slightly stronger integrability conditions we show that one also has almost sure convergence for median modified methods. We demonstrate the applicability of our theoretical results by considering randomly shifted lattice rules, randomised (t,d)-sequences, Latin hypercube samples, and randomised Frolov points. Secondly, we study integration w.r.t. probability measures which are available only via their non-normalised density. In this context we investigate Markov chain Monte Carlo methods which satisfy a spectral gap condition and functions which do not need to have a finite second moment. We prove error bounds for the absolute mean error where the rate of convergence is optimal. Illustrative scenarios where our theory is applicable are the random walk Metropolis algorithm as well as slice samplers. Finally, we study so-called adaptive increasingly rare Markov chain Monte Carlo algorithms. Based on a simultaneous Wasserstein contraction assumption we estimate the mean squared error and also prove bounds which characterise the path-wise convergence of the estimator. To demonstrate the applicability of our results we consider a number of examples, among which are doubly intractable distributions. Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-15196 ER - TY - JOUR A1 - Kaiser, Tobias T1 - Growth of log-analytic functions JF - Archiv der Mathematik N2 - We show that unary log-analytic functions are polynomially bounded. In the higher dimensional case, globally a log-analytic function can have exponential growth. We show that a log-analytic function is polynomially bounded on a definable set which contains the germ of every ray at infinity. KW - Log-analytic functions KW - Polynomially bounded KW - Exponential growth Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2023091614564557203657 VL - 120 IS - 6 SP - 605 EP - 614 PB - Springer Nature CY - Berlin ER - TY - JOUR A1 - Kaiser, Tobias T1 - Periods, power series, and integrated algebraic numbers JF - Mathematische Annalen N2 - Periods are defined as integrals of semialgebraic functions defined over the rationals. Periods form a countable ring not much is known about. Examples are given by taking the antiderivative of a power series which is algebraic over the polynomial ring over the rationals and evaluate it at a rational number. We follow this path and close these algebraic power series under taking iterated antiderivatives and nearby algebraic and geometric operations. We obtain a system of rings of power series whose coefficients form a countable real closed field. Using techniques from o-minimality we are able to show that every period belongs to this field. In the setting of o-minimality we define exponential integrated algebraic numbers and show that exponential periods and the Euler constant is an exponential integrated algebraic number. Hence they are a good candiate for a natural number system extending the period ring and containing important mathematical constants. KW - algebraic geometry KW - algebraic topology KW - algebra KW - associative rings and algebras KW - commutative rings and algebras KW - number theory Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2024040910285674698609 SN - 0025-5831 SN - 1432-1807 VL - 390 IS - 2 SP - 2043 EP - 2074 PB - Springer Berlin Heidelberg CY - Berlin/Heidelberg ER - TY - THES A1 - Liang, Hanning T1 - Deflectometric Measurement of the Topography of Reflecting Freeform Surfaces in Motion N2 - Measuring the topography of specular surfaces with strong surface structures in motion was impossible before this research. A new method based on singleshot phase-measuring de ectometry (SSPMD) and combining different solution aspects has been presented. Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-11672 ER - TY - THES A1 - Schlenker, Florian T1 - Delaunay Configuration B-Splines N2 - The generalization of univariate splines to higher dimensions is not straightforward. There are different approaches, each with its own advantages and drawbacks. A promising approach using Delaunay configurations and simplex splines is due to Neamtu. After recalling fundamentals of univariate splines, simplex splines, and the wellknown, multivariate DMS-splines, we address Neamtu’s DCB-splines. He defined two variants that we refer to as the nonpooled and the pooled approach, respectively. Regarding these spline spaces, we contribute the following results. We prove that, under suitable assumptions on the knot set, both variants exhibit the local finiteness property, i.e., these spline spaces are locally finite-dimensional and at each point only a finite number of basis candidate functions have a nonzero value. Additionally, we establish a criterion guaranteeing these properties within a compact region under mitigated assumptions. Moreover, we show that the knot insertion process known from univariate splines does not work for DCB-splines and reason why this behavior is inherent to these spline spaces. Furthermore, we provide a necessary criterion for the knot insertion property to hold true for a specific inserted knot. This criterion is also sufficient for bivariate, nonpooled DCB-splines of degrees zero and one. Numerical experiments suggest that the sufficiency also holds true for arbitrary spline degrees. Univariate functions can be approximated in terms of splines using the Schoenberg operator, where the approximation error decreases quadratically as the maximum distance between consecutive knots is reduced. We show that the Schoenberg operator can be defined analogously for both variants of DCB-splines with a similar error bound. Additionally, we provide a counterexample showing that the basis candidate functions of nonpooled DCB-splines are not necessarily linearly independent, contrary to earlier statements in the literature. In particular, this implies that the corresponding functions are not a basis for the space of nonpooled DCB-splines. N2 - Univariate Splines können nicht unmittelbar auf mehrere Dimensionen verallgemeinert werden. Jedoch gibt es verschiedene Ansätze mit jeweils unterschiedlichen Vor- und Nachteilen. Eine vielversprechende Herangehensweise, die Delaunay-Konfigurationen und Simplex-Splines verwendet, stammt von Neamtu. Nachdem wir die Grundlagen von univariaten Splines, Simplex-Splines und den bekannten multivariaten DMS-Splines wiederholt haben, beschäftigen wir uns mit Neamtus DCB-Splines. Er führte zwei verschiedene Varianten ein, die als nichtaggregierter beziehungsweise aggregierter Ansatz bezeichnet werden. In Bezug auf diese Splineräume präsentieren wir die folgenden Ergebnisse. Wir zeigen zum einen, dass beide Varianten unter geeigneten Voraussetzungen an die Knotenmenge die sogenannte Lokale-Endlichkeits-Eigenschaft besitzen. Dies bedeutet, dass die Splineräume lokal endlichdimensional sind und dass an jedem Punkt nur eine endliche Anzahl der Kandidaten an Basisfunktionen einen von null verschiedenen Wert aufweist. Zusätzlich ermitteln wir ein Kriterium, welches diese Eigenschaften auf einem kompakten Gebiet auch unter schwächeren Voraussetzungen garantiert. Darüber hinaus zeigen wir, dass der von den univariaten Splines her bekannte Prozess des Knoteneinfügens für DCB-Splines nicht funktioniert, und begründen, warum dieses Verhalten in der Natur dieser Splineräume liegt. Außerdem geben wir ein notwendiges Kriterium dafür an, dass die Knoteneinfüge-Eigenschaft für einen bestimmten einzufügenden Knoten gegeben sein kann. Für bivariate nicht-aggregierte DCB-Splines von Grad null und eins ist dieses Kriterium auch hinreichend. Numerische Experimente legen ferner die Vermutung nahe, dass dies unabhängig vom Splinegrad der Fall ist. Univariate Funktionen können mithilfe des Schoenberg-Operators durch Splines approximiert werden. Dabei hat eine Verringerung des maximalen Abstands zweier aufeinanderfolgender Knoten eine quadratische Verringerung des Approximationsfehlers zur Folge. Wir zeigen, dass der Schoenberg-Operator für beide Variaten von DCB-Splines auf analoge Art und Weise und mit einer ähnlichen Fehlerschranke definiert werden kann. Zusätzlich geben wir ein Gegenbeispiel an, das zeigt, dass die Basisfunktions-Kandidaten der nicht-aggregierten DCB-Splines nicht notwendigerweise linear unabhängig sind, was einen Gegensatz zu früheren Behauptungen in der Literatur darstellt. Dies impliziert insbesondere, dass die entsprechenden Funktionen keine Basis für den Raum der nicht-aggregierten DCB-Splines bilden. KW - Multivariate splines KW - Simplex splines KW - Delaunay triangulations KW - Delaunay configurations KW - Neamtu, Marian KW - Spline KW - Bivariater Spline KW - Spline-Raum KW - Simplexspline KW - Neamtu, Marian Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-11225 ER - TY - THES A1 - Stier, Julian T1 - Structure of Artificial Neural Networks : Empirical Investigations N2 - Within one decade, Deep Learning overtook the dominating solution methods of countless problems of artificial intelligence. "Deep" refers to the deep architectures with operations in manifolds of which there are no immediate observations. For these deep architectures some kind of structure is pre-defined -- but what is this structure? With a formal definition for structures of neural networks, neural architecture search problems and solution methods can be formulated under a common framework. Both practical and theoretical questions arise from closing the gap between applied neural architecture search and learning theory. Does structure make a difference or can it be chosen arbitrarily? This work is concerned with deep structures of artificial neural networks and examines automatic construction methods under empirical principles to shed light on to the so called ``black-box models''. Our contributions include a formulation of graph-induced neural networks that is used to pose optimisation problems for neural architecture. We analyse structural properties for different neural network objectives such as correctness, robustness or energy consumption and discuss how structure affects them. Selected automation methods for neural architecture optimisation problems are discussed and empirically analysed. With the insights gained from formalising graph-induced neural networks, analysing structural properties and comparing the applicability of neural architecture search methods qualitatively and quantitatively we advance these methods in two ways. First, new predictive models are presented for replacing computationally expensive evaluation schemes, and second, new generative models for informed sampling during neural architecture search are analysed and discussed. KW - neural architecture KW - deep learning KW - graph induced neural networks Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-14968 ER - TY - THES A1 - Juhos, Michael T1 - Probabilistic and geometric aspects of classical and non-commutative lp-type spaces in high dimensions N2 - This cumulative dissertation contains selected contributions to the field of asymptotic geometric analysis and high-dimensional probability. It is divided into two chapters: Chapter 1 explains some of the necessary theoretical background. In Section 1.1 it first gives a very concise history of asymptotic geometric analysis in general and then of the objects under study in particular, setting out some cornerstones in the discovery of the functional-analytic, geometric, and probabilistic properties of the spaces under consideration. The next section (1.2) gives the precise definitions and very basic properties of the three lp-type spaces that play a role in the contributed articles: the classical lp-sequence spaces, the mixed-norm sequence spaces, and the Schatten-classes Sp, each in its infinite- and finite-dimensional version. Section 1.3 is dedicated to the interplay between geometry and probability, expounding the general idea, introducing a few of the common tools, and exemplifying these on two kinds of limit theorems: Schechtman-Schmuckenschläger-type results and Poincaré-Maxwell-Borel lemmas. The first chapter concludes with Section 1.4, addressing a small sample of open questions pertaining to the contributed articles which are not answered in said articles and may be the interest of future research. The entirety of Chapter 2 consists of the contributed articles. N2 - Diese kumulative Dissertation enthält ausgewählte Beiträge zum Gebiet der asymptotischen geometrischen Analyse und der hochdimensionalen Wahrscheinlichkeit. Sie ist in zwei Kapitel geteilt: Kapitel 1 erklärt ein wenig des notwendigen theoretischen Hintergrunds. Abschnitt 1.1 bringt eine sehr kurz gefasste Geschichte der asymptotischen geometrischen Analyse im Allgemeinen und der Studienobjekte im Speziellen und legt einige Eckpunkte der Entdeckung der funktionalanalytischen, geometrischen und probabilistischen Eigenschaften der betrachteten Räume dar. Der nächste Abschnitt (1.2) gibt die genauen Definitionen und sehr grundlegenden Eigenschaften jener drei lp-artigen Räume, die in den beigetragenen Artikeln eine Rolle spielen: die klassischen lp-Folgenräume, die Folgenräume mit gemischter Norm und die Schattenklassen Sp, jeweils in der unendlich- und der endlichdimensionalen Version. Abschnitt 1.3 ist dem Zusammenspiel von Geometrie und Wahrscheinlichkeit gewidmet, er erörtert die allgemeine Idee, stellt einige der gebräuchlichen Werkzeuge vor und gibt zwei Beispiele von Grenzwertsätzen dazu: Schechtman-Schmuckenschläger-artige Ergebnisse und Poincaré-Maxwell-Borel-Lemmas. Das erste Kapitel schließt mit Abschnitt 1.4, der einen kleinen Satz von offenen Fragen anspricht, die zu den beigetragenen Artikeln gehören, darin aber nicht beantwortet werden und die das Interesse künftiger Forschung sein mögen. Kapitel 2 besteht zur Gänze aus den beigetragenen Artikeln. KW - functional analysis KW - asymptotic geometric analysis KW - limit theorems KW - lp-space KW - Schatten class Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-14857 ER - TY - JOUR A1 - Lengler, Johannes A1 - Opris, Andre A1 - Sudholt, Dirk T1 - Analysing Equilibrium States for Population Diversity JF - Algorithmica (ISSN: 1432-0541) N2 - Population diversity is crucial in evolutionary algorithms as it helps with global exploration and facilitates the use of crossover. Despite many runtime analyses showing advantages of population diversity, we have no clear picture of how diversity evolves over time. We study how the population diversity of (μ+1)algorithms, measured by the sum of pairwise Hamming distances, evolves in a fitness-neutral environment. We give an exact formula for the drift of population diversity and show that it is driven towards an equilibrium state. Moreover, we bound the expected time for getting close to the equilibrium state. We find that these dynamics, including the location of the equilibrium, are unaffected by surprisingly many algorithmic choices. All unbiased mutation operators with the same expected number of bit flips have the same effect on the expected diversity. Many crossover operators have no effect at all, including all binary unbiased, respectful operators. We review crossover operators from the literature and identify crossovers that are neutral towards the evolution of diversity and crossovers that are not. KW - Evolutionary algorithms KW - Runtime analysis KW - Diversity KW - Population dynamics Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2406282100292.409184699704 SN - 0178-4617 SN - 1432-0541 VL - 86 IS - 7 SP - 2317 EP - 2351 PB - Springer US CY - New York ER - TY - JOUR A1 - Aistleitner, Christoph A1 - Frühwirth, Lorenz A1 - Prochno, Joscha T1 - Diophantine conditions in the law of the iterated logarithm for lacunary systems JF - Probability Theory and Related Fields (ISSN: 1432-2064) N2 - It is a classical observation that lacunary function systems exhibit many properties which are typical for systems of independent random variables. However, it had already been observed by Erdős and Fortet in the 1950s that probability theory’s limit theorems may fail for lacunary sums (sum f(n_k x)) if the sequence ((n_k)_{k ge 1}) has a strong arithmetic “structure”. The presence of such structure can be assessed in terms of the number of solutions k, l of two-term linear Diophantine equations (an_k - bn_l = c). As the first author proved with Berkes in 2010, saving an (arbitrarily small) unbounded factor for the number of solutions of such equations compared to the trivial upper bound, rules out pathological situations as in the Erdős–Fortet example, and guarantees that (sum f(n_k x)) satisfies the central limit theorem (CLT) in a form which is in accordance with true independence. In contrast, as shown by the first author, for the law of the iterated logarithm (LIL) the Diophantine condition which suffices to ensure “truly independent” behavior requires saving this factor of logarithmic order. In the present paper we show that, rather surprisingly, saving such a logarithmic factor is actually the optimal condition in the LIL case. This result reveals the remarkable fact that the arithmetic condition required of ((n_k)_{k ge 1}) to ensure that (sum f(n_k x)) shows “truly random” behavior is a different one at the level of the CLT than it is at the level of the LIL: the LIL requires a stronger arithmetic condition than the CLT does. KW - Lacunary trigonometric sums KW - Law of the iterated logarithm KW - Diophantine equations Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2406190937284.886045166092 SN - 0178-8051 SN - 1432-2064 VL - 192 IS - 1 SP - 545 EP - 574 PB - Springer CY - Berlin/Heidelberg ER - TY - JOUR A1 - Andraschko, Bernhard A1 - Danner, Julian A1 - Kreuzer, Martin T1 - SAT Solving Using XOR-OR-AND Normal Forms JF - Mathematics in Computer Science (ISSN: 1661-8289) N2 - This paper introduces the XOR-OR-AND normal form (XNF) for logical formulas. It is a generalization of the well-known Conjunctive Normal Form (CNF) where literals are replaced by XORs of literals. As a first theoretic result, we show that every CNF formula is equisatisfiable to a formula in 2-XNF, i.e., a formula in XNF where each clause involves at most two XORs of literals. Subsequently, we present an algorithm which converts Boolean polynomials efficiently from their Algebraic Normal Form (ANF) to formulas in 2-XNF. Experiments with the cipher ASCON-128 show that cryptographic problems, which by design are based strongly on XOR-operations, can be represented using far fewer variables and clauses in 2-XNF than in CNF. In order to take advantage of this compact representation, new SAT solvers based on input formulas in 2-XNF need to be designed. By taking inspiration from graph-based 2-CNF SAT solving, we devise a new DPLL-based SAT solver for formulas in 2-XNF. Among others, we present advanced pre- and in-processing techniques. Finally, we give timings for random 2-XNF instances and instances related to key recovery attacks on round reduced ASCON-128, where our solver outperforms state-of-the-art alternative solving approaches. KW - - KW - SAT solving KW - XOR constraint KW - Algebraic normal form KW - Implication graph KW - Cryptographic attack KW - 03B70 KW - 13P15 KW - 05C90 KW - 94A60 Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2502242130589.859216082138 SN - 1661-8270 SN - 1661-8289 VL - 18 IS - 4 PB - Springer International Publishing CY - Cham ER - TY - JOUR A1 - Ghodselahi, Abdolhamid A1 - Kuhn, Fabian T1 - Toward Online Mobile Facility Location on General Metrics JF - Theory of Computing Systems N2 - We introduce an online variant of mobile facility location (MFL) (introduced by Demaine et al. (SODA 258–267 2007)). We call this new problem online mobile facility location (OMFL). In the OMFL problem, initially, we are given a set of k mobile facilities with their starting locations. One by one, requests are added. After each request arrives, one can make some changes to the facility locations before the subsequent request arrives. Each request is always assigned to the nearest facility. The cost of this assignment is the distance from the request to the facility. The objective is to minimize the total cost, which consists of the relocation cost of facilities and the distance cost of requests to their nearest facilities. We provide a lower bound for the OMFL problem that even holds on uniform metrics. A natural approach to solve the OMFL problem for general metric spaces is to utilize hierarchically well-separated trees (HSTs) and directly solve the OMFL problem on HSTs. In this paper, we provide the first step in this direction by solving a generalized variant of the OMFL problem on uniform metrics that we call G-OMFL. We devise a simple deterministic online algorithm and provide a tight analysis for the algorithm. The second step remains an open question. Inspired by the k-server problem, we introduce a new variant of the OMFL problem that focuses solely on minimizing movement cost. We refer to this variant as M-OMFL. Additionally, we provide a lower bound for M-OMFL that is applicable even on uniform metrics. KW - Mobile resources KW - Online requests KW - Competitive analysis KW - General cost function KW - Movement minimization Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2024022609363705445898 VL - 67 IS - 6 SP - 1268 EP - 1306 PB - Springer Nature CY - Berlin ER - TY - JOUR A1 - Fink, Thomas A1 - Forster, Brigitte A1 - Heinrich, Florian T1 - Gabor’s “complex signal” revisited: Complexifying frames and bases JF - PAMM (Proceedings in Applied Mathematics and Mechanics) N2 - In 1946, Dennis Gabor introduced the analytic signal 𝑓 + 𝑖𝐻𝑓 for real-valued signals 𝑓. Here, 𝐻 is the Hilbert transform. This complexification of functions allows for an analysis of their amplitude and phase information and has ever since given well-interpretable insight into the properties of the signals over time. The idea of complexification has been reconsidered with regard to many aspects: examples are the dual tree complex wavelet transform, or via the Riesz transform and the monogenic signal, that is, a multi-dimensional version of the Hilbert transform, which in combination with multi-resolution approaches leads to Riesz wavelets, and others. In this context, we ask two questions: - Which pairs of real orthonormal bases (ONBs), Riesz bases, frames and Parseval frames {𝑓 𝑛 } 𝑛∈ℕ and {𝑔 𝑛 } 𝑛∈ℕ can be “rebricked” to complex-valued ones {𝑓𝑛 + 𝑖𝑔 𝑛 } 𝑛∈ℕ? - And which real operators A allow for rebricking via the ansatz {𝑓𝑛 + 𝑖𝐴𝑓𝑛 } 𝑛∈ℕ? In this short note, we give answers to these questions with regard to a characterization which linear operators A are suitable for rebricking while maintaining the structure of the original real valued family. Surprisingly, the Hilbert transform is not among them. Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2023091815015485698899 VL - 23 IS - 3 PB - Wiley CY - Hoboken ER - TY - THES A1 - Frühwirth, Lorenz T1 - The Asymptotic Behavior of Birkhoff- and Lacunary Sums N2 - This doctoral thesis consists of three independently published research articles on the asymptoic behaviour of Lacunary- and Birkhoff sums. The former are sums formed by periodic functions and exponentially growing sequences of natural numbers. The corresponding summands often exhibit behavior typical of independent and identically distributed random variables. The methods used are of an analytical and probabilistic nature. The Birkhoff sums considered in this work are generated by the Kronecker sequence and by discontinuous functions. The methods employed are from the field of metric number theory, specifically classical results from continued fraction theory are utilized. Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-15677 ER - TY - THES A1 - Hasenpflug, Mareike T1 - Slice sampling on Riemannian manifolds N2 - This thesis is concerned with hybrid slice samplers for approximate sampling of distributions on Riemannian manifolds. First for distributions on the Euclidean unit sphere, and then for distributions on general Riemannian manifolds we introduce a geodesic-based hybrid slice sampler, called geodesic slice sampler. Under mild regularity assumptions, we establish reversibility with respect to the target distribution for this sampler and positive semi-definiteness of the corresponding operator. Moreover, on compact Riemannian manifolds we show uniform ergodicity with explicit constants for the geodesic slice sampler if the target distribution has a bounded density with respect to the Riemannian measure. As an important building block of this sampler, we provide an explicit expression for the shrinkage procedure proposed in (Neal, 2003) in terms of a Markov kernel. We establish that this kernel is reversible with respect to the uniform distribution on the target set and that its corresponding operator is positive semi-definite. Beyond the geodesic slice sampler, we apply these results also to elliptical slice sampling (Murray, Adams, MacKay, 2010) to obtain a proof for its reversibility with respect to the target distribution and positive semi-definiteness of the corresponding operator. KW - Markov chain Monte Carlo KW - Slice sampling KW - Riemannian manifolds Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-15903 ER - TY - JOUR A1 - Mironchenko, Andrii T1 - Well-posedness and properties of the flow for semilinear evolution equations JF - Mathematics of Control, Signals, and Systems N2 - We derive conditions for well-posedness of semilinear evolution equations with unbounded input operators. Based on this, we provide sufficient conditions for such properties of the flow map as Lipschitz continuity, bounded-implies-continuation property, boundedness of reachability sets, etc. These properties represent a basic toolbox for stability and robustness analysis of semilinear boundary control systems. We cover systems governed by general C0 -semigroups, and analytic semigroups that may have both boundary and distributed disturbances. We illustrate our findings on an example of a Burgers’ equation with nonlinear local dynamics and both distributed and boundary disturbances. KW - Well-posedness KW - Evolution equations KW - Boundary control systems KW - Infinite-dimensional systems KW - Analytic systems Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2024022307494197431619 VL - 36 IS - 3 SP - 483 EP - 523 PB - Springer Nature CY - Berlin ER - TY - JOUR A1 - Rudolf, Daniel A1 - Schär, Philip T1 - Dimension-independent spectral gap of polar slice sampling JF - Statistics and Computing N2 - Polar slice sampling, a Markov chain construction for approximate sampling, performs, under suitable assumptions on the target and initial distribution, provably independent of the state space dimension. We extend the aforementioned result of Roberts and Rosenthal (Stoch Model 18(2):257–280, 2002) by developing a theory which identifies conditions, in terms of a generalized level set function, that imply an explicit lower bound on the spectral gap even in a general slice sampling context. Verifying the identified conditions for polar slice sampling yields a lower bound of 1/2 on the spectral gap for arbitrary dimension if the target density is rotationally invariant, log-concave along rays emanating from the origin and sufficiently smooth. The general theoretical result is potentially applicable beyond the polar slice sampling framework. KW - MCMC KW - Slice Sampling KW - Spectral gap Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2024011821064231531382 VL - 34 IS - 1 PB - Springer Nature CY - Berlin ER - TY - THES A1 - Mexis, Nico T1 - A Comprehensive Comparison of Fuzzy Extractor Schemes Employing Different Error Correction Codes N2 - This thesis deals with fuzzy extractors, security primitives often used in conjunction with Physical Unclonable Functions (PUFs). A fuzzy extractor works in two stages: The generation phase and the reproduction phase. In the generation phase, an Error Correction Code (ECC) is used to compute redundant bits for a given PUF response, which are then stored as helper data, and a key is extracted from the response. Then, in the reproduction phase, another (possibly noisy) PUF response can be used in conjunction with this helper data to extract the original key. It is clear that the performance of the fuzzy extractor is strongly dependent on the underlying ECC. Therefore, a comparison of ECCs in the context of fuzzy extractors is essential in order to make them as suitable as possible for a given situation. It is important to note that due to the plethora of various PUFs with different characteristics, it is very unrealistic to propose a single metric by which the suitability of a given ECC can be measured. First, we give a brief introduction to the topic, followed by a detailed description of the background of the ECCs and fuzzy extractors studied. Then, we summarise related work and describe an implementation of the ECCs under consideration. Finally, we carry out the actual comparison of the ECCs and the thesis concludes with a summary of the results and suggestions for future work. N2 - Diese Arbeit befasst sich mit Fuzzy Extractors, Sicherheitsprimitiven, die häufig in Verbindung mit Physical Unclonable Functions (PUFs) verwendet werden. Ein Fuzzy Extractor arbeitet in zwei Phasen: Der Generierungsphase und der Reproduktionsphase. In der Generierungsphase wird ein Fehlerkorrekturverfahren (ECC) verwendet, um redundante Bits für eine gegebene PUF-Antwort zu berechnen, die dann als Hilfsdaten gespeichert werden, und ein Schlüssel wird aus der Antwort extrahiert. In der Reproduktionsphase kann dann eine andere (möglicherweise verrauschte) PUF-Antwort zusammen mit diesen Hilfsdaten verwendet werden, um den ursprünglichen Schlüssel zu extrahieren. Es ist klar, dass die Leistung des Fuzzy Extractors stark von der Leistung des zugrunde liegenden ECC abhängt. Daher ist es unerlässlich, ECCs in Verbindung mit Fuzzy Extractors zu vergleichen, um sie für eine bestimmte Situation so geeignet wie möglich zu machen. Es ist wichtig, darauf hinzuweisen, dass es aufgrund der Vielzahl verschiedener PUFs mit unterschiedlichen Eigenschaften sehr unrealistisch ist, eine einzige Metrik vorzuschlagen, mit der die Eignung eines bestimmten ECCs gemessen werden kann. Wir beginnen mit einer kurzen Einführung in das Thema, gefolgt von einer detaillierten Beschreibung des Hintergrunds der untersuchten ECCs und Fuzzy Extractors. Anschließend fassen wir verwandte Arbeiten zusammen und beschreiben eine Implementierung der untersuchten ECCs. Schließlich führen wir den eigentlichen Vergleich der ECCs durch und schließen die Arbeit mit einer Zusammenfassung der Ergebnisse und Vorschlägen für zukünftige Arbeiten ab. T2 - Ein umfassender Vergleich von Fuzzy Extractors unter Verwendung verschiedener Fehlerkorrekturverfahren KW - Fuzzy extractor KW - Error correction KW - Vorwärtsfehlerkorrektur KW - Codierungstheorie KW - Physical unclonable function KW - Biometrie Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-12914 VL - 2023 ER - TY - JOUR A1 - Frühwirth, Lorenz A1 - Juhos, Michael A1 - Prochno, Joscha T1 - The large deviation behavior of lacunary sums JF - Monatshefte für Mathematik N2 - We study the large deviation behavior of lacunary sums (Sn /n)n∈N with Sn :=∑[k=1...n] f (a(k)U), n ∈ |N, where U is uniformly distributed on [0, 1], (a(k))k∈|N is an Hadamard gap sequence, and f : |R → |R is a 1-periodic, (Lipschitz-)continuous mapping. In the case of large gaps, we show that the normalized partial sums satisfy a large deviation principle at speed n and with a good rate function which is the same as in the case of independent and identically distributed random variables U(k), k ∈ |N, having uniform distribution on [0, 1]. When the lacunary sequence (a(k))k∈|N is a geometric progression, then we also obtain large deviation principles at speed n, but with a good rate function that is different from the independent case, its form depending in a subtle way on the interplay between the function f and the arithmetic properties of the gap sequence. Our work generalizes some results recently obtained by Aistleitner, Gantert, Kabluchko, Prochno, and Ramanan [Large deviation principles for lacunary sums, preprint, 2020] who initiated this line of research for the case of lacunary trigonometric sums. KW - Hadamard gap sequence KW - Large deviation principle KW - Large gap condition KW - Geometric progression Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2022081723261050522140 VL - 2022 IS - 199 SP - 113 EP - 133 PB - Springer Nature CY - Berlin ER - TY - JOUR A1 - Harks, Tobias A1 - Schwarz, Julian T1 - Generalized Nash equilibrium problems with mixed-integer variables JF - Mathematical Programming N2 - We consider generalized Nash equilibrium problems (GNEPs) with non-convex strategy spaces and non-convex cost functions. This general class of games includes the important case of games with mixed-integer variables for which only a few results are known in the literature. We present a new approach to characterize equilibria via a convexification technique using the Nikaido–Isoda function. To any given instance of the GNEP, we construct a set of convexified instances and show that a feasible strategy profile is an equilibrium for the original instance if and only if it is an equilibrium for any convexified instance and the convexified cost functions coincide with the initial ones. We develop this convexification approach along three dimensions: We first show that for quasi-linear models, where a convexified instance exists in which for fixed strategies of the opponent players, the cost function of every player is linear and the respective strategy space is polyhedral, the convexification reduces the GNEP to a standard (non-linear) optimization problem. Secondly, we derive two complete characterizations of those GNEPs for which the convexification leads to a jointly constrained or a jointly convex GNEP, respectively. These characterizations require new concepts related to the interplay of the convex hull operator applied to restricted subsets of feasible strategies and may be interesting on their own. Note that this characterization is also computationally relevant as jointly convex GNEPs have been extensively studied in the literature. Finally, we demonstrate the applicability of our results by presenting a numerical study regarding the computation of equilibria for three classes of GNEPs related to integral network flows and discrete market equilibria. KW - Generalized Nash equilibrium problem KW - Mixed-integer nonlinear problem KW - Non-convex games KW - Complementarity and equilibrium problems and variational inequalities (finite dimensions) KW - Mixed integer programming KW - Noncooperative games Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2405152117292.567771401889 SN - 0025-5610 SN - 1436-4646 VL - 209 IS - 1 SP - 231 EP - 277 PB - Springer Berlin Heidelberg CY - Berlin/Heidelberg ER - TY - JOUR A1 - Kreuzer, Martin A1 - Long, Le Ngoc A1 - Robbiano, Lorenzo T1 - Re-embeddings of affine algebras via Gröbner fans of linear ideals JF - Beiträge zur Algebra und Geometrie / Contributions to Algebra and Geometry N2 - Given an affine algebra R=K[x1,⋯,xn]/Iover a field  K , where I is an ideal in the polynomial ring P=K[x1,⋯,xn], we examine the task of effectively calculating re-embeddings of  I , i.e., of presentations R=P′/I′such that P′=K[y1,⋯,ym]has fewer indeterminates. For cases when the number of indeterminates  n is large and Gröbner basis computations are infeasible, we have introduced the method of Z -separating re-embeddings in Kreuzer et al. (J Algebra Appl 21, 2022) and Kreuzer, et al. (São Paulo J Math Sci, 2022). This method tries to detect polynomials of a special shape in  I which allow us to eliminate the indeterminates in the tuple  Z by a simple substitution process. Here we improve this approach by showing that suitable candidate tuples  Z can be found using the Gröbner fan of the linear part of  I . Then we describe a method to compute the Gröbner fan of a linear ideal, and we improve this computation in the case of binomial linear ideals using a cotangent equivalence relation. Finally, we apply the improved technique in the case of the defining ideals of border basis schemes. KW - Re-embedding KW - Optimal embedding KW - Gröbner fan KW - Cotangent space KW - Border basis scheme Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2024041316352253862922 SN - 0138-4821 SN - 2191-0383 VL - 65 IS - 4 SP - 827 EP - 851 PB - Springer Berlin Heidelberg CY - Berlin/Heidelberg ER - TY - JOUR A1 - Prochno, Joscha A1 - Rudolf, Daniel T1 - The minimal spherical dispersion JF - The Journal of Geometric Analysis N2 - We prove upper and lower bounds on the minimal spherical dispersion, improving upon previous estimates obtained by Rote and Tichy in (Anz Österreich Akad Wiss Math Nat Kl 132:3–10, 1995). In particular, we see that the inverse N(ε,d)of the minimal spherical dispersion is, for fixed ε>0, linear in the dimension d of the ambient space. We also derive upper and lower bounds on the expected dispersion for points chosen independently and uniformly at random from the Euclidean unit sphere. In terms of the corresponding inverse N~(ε,d), our bounds are optimal with respect to the dependence on ε. KW - Dispersion KW - Expected dispersion KW - Spherical cap KW - Spherical dispersion KW - VC-dimension Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2405020842543.936733306281 SN - 1050-6926 SN - 1559-002X VL - 34 IS - 3 PB - Springer US CY - New York ER - 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 -