Conference Contributions
Untergeordnete Publikationstypen
-
Conference Paper [37068]
-
Conference Poster [2501]
-
Conference Proceedings [516]
-
Other Conference Item [20584]
Neueste Zugänge
-
Parameterised Holant Problems
(2025)Leibniz International Proceedings in Informatics LipicsWe investigate the complexity of parameterised holant problems p-Holant(S) for families of symmetric signatures S. The parameterised holant framework has been introduced by Curticapean in 2015 as a counter-part to the classical and well-established theory of holographic reductions and algorithms, and it constitutes an extensive family of coloured and weighted counting constraint satisfaction problems on graph-like structures, encoding as ...Conference Paper -
Deterministic Complexity Analysis of Hermitian Eigenproblems
(2025)Leibniz International Proceedings in Informatics LipicsIn this work we revisit the arithmetic and bit complexity of Hermitian eigenproblems. Recently, [BGVKS, FOCS 2020] proved that a (non-Hermitian) matrix A can be diagonalized with a randomized algorithm in O(n<sup>ω</sup> log<sup>2</sup>(n/<inf>ϵ</inf>)) arithmetic operations, where ω ≲ 2.371 is the square matrix multiplication exponent, and [Shah, SODA 2025] significantly improved the bit complexity for the Hermitian case. Our main goal ...Conference Paper -
Improved Streaming Edge Coloring
(2025)Leibniz International Proceedings in Informatics LipicsGiven a graph, an edge coloring assigns colors to edges so that no pairs of adjacent edges share the same color. We are interested in edge coloring algorithms under the W-streaming model. In this model, the algorithm does not have enough memory to hold the entire graph, so the edges of the input graph are read from a data stream one by one in an unknown order, and the algorithm needs to print a valid edge coloring in an output stream. The ...Conference Paper -
Decremental (1 + ϵ)-Approximate Maximum Eigenvector: Dynamic Power Method
(2025)Leibniz International Proceedings in Informatics LipicsWe present a dynamic algorithm for maintaining (1 + ϵ)-approximate maximum eigenvector and eigenvalue of a positive semi-definite matrix A undergoing decreasing updates, i.e., updates which may only decrease eigenvalues. Given a vector v updating A ← A − vv<sup>⊤</sup>, our algorithm takes Õ(nnz(v)) amortized update time, i.e., polylogarithmic per non-zeros in the update vector. Our technique is based on a novel analysis of the influential ...Conference Paper -
Acceleration Meets Inverse Maintenance: Faster ℓ∞-Regression
(2025)Leibniz International Proceedings in Informatics LipicsWe propose a randomized multiplicative weight update (MWU) algorithm for ℓ∞ regression that runs in O<sup>e</sup>(n<sup>2+1/22.5</sup>poly(1/ϵ)) time when ω = 2 + o(1), improving upon the previous best O<sup>e</sup>(n<sup>2+1/18</sup>poly log(1/ϵ)) runtime in the low-accuracy regime. Our algorithm combines state-of-the-art inverse maintenance data structures with acceleration. In order to do so, we propose a novel acceleration scheme for ...Conference Paper -
ARRIVAL: Recursive Framework & ℓ1-Contraction
(2025)Leibniz International Proceedings in Informatics LipicsARRIVAL is the problem of deciding which out of two possible destinations will be reached first by a token that moves deterministically along the edges of a directed graph, according to so-called switching rules. It is known to lie in NP ∩ CoNP, but not known to lie in P. The state-of-the-art algorithm due to Gärtner et al. (ICALP ‘21) runs in time 2<sup>O</sup>(√n log n<sup>)</sup> on an n-vertex graph. We prove that ARRIVAL can be solved ...Conference Paper -
Near-Optimal Algorithm for Directed Expander Decompositions
(2025)Leibniz International Proceedings in Informatics LipicsIn this work, we present the first algorithm to compute expander decompositions in an m-edge directed graph with near-optimal time Õ(m)<sup>1</sup>. Further, our algorithm can maintain such a decomposition in a dynamic graph and again obtains near-optimal update times. Our result improves over previous algorithms [2, 18] that only obtained algorithms optimal up to subpolynomial factors. In order to obtain our new algorithm, we present a ...Conference Paper -
Near-Optimal Directed Low-Diameter Decompositions
(2025)Leibniz International Proceedings in Informatics LipicsLow Diameter Decompositions (LDDs) are invaluable tools in the design of combinatorial graph algorithms. While historically they have been applied mainly to undirected graphs, in the recent breakthrough for the negative-length Single Source Shortest Path problem, Bernstein, Nanongkai, and Wulff-Nilsen [FOCS’22] extended the use of LDDs to directed graphs for the first time. Specifically, their LDD deletes each edge with probability at ...Conference Paper -
Reliability analysis of stochastic systems using stochastic polynomial chaos expansions and active learning
(2025)Stochastic simulators are increasingly adopted in structural design, particularly in wind and earthquake engineering. Unlike traditional deterministic simulators, which always produce the same response for a given set of inputs, stochastic simulators yield varying responses due to inherent randomness. This variability arises from latent variables not explicitly modeled by the analyst. For instance, turbulent wind fields or earthquake ...Other Conference Item -
Let's Get Visual - Testing Visual Analogies and Metaphors for Conveying Privacy Policies and Data Handling Information
(2025)2025 IEEE Symposium on Security and Privacy (SP)Conference Paper -
Use of stochastic emulators to establish fragility curves of structures under tornado winds
(2025)Design optimization is crucial in ensuring that structures are safe and robust against uncertainties. To account for various uncertainties in the design (e.g., manufacturing tolerances) or the structure’s environment (e.g., loads), reliability-based design optimization (RBDO) trades the design cost against a target reliability level. Solving an RBDO problem is however computationally expensive as it entails performing a reliability analysis ...Other Conference Item -
Polynomial chaos expansions of simulators with mixed continuous and categorical variables
(2025)Uncertainty quantification analysis typically requires numerous model evaluations, making it intractable for complex computational models due to high computational demand. To alleviate this burden, surrogate models can be constructed and employed as proxies for the original models. For most simulators used in engineering applications, input parameters are modeled by continuous random variables. However, simulators may also include categorical ...Other Conference Item -
Numerical Solver for Characterization of Semiconductor Devices
(2025)The classical drift-diffusion model (DDM) is a well-established and widely used model for simulating the charge transport in semiconductor devices. In this work, a numerical solver, incorporating DDM, has been developed, based on the finite element method. The study is conducted for a doped semiconductor block with an insulating layer. In order to assess the accuracy of the DDM solver, a commercialized tool has been used as a reference. ...Other Conference Item -
Switching lenses: The role of perspective in conceptual change processes
(2025)When looking out of the window, the horizon in front of you looks flat. Observing the curvature of our planet's surface is hardly possible. Understanding the concept of "the Earth as a sphere in space" involves a change of perspective from the first person view to that of an observer from space, that is, level-2 visual perspective taking (Gunia et al., 2021). Already Piaget pointed out the importance of perspective ...Other Conference Item -
Fully load-bearing reinforced 3D printed concrete and its application in Tor Alva, the world-tallest 3D printed concrete tower
(2025)Hormigón y Acero ~ Special Issue - Proceedings of the IX ACHE CongressDigital fabrication with concrete (DFC), particularly 3D printed concrete (3DPC), is a rapidly advancing construction method. However, it is not yet covered by current standards and lacks established mechanical models, reinforcement concepts, and load-bearing validation for full-scale structures. Tor Alva, a 30-meter-high tower and the tallest of its kind, is an example of a full-scale application (2024-2025) in the Swiss Alps using DFC. ...Conference Paper -
Causal Inference for Interpretable and Robust Deep Learning in Mobility Analysis
(2025)Other Conference Item -
Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
(2025)Proceedings of the Annual ACM Symposium on Theory of ComputingWe present a nearly linear work parallel algorithm for approximating the Held-Karp bound for Metric TSP. Given an edge-weighted undirected graph G=(V,E) on m edges and ϵ>0, it returns a (1+ϵ)-approximation to the Held-Karp bound with high probability, in Õ(m/ϵ<sup>4</sup>) work and Õ(1/ϵ<sup>4</sup>) depth. While a nearly linear time sequential algorithm was known for almost a decade (Chekuri and Quanrud '17), it was not known how to ...Conference Paper -
SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More
(2025)Proceedings of the Annual ACM Symposium on Theory of ComputingWe study sparse singular value certificates for random rectangular matrices. If M is a d × n matrix with independent Gaussian entries, we give a new family of polynomial-time algorithms which can certify upper bounds on the maximum of ||M u||, where u is a unit vector with at most n n nonzero entries for a given n ϵ (0,1). This basic algorithmic primitive lies at the heart of a wide range of problems across algorithmic statistics and ...Conference Paper -
Vizing's Theorem in Near-Linear Time
(2025)Proceedings of the Annual ACM Symposium on Theory of ComputingVizing's theorem states that any n-vertex m-edge graph of maximum degree Δcan be edge colored using at most Δ+ 1 different colors [Vizing, 1964]. Vizing's original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to Õ(m√n) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. Very recently, independently and concurrently, using randomization, this runtime ...Conference Paper