TY - JOUR A1 - Rudolf, Daniel A1 - Schär, Philip T1 - Dimension-independent spectral gap of polar slice sampling JF - Statistics and Computing N2 - Polar slice sampling, a Markov chain construction for approximate sampling, performs, under suitable assumptions on the target and initial distribution, provably independent of the state space dimension. We extend the aforementioned result of Roberts and Rosenthal (Stoch Model 18(2):257–280, 2002) by developing a theory which identifies conditions, in terms of a generalized level set function, that imply an explicit lower bound on the spectral gap even in a general slice sampling context. Verifying the identified conditions for polar slice sampling yields a lower bound of 1/2 on the spectral gap for arbitrary dimension if the target density is rotationally invariant, log-concave along rays emanating from the origin and sufficiently smooth. The general theoretical result is potentially applicable beyond the polar slice sampling framework. KW - MCMC KW - Slice Sampling KW - Spectral gap Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2024011821064231531382 VL - 34 IS - 1 PB - Springer Nature CY - Berlin ER - TY - THES A1 - Mexis, Nico T1 - A Comprehensive Comparison of Fuzzy Extractor Schemes Employing Different Error Correction Codes N2 - This thesis deals with fuzzy extractors, security primitives often used in conjunction with Physical Unclonable Functions (PUFs). A fuzzy extractor works in two stages: The generation phase and the reproduction phase. In the generation phase, an Error Correction Code (ECC) is used to compute redundant bits for a given PUF response, which are then stored as helper data, and a key is extracted from the response. Then, in the reproduction phase, another (possibly noisy) PUF response can be used in conjunction with this helper data to extract the original key. It is clear that the performance of the fuzzy extractor is strongly dependent on the underlying ECC. Therefore, a comparison of ECCs in the context of fuzzy extractors is essential in order to make them as suitable as possible for a given situation. It is important to note that due to the plethora of various PUFs with different characteristics, it is very unrealistic to propose a single metric by which the suitability of a given ECC can be measured. First, we give a brief introduction to the topic, followed by a detailed description of the background of the ECCs and fuzzy extractors studied. Then, we summarise related work and describe an implementation of the ECCs under consideration. Finally, we carry out the actual comparison of the ECCs and the thesis concludes with a summary of the results and suggestions for future work. N2 - Diese Arbeit befasst sich mit Fuzzy Extractors, Sicherheitsprimitiven, die häufig in Verbindung mit Physical Unclonable Functions (PUFs) verwendet werden. Ein Fuzzy Extractor arbeitet in zwei Phasen: Der Generierungsphase und der Reproduktionsphase. In der Generierungsphase wird ein Fehlerkorrekturverfahren (ECC) verwendet, um redundante Bits für eine gegebene PUF-Antwort zu berechnen, die dann als Hilfsdaten gespeichert werden, und ein Schlüssel wird aus der Antwort extrahiert. In der Reproduktionsphase kann dann eine andere (möglicherweise verrauschte) PUF-Antwort zusammen mit diesen Hilfsdaten verwendet werden, um den ursprünglichen Schlüssel zu extrahieren. Es ist klar, dass die Leistung des Fuzzy Extractors stark von der Leistung des zugrunde liegenden ECC abhängt. Daher ist es unerlässlich, ECCs in Verbindung mit Fuzzy Extractors zu vergleichen, um sie für eine bestimmte Situation so geeignet wie möglich zu machen. Es ist wichtig, darauf hinzuweisen, dass es aufgrund der Vielzahl verschiedener PUFs mit unterschiedlichen Eigenschaften sehr unrealistisch ist, eine einzige Metrik vorzuschlagen, mit der die Eignung eines bestimmten ECCs gemessen werden kann. Wir beginnen mit einer kurzen Einführung in das Thema, gefolgt von einer detaillierten Beschreibung des Hintergrunds der untersuchten ECCs und Fuzzy Extractors. Anschließend fassen wir verwandte Arbeiten zusammen und beschreiben eine Implementierung der untersuchten ECCs. Schließlich führen wir den eigentlichen Vergleich der ECCs durch und schließen die Arbeit mit einer Zusammenfassung der Ergebnisse und Vorschlägen für zukünftige Arbeiten ab. T2 - Ein umfassender Vergleich von Fuzzy Extractors unter Verwendung verschiedener Fehlerkorrekturverfahren KW - Fuzzy extractor KW - Error correction KW - Vorwärtsfehlerkorrektur KW - Codierungstheorie KW - Physical unclonable function KW - Biometrie Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-12914 VL - 2023 ER - TY - JOUR A1 - Frühwirth, Lorenz A1 - Juhos, Michael A1 - Prochno, Joscha T1 - The large deviation behavior of lacunary sums JF - Monatshefte für Mathematik N2 - We study the large deviation behavior of lacunary sums (Sn /n)n∈N with Sn :=∑[k=1...n] f (a(k)U), n ∈ |N, where U is uniformly distributed on [0, 1], (a(k))k∈|N is an Hadamard gap sequence, and f : |R → |R is a 1-periodic, (Lipschitz-)continuous mapping. In the case of large gaps, we show that the normalized partial sums satisfy a large deviation principle at speed n and with a good rate function which is the same as in the case of independent and identically distributed random variables U(k), k ∈ |N, having uniform distribution on [0, 1]. When the lacunary sequence (a(k))k∈|N is a geometric progression, then we also obtain large deviation principles at speed n, but with a good rate function that is different from the independent case, its form depending in a subtle way on the interplay between the function f and the arithmetic properties of the gap sequence. Our work generalizes some results recently obtained by Aistleitner, Gantert, Kabluchko, Prochno, and Ramanan [Large deviation principles for lacunary sums, preprint, 2020] who initiated this line of research for the case of lacunary trigonometric sums. KW - Hadamard gap sequence KW - Large deviation principle KW - Large gap condition KW - Geometric progression Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2022081723261050522140 VL - 2022 IS - 199 SP - 113 EP - 133 PB - Springer Nature CY - Berlin ER - TY - JOUR A1 - Harks, Tobias A1 - Schwarz, Julian T1 - Generalized Nash equilibrium problems with mixed-integer variables JF - Mathematical Programming N2 - We consider generalized Nash equilibrium problems (GNEPs) with non-convex strategy spaces and non-convex cost functions. This general class of games includes the important case of games with mixed-integer variables for which only a few results are known in the literature. We present a new approach to characterize equilibria via a convexification technique using the Nikaido–Isoda function. To any given instance of the GNEP, we construct a set of convexified instances and show that a feasible strategy profile is an equilibrium for the original instance if and only if it is an equilibrium for any convexified instance and the convexified cost functions coincide with the initial ones. We develop this convexification approach along three dimensions: We first show that for quasi-linear models, where a convexified instance exists in which for fixed strategies of the opponent players, the cost function of every player is linear and the respective strategy space is polyhedral, the convexification reduces the GNEP to a standard (non-linear) optimization problem. Secondly, we derive two complete characterizations of those GNEPs for which the convexification leads to a jointly constrained or a jointly convex GNEP, respectively. These characterizations require new concepts related to the interplay of the convex hull operator applied to restricted subsets of feasible strategies and may be interesting on their own. Note that this characterization is also computationally relevant as jointly convex GNEPs have been extensively studied in the literature. Finally, we demonstrate the applicability of our results by presenting a numerical study regarding the computation of equilibria for three classes of GNEPs related to integral network flows and discrete market equilibria. KW - Generalized Nash equilibrium problem KW - Mixed-integer nonlinear problem KW - Non-convex games KW - Complementarity and equilibrium problems and variational inequalities (finite dimensions) KW - Mixed integer programming KW - Noncooperative games Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2405152117292.567771401889 SN - 0025-5610 SN - 1436-4646 VL - 209 IS - 1 SP - 231 EP - 277 PB - Springer Berlin Heidelberg CY - Berlin/Heidelberg ER - TY - JOUR A1 - Kreuzer, Martin A1 - Long, Le Ngoc A1 - Robbiano, Lorenzo T1 - Re-embeddings of affine algebras via Gröbner fans of linear ideals JF - Beiträge zur Algebra und Geometrie / Contributions to Algebra and Geometry N2 - Given an affine algebra R=K[x1,⋯,xn]/Iover a field  K , where I is an ideal in the polynomial ring P=K[x1,⋯,xn], we examine the task of effectively calculating re-embeddings of  I , i.e., of presentations R=P′/I′such that P′=K[y1,⋯,ym]has fewer indeterminates. For cases when the number of indeterminates  n is large and Gröbner basis computations are infeasible, we have introduced the method of Z -separating re-embeddings in Kreuzer et al. (J Algebra Appl 21, 2022) and Kreuzer, et al. (São Paulo J Math Sci, 2022). This method tries to detect polynomials of a special shape in  I which allow us to eliminate the indeterminates in the tuple  Z by a simple substitution process. Here we improve this approach by showing that suitable candidate tuples  Z can be found using the Gröbner fan of the linear part of  I . Then we describe a method to compute the Gröbner fan of a linear ideal, and we improve this computation in the case of binomial linear ideals using a cotangent equivalence relation. Finally, we apply the improved technique in the case of the defining ideals of border basis schemes. KW - Re-embedding KW - Optimal embedding KW - Gröbner fan KW - Cotangent space KW - Border basis scheme Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2024041316352253862922 SN - 0138-4821 SN - 2191-0383 VL - 65 IS - 4 SP - 827 EP - 851 PB - Springer Berlin Heidelberg CY - Berlin/Heidelberg ER - TY - JOUR A1 - Prochno, Joscha A1 - Rudolf, Daniel T1 - The minimal spherical dispersion JF - The Journal of Geometric Analysis N2 - We prove upper and lower bounds on the minimal spherical dispersion, improving upon previous estimates obtained by Rote and Tichy in (Anz Österreich Akad Wiss Math Nat Kl 132:3–10, 1995). In particular, we see that the inverse N(ε,d)of the minimal spherical dispersion is, for fixed ε>0, linear in the dimension d of the ambient space. We also derive upper and lower bounds on the expected dispersion for points chosen independently and uniformly at random from the Euclidean unit sphere. In terms of the corresponding inverse N~(ε,d), our bounds are optimal with respect to the dependence on ε. KW - Dispersion KW - Expected dispersion KW - Spherical cap KW - Spherical dispersion KW - VC-dimension Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2405020842543.936733306281 SN - 1050-6926 SN - 1559-002X VL - 34 IS - 3 PB - Springer US CY - New York ER - TY - JOUR A1 - Kreuzer, Martin A1 - Walsh, Florian T1 - Computing the binomial part of a polynomial ideal JF - Journal of Symbolic Computation (Online ISSN: 1095-855X) N2 - Given an ideal I in a polynomial ring K[x1,...,xn] over a field K, we present a complete algorithm to compute the binomial part of I, i.e., the subideal Bin(I) of I generated by all monomials and binomials in I. This is achieved step-by-step. First we collect and extend several algorithms for computing exponent lattices in different kinds of fields. Then we generalize them to compute exponent lattices of units in 0-dimensional K-algebras, where we have to generalize the computation of the separable part of an algebra to non-perfect fields in characteristic p. Next we examine the computation of unit lattices in finitely generated K-algebras, as well as their associated characters and lattice ideals. This allows us to calculate Bin(I) when I is saturated with respect to the indeterminates by reducing the task to the 0-dimensional case. Finally, we treat the computation of Bin(I) for general ideals by computing their cellular decomposition and dealing with finitely many special ideals called (s,t)-binomial parts. All algorithms have been implemented in SageMath. KW - binomial part KW - binomial ideal KW - exponent lattice KW - cellular decomposition Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-18708 VL - 2024 IS - 124 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Frühwirth, Lorenz A1 - Prochno, Joscha T1 - Sanov-type large deviations and conditional limit theorems for high-dimensional Orlicz balls JF - Journal of Mathematical Analysis and Applications (Online ISSN: 1096-0813) N2 - In this paper, we prove a Sanov-type large deviation principle for the sequence of empirical measures of vectors chosen uniformly at random from an Orlicz ball. From this level-2 large deviation result, in a combination with Gibbs conditioning, entropy maximization and an Orlicz version of the Poincaré-Maxwell-Borel lemma, we deduce a conditional limit theorem for high-dimensional Orlicz balls. In more geometric parlance, the latter shows that if V1 and V2 are Orlicz functions, then random points in the V1-Orlicz ball, conditioned on having a small V2-Orlicz radius, look like an appropriately scaled V2-Orlicz ball. In fact, we show that the limiting distribution in our Poincaré-Maxwell-Borel lemma, and thus the geometric interpretation, undergoes a phase transition depending on the magnitude of the V2-Orlicz radius. KW - Entropy maximization KW - Gibbs conditioning principle KW - Large deviation principle KW - Orlicz space KW - Poincaré-Maxwell-Borel lemma KW - Sanov's theorem Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-18723 VL - 2024 IS - 536,1 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Peña Ferrández, Juan Manuel A1 - Sauer, Thomas T1 - Stabilized recovery and model reduction for multivariate exponential polynomials JF - Journal of Symbolic Computation (Online ISSN: 1095-855X) N2 - Recovery of multivariate exponential polynomials, i.e., the multivariate version of Prony's problem, can be stabilized by using more than the minimally needed multiinteger samples of the function. We present an algorithm that takes into account this extra information and prove a backward error estimate for the algebraic recovery method SMILE. In addition, we give a method to approximate data by an exponential polynomial sequence of a given structure as a step in the direction of multivariate model reduction. KW - Prony's method KW - Gröbner basis KW - Backwards error KW - Model reduction Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-18748 VL - 2024 IS - 125 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Kabluchko, Zakhar A1 - Prochno, Joscha A1 - Sonnleitner, Mathias T1 - A probabilistic approach to Lorentz balls l(^n)(q,1) JF - Journal of Functional Analysis (Online ISSN: 1096-0783) N2 - We develop a probabilistic approach to study the volumetric and geometric properties of unit balls |B(^n)(q,1) of finite-dimensional Lorentz sequence spaces l(^n)(q,1). More precisely, we show that the empirical distribution of a random vector X^(n) uniformly distributed on its volume normalized unit ball converges weakly to a compactly supported symmetric probability distribution with explicitly given density; as a consequence we obtain a weak Poincaré-Maxwell-Borel principle for any fixed number k in |N of coordinates of X^(n) as n grows infinitly. Moreover, we prove a central limit theorem for the largest coordinate of X^(n), demonstrating a quite different behavior than in the case of the l(^n)(q) balls, where a Gumbel distribution appears in the limit. Finally, we prove a Schechtman-Schmuckenschläger type result for the asymptotic volume of intersections of volume normalized l(^n)(q,1) and l(^n)(p) balls. KW - Central limit theorem KW - Concentration of measure KW - Convex body KW - Maximum entropy principle Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-18878 VL - 2025 IS - 288, 1 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Müller-Gronbach, Thomas A1 - Yaroslavtseva, Larisa T1 - On the complexity of strong approximation of stochastic differential equations with a non-Lipschitz drift coefficient JF - Journal of Complexity (Online ISSN: 1090-2708) N2 - We survey recent developments in the field of complexity of pathwise approximation in p-th mean of the solution of a stochastic differential equation at the final time based on finitely many evaluations of the driving Brownian motion. First, we briefly review the case of equations with globally Lipschitz continuous coefficients, for which an error rate of at least 1/2 in terms of the number of evaluations of the driving Brownian motion is always guaranteed by using the equidistant Euler-Maruyama scheme. Then we illustrate that giving up the global Lipschitz continuity of the coefficients may lead to a non-polynomial decay of the error for the Euler-Maruyama scheme or even to an arbitrary slow decay of the smallest possible error that can be achieved on the basis of finitely many evaluations of the driving Brownian motion. Finally, we turn to recent positive results for equations with a drift coefficient that is not globally Lipschitz continuous. Here we focus on scalar equations with a Lipschitz continuous diffusion coefficient and a drift coefficient that satisfies piecewise smoothness assumptions or has fractional Sobolev regularity and we present corresponding complexity results. KW - Stochastic differential equations KW - Non-Lipschitz drift coefficient KW - Strong approximation in p-th mean KW - Complexity KW - Lower error bounds KW - Error rates Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-18819 VL - 2024 IS - 85 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Epperlein, Jeremias A1 - Wirth, Fabian T1 - The joint spectral radius is pointwise Hölder continuous JF - Linear Algebra and its Applications N2 - We show that the joint spectral radius is pointwise Hölder continuous. In addition, the joint spectral radius is locally Hölder continuous for ε-inflations. In the two-dimensional case, local Hölder continuity holds on the matrix sets with positive joint spectral radius. KW - Joint spectral radius KW - Hölder continuity KW - Extremal norm Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-19140 SN - 1873-1856 VL - 2025 IS - 704 SP - 92 EP - 122 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Glock, Stefan A1 - Munhá Correia, David A1 - Sudakov, Benny T1 - Hamilton cycles in pseudorandom graphs JF - Advances in Mathematics N2 - Finding general conditions which ensure that a graph is Hamiltonian is a central topic in graph theory. An old and well-known conjecture in the area states that any d-regular n-vertex graph G whose second largest eigenvalue in absolute value λ(G) is at most d/C, for some universal constant C > 0, has a Hamilton cycle. In this paper, we obtain two main results which make substantial progress towards this problem. Firstly, we settle this conjecture in full when the degree d is at least a small power of n. Secondly, in the general case we show that λ(G) ≤ d/C(log n)1/3 implies the existence of a Hamilton cycle, improving the 20-year old bound of d/ log1−o(1) n of Krivelevich and Sudakov. We use in a novel way a variety of methods, such as a robust Pósa rotation-extension technique, the Friedman-Pippenger tree embedding with rollbacks and the absorbing method, combined with additional tools and ideas. Our results have several interesting applications. In particular, they imply the currently best-known bounds on the number of generators which guarantee the Hamiltonicity of random Cayley graphs, which is an important partial case of the well known Hamiltonicity conjecture of Lovász. They can also be used to improve a result of Alon and Bourgain on additive patterns in multiplicative subgroups. KW - Hamilton cycle KW - Hamiltonicity KW - Pseudorandom graph KW - Expander graph Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-19151 VL - 2024 IS - 458 B PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Kreuzer, Martin A1 - Linh, Tran N. K. A1 - Long, Le N. T1 - Differential theory of zero-dimensional schemes JF - Journal of Pure and Applied Algebra N2 - To study a 0-dimensional scheme |X in |P^n over a perfect field K, we use the module of Kähler differentials (Omega)(^1)(_{R/K}) of its homogeneous coordinate ring R and its exterior powers, the higher modules of Kähler differentials (Omega)(^m)(_{R/K}). One of our main results is a characterization of weakly curvilinear schemes |X by the Hilbert polynomials of the modules (Omega)(^m)(_{R/K}) which allows us to check this property algorithmically without computing the primary decomposition of the vanishing ideal of |X. Further main achievements are precise formulas for the Hilbert functions and Hilbert polynomials of the modules (Omega)(^m)(_{R/K}) for a fat point scheme |X which extend and settle previous partial results and conjectures. Underlying these results is a novel method: we first embed the homogeneous coordinate ring R into its truncated integral closure ~R. Then we use the corresponding map from the module of Kähler differentials (Omega)(^1)(_{R/K}) to (Omega)(^1)(_{~R/K}) to find a formula for the Hilbert polynomial HP((Omega)(^1)(_{R/K})) and a sharp bound for the regularity index ri((Omega)(^1)(_{R/K})). Next we extend this to formulas for the Hilbert polynomials HP((Omega)(^m)(_{R/K})) and bounds for the regularity indices of the higher modules of Kähler differentials. As a further application, we characterize uniformity conditions on |X using the Hilbert functions of the Kähler differential modules of |X and its subschemes. KW - Kähler differential module KW - Zero-dimensional scheme KW - Regularity index KW - Hilbert function KW - Curvilinear scheme KW - Fat point scheme Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-19130 SN - 1873-1376 VL - 229 (2025) IS - 1 PB - Elsevier CY - Amsterdam ER -