@article{ChenMuellerYokoyama2024, author = {Chen, Yijia and M{\"u}ller, Moritz and Yokoyama, Keita}, title = {A parameterized halting problem, Δ0 truth and the MRDP theorem}, series = {The Journal of Symbolic Logic (ISSN 1943-5886)}, volume = {90 (2025)}, journal = {The Journal of Symbolic Logic (ISSN 1943-5886)}, number = {2}, publisher = {Cambridge University Press}, address = {Cambridge}, issn = {1943-5886}, doi = {10.1017/jsl.2024.44}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19308}, pages = {483 -- 508}, year = {2024}, abstract = {We study the parameterized complexity of the problem to decide whether a given natural number n satisfies a given Δ0-formula ϕ(x); the parameter is the size of ϕ. This parameterization focusses attention on instances where n is large compared to the size of ϕ.We show unconditionally that this problem does not belong to the parameterized analogue of AC0. From this we derive that certain natural upper bounds on the complexity of our parameterized problem imply certain separations of classical complexity classes. This connection is obtained via an analysis of a parameterized halting problem. Some of these upper bounds follow assuming that IΔ0 proves the MRDP theorem in a certain weak sense.}, language = {en} } @article{Hofstadler2025, author = {Hofstadler, Julian}, title = {Optimal convergence rates of MCMC integration for functions with unbounded second moment}, series = {Journal of Applied Probability}, volume = {62 (2025)}, journal = {Journal of Applied Probability}, number = {3}, publisher = {Cambridge University Press}, address = {Cambridge}, doi = {10.1017/jpr.2024.108}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19310}, pages = {1069 -- 1075}, year = {2025}, abstract = {We study the Markov chain Monte Carlo estimator for numerical integration for func- tions that do not need to be square integrable with respect to the invariant distribution. For chains with a spectral gap we show that the absolute mean error for L^p functions, with p ∈ (1, 2), decreases like n^(1/p)-1 , which is known to be the optimal rate. This improves currently known results where an additional parameter δ > 0 appears and the convergence is of order n^((1+δ)/p)-1 .}, language = {en} } @phdthesis{Henle2025, author = {Henle, Mona}, title = {Multi-Leader Congestion Games with an Adversary}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19683}, school = {Universit{\"a}t Passau}, pages = {112 Seiten}, year = {2025}, abstract = {In this thesis, we introduced a congestion game with multiple leaders and a single follower (adversary) which is motivated by security applications with congestion effects. Our objective was to understand the result and the impact of selfish acting individuals in these games. In this regard, we analyzed the existence, the computation and the quality of (approximate) pure Nash equilibria. First, we observed that an exact pure Nash equilibrium always exists in the resulting strategic game among the leaders if the resource cost coefficients are identical and the underlying congestion game is a matroid congestion game. If one of these two conditions is not fulfilled, the existence of PNE is not ensured anymore in general. Consequently, we focused on approximate equilibria. For the case of symmetric singleton strategies, one of our main result established that K ≈ 1.1974, the unique solution of a cubic polynomial equation, is the smallest possible factor such that the existence of a K-approximate equilibrium is guaranteed for all instances of the game. To this end, we presented an efficient algorithm which computes a K-approximate PNE. Furthermore, we showed that the factor K is tight by providing an instance where no α-approximate PNE with α < K exists. However, for a specific symmetric singleton instance there might be a better α-approximate PNE, i.e., with α < K. A given instance could even admit an exact PNE. We provided therefore a polynomial time procedure that computes a best approximate PNE of a given instance. In particular, this procedure can verify the existence of an exact PNE in a given instance efficiently and, if it exists, can also determine the corresponding load vector. Finally, for symmetric singleton instances with two resources, we compared the total cost of a best (cheapest) and worst (most expensive) PNE to the total cost of an optimal outcome, termed by the price of stability and the price of anarchy, respectively. In particular, we verified that the PoS and the PoA are 4/3.}, subject = {Spieltheorie}, language = {en} } @phdthesis{Schiermeier2025, author = {Schiermeier, Kathrin}, title = {Multidimensional Wavelets and Neural Networks}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19742}, school = {Universit{\"a}t Passau}, pages = {xx, 168 Seiten}, year = {2025}, abstract = {The construction of scaling functions and wavelets in multiple dimensions and for arbitrary scaling matrices is a challenging task entailing some complexities. Existing approaches mainly focus on the two-dimensional case using dyadic or quincunx sampling. This thesis aims to develop a method to construct multidimensional scaling and wavelet filters yielding orthogonal scaling functions and wavelets under the usage of convolutional neural networks. We start by recalling substantial fundamentals of ideals, modules, Fourier analysis, filterbanks and multiresolution analyses, where the mentioned concepts are already considered in an arbitrary dimensional setting to prepare the proof of the main result. There, we show the connection between multivariate scaling functions and multidimensional filters possessing certain properties. This enables us to construct scaling functions and corresponding wavelets by discrete filter design. Exploiting the link between the discrete wavelet decomposition, filterbanks and neural networks, we utilize the latter to do so. Being the main difficulty of this process, we especially focus on the Cohen criterion, which concerns the zeros of the Fourier transform of the scaling filter in modulus representing a multivariate trigonometric polynomial. After transferring the Bernstein inequality for univariate trigonomic polynomials to multiple dimensions, we present a method to derive a finite set of inequality constraints implying that the Cohen criterion holds true for a given multivariate cosine sum. Afterwards, we introduce neural networks and TensorFlow as the main tools to execute the described approach, formulate the described objective as an optimization problem and present some smaller numerical experiments and their results. A second objective of this thesis is the construction of filters possessing a unimodular modulation vector and therefore the ability to be completed to a perfect reconstruction filterbank. Both - the construction and the filterbank completion - can also be considered in a neural network framework as we will detail in the last section of this thesis alongside with the presentation of corresponding numerical experiments. In the context of filterbank completion, a further observation which allows to complete any given interpolatory filter to a perfect reconstruction filterbank in a very intuitive and simple way is presented. Furthermore, we explain that any given unimodular filter can be rendered interpolatory through prefiltering.}, language = {en} } @phdthesis{Neuwirth2026, author = {Neuwirth, Daniel}, title = {Einbettung und Charakterisierung von aligned bar 1-visibility Graphen und outer fan free Graphen}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19930}, school = {Universit{\"a}t Passau}, pages = {VII, 247 Seiten}, year = {2026}, abstract = {In dieser Arbeit werden drei verschiedene Klassen von Graphen untersucht. Die Klassen sind die bar (1;1)-visibilty Graphen, die aligned bar 1-visibility Graphen und die outer fan free Graphen. Die Klassen werden durch ihre m{\"o}glichen Einbettungen charakterisiert. Die Repr{\"a}sentation der bar (1; j)-visibility Graphen ist, dass jeder Knoten als horizontaler Strich und jede Kante als vertikaler Strich gezeichnet wird. Eine Kante kann einen Knoten genau einmal schneiden und ein Knoten kann j-mal geschnitten werden. Wir erweitern die Ergebnisse von Dean et. al. und geben Beispiele mit einer maximalen Dichte an f{\"u}r bar (1; 2)-visibility, bar (1; 3)-visibility und bar (1; 4)-visibility Graphen und geben einen maximal d{\"u}nnen Graphen f{\"u}r die Klasse der bar (1;1) visibility Graphen an. Wir zeigen, dass die Klassen der bar (1; j)-visibility Graphen f{\"u}r 1 < j < 1eine unendliche Hierarchie bilden. Abschließend beweisen wir, dass das Erkennungsproblem ob ein Graph eine bar (1;1)-visibility Repr{\"a}sentation hat, NP-vollst{\"a}ndig ist. Die Klasse der aligned bar 1-visibility Graphen (AB1V ) erh{\"a}lt man, indem man die bar (1;1)-visibility Repr{\"a}sentation um 90 Grad dreht und alle Knoten verl{\"a}ngert, so dass diese alle mit der y-Koordinate 0 starten. Die relative Position bzgl. der x-Koordinate wird mit der t-Ordnung beschrieben und mit der r-Ordnung die relative Position bzgl. der y-Koordinate. Wir erweitern die Erkenntnisse von Felsner und Massow f{\"u}r die Klasse der AB1V Graphen bzgl. ihrer maximalen Dichte, der minimale Grad eines Knotens. Wir f{\"u}hren die Methode Pfadaddition ein, um anhand deren Abschlusseigenschaften zu unterscheiden, ob ein Graph in einer Klasse liegt oder nicht. Diese Methode nutzen wir, um die Beziehung der Klasse der AB1V Graphen mit anderen Klassen zu untersuchen. F{\"u}r die Klasse der maximalen Graphen geben wir einen d{\"u}nnen Graphen und eine untere Schranke bzgl. der Dichte an. Wir geben einen Algorithmus an, welcher eine Bucheinbettung aus einer AB1V Einbettung berechnet. F{\"u}r die Klassen der optimalen AB1V Graphen geben wir einen Einbettungsalgorithmus an. Wir verbessern den Erkennungsalgorithmus von Felsner und Massow, ob ein Graph mit einer gegebenen t-Ordnung eine AB1V Einbettung besitzt. F{\"u}r die Klasse der distinkt strong AB1V Graphen, Graphen in der jeder Knoten ein unterschiedliche r-Ordnung hat und maximal f{\"u}r die r-Ordnung ist, geben wir einen Algorithmus an, der in O(n6) eine m{\"o}gliche Einbettung berechnet. Zum Schluss zeigen wir f{\"u}r diese Klasse, dass es exponentiell viele verschiedene Einbettungen gibt. Ein Graph hat eine outer fan free Einbettung, wenn alle Knoten inzident zu einer Fl{\"a}che sind und keine Kante von zwei Kanten geschnitten wird, die adjazent zu einem Knoten sind. Wir untersuchen diese Klasse zuerst auf die Dichte. Weiter erforschen wir die Beziehung zwischen den Klassen der AB1V , RAC und k-planaren Graphen. Abschließend geben wir eine Reduktion von NAE-3-SAT auf das Erkennungsproblem von outer fan free Graphen an.}, language = {de} }