@inproceedings{22000,
  abstract     = {Simplicial approximation provides a framework for constructing simplicial complexes that are homotopy equivalent to a given manifold, provided a CW structure is explicitly known. However, its conventional implementation quickly becomes intractable on a computer: barycentric subdivision produces poorly shaped simplices, and the star condition introduces many vertices. To address these limitations, this article develops a subdivision scheme based on spherical Delaunay triangulations, which attains better refinement properties than barycentric subdivisions. Moreover, the star condition is reframed as two independent problems, one geometric and the other combinatorial, respectively tackled in the language of locally equiconnected spaces and the list homomorphism problem, allowing an exponential reduction in the number of vertices. Via a prototype implementation, we obtain simplicial complexes homotopy equivalent to Grassmannians and Stiefel manifolds up to dimension 5.},
  author       = {Tinarrage, Raphaël},
  booktitle    = {42nd International Symposium on Computational Geometry},
  isbn         = {9783959774185},
  issn         = {1868-8969},
  keywords     = {Triangulation of manifolds, Simplicial approximation, CW complexes, Delaunay complexes, List homomorphism problem, Topological Data Analysis},
  location     = {New Brunswick, NJ, United States},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Simplicial approximation to CW complexes with spherical Delaunay triangulations}},
  doi          = {10.4230/LIPIcs.SoCG.2026.93},
  volume       = {367},
  year         = {2026},
}

@inproceedings{22002,
  abstract     = {Topological simplification is the process of reducing complexity of a function while maintaining its essential features. Its goal is to find a new filter function, which reorders cells of the input complex in a way which eliminates some persistent homological features, without affecting the rest. We present a new approach to simplification based on the concept of forbidden regions and combinatorial dynamics. It allows us to reorder and cancel critical values, whose cancellation is not possible using existing methods because they are not consecutive in the total order. Each such cancellation takes O(c⋅n) time in the worst case, where c is the number of birth-death pairs and n is the size of the input complex.},
  author       = {Leśkiewicz, Jakub and Furmanek, Bartosz and Lipiński, Michał and Morozov, Dmitriy},
  booktitle    = {42nd International Symposium on Computational Geometry},
  isbn         = {9783959774185},
  issn         = {1868-8969},
  keywords     = {persistent homology, topological simplification, depth posets},
  location     = {New Brunswick, NJ, United States},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Topological simplification guided by forbidden regions}},
  doi          = {10.4230/LIPIcs.SoCG.2026.72},
  volume       = {367},
  year         = {2026},
}

@inproceedings{22003,
  abstract     = {Let G be a finite, connected metric graph and let X be a subset of G. If X is sufficiently dense in G, we show that the Gromov-Hausdorff distance matches the Hausdorff distance, namely d_GH(G,X) = d_H(G,X). When the metric graph is the circle G = S¹ with circumference 2π, a recent study established the equality d_GH(S¹,X) = d_H(S¹,X) whenever d_GH(S¹,X) < π/6. Our results relax this hypothesis to d_GH(S¹,X) < π/3, and furthermore, we show that the constant π/3 is the best possible. We lower bound the Gromov-Hausdorff distance d_GH(G,X) by the Hausdorff distance d_H(G,X) via a simple topological obstruction: the existence of a possibly discontinuous function f: G → X with too small distortion contradicts the connectedness of G.},
  author       = {Adams, Henry and Majhi, Sushovan and Manin, Fedor and Virk, Ziga and Zava, Nicolò},
  booktitle    = {42nd International Symposium on Computational Geometry},
  isbn         = {9783959774185},
  issn         = {1868-8969},
  keywords     = {Gromov–Hausdorff distance, distortion, connectedness, Borsuk–Ulam theorem},
  location     = {New Brunswick, NJ, United States},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Lower bounding the Gromov–Hausdorff distance in metric graphs}},
  doi          = {10.4230/LIPIcs.SoCG.2026.3},
  volume       = {367},
  year         = {2026},
}

@inproceedings{22004,
  abstract     = {Recent research on computing the diameter of geometric intersection graphs has made significant strides, primarily focusing on the 2D case [Duraj et al., 2024; Hsien-Chih Chang et al., 2024; Chan et al., 2025] where truly subquadratic-time algorithms were given for simple objects such as unit-disks and (axis-aligned) squares. However, in three or higher dimensions, there is no known truly subquadratic-time algorithm for any intersection graph of non-trivial objects, even basic ones such as unit balls or (axis-aligned) unit cubes. This was partially explained by the pioneering work of Bringmann et al. [Karl Bringmann et al., 2022] which gave several truly subquadratic lower bounds, notably for unit balls or unit cubes in 3D when the graph diameter Δ is at least Ω(log n), hinting at a pessimistic outlook for the complexity of the diameter problem in higher dimensions. In this paper, we substantially extend the landscape of diameter computation for objects in three and higher dimensions, giving a few positive results. Our highlighted findings include:  
1) A truly subquadratic-time algorithm for deciding if the diameter of unit cubes in 3D is at most 3 (Diameter-3 hereafter), the first algorithm of its kind for objects in 3D or higher dimensions. Our algorithm is based on a novel connection to pseudolines, which is of independent interest. 
2) A truly subquadratic time lower bound for Diameter-3 of unit balls in 3D under the Orthogonal Vector (OV) hypothesis, giving the first separation between unit balls and unit cubes in the small diameter regime. Previously, computing the diameter for both objects was known to be quadratic hard when the diameter is Ω(log n) [Karl Bringmann et al., 2022]. 
3) A near-linear-time algorithm for Diameter-2 of unit cubes in 3D, generalizing the previous result for unit squares in 2D [Karl Bringmann et al., 2022]. 
4) A truly subquadratic-time algorithm and lower bound for Diameter-2 and Diameter-3 of rectangular boxes (of arbitrary dimension and sizes), respectively.},
  author       = {Chan, Timothy M. and Chang, Hsien Chih and Gao, Jie and Kisfaludi-Bak, Sándor and Le, Hung and Zheng, Da Wei},
  booktitle    = {42nd International Symposium on Computational Geometry},
  isbn         = {9783959774185},
  issn         = {1868-8969},
  keywords     = {Graph Diameter, Geometric Intersection Graphs, Unit Ball Graphs},
  location     = {New Brunswick, NJ, United States},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Charting the diameter computation landscape of intersection graphs in 3D and above}},
  doi          = {10.4230/LIPIcs.SoCG.2026.29},
  volume       = {367},
  year         = {2026},
}

@inproceedings{21411,
  abstract     = {To achieve fast recovery from link failures, most modern communication networks feature fully
decentralized fast re-routing mechanisms. These re-routing mechanisms rely on pre-installed static re-routing rules at the nodes (the routers), which depend only on local failure information, namely on the failed links incident to the node. Ideally, a network is perfectly resilient: the re-routing rules ensure that packets are always successfully routed to their destinations as long as the source and the destination are still physically connected in the underlying network after the failures. Unfortunately, there are examples where achieving perfect resilience is not possible. Surprisingly, only very little is known about the algorithmic aspect of when and how perfect resilience can be achieved. We investigate the computational complexity of analyzing such local fast re-routing mechanisms. Our main result is a negative one: we show that even checking whether a given set of static re-routing rules ensures perfect resilience is coNP-complete. Additionally, we investigate other fundamental variations of the problem. In particular, we show that our coNP-completeness proof also applies to scenarios where the re-routing rules have specific patterns (known as skipping in the literature). On the positive side, for scenarios where nodes do not have information about the link from which a packet arrived (the so-called in-port), we present a linear-time algorithm to realize perfect resilience whenever possible (which we show can also be determined in linear time). },
  author       = {Bentert, Matthias and Ceylan, Esra and Hübner, Valentin and Schmid, Stefan and Srba, Jiří},
  booktitle    = {29th International Conference on Principles of Distributed Systems},
  isbn         = {9783959774093},
  issn         = {1868-8969},
  location     = {Iaşi, Romania},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Fast re-routing in networks: On the complexity of perfect resilience}},
  doi          = {10.4230/LIPIcs.OPODIS.2025.31},
  volume       = {361},
  year         = {2026},
}

@inproceedings{22146,
  abstract     = {We study differentially private model training with stochastic gradient descent under learning rate scheduling and correlated noise. Although correlated noise, in particular via matrix factorizations, has been shown to improve accuracy, prior theoretical work focused primarily on the prefix-sum workload. That workload assumes a constant learning rate, whereas in practice learning rate schedules are widely used to accelerate training and improve convergence. We close this gap by deriving general upper and lower bounds for a broad class of learning rate schedules in both single- and multi-epoch settings. Building on these results, we propose a learning-rate-aware factorization that achieves improvements over prefix-sum factorizations under both MaxSE and MeanSE error metrics. Our theoretical analysis yields memory-efficient constructions suitable for practical deployment, and experiments on CIFAR-10 and IMDB datasets confirm that schedule-aware factorizations improve accuracy in private training.},
  author       = {Kalinin, Nikita and Andersson, Joel D},
  booktitle    = {7th Symposium on Foundations of Responsible Computing},
  isbn         = {9783959774192},
  issn         = {1868-8969},
  keywords     = {differential privacy, machine learning, matrix factorization},
  location     = {Cambridge, MA; United States},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Learning rate scheduling with matrix factorization for private training}},
  doi          = {10.4230/LIPIcs.FORC.2026.2},
  volume       = {368},
  year         = {2026},
}

@inproceedings{22299,
  abstract     = {The depth poset of a filtered Lefschetz complex reflects the dependencies between the cancellations of different shallow birth-death pairs. Using the fast algorithms for computing the depth poset in [Edelsbrunner et al., 2026] and for updating the persistence diagram under transpositions in [Cohen-Steiner et al., 2006], we give a complete case analysis of how transpositions of cells in the filter affect the depth poset. In addition, we present statistics on the depth poset for random point data and its sensitivity to the transpositions that occur in random straight-line homotopies.},
  author       = {Edelsbrunner, Herbert and Lipiński, Michał and Mrozek, Marian and Soriano Trigueros, Manuel and Zimin, Fedor},
  booktitle    = {42nd International Symposium on Computational Geometry},
  isbn         = {9783959774185},
  issn         = {1868-8969},
  keywords     = {Algebraic topology, Lefschetz complexes, persistent homology, vines and vineyards, birth-death pairs, shallow pairs, relations, partial orders, transpositions, Theory of computation → Computational geometry},
  location     = {New Brunswick, NJ, United States},
  publisher    = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik},
  title        = {{The depth poset under transpositions in the filter}},
  doi          = {10.4230/LIPICS.SOCG.2026.41},
  volume       = {367},
  year         = {2026},
}

@inproceedings{22405,
  abstract     = {Computing the diameter of the intersection graphs of objects is a basic problem in computational geometry. Previous works showed that the complexity of computing the diameter mainly depends on the object types: for unit disks and squares in 2D, the problem is solvable in truly subquadratic time [Chan et al., 2025], while for other objects, including unit segments and equilateral triangles in 2D or unit balls and axis-parallel unit cubes in 3D, there is no truly subquadratic time algorithm under the Orthogonal Vector (OV) hypothesis [Bringmann et al., 2022]. 
We undertake a comprehensive study of computing the diameter of geometric intersection graphs for various types of objects. We discover many new irregularities, showing that the landscape is extremely nuanced: the source of hardness is a combination of the object type, the true diameter value, and how the objects intersect with each other. Our highlighted results for the 2D case include:  
1) The diameter of non-degenerate, axis-aligned line segments can be computed in truly subquadratic time. Previous hardness result [Bringmann et al., 2022] for line segments applies only to degenerate instances. On the other hand, for the degenerate case, we show that a truly subquadratic time algorithm exists when the true diameter is constant. 
2) An almost-linear-time algorithm for unit-square graphs of constant diameter. Previous algorithms [Duraj et al., 2024; Chan et al., 2025] rely on succinct representation assuming bounded VC-dimension; for such a strategy Ω(n^{7/4}) time is an inherent barrier. 
3) An Õ(n^{4/3})-time algorithm to decide if the diameter of a unit-disk graph is at most 2. This improves upon the recent algorithm with running time Õ(n^{2-1/9}) [Chan et al., 2025]. 
4) Deciding if the diameter of intersection graphs of fat triangles or line segments is at most 2 is truly subquadratic-hard under fine-grained complexity assumptions. Previous lower bounds [Bringmann et al., 2022] only hold when deciding if diameter is at most 3.  Our findings are presented in a pair of papers. This paper focuses solely on the 2D case, while the companion paper is devoted to higher-dimensional cases.},
  author       = {Chan, Timothy M. and Chang, Hsien-Chih and Gao, Jie and Kisfaludi-Bak, Sándor and Le, Hung and Zheng, Da Wei},
  booktitle    = {53rd International Colloquium on Automata, Languages, and Programming},
  issn         = {1868-8969},
  keywords     = {String graphs, Fine-grained complexity, Theory of computation → Computational geometry},
  location     = {Egham, United Kingdom},
  publisher    = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik},
  title        = {{Charting the landscape of diameter computation on geometric intersection graphs in the plane}},
  doi          = {10.4230/LIPICS.ICALP.2026.54},
  volume       = {374},
  year         = {2026},
}

@inproceedings{22007,
  abstract     = {Truncation of cryptographic outputs is a technique that was recently introduced in Baldimtsi et al. [Foteini Baldimtsi et al., 2022]. The general idea is to try out many inputs to some cryptographic algorithm until the output (e.g. a public-key or some hash value) falls into some sparse set and thus can be compressed: by trying out an expected 2^k different inputs one will find an output that starts with k zeros.
Using such truncation one can for example save substantial gas fees on Blockchains where storing values is very expensive. While [Foteini Baldimtsi et al., 2022] show that truncation preserves the security of the underlying primitive, they only consider a setting without preprocessing. In this work we show that lower bounds on the time-space tradeoff for inverting random functions and permutations also hold with truncation, except for parameters ranges where the bound fails to hold for "trivial" reasons.
Concretely, it’s known that any algorithm that inverts a random function or permutation with range N making T queries and using S bits of auxiliary input must satisfy S⋅ T ≥ Nlog N. This lower bound no longer holds in the truncated setting where one must only invert a challenge from a range of size N/2^k, as now one can simply save the replies to all N/2^k challenges, which requires S = log N⋅ N /2^k bits and allows to invert with T = 1 query.
We show that with truncation, whenever S is somewhat smaller than the log N⋅ N /2^k bits required to store the entire truncated function table, the known S⋅ T ≥ Nlog N lower bound applies.},
  author       = {Pietrzak, Krzysztof Z and Wang, Pengxiang},
  booktitle    = {6th Conference on Information-Theoretic Cryptography},
  isbn         = {9783959773850},
  issn         = {1868-8969},
  keywords     = {Time-Space Lower Bounds, Blockchains},
  location     = {Santa Barbara, CA, United States},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Time-space tradeoffs of truncation with preprocessing}},
  doi          = {10.4230/LIPIcs.ITC.2025.4},
  volume       = {343},
  year         = {2025},
}

@inproceedings{20005,
  abstract     = {We generalize a classical result by Boris Delaunay that introduced Delaunay triangulations. In particular, we prove that for a locally finite and coarsely dense generic point set A in ℝ^d, every generic point of ℝ^d belongs to exactly binom(d+k,d) simplices whose vertices belong to A and whose circumspheres enclose exactly k points of A. We extend this result to the cases in which the points are weighted, and when A contains only finitely many points in ℝ^d or in 𝕊^d. Furthermore, we use the result to give a new geometric proof for the fact that volumes of hypersimplices are Eulerian numbers.},
  author       = {Edelsbrunner, Herbert and Garber, Alexey and Saghafian, Morteza},
  booktitle    = {41st International Symposium on Computational Geometry},
  isbn         = {9783959773706},
  issn         = {1868-8969},
  location     = {Kanazawa, Japan},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{On spheres with k points inside}},
  doi          = {10.4230/LIPIcs.SoCG.2025.43},
  volume       = {332},
  year         = {2025},
}

@inproceedings{20006,
  abstract     = {In numerous fields, dynamic time series data require continuous updates, necessitating efficient data processing techniques for accurate analysis. This paper examines the banana tree data structure, specifically designed to efficiently maintain the multi-scale topological descriptor commonly known as persistent homology for dynamically changing time series data. We implement this data structure and conduct an experimental study to assess its properties and runtime for update operations. Our findings indicate that banana trees are highly effective with unbiased random data, outperforming state-of-the-art static algorithms in these scenarios. Additionally, our results show that real-world time series share structural properties with unbiased random walks, suggesting potential practical utility for our implementation.},
  author       = {Ost, Lara and Cultrera di Montesano, Sebastiano and Edelsbrunner, Herbert},
  booktitle    = {41st International Symposium on Computational Geometry},
  isbn         = {9783959773706},
  issn         = {1868-8969},
  location     = {Kanazawa, Japan},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Banana trees for the persistence in time series experimentally}},
  doi          = {10.4230/LIPIcs.SoCG.2025.71},
  volume       = {332},
  year         = {2025},
}

@inproceedings{20004,
  abstract     = {A long-standing conjecture of Eckhoff, Linhart, and Welzl, which would generalize McMullen’s Upper Bound Theorem for polytopes and refine asymptotic bounds due to Clarkson, asserts that for k ⩽ ⌊(n-d-2)/2⌋, the complexity of the (⩽ k)-level in a simple arrangement of n hemispheres in S^d is maximized for arrangements that are polar duals of neighborly d-polytopes. We prove this conjecture in the case n = d+4. By Gale duality, this implies the following result about crossing numbers: In every spherical arc drawing of K_n in S² (given by a set V ⊂ S² of n unit vectors connected by spherical arcs), the number of crossings is at least 1/4 ⌊n/2⌋ ⌊(n-1)/2⌋ ⌊(n-2)/2⌋ ⌊(n-3)/2⌋. This lower bound is attained if every open linear halfspace contains at least ⌊(n-2)/2⌋ of the vectors in V.
Moreover, we determine the space of all linear and affine relations that hold between the face numbers of levels in simple arrangements of n hemispheres in S^d. This completes a long line of research on such relations, answers a question posed by Andrzejak and Welzl in 2003, and generalizes the classical fact that the Dehn-Sommerville relations generate all linear relations between the face numbers of simple polytopes (which correspond to the 0-level).
To prove these results, we introduce the notion of the g-matrix, which encodes the face numbers of levels in an arrangement and generalizes the classical g-vector of a polytope.},
  author       = {Streltsova, Elizaveta and Wagner, Uli},
  booktitle    = {41st International Symposium on Computational Geometry},
  isbn         = {9783959773706},
  issn         = {1868-8969},
  location     = {Kanazawa, Japan},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers}},
  doi          = {10.4230/LIPIcs.SoCG.2025.75},
  volume       = {332},
  year         = {2025},
}

@inproceedings{17170,
  abstract     = {In this article we extend and strengthen the seminal work by Niyogi, Smale, and Weinberger on the learning of the homotopy type from a sample of an underlying space. In their work, Niyogi, Smale, and Weinberger studied samples of C² manifolds with positive reach embedded in ℝ^d. We extend their results in the following ways: - As the ambient space we consider both ℝ^d and Riemannian manifolds with lower bounded sectional curvature. - In both types of ambient spaces, we study sets of positive reach - a significantly more general setting than C² manifolds - as well as general manifolds of positive reach. - The sample P of a set (or a manifold) 𝒮 of positive reach may be noisy. We work with two one-sided Hausdorff distances - ε and δ - between P and 𝒮. We provide tight bounds in terms of ε and δ, that guarantee that there exists a parameter r such that the union of balls of radius r centred at the sample P deformation-retracts to 𝒮. We exhibit their tightness by an explicit construction. We carefully distinguish the roles of δ and ε. This is not only essential to achieve tight bounds, but also sensible in practical situations, since it allows one to adapt the bound according to sample density and the amount of noise present in the sample separately.},
  author       = {Attali, Dominique and Kourimska, Hana and Fillmore, Christopher D and Ghosh, Ishika and Lieutier, André and Stephenson, Elizabeth R and Wintraecken, Mathijs},
  booktitle    = {40th International Symposium on Computational Geometry},
  isbn         = {9783959773164},
  issn         = {1868-8969},
  location     = {Athens, Greece},
  pages        = {11:1--11:19},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and of Riemannian manifolds}},
  doi          = {10.4230/LIPIcs.SoCG.2024.11},
  volume       = {293},
  year         = {2024},
}

@inproceedings{18928,
  abstract     = {Algorithms with predictions is a new research direction that leverages machine learned predictions for algorithm design. So far a plethora of recent works have incorporated predictions to improve on worst-case bounds for online problems. In this paper, we initiate the study of complexity of dynamic data structures with predictions, including dynamic graph algorithms. Unlike online algorithms, the goal in dynamic data structures is to maintain the solution efficiently with every update.
We investigate three natural models of prediction: (1) δ-accurate predictions where each predicted request matches the true request with probability δ, (2) list-accurate predictions where a true request comes from a list of possible requests, and (3) bounded delay predictions where the true requests are a permutation of the predicted requests. We give general reductions among the prediction models, showing that bounded delay is the strongest prediction model, followed by list-accurate, and δ-accurate.
Further, we identify two broad problem classes based on lower bounds due to the Online Matrix Vector (OMv) conjecture. Specifically, we show that locally correctable dynamic problems have strong conditional lower bounds for list-accurate predictions that are equivalent to the non-prediction setting, unless list-accurate predictions are perfect. Moreover, we show that locally reducible dynamic problems have time complexity that degrades gracefully with the quality of bounded delay predictions. We categorize problems with known OMv lower bounds accordingly and give several upper bounds in the delay model that show that our lower bounds are almost tight.
We note that concurrent work by v.d.Brand et al. [SODA '24] and Liu and Srinivas [arXiv:2307.08890] independently study dynamic graph algorithms with predictions, but their work is mostly focused on showing upper bounds.},
  author       = {Henzinger, Monika H and Saha, Barna and Seybold, Martin P. and Ye, Christopher},
  booktitle    = {15th Innovations in Theoretical Computer Science Conference},
  isbn         = {9783959773096},
  issn         = {1868-8969},
  location     = {Berkeley, CA, United States},
  pages        = {62:1--62:25},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{On the complexity of algorithms with predictions for dynamic graph problems}},
  doi          = {10.4230/LIPIcs.ITCS.2024.62},
  volume       = {287},
  year         = {2024},
}

@inproceedings{15168,
  abstract     = {A linearly ordered (LO) k-colouring of a hypergraph is a colouring of its vertices with colours 1, … , k such that each edge contains a unique maximal colour. Deciding whether an input hypergraph admits LO k-colouring with a fixed number of colours is NP-complete (and in the special case of graphs, LO colouring coincides with the usual graph colouring). Here, we investigate the complexity of approximating the "linearly ordered chromatic number" of a hypergraph. We prove that the following promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between the case that it is LO 3-colourable, and the case that it is not even LO 4-colourable. We prove this result by a combination of algebraic, topological, and combinatorial methods, building on and extending a topological approach for studying approximate graph colouring introduced by Krokhin, Opršal, Wrochna, and Živný (2023).},
  author       = {Filakovský, Marek and Nakajima, Tamio Vesa and Opršal, Jakub and Tasinato, Gianluca and Wagner, Uli},
  booktitle    = {41st International Symposium on Theoretical Aspects of Computer Science},
  isbn         = {9783959773119},
  issn         = {1868-8969},
  location     = {Clermont-Ferrand, France},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs}},
  doi          = {10.4230/LIPIcs.STACS.2024.34},
  volume       = {289},
  year         = {2024},
}

@inproceedings{13292,
  abstract     = {The operator precedence languages (OPLs) represent the largest known subclass of the context-free languages which enjoys all desirable closure and decidability properties. This includes the decidability of language inclusion, which is the ultimate verification problem. Operator precedence grammars, automata, and logics have been investigated and used, for example, to verify programs with arithmetic expressions and exceptions (both of which are deterministic pushdown but lie outside the scope of the visibly pushdown languages). In this paper, we complete the picture and give, for the first time, an algebraic characterization of the class of OPLs in the form of a syntactic congruence that has finitely many equivalence classes exactly for the operator precedence languages. This is a generalization of the celebrated Myhill-Nerode theorem for the regular languages to OPLs. As one of the consequences, we show that universality and language inclusion for nondeterministic operator precedence automata can be solved by an antichain algorithm. Antichain algorithms avoid determinization and complementation through an explicit subset construction, by leveraging a quasi-order on words, which allows the pruning of the search space for counterexample words without sacrificing completeness. Antichain algorithms can be implemented symbolically, and these implementations are today the best-performing algorithms in practice for the inclusion of finite automata. We give a generic construction of the quasi-order needed for antichain algorithms from a finite syntactic congruence. This yields the first antichain algorithm for OPLs, an algorithm that solves the ExpTime-hard language inclusion problem for OPLs in exponential time.},
  author       = {Henzinger, Thomas A and Kebis, Pavol and Mazzocchi, Nicolas Adrien and Sarac, Naci E},
  booktitle    = {50th International Colloquium on Automata, Languages, and Programming},
  isbn         = {9783959772785},
  issn         = {1868-8969},
  location     = {Paderborn, Germany},
  pages        = {129:1----129:20},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Regular methods for operator precedence languages}},
  doi          = {10.4230/LIPIcs.ICALP.2023.129},
  volume       = {261},
  year         = {2023},
}

@inproceedings{14417,
  abstract     = {Entropic risk (ERisk) is an established risk measure in finance, quantifying risk by an exponential re-weighting of rewards. We study ERisk for the first time in the context of turn-based stochastic games with the total reward objective. This gives rise to an objective function that demands the control of systems in a risk-averse manner. We show that the resulting games are determined and, in particular, admit optimal memoryless deterministic strategies. This contrasts risk measures that previously have been considered in the special case of Markov decision processes and that require randomization and/or memory. We provide several results on the decidability and the computational complexity of the threshold problem, i.e. whether the optimal value of ERisk exceeds a given threshold. In the most general case, the problem is decidable subject to Shanuel’s conjecture. If all inputs are rational, the resulting threshold problem can be solved using algebraic numbers, leading to decidability via a polynomial-time reduction to the existential theory of the reals. Further restrictions on the encoding of the input allow the solution of the threshold problem in NP∩coNP. Finally, an approximation algorithm for the optimal value of ERisk is provided.},
  author       = {Baier, Christel and Chatterjee, Krishnendu and Meggendorfer, Tobias and Piribauer, Jakob},
  booktitle    = {48th International Symposium on Mathematical Foundations of Computer Science},
  isbn         = {9783959772921},
  issn         = {1868-8969},
  location     = {Bordeaux, France},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Entropic risk for turn-based stochastic games}},
  doi          = {10.4230/LIPIcs.MFCS.2023.15},
  volume       = {272},
  year         = {2023},
}

@inproceedings{13221,
  abstract     = {The safety-liveness dichotomy is a fundamental concept in formal languages which plays a key role in verification. Recently, this dichotomy has been lifted to quantitative properties, which are arbitrary functions from infinite words to partially-ordered domains. We look into harnessing the dichotomy for the specific classes of quantitative properties expressed by quantitative automata. These automata contain finitely many states and rational-valued transition weights, and their common value functions Inf, Sup, LimInf, LimSup, LimInfAvg, LimSupAvg, and DSum map infinite words into the totallyordered domain of real numbers. In this automata-theoretic setting, we establish a connection between quantitative safety and topological continuity and provide an alternative characterization of quantitative safety and liveness in terms of their boolean counterparts. For all common value functions, we show how the safety closure of a quantitative automaton can be constructed in PTime, and we provide PSpace-complete checks of whether a given quantitative automaton is safe or live, with the exception of LimInfAvg and LimSupAvg automata, for which the safety check is in ExpSpace. Moreover, for deterministic Sup, LimInf, and LimSup automata, we give PTime decompositions into safe and live automata. These decompositions enable the separation of techniques for safety and liveness verification for quantitative specifications.},
  author       = {Boker, Udi and Henzinger, Thomas A and Mazzocchi, Nicolas Adrien and Sarac, Naci E},
  booktitle    = {34th International Conference on Concurrency Theory},
  isbn         = {9783959772990},
  issn         = {1868-8969},
  location     = {Antwerp, Belgium},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Safety and liveness of quantitative automata}},
  doi          = {10.4230/LIPIcs.CONCUR.2023.17},
  volume       = {279},
  year         = {2023},
}

@inproceedings{13120,
  abstract     = {We formalized general (i.e., type-0) grammars using the Lean 3 proof assistant. We defined basic notions of rewrite rules and of words derived by a grammar, and used grammars to show closure of the class of type-0 languages under four operations: union, reversal, concatenation, and the Kleene star. The literature mostly focuses on Turing machine arguments, which are possibly more difficult to formalize. For the Kleene star, we could not follow the literature and came up with our own grammar-based construction.},
  author       = {Dvorak, Martin and Blanchette, Jasmin},
  booktitle    = {14th International Conference on Interactive Theorem Proving},
  isbn         = {9783959772846},
  issn         = {1868-8969},
  location     = {Bialystok, Poland},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Closure properties of general grammars - formally verified}},
  doi          = {10.4230/LIPIcs.ITP.2023.15},
  volume       = {268},
  year         = {2023},
}

@inproceedings{11808,
  abstract     = {In recent years, significant advances have been made in the design and analysis of fully dynamic algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. Here, we present a quick reference guide to recent engineering and theory results in the area of fully dynamic graph algorithms.},
  author       = {Hanauer, Kathrin and Henzinger, Monika H and Schulz, Christian},
  booktitle    = {1st Symposium on Algorithmic Foundations of Dynamic Networks},
  isbn         = {9783959772242},
  issn         = {1868-8969},
  location     = {Virtual},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Recent advances in fully dynamic graph algorithms}},
  doi          = {10.4230/LIPIcs.SAND.2022.1},
  volume       = {221},
  year         = {2022},
}