@phdthesis{Schneider2015, author = {Schneider, Thilo}, title = {Mathematical Methods for the Approximation of Radar Traces}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-3269}, school = {Universit{\"a}t Passau}, pages = {114}, year = {2015}, abstract = {Most major airports collect recordings of the position of aircrafts at specific times. Those data typically requires extensive smoothing and corrections before it can be used for later analysis. Conventional smoothing approaches fail to model the movement physically correct, i.e. do not take standstills of aircrafts into account. In this thesis we develop a method to detect standstills, employ robust smoothing splines for data fitting, add adequate boundary conditions for the detected standstill periods (i.e. force the function to be constant and to entry- and exit-direction for the standstills to be identical) and give an algorithm to solve those approximation problems efficiently. In the progress we give an explicit proof for the convergence of the IRLS algorithm proposed by Huber to solve M-type estimates for non-linear approximation problems. Furthermore we derive a blueprint for a method to solve separable, quadratic least squares problems with very few quadratic variables.}, subject = {Spline-Approximation}, language = {en} } @phdthesis{Kriegl2015, author = {Kriegl, Markus}, title = {Generalizations and Applications of Border Bases}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-3628}, school = {Universit{\"a}t Passau}, year = {2015}, abstract = {This doctoral thesis is devoted to generalize border bases to the module setting and to apply them in various ways. First, we generalize the theory of border bases to finitely generated modules over a polynomial ring. We characterize these generalized border bases and show that we can compute them. As an application, we are able to characterize subideal border bases in various new ways and give a new algorithm for their computation. Moreover, we prove Schreyer's Theorem for border bases of submodules of free modules of finite rank over a polynomial ring. In the second part of this thesis, we study the effect of homogenization to border bases of zero-dimensional ideals. This yields the new concept of projective border bases of homogeneous one-dimensional ideals. We show that there is a one-to-one correspondence between projective border bases and zero-dimensional closed subschemes of weighted projective spaces that have no point on the hyperplane at infinity. Applying that correspondence, we can characterize uniform zero-dimensional closed subschemes of weighted projective spaces that have a rational support over the base field in various ways. Finally, we introduce projective border basis schemes as specific subschemes of border basis schemes. We show that these projective border basis schemes parametrize all zero-dimensional closed subschemes of a weighted projective space whose defining ideals possess a projective border basis. Assuming that the base field is algebraically closed, we are able to prove that the set of all closed points of a projective border basis scheme that correspond to a uniform subscheme is a constructive set with respect to the Zariski topology.}, language = {en} } @phdthesis{Bermeitinger2024, author = {Bermeitinger, Bernhard}, title = {Investigating a Second-Order Optimization Strategy for Neural Networks}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-14087}, school = {Universit{\"a}t Passau}, pages = {xv, 59 Seiten}, year = {2024}, abstract = {In summary, this cumulative dissertation investigates the application of the conjugate gradient method CG for the optimization of artificial neural networks (NNs) and compares this method with common first-order optimization methods, especially the stochastic gradient descent (SGD). The presented research results show that CG can effectively optimize both small and very large networks. However, the default machine precision of 32 bits can lead to problems. The best results are only achieved in 64-bits computations. The research also emphasizes the importance of the initialization of the NNs' trainable parameters and shows that an initialization using singular value decomposition (SVD) leads to drastically lower error values. Surprisingly, shallow but wide NNs, both in Transformer and CNN architectures, often perform better than their deeper counterparts. Overall, the research results recommend a re-evaluation of the previous preference for extremely deep NNs and emphasize the potential of CG as an optimization method.}, language = {en} } @phdthesis{Fink2023, author = {Fink, Simon Dominik}, title = {Constrained Planarity Algorithms in Theory and Practice}, doi = {10.15475/cpatp.2024}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-13817}, school = {Universit{\"a}t Passau}, pages = {216 Seiten}, year = {2023}, abstract = {In the constrained planarity setting, we ask whether a graph admits a crossing-free drawing that additionally satisfies a given set of constraints. These constraints are often derived from very natural problems; prominent examples are Level Planarity, where vertices have to lie on given horizontal lines indicating a hierarchy, Partially Embedded Planarity, where we extend a given drawing without modifying already-drawn parts, and Clustered Planarity, where we additionally draw the boundaries of clusters which recursively group the vertices in a crossing-free manner. In the last years, the family of constrained planarity problems received a lot of attention in the field of graph drawing. Efficient algorithms were discovered for many of them, while a few others turned out to be NP-complete. In contrast to the extensive theoretical considerations and the direct motivation by applications, only very few of the found algorithms have been implemented and evaluated in practice. The goal of this thesis is to advance the research on both theoretical as well as practical aspects of constrained planarity. On the theoretical side, we consider two types of constrained planarity problems. The first type are problems that individually constrain the rotations of vertices, that is they restrict the counter-clockwise cyclic orders of the edges incident to vertices. We give a simple linear-time algorithm for the problem Partially Embedded Planarity, which also generalizes to further constrained planarity variants of this type. The second type of constrained planarity problem concerns more involved planarity variants that come down to the question whether there are embeddings of one or multiple graphs such that the rotations of certain vertices are in sync in a certain way. Clustered Planarity and a variant of the Simultaneous Embedding with Fixed Edges Problem (Connected SEFE-2) are well-known problems of this type. Both are generalized by our Synchronized Planarity problem, for which we give a quadratic algorithm. Through reductions from various other problems, we provide a unified modelling framework for almost all known efficiently solvable constrained planarity variants that also directly provides a quadratic-time solution to all of them. For both our algorithms, a key ingredient for reaching an efficient solution is the usage of the right data structure for the problem at hand. In this case, these data structures are the SPQR-tree and the PC-tree, which describe planar embedding possibilities from a global and a local perspective, respectively. More specifically, PC-trees can be used to locally describe the possible cyclic orders of edges around vertices in all planar embeddings of a graph. This makes it a key component for our algorithms, as it allows us to test planarity while also respecting further constraints, and to communicate constraints arising from the surrounding graph structure between vertices with synchronized rotation. Bridging over to the practical side, we present the first correct implementation of PC-trees. We also describe further improvements, which allow us to outperform all implementations of alternative data structures (out of which we only found very few to be fully correct) by at least a factor of 4. We show that this yields a simple and competitive planarity test that can also yield an embedding to certify planarity. We also use our PC-tree implementation to implement our quadratic algorithm for solving Synchronized Planarity. Here, we show that our algorithm greatly outperforms previous attempts at solving related problems like Clustered Planarity in practice. We also engineer its running time and show how degrees of freedom in the theoretical algorithm can be leveraged to yield an up to tenfold speed-up in practice.}, language = {en} } @phdthesis{Brummer2022, author = {Brummer, Stephan}, title = {Numerisch robuste Berechnung der zirkul{\"a}ren Sichtbarkeitsmenge}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-12299}, school = {Universit{\"a}t Passau}, pages = {viii, 170 Seiten}, year = {2022}, abstract = {Sichtbarkeitsprobleme, wie das Folgende, geh{\"o}ren zu den grundlegenden Problemen der algorithmischen Geometrie: Berechne zu einem einfachen Polygon, dem sogenannten Kanal, und zu einem darin enthaltenen Punkt die von diesem Punkt aus sichtbare Punktmenge. Dabei ist ein Punkt von einem anderen Punkt aus sichtbar, wenn deren Verbindungsstrecke den Kanal nicht verl{\"a}sst. Wir wollen uns in dieser Arbeit mit zirkul{\"a}rer Sichtbarkeit besch{\"a}ftigen. Zur Verbindung zweier Punkte sind dann nicht nur Strecken, sondern auch Kreisb{\"o}gen zul{\"a}ssig. Außerdem betrachten wir als Ausgangspunkt dieser sogenannten Sichtbarkeitskreisb{\"o}gen und -strecken eine Kante des Kanals anstatt eines einzelnen Punkts. Konkret liefert diese Arbeit einen Beitrag zur numerisch robusten Bestimmung der zirkul{\"a}ren Sichtbarkeitsmenge ausgehend von einer Kante des Kanals. Hierf{\"u}r wird in dieser Arbeit ein Algorithmus vorgestellt, mit dem f{\"u}r einen gegebenen Punkt festgestellt werden kann, ob dieser von der Startkante aus sichtbar ist. Im Fall eines sichtbaren Punkts wird ein Sichtbarkeitskreisbogen berechnet, der zwei Kanalber{\"u}hrungen besitzt. Damit kann der Algorithmus bei geeigneter Wahl des zu untersuchenden Punkts - der als dritte Kanalber{\"u}hrung fungiert - direkt zur Berechnung von sogenannten Grenzkreisb{\"o}gen der Sichtbarkeitsmenge benutzt werden. Diese definieren den Rand der zirkul{\"a}ren Sichtbarkeitsmenge und zeichnen sich dadurch aus, dass sie vom Kanal dreimal abwechselnd von links und von rechts ber{\"u}hrt werden. Der beschriebene Algorithmus basiert auf der Untersuchung derjenigen Kreisb{\"o}gen, die zwar nicht notwendigerweise vollst{\"a}ndig im Kanal liegen, aber die Startkante mit dem Punkt verbinden, dessen Sichtbarkeit bestimmt werden soll. Insbesondere werden dabei die Bereiche untersucht, in denen der jeweilige Kreisbogen den Kanal verl{\"a}sst, die sogenannten Verletzungen. Da die „Schwere" einer solchen Verletzung quantifizierbar ist, wird ein iteratives Vorgehen erm{\"o}glicht. Dabei wird der Kreisbogen iterativ so ver{\"a}ndert, dass dieser bei gleichem Endpunkt den Kanal immer „weniger verl{\"a}sst". Ist der Endpunkt und damit der zu untersuchende Punkt nicht sichtbar, wird im Laufe des Algorithmus festgestellt, dass keine derartige Verbesserung m{\"o}glich ist. Der vorgestellte Algorithmus ist numerisch robust, einfach umzusetzen und besitzt eine in der Anzahl der Kanalecken lineare Laufzeit.}, language = {de} } @article{Schwartz2023, author = {Schwartz, Niels}, title = {Topology of closure systems in algebraic lattices}, series = {Algebra universalis}, volume = {84}, journal = {Algebra universalis}, number = {2}, publisher = {Springer Nature}, address = {Berlin}, doi = {10.1007/s00012-023-00815-7}, url = {http://nbn-resolving.de/urn:nbn:de:101:1-2023090808111682406614}, pages = {1 -- 33}, year = {2023}, abstract = {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.}, language = {en} } @article{MuenchRutterStumpf2023, author = {M{\"u}nch, Miriam and Rutter, Ignaz and Stumpf, Peter}, title = {Partial and Simultaneous Transitive Orientations via Modular Decompositions}, series = {Algorithmica}, volume = {86}, journal = {Algorithmica}, number = {4}, publisher = {Springer Nature}, address = {Berlin}, doi = {10.1007/s00453-023-01188-y}, url = {http://nbn-resolving.de/urn:nbn:de:101:1-2024022914111908687000}, pages = {1263 -- 1292}, year = {2023}, abstract = {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.}, language = {en} } @article{FruehwirthProchno2023, author = {Fr{\"u}hwirth, Lorenz and Prochno, Joscha}, title = {H{\"o}lder's inequality and its reverse — a probabilistic point of view}, series = {Mathematische Nachrichten}, volume = {296}, journal = {Mathematische Nachrichten}, number = {12}, publisher = {Wiley}, address = {Hoboken}, doi = {10.1002/mana.202200411}, url = {http://nbn-resolving.de/urn:nbn:de:101:1-2023062315175042989607}, pages = {5493 -- 5512}, year = {2023}, abstract = {In this article, we take a probabilistic look at H{\"o}lder's inequality, considering the ratio of terms in the classical H{\"o}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{\"o}lder ratio.}, language = {en} } @phdthesis{Hofstadler2024, author = {Hofstadler, Julian}, title = {Qualitative and quantitative convergence results for randomised integration methods}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-15196}, school = {Universit{\"a}t Passau}, pages = {III, 80 Seiten}, year = {2024}, abstract = {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.}, language = {en} } @article{Kaiser2023, author = {Kaiser, Tobias}, title = {Growth of log-analytic functions}, series = {Archiv der Mathematik}, volume = {120}, journal = {Archiv der Mathematik}, number = {6}, publisher = {Springer Nature}, address = {Berlin}, doi = {10.1007/s00013-023-01857-y}, url = {http://nbn-resolving.de/urn:nbn:de:101:1-2023091614564557203657}, pages = {605 -- 614}, year = {2023}, abstract = {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.}, language = {en} } @article{Kaiser2024, author = {Kaiser, Tobias}, title = {Periods, power series, and integrated algebraic numbers}, series = {Mathematische Annalen}, volume = {390}, journal = {Mathematische Annalen}, number = {2}, publisher = {Springer Berlin Heidelberg}, address = {Berlin/Heidelberg}, issn = {0025-5831}, doi = {10.1007/s00208-024-02802-2}, url = {http://nbn-resolving.de/urn:nbn:de:101:1-2024040910285674698609}, pages = {2043 -- 2074}, year = {2024}, abstract = {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.}, language = {en} } @phdthesis{Liang2023, author = {Liang, Hanning}, title = {Deflectometric Measurement of the Topography of Reflecting Freeform Surfaces in Motion}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-11672}, school = {Universit{\"a}t Passau}, pages = {xiv, 157 Seiten}, year = {2023}, abstract = {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.}, language = {en} } @phdthesis{Schlenker2022, author = {Schlenker, Florian}, title = {Delaunay Configuration B-Splines}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-11225}, school = {Universit{\"a}t Passau}, pages = {xxiii, 223 Seiten}, year = {2022}, abstract = {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.}, subject = {Spline}, language = {en} } @phdthesis{Stier2024, author = {Stier, Julian}, title = {Structure of Artificial Neural Networks : Empirical Investigations}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-14968}, school = {Universit{\"a}t Passau}, pages = {xxvi, 350 Seiten}, year = {2024}, abstract = {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.}, language = {en} } @phdthesis{Juhos2024, author = {Juhos, Michael}, title = {Probabilistic and geometric aspects of classical and non-commutative lp-type spaces in high dimensions}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-14857}, school = {Universit{\"a}t Passau}, pages = {viii, 157 Seiten}, year = {2024}, abstract = {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{\"a}ger-type results and Poincar{\´e}-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.}, language = {en} } @article{LenglerOprisSudholt2024, author = {Lengler, Johannes and Opris, Andre and Sudholt, Dirk}, title = {Analysing Equilibrium States for Population Diversity}, series = {Algorithmica (ISSN: 1432-0541)}, volume = {86}, journal = {Algorithmica (ISSN: 1432-0541)}, number = {7}, publisher = {Springer US}, address = {New York}, issn = {0178-4617}, doi = {10.1007/s00453-024-01226-3}, url = {http://nbn-resolving.de/urn:nbn:de:101:1-2406282100292.409184699704}, pages = {2317 -- 2351}, year = {2024}, abstract = {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.}, language = {en} } @article{AistleitnerFruehwirthProchno2024, author = {Aistleitner, Christoph and Fr{\"u}hwirth, Lorenz and Prochno, Joscha}, title = {Diophantine conditions in the law of the iterated logarithm for lacunary systems}, series = {Probability Theory and Related Fields (ISSN: 1432-2064)}, volume = {192}, journal = {Probability Theory and Related Fields (ISSN: 1432-2064)}, number = {1}, publisher = {Springer}, address = {Berlin/Heidelberg}, issn = {0178-8051}, doi = {10.1007/s00440-024-01272-6}, url = {http://nbn-resolving.de/urn:nbn:de:101:1-2406190937284.886045166092}, pages = {545 -- 574}, year = {2024}, abstract = {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.}, language = {en} } @article{AndraschkoDannerKreuzer2024, author = {Andraschko, Bernhard and Danner, Julian and Kreuzer, Martin}, title = {SAT Solving Using XOR-OR-AND Normal Forms}, series = {Mathematics in Computer Science (ISSN: 1661-8289)}, volume = {18}, journal = {Mathematics in Computer Science (ISSN: 1661-8289)}, number = {4}, publisher = {Springer International Publishing}, address = {Cham}, issn = {1661-8270}, doi = {10.1007/s11786-024-00594-x}, url = {http://nbn-resolving.de/urn:nbn:de:101:1-2502242130589.859216082138}, pages = {26 Seiten}, year = {2024}, abstract = {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.}, subject = {-}, language = {en} } @article{GhodselahiKuhn2023, author = {Ghodselahi, Abdolhamid and Kuhn, Fabian}, title = {Toward Online Mobile Facility Location on General Metrics}, series = {Theory of Computing Systems}, volume = {67}, journal = {Theory of Computing Systems}, number = {6}, publisher = {Springer Nature}, address = {Berlin}, doi = {10.1007/s00224-023-10145-9}, url = {http://nbn-resolving.de/urn:nbn:de:101:1-2024022609363705445898}, pages = {1268 -- 1306}, year = {2023}, abstract = {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.}, language = {en} } @article{FinkForsterHeinrich2023, author = {Fink, Thomas and Forster, Brigitte and Heinrich, Florian}, title = {Gabor's "complex signal" revisited: Complexifying frames and bases}, series = {PAMM (Proceedings in Applied Mathematics and Mechanics)}, volume = {23}, journal = {PAMM (Proceedings in Applied Mathematics and Mechanics)}, number = {3}, publisher = {Wiley}, address = {Hoboken}, doi = {10.1002/pamm.202300155}, url = {http://nbn-resolving.de/urn:nbn:de:101:1-2023091815015485698899}, pages = {8}, year = {2023}, abstract = {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.}, language = {en} } @phdthesis{Fruehwirth2025, author = {Fr{\"u}hwirth, Lorenz}, title = {The Asymptotic Behavior of Birkhoff- and Lacunary Sums}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-15677}, school = {Universit{\"a}t Passau}, pages = {109 Seiten}, year = {2025}, abstract = {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.}, language = {en} } @phdthesis{Hasenpflug2025, author = {Hasenpflug, Mareike}, title = {Slice sampling on Riemannian manifolds}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-15903}, school = {Universit{\"a}t Passau}, pages = {iii, 118 Seiten}, year = {2025}, abstract = {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.}, language = {en} } @article{Mironchenko2023, author = {Mironchenko, Andrii}, title = {Well-posedness and properties of the flow for semilinear evolution equations}, series = {Mathematics of Control, Signals, and Systems}, volume = {36}, journal = {Mathematics of Control, Signals, and Systems}, number = {3}, publisher = {Springer Nature}, address = {Berlin}, doi = {10.1007/s00498-023-00378-x}, url = {http://nbn-resolving.de/urn:nbn:de:101:1-2024022307494197431619}, pages = {483 -- 523}, year = {2023}, abstract = {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.}, language = {en} } @article{RudolfSchaer2023, author = {Rudolf, Daniel and Sch{\"a}r, Philip}, title = {Dimension-independent spectral gap of polar slice sampling}, series = {Statistics and Computing}, volume = {34}, journal = {Statistics and Computing}, number = {1}, publisher = {Springer Nature}, address = {Berlin}, doi = {10.1007/s11222-023-10335-y}, url = {http://nbn-resolving.de/urn:nbn:de:101:1-2024011821064231531382}, pages = {14 Seiten}, year = {2023}, abstract = {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.}, language = {en} } @misc{Mexis2023, type = {Master Thesis}, author = {Mexis, Nico}, title = {A Comprehensive Comparison of Fuzzy Extractor Schemes Employing Different Error Correction Codes}, volume = {2023}, doi = {10.15475/ccfesedecc.2023}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-12914}, school = {Universit{\"a}t Passau}, pages = {vii, 100 Seiten}, year = {2023}, abstract = {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.}, subject = {Vorw{\"a}rtsfehlerkorrektur}, language = {en} } @article{FruehwirthJuhosProchno2022, author = {Fr{\"u}hwirth, Lorenz and Juhos, Michael and Prochno, Joscha}, title = {The large deviation behavior of lacunary sums}, series = {Monatshefte f{\"u}r Mathematik}, volume = {2022}, journal = {Monatshefte f{\"u}r Mathematik}, number = {199}, publisher = {Springer Nature}, address = {Berlin}, doi = {10.1007/s00605-022-01733-x}, url = {http://nbn-resolving.de/urn:nbn:de:101:1-2022081723261050522140}, pages = {113 -- 133}, year = {2022}, abstract = {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.}, language = {en} } @article{HarksSchwarz2024, author = {Harks, Tobias and Schwarz, Julian}, title = {Generalized Nash equilibrium problems with mixed-integer variables}, series = {Mathematical Programming}, volume = {209}, journal = {Mathematical Programming}, number = {1}, publisher = {Springer Berlin Heidelberg}, address = {Berlin/Heidelberg}, issn = {0025-5610}, doi = {10.1007/s10107-024-02063-6}, url = {http://nbn-resolving.de/urn:nbn:de:101:1-2405152117292.567771401889}, pages = {231 -- 277}, year = {2024}, abstract = {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.}, language = {en} } @article{KreuzerLongRobbiano2024, author = {Kreuzer, Martin and Long, Le Ngoc and Robbiano, Lorenzo}, title = {Re-embeddings of affine algebras via Gr{\"o}bner fans of linear ideals}, series = {Beitr{\"a}ge zur Algebra und Geometrie / Contributions to Algebra and Geometry}, volume = {65}, journal = {Beitr{\"a}ge zur Algebra und Geometrie / Contributions to Algebra and Geometry}, number = {4}, publisher = {Springer Berlin Heidelberg}, address = {Berlin/Heidelberg}, issn = {0138-4821}, doi = {10.1007/s13366-024-00733-2}, url = {http://nbn-resolving.de/urn:nbn:de:101:1-2024041316352253862922}, pages = {827 -- 851}, year = {2024}, abstract = {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{\"o}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{\~a}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{\"o}bner fan of the linear part of  I . Then we describe a method to compute the Gr{\"o}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.}, language = {en} } @article{ProchnoRudolf2024, author = {Prochno, Joscha and Rudolf, Daniel}, title = {The minimal spherical dispersion}, series = {The Journal of Geometric Analysis}, volume = {34}, journal = {The Journal of Geometric Analysis}, number = {3}, publisher = {Springer US}, address = {New York}, issn = {1050-6926}, doi = {10.1007/s12220-023-01527-z}, url = {http://nbn-resolving.de/urn:nbn:de:101:1-2405020842543.936733306281}, pages = {14 Seiten}, year = {2024}, abstract = {We prove upper and lower bounds on the minimal spherical dispersion, improving upon previous estimates obtained by Rote and Tichy in (Anz {\"O}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 ε.}, language = {en} } @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} }