Sebastian Wild
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Sebastian Wild has a total of 48 co-authors. Here are the top co-authors by number of shared publications:
- Markus E. Nebel
Universität Bielefeld
16 shared publications - Conrado Martínez
Universitat Politecnica de Catalunya
6 shared publications - Viktor Zamaraev
University of Liverpool UK
4 shared publications Markus E. Nebel
3 shared publicationsRaphael Reitzig
University of Kaiserslautern
3 shared publicationsDavid Durfee
Georgia Institute of Technology
2 shared publications
Latest Publications
- 2 January 2026
- Published by Springer Nature
- p. 270-285
Succinct Preferential-Attachment Graphs
- Open Access
- 1 October 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in TheoretiCS
- Vol. ume 4
Randomized Communication and Implicit Graph Representations
We initiate the focused study of constant-cost randomized communication, with emphasis on its connection to graph representations. We observe that constant-cost randomized communication problems are equivalent to hereditary (i.e. closed under taking induced subgraphs) graph classes which admit constant-size adjacency sketches and probabilistic universal graphs (PUGs), which are randomized versions of the well-studied adjacency labeling schemes and induced-universal graphs. This gives a new perspective on long-standing questions about the existence of these objects, including new methods of constructing adjacency labeling schemes. We ask three main questions about constant-cost communication, or equivalently, constant-size PUGs: (1) Are there any natural, non-trivial problems aside from Equality and k-Hamming Distance which have constant-cost communication? We provide a number of new examples, including deciding whether two vertices have path-distance at most k in a planar graph, and showing that constant-size PUGs are preserved by the Cartesian product operation. (2) What structures of a problem explain the existence or non-existence of a constant-cost protocol? We show that in many cases a Greater-Than subproblem is such a structure. (3) Is the Equality problem complete for constant-cost randomized communication? We show that it is not: there are constant-cost problems which do not reduce to Equality.81 pages. This is the TheoretiCS journal version
- 1 October 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in TheoretiCS
- Vol. ume 4
Open AccessRandomized Communication and Implicit Graph Representations
We initiate the focused study of constant-cost randomized communication, with emphasis on its connection to graph representations. We observe that constant-cost randomized communication problems are equivalent to hereditary (i.e. closed under taking induced subgraphs) graph classes which admit constant-size adjacency sketches and probabilistic universal graphs (PUGs), which are randomized versions of the well-studied adjacency labeling schemes and induced-universal graphs. This gives a new perspective on long-standing questions about the existence of these objects, including new methods of constructing adjacency labeling schemes. We ask three main questions about constant-cost communication, or equivalently, constant-size PUGs: (1) Are there any natural, non-trivial problems aside from Equality and k-Hamming Distance which have constant-cost communication? We provide a number of new examples, including deciding whether two vertices have path-distance at most k in a planar graph, and showing that constant-size PUGs are preserved by the Cartesian product operation. (2) What structures of a problem explain the existence or non-existence of a constant-cost protocol? We show that in many cases a Greater-Than subproblem is such a structure. (3) Is the Equality problem complete for constant-cost randomized communication? We show that it is not: there are constant-cost problems which do not reduce to Equality.81 pages. This is the TheoretiCS journal version
- Open Access
Succinct Preferential Attachment Graphs
Computing over compressed data combines the space saving of data compression with efficient support for queries directly on the compressed representation. Such data structures are widely applied in text indexing and have been successfully generalised to trees. For graphs, support for computing over compressed data remains patchy; typical results in the area of succinct data structures are restricted to a specific class of graphs and use the same, worst-case amount of space for any graph from this class. In this work, we design a data structure whose space usage automatically improves with the compressibility of the graph at hand, while efficiently supporting navigational operations (simulating adjacency-list access). Specifically, we show that the space usage approaches the instance-optimal space when the graph is drawn according to the classic Barabási-Albert model of preferential-attachment graphs. Our data-structure techniques also work for arbitrary graphs, guaranteeing a size asymptotically no larger than an entropy-compressed edge list. A key technical contribution is the careful analysis of the instance-optimal space usage.
Open AccessSuccinct Preferential Attachment Graphs
Computing over compressed data combines the space saving of data compression with efficient support for queries directly on the compressed representation. Such data structures are widely applied in text indexing and have been successfully generalised to trees. For graphs, support for computing over compressed data remains patchy; typical results in the area of succinct data structures are restricted to a specific class of graphs and use the same, worst-case amount of space for any graph from this class. In this work, we design a data structure whose space usage automatically improves with the compressibility of the graph at hand, while efficiently supporting navigational operations (simulating adjacency-list access). Specifically, we show that the space usage approaches the instance-optimal space when the graph is drawn according to the classic Barabási-Albert model of preferential-attachment graphs. Our data-structure techniques also work for arbitrary graphs, guaranteeing a size asymptotically no larger than an entropy-compressed edge list. A key technical contribution is the careful analysis of the instance-optimal space usage.
- Open Access
Randomized Communication and Implicit Graph Representations
We study constant-cost randomized communication problems and relate them to implicit graph representations in structural graph theory. Specifically, constant-cost communication problems correspond to hereditary graph families that admit constant-size adjacency sketches, or equivalently constant-size probabilistic universal graphs (PUGs), and these graph families are a subset of families that admit adjacency labeling schemes of size O(log n), which are the subject of the well-studied implicit graph question (IGQ). We initiate the study of the hereditary graph families that admit constant-size PUGs, with the two (equivalent) goals of (1) understanding randomized constant-cost communication problems, and (2) understanding a probabilistic version of the IGQ. For each family $\mathcal F$ studied in this paper (including the monogenic bipartite families, product graphs, interval and permutation graphs, families of bounded twin-width, and others), it holds that the subfamilies $\mathcal H \subseteq \mathcal F$ admit constant-size PUGs (i.e. adjacency sketches) if and only if they are stable (i.e. they forbid a half-graph as a semi-induced subgraph). The correspondence between communication problems and hereditary graph families allows for a new method of constructing adjacency labeling schemes. By this method, we show that the induced subgraphs of any Cartesian products are positive examples to the IGQ. We prove that this probabilistic construction cannot be derandomized by using an Equality oracle, i.e. the Equality oracle cannot simulate the k-Hamming Distance communication protocol. We also obtain constant-size sketches for deciding $\mathsf{dist}(x, y) \le k$ for vertices $x$, $y$ in any stable graph family with bounded twin-width. This generalizes to constant-size sketches for deciding first-order formulas over the same graphs.Open AccessRandomized Communication and Implicit Graph Representations
We study constant-cost randomized communication problems and relate them to implicit graph representations in structural graph theory. Specifically, constant-cost communication problems correspond to hereditary graph families that admit constant-size adjacency sketches, or equivalently constant-size probabilistic universal graphs (PUGs), and these graph families are a subset of families that admit adjacency labeling schemes of size O(log n), which are the subject of the well-studied implicit graph question (IGQ). We initiate the study of the hereditary graph families that admit constant-size PUGs, with the two (equivalent) goals of (1) understanding randomized constant-cost communication problems, and (2) understanding a probabilistic version of the IGQ. For each family $\mathcal F$ studied in this paper (including the monogenic bipartite families, product graphs, interval and permutation graphs, families of bounded twin-width, and others), it holds that the subfamilies $\mathcal H \subseteq \mathcal F$ admit constant-size PUGs (i.e. adjacency sketches) if and only if they are stable (i.e. they forbid a half-graph as a semi-induced subgraph). The correspondence between communication problems and hereditary graph families allows for a new method of constructing adjacency labeling schemes. By this method, we show that the induced subgraphs of any Cartesian products are positive examples to the IGQ. We prove that this probabilistic construction cannot be derandomized by using an Equality oracle, i.e. the Equality oracle cannot simulate the k-Hamming Distance communication protocol. We also obtain constant-size sketches for deciding $\mathsf{dist}(x, y) \le k$ for vertices $x$, $y$ in any stable graph family with bounded twin-width. This generalizes to constant-size sketches for deciding first-order formulas over the same graphs. - Open Access
- 4 July 2023
- Published by Springer Nature in Research Square
A House Divided: Cooperation, Polarization, and the Power of Reputation
Altruistic cooperation has enabled humans to thrive1. However, the interaction of sentient individuals faces the dilemma of limiting the downsides of personally beneficial, but globally detrimental selfish behavior without causing even more damage through escalating conflicts. The evolution of cooperation has been studied in non-zero sum games, with the Prisoner’s Dilemma, “the E. coli of social psychology”2, providing a fundamental test case. Typically3-12, interactions between individuals may (i) occur repeatedly, (ii) involve groups of individuals, (iii) be subject to evolutionary mechanisms, often based on the study of equilibria for homogeneous settings.13 However, a better understanding of the non-equilibrium dynamics of cooperation in structured environments is crucial for further progress. Here we consider an inhomogeneous, spatial, dynamic setting, in which evolution occurs not necessarily at an equilibrium. We demonstrate how minimal, publicly observable information on previous behavior can be exploited to outperform alternatives, achieving evolutionary performance similar to clandestine, membership-based strategies. We also show how polarization (with a cooperating population disintegrating into competing factions) and tribalism (with cooperation solely based on group membership instead of behavior) can arise, how these phenomena can be overcome with two additional mechanisms, and how cooperation can erode. Our results demonstrate how cooperation, reputation, polarization and tribalism are intricately linked, even in a simple mathematical model in which they arise in absence of complex psychological mechanisms. This provides a fundamental explanation for how robust cooperation may break down when faced with eroding universality of globally recognized values and of local, direct reciprocity; it may also help to prevent behavior-based reputation systems from giving way to emergent polarization and, ultimately, purely membership-based tribalism. We also anticipate that our methods will be of critical importance for the design and implementation of artificial structures based on the interaction of many independent, self-interested virtual agents.
- 4 July 2023
- Published by Springer Nature in Research Square
Open AccessA House Divided: Cooperation, Polarization, and the Power of Reputation
Altruistic cooperation has enabled humans to thrive1. However, the interaction of sentient individuals faces the dilemma of limiting the downsides of personally beneficial, but globally detrimental selfish behavior without causing even more damage through escalating conflicts. The evolution of cooperation has been studied in non-zero sum games, with the Prisoner’s Dilemma, “the E. coli of social psychology”2, providing a fundamental test case. Typically3-12, interactions between individuals may (i) occur repeatedly, (ii) involve groups of individuals, (iii) be subject to evolutionary mechanisms, often based on the study of equilibria for homogeneous settings.13 However, a better understanding of the non-equilibrium dynamics of cooperation in structured environments is crucial for further progress. Here we consider an inhomogeneous, spatial, dynamic setting, in which evolution occurs not necessarily at an equilibrium. We demonstrate how minimal, publicly observable information on previous behavior can be exploited to outperform alternatives, achieving evolutionary performance similar to clandestine, membership-based strategies. We also show how polarization (with a cooperating population disintegrating into competing factions) and tribalism (with cooperation solely based on group membership instead of behavior) can arise, how these phenomena can be overcome with two additional mechanisms, and how cooperation can erode. Our results demonstrate how cooperation, reputation, polarization and tribalism are intricately linked, even in a simple mathematical model in which they arise in absence of complex psychological mechanisms. This provides a fundamental explanation for how robust cooperation may break down when faced with eroding universality of globally recognized values and of local, direct reciprocity; it may also help to prevent behavior-based reputation systems from giving way to emergent polarization and, ultimately, purely membership-based tribalism. We also anticipate that our methods will be of critical importance for the design and implementation of artificial structures based on the interaction of many independent, self-interested virtual agents.
- Open Access
RNA secondary structures: from ab initio prediction to better compression, and back
In this paper, we use the biological domain knowledge incorporated into stochastic models for ab initio RNA secondary-structure prediction to improve the state of the art in joint compression of RNA sequence and structure data (Liu et al., BMC Bioinformatics, 2008). Moreover, we show that, conversely, compression ratio can serve as a cheap and robust proxy for comparing the prediction quality of different stochastic models, which may help guide the search for better RNA structure prediction models. Our results build on expert stochastic context-free grammar models of RNA secondary structures (Dowell & Eddy, BMC Bioinformatics, 2004; Nebel & Scheid, Theory in Biosciences, 2011) combined with different (static and adaptive) models for rule probabilities and arithmetic coding. We provide a prototype implementation and an extensive empirical evaluation, where we illustrate how grammar features and probability models affect compression ratios.
Open AccessRNA secondary structures: from ab initio prediction to better compression, and back
In this paper, we use the biological domain knowledge incorporated into stochastic models for ab initio RNA secondary-structure prediction to improve the state of the art in joint compression of RNA sequence and structure data (Liu et al., BMC Bioinformatics, 2008). Moreover, we show that, conversely, compression ratio can serve as a cheap and robust proxy for comparing the prediction quality of different stochastic models, which may help guide the search for better RNA structure prediction models. Our results build on expert stochastic context-free grammar models of RNA secondary structures (Dowell & Eddy, BMC Bioinformatics, 2004; Nebel & Scheid, Theory in Biosciences, 2011) combined with different (static and adaptive) models for rule probabilities and arithmetic coding. We provide a prototype implementation and an extensive empirical evaluation, where we illustrate how grammar features and probability models affect compression ratios.
- Open Access
- 21 February 2023
- Published by Springer Nature in Mathematical Programming
- Vol. 203 (1-2) , 187-205
A simple and fast linear-time algorithm for divisor methods of apportionment
Proportional apportionment is the problem of assigning seats to states (resp. parties) according to their relative share of the population (resp. votes), a field heavily influenced by the early work of Michel Balinski, not least his influential 1982 book with Peyton Young (Fair representation, 2nd edn. Brookings Institution Press, Washington, D.C., 2001). In this article, we consider the computational cost of divisor methods (also known as highest averages methods), the de-facto standard solution that is used in many countries. We show that a simple linear-time algorithm can exactly simulate all instances of the family of divisor methods of apportionment by reducing the problem to a single call to a selection algorithm. All previously published solutions were iterative methods that either offer no linear-time guarantee in the worst case or require a complex update step that suffers from numerical instability.
- 21 February 2023
- Published by Springer Nature in Mathematical Programming
- Vol. 203 (1-2) , 187-205
Open AccessA simple and fast linear-time algorithm for divisor methods of apportionment
Proportional apportionment is the problem of assigning seats to states (resp. parties) according to their relative share of the population (resp. votes), a field heavily influenced by the early work of Michel Balinski, not least his influential 1982 book with Peyton Young (Fair representation, 2nd edn. Brookings Institution Press, Washington, D.C., 2001). In this article, we consider the computational cost of divisor methods (also known as highest averages methods), the de-facto standard solution that is used in many countries. We show that a simple linear-time algorithm can exactly simulate all instances of the family of divisor methods of apportionment by reducing the problem to a single call to a selection algorithm. All previously published solutions were iterative methods that either offer no linear-time guarantee in the worst case or require a complex update step that suffers from numerical instability.
- Open Access
Multiway Powersort
We present a stable mergesort variant, Multiway Powersort, that exploits existing runs and finds nearly-optimal merging orders for k-way merges with negligible overhead. This builds on Powersort (Munro & Wild, ESA2018), which has recently replaced Timsort's suboptimal merge policy in the CPython reference implementation of Python, as well as in PyPy and further libraries. Multiway Powersort reduces the number of memory transfers, which increasingly determine the cost of internal sorting (as observed with Multiway Quicksort (Kushagra et al., ALENEX 2014; Aum\"uller & Dietzfelbinger, TALG 2016; Wild, PhD thesis 2016) and the inclusion of Dual-Pivot Quicksort in the Java runtime library). We demonstrate that our 4-way Powersort implementation can achieve substantial speedups over standard (2-way) Powersort and other stable sorting methods without compromising the optimally run-adaptive performance of Powersort.
Open AccessMultiway Powersort
We present a stable mergesort variant, Multiway Powersort, that exploits existing runs and finds nearly-optimal merging orders for k-way merges with negligible overhead. This builds on Powersort (Munro & Wild, ESA2018), which has recently replaced Timsort's suboptimal merge policy in the CPython reference implementation of Python, as well as in PyPy and further libraries. Multiway Powersort reduces the number of memory transfers, which increasingly determine the cost of internal sorting (as observed with Multiway Quicksort (Kushagra et al., ALENEX 2014; Aum\"uller & Dietzfelbinger, TALG 2016; Wild, PhD thesis 2016) and the inclusion of Dual-Pivot Quicksort in the Java runtime library). We demonstrate that our 4-way Powersort implementation can achieve substantial speedups over standard (2-way) Powersort and other stable sorting methods without compromising the optimally run-adaptive performance of Powersort.
- Open Access
Succinct Permutation Graphs
We present a succinct data structure for permutation graphs, and their superclass of circular permutation graphs, i.e., data structures using optimal space up to lower order terms. Unlike concurrent work on circle graphs (Acan et al. 2022), our data structure also supports distance and shortest-path queries, as well as adjacency and neighborhood queries, all in optimal time. We present in particular the first succinct exact distance oracle for (circular) permutation graphs. A second succinct data structure also supports degree queries in time independent of the neighborhood's size at the expense of an $O(\log n/\log \log n)$-factor overhead in all running times. Furthermore, we develop a succinct data structure for the class of bipartite permutation graphs. We demonstrate how to run algorithms directly over our succinct representations for several problems on permutation graphs: Clique, Coloring, Independent Set, Hamiltonian Cycle, All-Pair Shortest Paths, and others. Finally, we initiate the study of semi-distributed graph representations; a concept that smoothly interpolates between distributed (labeling schemes) and centralized (standard data structures). We show how to turn some of our data structures into semi-distributed representations by storing only $O(n)$ bits of additional global information, circumventing the lower bound on distance labeling schemes for permutation graphs.Open AccessSuccinct Permutation Graphs
We present a succinct data structure for permutation graphs, and their superclass of circular permutation graphs, i.e., data structures using optimal space up to lower order terms. Unlike concurrent work on circle graphs (Acan et al. 2022), our data structure also supports distance and shortest-path queries, as well as adjacency and neighborhood queries, all in optimal time. We present in particular the first succinct exact distance oracle for (circular) permutation graphs. A second succinct data structure also supports degree queries in time independent of the neighborhood's size at the expense of an $O(\log n/\log \log n)$-factor overhead in all running times. Furthermore, we develop a succinct data structure for the class of bipartite permutation graphs. We demonstrate how to run algorithms directly over our succinct representations for several problems on permutation graphs: Clique, Coloring, Independent Set, Hamiltonian Cycle, All-Pair Shortest Paths, and others. Finally, we initiate the study of semi-distributed graph representations; a concept that smoothly interpolates between distributed (labeling schemes) and centralized (standard data structures). We show how to turn some of our data structures into semi-distributed representations by storing only $O(n)$ bits of additional global information, circumventing the lower bound on distance labeling schemes for permutation graphs. - Open Access
- 24 September 2022
- Published by Springer Nature in Algorithmica
- Vol. 85 (2) , 509-543
Succinct Permutation Graphs
- 24 September 2022
- Published by Springer Nature in Algorithmica
- Vol. 85 (2) , 509-543
Open AccessSuccinct Permutation Graphs