@article{GishbolinerGlockSgueglia2025, author = {Gishboliner, Lior and Glock, Stefan and Sgueglia, Amedeo}, title = {Tight Hamilton cycles with high discrepancy}, series = {Combinatorics, Probability and Computing (1469-2163)}, volume = {34 (2025)}, journal = {Combinatorics, Probability and Computing (1469-2163)}, number = {4}, publisher = {Cambridge University Press}, address = {Cambridge}, issn = {1469-2163}, doi = {10.1017/S0963548325000057}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19166}, pages = {565 -- 584}, year = {2025}, abstract = {In this paper, we study discrepancy questions for spanning subgraphs of k-uniform hypergraphs. Our main result is that, for any integers k ≥ 3 and r ≥ 2, any r-colouring of the edges of a k-uniform n-vertex hypergraph G with minimum (k-1)-degree δ(G) ≥ (1/2+o(1))n contains a tight Hamilton cycle with high discrepancy, that is, with at least n/r +� (n) edges of one colour. The minimum degree condition is asymptotically best possible and our theorem also implies a corresponding result for perfect matchings. Our tools combine various structural techniques such as Tur{\´a}n-type problems and hypergraph shadows with probabilistic techniques such as random walks and the nibble method. We also propose several intriguing problems for future research.}, language = {en} } @article{ChenMuellerYokoyama2024, author = {Chen, Yijia and M{\"u}ller, Moritz and Yokoyama, Keita}, title = {A parameterized halting problem, Δ0 truth and the MRDP theorem}, series = {The Journal of Symbolic Logic (ISSN 1943-5886)}, volume = {90 (2025)}, journal = {The Journal of Symbolic Logic (ISSN 1943-5886)}, number = {2}, publisher = {Cambridge University Press}, address = {Cambridge}, issn = {1943-5886}, doi = {10.1017/jsl.2024.44}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19308}, pages = {483 -- 508}, year = {2024}, abstract = {We study the parameterized complexity of the problem to decide whether a given natural number n satisfies a given Δ0-formula ϕ(x); the parameter is the size of ϕ. This parameterization focusses attention on instances where n is large compared to the size of ϕ.We show unconditionally that this problem does not belong to the parameterized analogue of AC0. From this we derive that certain natural upper bounds on the complexity of our parameterized problem imply certain separations of classical complexity classes. This connection is obtained via an analysis of a parameterized halting problem. Some of these upper bounds follow assuming that IΔ0 proves the MRDP theorem in a certain weak sense.}, language = {en} } @article{LechldeMeerFuermann2024, author = {Lechl, Michael and de Meer, Hermann and F{\"u}rmann, Tim}, title = {A stochastic flexibility calculus for uncertainty-aware energy flexibility management}, series = {Applied Energy}, volume = {2025}, journal = {Applied Energy}, number = {379}, doi = {10.1016/j.apenergy.2024.124907}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19233}, pages = {16 Seiten}, year = {2024}, abstract = {The increasing share of volatile renewables in power systems requires more reserves to balance forecast errors in renewable generation and power fluctuations. In contrast, common reserves such as gas-fired power plants are phased out, impeding the procurement of sufficient reserves. Alternative reserves, particularly on the demand side, such as battery storage systems, also exhibit some degree of freedom to deviate from their scheduled operating point to supply or consume more or less power, thus providing a flexibility potential. However, demand-side flexibility potentials are generally subject to uncertainties, and so is the generation of volatile renewables. The challenge is incorporating the uncertainties on both sides to procure sufficient (uncertain) flexibility potential in advance. Considering uncertainty is important to avoid additional, drastic measures in real-time to balance generation and demand, such as curtailing renewable generation or load shedding. This work presents a stochastic flexibility calculus that provides an indicator for computing the risk of insufficient flexibility potentials or, conversely, guarantees for sufficient flexibility potentials. Thus, the stochastic flexibility calculus contributes to overcoming the challenge of procuring sufficient flexibility potentials in renewable-based systems. An evaluation based on real data is performed using an example of a renewable energy community consisting of households equipped with photovoltaic power plants and battery storage systems. The newly introduced stochastic flexibility calculus computes the number of households that must operate their battery storage systems flexibly to balance forecast errors locally. The results show that the forecast method significantly influences this number. Some numerical results appear unexpected, as too many flexibility-friendly households can negatively impact the aggregated household flexibility potential.}, language = {en} } @article{BaumannPfretzschnerRutter2024, author = {Baumann, Jakob and Pfretzschner, Matthias and Rutter, Ignaz}, title = {Parameterized complexity of vertex splitting to pathwidth at most 1}, series = {Theoretical Computer Science}, volume = {2024}, journal = {Theoretical Computer Science}, number = {1021}, publisher = {Elsevier}, address = {Amsterdam}, issn = {1879-2294}, doi = {10.1016/j.tcs.2024.114928}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19195}, pages = {15 Seiten}, year = {2024}, abstract = {Motivated by the planarization of 2-layered straight-line drawings, we consider the problem of modifying a graph such that the resulting graph has pathwidth at most 1. The problem Pathwidth-One Vertex Explosion (POVE) asks whether such a graph can be obtained using at most 𝑘 vertex explosions, where a vertex explosion replaces a vertex 𝑣 by deg(𝑣) degree-1 vertices, each incident to exactly one edge that was originally incident to 𝑣. For POVE, we give an FPT algorithm with running time 𝑂(4𝑘 ⋅ 𝑚) and an 𝑂(𝑘2) kernel, thereby improving over the 𝑂(𝑘6) kernel by Ahmed et al. [2] in a more general setting. Similarly, a vertex split replaces a vertex 𝑣 by two distinct vertices 𝑣1 and 𝑣2 and distributes the edges originally incident to 𝑣 arbitrarily to 𝑣1 and 𝑣2. Analogously to POVE, we define the problem variant Pathwidth-One Vertex Splitting (POVS) that uses the split operation instead of vertex explosions. Here we obtain a linear kernel and an algorithm with running time 𝑂((6𝑘 + 12)𝑘 ⋅ 𝑚). This answers an open question by Ahmed et al. [2]. Finally, we consider the problem Π-VertexSplitting (Π-VS), which generalizes the problem POVS and asks whether a given graph can be turned into a graph of a specific graph class Π using at most 𝑘 vertex splits. For graph classes Π that can be dfined in monadic second-order graph logic (MSO2), we show that the problem Π-VS can be expressed as an MSO2 formula, resulting in an FPT algorithm for Π-VS parameterized by 𝑘 if Π additionally has bounded treewidth. We obtain the same result for the problem variant using vertex explosions. [2] R. Ahmed, S.G. Kobourov, M. Kryven, An FPT algorithm for bipartite vertex splitting, in: P. Angelini, R. von Hanxleden (Eds.), Graph Drawing and Network Visualization -30th International Symposium, GD 2022, in: Lecture Notes in Computer Science, vol.13764, Springer, 2022, pp.261--268.}, language = {en} } @article{ŁatuszyńskiRudolf2024, author = {Łatuszyński, Krzysztof and Rudolf, Daniel}, title = {Convergence of hybrid slice sampling via spectral gap}, series = {Advances in Applied Probability}, volume = {56 (2024)}, journal = {Advances in Applied Probability}, number = {4}, publisher = {Cambridge University Press}, address = {Cambridge}, issn = {1475-6064}, doi = {10.1017/apr.2024.16}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19264}, pages = {1440 -- 1466}, year = {2024}, abstract = {It is known that the simple slice sampler has robust convergence properties; however, the class of problems where it can be implemented is limited. In contrast, we consider hybrid slice samplers which are easily implementable and where another Markov chain approximately samples the uniform distribution on each slice. Under appropriate assumptions on the Markov chain on the slice, we give a lower bound and an upper bound of the spectral gap of the hybrid slice sampler in terms of the spectral gap of the simple slice sampler. An immediate consequence of this is that the spectral gap and geometric ergodicity of the hybrid slice sampler can be concluded from the spectral gap and geometric ergodicity of the simple version, which is very well understood. These results indicate that robustness properties of the simple slice sampler are inherited by (appropriately designed) easily implementable hybrid versions. We apply the developed theory and analyze a number of specific algorithms, such as the stepping-out shrinkage slice sampling, hit-and-run slice sampling on a class of multivariate targets, and an easily implementable combination of both procedures on multidimensional bimodal densities.}, 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} } @article{StockerAlshawishBoretal.2022, author = {Stocker, Armin and Alshawish, Ali and Bor, Martin and Vidler, John and Gouglidis, Antonios and Scott, Andrew and Marnerides, Angelos and De Meer, Hermann and Hutchison, David}, title = {An ICT architecture for enabling ancillary services in Distributed Renewable Energy Sources based on the SGAM framework}, series = {Energy Informatics (2520-8942)}, volume = {2022}, journal = {Energy Informatics (2520-8942)}, number = {5}, publisher = {Springer International Publishing}, address = {Berlin}, issn = {2520-8942}, doi = {10.1186/s42162-022-00189-5}, url = {http://nbn-resolving.de/urn:nbn:de:101:1-2022071721175548518669}, pages = {28 Seiten}, year = {2022}, abstract = {Smart Grids are electrical grids that require a decentralised way of controlling electric power conditioning and thereby control the production and distribution of energy. Yet, the integration of Distributed Renewable Energy Sources (DRESs) in the Smart Grid introduces new challenges with regards to electrical grid balancing and storing of electrical energy, as well as additional monetary costs. Furthermore, the future smart grid also has to take over the provision of Ancillary Services (ASs). In this paper, a distributed ICT infrastructure to solve such challenges, specifically related to ASs in future Smart Grids, is described. The proposed infrastructure is developed on the basis of the Smart Grid Architecture Model (SGAM) framework, which is defined by the European Commission in Smart Grid Mandate M/490. A testbed that provides a flexible, secure, and low-cost version of this architecture, illustrating the separation of systems and responsibilities, and supporting both emulated DRESs and real hardware has been developed. The resulting system supports the integration of a variety of DRESs with a secure two-way communication channel between the monitoring and controlling components. It assists in the analysis of various inter-operabilities and in the verification of eventual system designs. To validate the system design, the mapping of the proposed architecture to the testbed is presented. Further work will help improve the architecture in two directions; first, by investigating specific-purpose use cases, instantiated using this more generic framework; and second, by investigating the effects a realistic number and variety of connected devices within different grid configurations has on the testbed infrastructure.}, language = {en} } @phdthesis{Danner2025, author = {Danner, Julian}, title = {SAT Solving Using XOR-OR-AND Normal Forms and Cryptographic Fault Attacks}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19171}, school = {Universit{\"a}t Passau}, pages = {vi, 237 Seiten}, year = {2025}, abstract = {The Boolean satisfiability problem (SAT) lies at the core of computational logic and has found many applications in verification, cryptography, and artificial intelligence. While conflict-driven SAT solvers (CDCL) excel on large industrial instances, they struggle with XOR-rich instances arising frequently in cryptanalysis, due to the inefficiency of CNF encodings of linear constraints. Conversely, algebraic approaches can work with linear XOR constraints naturally but fail to scale to relevant sizes. Bridging these complementary paradigms with a focus on cryptographic problems is at the heart of this thesis. On one hand, this dissertation advances SAT solving by introducing the XOR-OR-AND normal form (XNF) as a generalization of the conjunctive normal form (CNF), where literals are replaced by XOR chains of literals. This allows for a native representation of XOR constraints. We generalize the CDCL architecture to the richer language of XNFs. The underlying reasoning based on the proof system SRES which is shown to be exponentially stronger than classical resolution. An implementation demonstrates competitive performance and often surpasses state-of-the-art algebraic and logic solvers on random and cryptographic benchmarks. Furthermore, we prove that every XNF formula can be converted in polynomial time to a formula in 2-XNF, enabling a graph-based approach similar to 2-SAT. Building on this, we propose advanced in- and pre-processing techniques, and construct a simple DPLL-based solving framework. Our implementation, 2-Xornado, outperforms modern algebraic and logic solving approaches on many random and some structured cryptographic problems. On the other hand, we apply combined algebraic and logical techniques to cryptanalysis of stream ciphers. We introduce a formal guess-and-determine (GD) framework using a logical abstraction of the information flow in the internal state. From an algebraic point of view, we can then find optimal GD attacks utilizing a Gr{\"o}bner basis. As a case study, we apply this method to aid in the construction of novel fault attacks on the ciphers KCipher-2 and Enocoro-128v2. Using ad hoc methods combining algebraic and logical approaches, we show that both ciphers are vulnerable to active side-channel attacks under rather weak fault models.}, language = {en} } @phdthesis{Prummer2025, author = {Prummer, Michael}, title = {Asset Tokenization and Authentication in the Industrial Metaverse}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19566}, school = {Universit{\"a}t Passau}, pages = {xviii, 196 Seiten}, year = {2025}, abstract = {The Industrial Revolution is a crucial development step in human history that started three centuries ago and is still ongoing. It continually influences and shapes the globalized world. Today, industries account for 20\% of carbon dioxide emissions worldwide and require more than a third of global energy consumption. Current problems, such as climate change, increasing waste, and pollution, require simultaneous optimization across all industrial domains, infrastructure, and systems as they depend on each other. The global industry faces the immense challenges of providing for a surging world population expected to peak in the mid-2080s with 10.4 billion people, as reported by the United Nations. Hence, industries are expected to become less resource-intensive, sustainable, and more resilient to disrupted supply chains while producing for a growing population for the next decades. The Fourth Industrial Revolution, or Industry 4.0 (I4.0), started around 2010 and is still an ongoing transformation of industrial processes towards digitalization, creating smart factories referring to the digital data integration of the entire manufacturing cycle. I4.0 is incredibly information-intensive and requires immense data to simulate and predict essential operations based on a digital shadow of the factory, a so-called digital twin. The Metaverse is considered a digitalization megatrend merging digital and physical worlds, creating immersive experiences and new opportunities for interaction and innovation across various sectors and industries. The vision of the Metaverse promotes interconnected and interoperable real-time 3D virtual worlds that can be frictionlessly traversed while sustaining ownership of one's assets under a self-sovereign identity in a decentralized environment without platform lock-ins to a specific ecosystem. Therefore, the Metaverse creates an immersive parallel reality with collective virtually shared spaces for entertainment, social interactions, education, and a new working environment. The Industrial Metaverse synthesizes Metaverse concepts with current industrial automation, such as I4.0, to deepen the digital-physical convergence by interconnecting internal and external systems to enable decision-making and predictions based on significantly broader knowledge. An Industrial Metaverse factory is entirely mirrored to integrate digital twins of all types of equipment, assets, and other entities that can communicate vertically and horizontally, as well as the knowledge about relevant external systems and industrial core sectors. Through the comprehensive data integration of the Industrial Metaverse, AI-driven applications can predict future events, reducing system and hardware failures. Furthermore, the interconnected virtual environments create a meta-ecosystem for global collaboration, providing spaces for solving complex problems such as engineering and product design tasks, simulation of product twins, and reduced development time and costs. The connected industrial ecosystems create a token-based digital economy for exchanging data, assets, and services cross-metaverse connecting isolated data silos. Sharing digital twin resources and services with other systems enables new innovative applications and growing ecosystems. The theoretical part of this thesis defines the essential characteristics and key technologies of the Industrial Metaverse to derive a reference architecture for a decentralized system of systems, outlining the fundamental Industrial Metaverse building blocks. Interoperable data exchange, access management, and system communication are critical challenges. Especially interoperability of assets such as 3D files that come in different formats and identities must be ensured to move between virtual environments. The unique fusion of technologies leverages interconnected digital twins in the context of immersion, interaction, and collaboration for secure, autonomous-governed, decentralized industrial applications. Hence, the Industrial Metaverse requires the possibility of exchanging assets, products, and services across all systems in a secure manner. Distributed ledger technology enables tamper-proof transactions of assets and value in a decentralized token economy. Therefore, we investigate the feasibility of current tokenization methods for industrial assets, in particular, Printed Circuit Board (PCB) designs and 3D models. We contribute methods to create unique fingerprints of PCB designs to enable their exchange in the token economy. We investigate how to bind files in different formats and quality representations to the same token. A robust multi-file binding based on the copper layers of a PCB design was achieved by calculating an adaptive perceptual hash of all files. The adaptive perceptual hash was evaluated against numerous tamperings of the routing layout of a PCB, showing decent resistance to layout changes. The resulting adaptive perceptual hash can be used as an additional identification attribute in a tokenized asset. Furthermore, assets must be authenticatable and verifiable by marketplaces, manufacturers, and other participants to create trust in a decentralized environment. While assets can be tampered with to manipulate, for example, cryptographic hashes that link the file to the token, perceptual hashes can compute a perceived or functional similarity of two objects instead of the plain file integrity. Without the possibility of verifying and protecting intellectual property, mass adoption of the Metaverse and Industrial Metaverse is unlikely. Therefore, we contribute to detecting tampering attacks on 3D models by introducing a 3D perceptual hash that is robust to a set of mesh manipulations, enabling the trusted exchange and authentication of 3D data in the Metaverse.}, language = {en} } @phdthesis{Ellinger2025, author = {Ellinger, Simon}, title = {On optimal error rates for strong approximation of stochastic differential equations with irregular drift coefficients}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19634}, school = {Universit{\"a}t Passau}, pages = {179 Seiten in verschiedenen Seitenz{\"a}hlungen}, year = {2025}, abstract = {In this dissertation we study strong approximation of stochastic differential equations (SDEs) with irregular drift coefficients at the final time point or globally in time by methods that use only finitely many evaluations of the driving Brownian motion. We show the optimality of well-known methods, such as the Euler-Maruyama scheme or a transformed Milstein scheme, for classes of piecewise Lipschitz continuous, H{\"o}lder continuous and Sobolev regular drift coefficients. To do this, we derive the optimal error rates for the different classes of irregular drift coefficients. Furthermore, we show that the solution of an SDE with piecewise H{\"o}lder continuous drift coefficient has a regular local density, which is used in the proofs of the lower bounds.}, language = {en} }