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