@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} }