@inproceedings{17327,
  abstract     = {Sequential decision-making in probabilistic environments is a fundamental problem with many applications in AI and economics. In this paper, we present an algorithm for synthesizing sequential decision-making agents that optimize statistical properties such as maximum and average response times. In the general setting of sequential decision-making, the environment is modeled as a random process that generates inputs. The agent responds to each input, aiming to maximize rewards and minimize costs within a specified time horizon. The corresponding synthesis problem is known to be PSPACE-hard. We consider the special case where the input distribution, reward, and cost depend on input-output statistics specified by counter automata. For such problems, this paper presents the first PTIME synthesis algorithms. We introduce the notion of statistical abstraction, which clusters statistically indistinguishable input-output sequences into equivalence classes. This abstraction allows for a dynamic programming algorithm whose complexity grows polynomially with the considered horizon, making the statistical case exponentially more efficient than the general case. We evaluate our algorithm on three different application scenarios of a client-server protocol, where multiple clients compete via bidding to gain access to the service offered by the server. The synthesized policies optimize profit while guaranteeing that none of the server’s clients is disproportionately starved of the service.},
  author       = {Cano, Filip and Henzinger, Thomas A and Könighofer, Bettina and Kueffner, Konstantin and Mallik, Kaushik},
  booktitle    = {9th International Conference on Formal Structures for Computation and Deduction},
  isbn         = {9783959773232},
  issn         = {1868-8969},
  location     = {Tallinn, Estonia},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Abstraction-based decision making for statistical properties}},
  doi          = {10.4230/LIPIcs.FSCD.2024.2},
  volume       = {299},
  year         = {2024},
}

@inproceedings{18066,
  abstract     = {Graph games lie at the algorithmic core of many automated design problems in computer science. These are games usually played between two players on a given graph, where the players keep moving a token along the edges according to pre-determined rules (turn-based, concurrent, etc.), and the winner is decided based on the infinite path (aka play) traversed by the token from a given initial position. In bidding games, the players initially get some monetary budgets which they need to use to bid for the privilege of moving the token at each step. Each round of bidding affects the players' available budgets, which is the only form of update that the budgets experience. We introduce bidding games with charging where the players can additionally improve their budgets during the game by collecting vertex-dependent monetary rewards, aka the "charges." Unlike traditional bidding games (where all charges are zero), bidding games with charging allow non-trivial recurrent behaviors. For example, a reachability objective may require multiple detours to vertices with high charges to earn additional budget. We show that, nonetheless, the central property of traditional bidding games generalizes to bidding games with charging: For each vertex there exists a threshold ratio, which is the necessary and sufficient fraction of the total budget for winning the game from that vertex. While the thresholds of traditional bidding games correspond to unique fixed points of linear systems of equations, in games with charging, these fixed points are no longer unique. This significantly complicates the proof of existence and the algorithmic computation of thresholds for infinite-duration objectives. We also provide the lower complexity bounds for computing thresholds for Rabin and Streett objectives, which are the first known lower bounds in any form of bidding games (with or without charging), and we solve the following repair problem for safety and reachability games that have unsatisfiable objectives: Can we distribute a given amount of charge to the players in a way such that the objective can be satisfied?},
  author       = {Avni, Guy and Goharshady, Ehsan Kafshdar and Henzinger, Thomas A and Mallik, Kaushik},
  booktitle    = {35th International Conference on Concurrency Theory},
  isbn         = {9783959773393},
  issn         = {1868-8969},
  location     = {Calgary, Canada},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Bidding games with charging}},
  doi          = {10.4230/LIPIcs.CONCUR.2024.8},
  volume       = {311},
  year         = {2024},
}

@inproceedings{18067,
  abstract     = {An automaton 𝒜 is history-deterministic if its nondeterminism can be resolved on the fly, only using the prefix of the word read so far. This mild form of nondeterminism has attracted particular attention for its applications in synthesis problems. An automaton 𝒜 is guidable with respect to a class C of automata if it can fairly simulate every automaton in C, whose language is contained in that of 𝒜. In other words, guidable automata are those for which inclusion and simulation coincide, making them particularly interesting for model-checking. We study the connection between these two notions, and specifically the question of when they coincide. For classes of automata on which they do, deciding guidability, an otherwise challenging decision problem, reduces to deciding history-determinism, a problem that is starting to be well-understood for many classes. We provide a selection of sufficient criteria for a class of automata to guarantee the coincidence of the notions, and use them to show that the notions coincide for the most common automata classes, among which are ω-regular automata and many infinite-state automata with safety and reachability acceptance conditions, including vector addition systems with states, one-counter nets, pushdown-, Parikh-, and timed-automata. We also demonstrate that history-determinism and guidability do not always coincide, for example, for the classes of timed automata with a fixed number of clocks.},
  author       = {Boker, Udi and Henzinger, Thomas A and Lehtinen, Karoliina and Prakash, Aditya},
  booktitle    = {35th International Conference on Concurrency Theory},
  isbn         = {9783959773393},
  issn         = {1868-8969},
  location     = {Calgary, Canada},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{History-determinism vs fair simulation}},
  doi          = {10.4230/LIPIcs.CONCUR.2024.12},
  volume       = {311},
  year         = {2024},
}

@inproceedings{18068,
  abstract     = {We study the following refinement relation between nondeterministic state-transition models: model ℬ strategically dominates model 𝒜 iff every deterministic refinement of 𝒜 is language contained in some deterministic refinement of ℬ. While language containment is trace inclusion, and the (fair) simulation preorder coincides with tree inclusion, strategic dominance falls strictly between the two and can be characterized as "strategy inclusion" between 𝒜 and ℬ: every strategy that resolves the nondeterminism of 𝒜 is dominated by a strategy that resolves the nondeterminism of ℬ. Strategic dominance can be checked in 2-ExpTime by a decidable first-order Presburger logic with quantification over words and strategies, called resolver logic. We give several other applications of resolver logic, including checking the co-safety, co-liveness, and history-determinism of boolean and quantitative automata, and checking the inclusion between hyperproperties that are specified by nondeterministic boolean and quantitative automata.},
  author       = {Henzinger, Thomas A and Mazzocchi, Nicolas Adrien and Sarac, Naci E},
  booktitle    = {35th International Conference on Concurrency Theory},
  isbn         = {9783959773393},
  issn         = {1868-8969},
  location     = {Calgary, Canada},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Strategic dominance: A new preorder for nondeterministic processes}},
  doi          = {10.4230/LIPIcs.CONCUR.2024.29},
  volume       = {311},
  year         = {2024},
}

@inproceedings{18156,
  abstract     = {Privately counting distinct elements in a stream is a fundamental data analysis problem with many applications in machine learning. In the turnstile model, Jain et al. [NeurIPS2023] initiated the study of this problem parameterized by the maximum flippancy of any element, i.e., the number of times that the count of an element changes from 0 to above 0 or vice versa. They give an item-level (ε,δ)-differentially private algorithm whose additive error is tight with respect to that parameterization. In this work, we show that a very simple algorithm based on the sparse vector technique achieves a tight additive error for item-level (ε,δ)-differential privacy and item-level ε-differential privacy with regards to a different parameterization, namely the sum of all flippancies. Our second result is a bound which shows that for a large class of algorithms, including all existing differentially private algorithms for this problem, the lower bound from item-level differential privacy extends to event-level differential privacy. This partially answers an open question by Jain et al. [NeurIPS2023].},
  author       = {Henzinger, Monika H and Sricharan, A. R. and Steiner, Teresa Anna},
  booktitle    = {International Conference on Approximation Algorithms for Combinatorial Optimization Problems },
  isbn         = {9783959773485},
  issn         = {1868-8969},
  location     = {London, United Kingdom},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Private counting of distinct elements in the turnstile model and extensions}},
  doi          = {10.4230/LIPIcs.APPROX/RANDOM.2024.40},
  volume       = {317},
  year         = {2024},
}

@inproceedings{18175,
  abstract     = {Large-scale software repositories are a source of insights for software engineering. They offer an unmatched window into the software development process at scale. Their sheer number and size holds the promise of broadly applicable results. At the same time, that very size presents practical challenges for scaling tools and algorithms to millions of projects. A reasonable approach is to limit studies to representative samples of the population of interest. Broadly applicable conclusions can then be obtained by generalizing to the entire population. The contribution of this paper is a standardized experimental design methodology for choosing the inputs of studies working with large-scale repositories. We advocate for a methodology that clearly lays out what the population of interest is, how to sample it, and that fosters reproducibility. Along the way, we discourage researchers from using extrinsic attributes of projects such as stars, that measure some unclear notion of popularity.},
  author       = {Maj, Petr and Muroya Lei, Stefanie and Siek, Konrad and Di Grazia, Luca and Vitek, Jan},
  booktitle    = {38th European Conference on Object-Oriented Programming},
  isbn         = {9783959773416},
  issn         = {1868-8969},
  location     = {Vienna, Austria},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{The fault in our stars: Designing reproducible large-scale code analysis experiments}},
  doi          = {10.4230/LIPIcs.ECOOP.2024.27},
  volume       = {313},
  year         = {2024},
}

@inproceedings{18308,
  abstract     = {We study in this paper the problem of maintaining a solution to k-median and k-means clustering in a fully dynamic setting. To do so, we present an algorithm to efficiently maintain a coreset, a compressed version of the dataset, that allows easy computation of a clustering solution at query time. Our coreset algorithm has near-optimal update time of Õ(k) in general metric spaces, which reduces to Õ(d) in the Euclidean space ℝ^d. The query time is O(k²) in general metrics, and O(kd) in ℝ^d. To maintain a constant-factor approximation for k-median and k-means clustering in Euclidean space, this directly leads to an algorithm with update time Õ(d), and query time Õ(kd + k²). To maintain a O(polylog k)-approximation, the query time is reduced to Õ(kd).},
  author       = {La Tour, Max Dupré and Henzinger, Monika H and Saulpic, David},
  booktitle    = {32nd Annual European Symposium on Algorithms},
  isbn         = {9783959773386},
  issn         = {1868-8969},
  location     = {London, United Kingdom},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Fully dynamic k-means coreset in near-optimal update time}},
  doi          = {10.4230/LIPIcs.ESA.2024.100},
  volume       = {308},
  year         = {2024},
}

@inproceedings{18309,
  abstract     = {The problem of designing connectivity oracles supporting vertex failures is one of the basic data structures problems for undirected graphs. It is already well understood: previous works [Duan-Pettie STOC'10; Long-Saranurak FOCS'22] achieve query time linear in the number of failed vertices, and it is conditionally optimal as long as we require preprocessing time polynomial in the size of the graph and update time polynomial in the number of failed vertices. We revisit this problem in the paradigm of algorithms with predictions: we ask if the query time can be improved if the set of failed vertices can be predicted beforehand up to a small number of errors. More specifically, we design a data structure that, given a graph G = (V,E) and a set of vertices predicted to fail D̂ ⊆ V of size d = |D̂|, preprocesses it in time Õ(d|E|) and then can receive an update given as the symmetric difference between the predicted and the actual set of failed vertices D̂△D = (D̂ ⧵ D) ∪ (D ⧵ D̂) of size η = |D̂△D|, process it in time Õ(η⁴), and after that answer connectivity queries in G ⧵ D in time O(η). Viewed from another perspective, our data structure provides an improvement over the state of the art for the fully dynamic subgraph connectivity problem in the sensitivity setting [Henzinger-Neumann ESA'16]. We argue that the preprocessing time and query time of our data structure are conditionally optimal under standard fine-grained complexity assumptions.},
  author       = {Hu, Bingbing and Kosinas, Evangelos and Polak, Adam},
  booktitle    = {32nd Annual European Symposium on Algorithms},
  isbn         = {9783959773386},
  issn         = {1868-8969},
  location     = {London, United Kingdom},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Connectivity oracles for predictable vertex failures}},
  doi          = {10.4230/LIPIcs.ESA.2024.72},
  volume       = {308},
  year         = {2024},
}

@inproceedings{18557,
  abstract     = {Broadcast and Consensus are most fundamental tasks in distributed computing. These tasks are particularly challenging in dynamic networks where communication across the network links may be unreliable, e.g., due to mobility or failures. Over the last years, researchers have derived several impossibility results and high time complexity lower bounds for these tasks. Specifically for the setting where in each round of communication the adversary is allowed to choose one rooted tree along which the information is disseminated, there is a lower as well as an upper bound that is linear in the number n of nodes for Broadcast and for n ≥ 3 the adversary can guarantee that Consensus never happens. This setting is called the oblivious message adversary for rooted trees. Also note that if the adversary is allowed to choose a graph that does not contain a rooted tree, then it can guarantee that Broadcast and Consensus will never happen. However, such deterministic adversarial models may be overly pessimistic, as many processes in real-world settings are stochastic in nature rather than worst-case. This paper studies Broadcast on stochastic dynamic networks and shows that the situation is very different to the deterministic case. In particular, we show that if information dissemination occurs along random rooted trees and directed Erdős–Rényi graphs, Broadcast completes in O(log n) rounds of communication with high probability. The fundamental insight in our analysis is that key variables are mutually independent. We then study two adversarial models, (a) one with Byzantine nodes and (b) one where an adversary controls the edges. (a) Our techniques without Byzantine nodes are general enough so that they can be extended to Byzantine nodes. (b) In the spirit of smoothed analysis, we introduce the notion of randomized oblivious message adversary, where in each round, an adversary picks k ≤ 2n/3 edges to appear in the communication network, and then a graph (e.g. rooted tree or directed Erdős–Rényi graph) is chosen uniformly at random among the set of all such graphs that include these edges. We show that Broadcast completes in a finite number of rounds, which is, e.g., O(k+log n) rounds in rooted trees. We then extend these results to All-to-All Broadcast, and Consensus, and give lower bounds that show that most of our upper bounds are tight.},
  author       = {El-Hayek, Antoine and Henzinger, Monika H and Schmid, Stefan},
  booktitle    = {38th International Symposium on Distributed Computing},
  isbn         = {9783959773522},
  issn         = {1868-8969},
  location     = {Madrid, Spain},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges}},
  doi          = {10.4230/LIPIcs.DISC.2024.21},
  volume       = {319},
  year         = {2024},
}

@inproceedings{12760,
  abstract     = {Dynamic programming (DP) is one of the fundamental paradigms in algorithm design. However,
many DP algorithms have to fill in large DP tables, represented by two-dimensional arrays, which causes at least quadratic running times and space usages. This has led to the development of improved algorithms for special cases when the DPs satisfy additional properties like, e.g., the Monge property or total monotonicity.
In this paper, we consider a new condition which assumes (among some other technical assumptions) that the rows of the DP table are monotone. Under this assumption, we introduce
a novel data structure for computing (1 + ϵ)-approximate DP solutions in near-linear time and
space in the static setting, and with polylogarithmic update times when the DP entries change
dynamically. To the best of our knowledge, our new condition is incomparable to previous conditions and is the first which allows to derive dynamic algorithms based on existing DPs. Instead of using two-dimensional arrays to store the DP tables, we store the rows of the DP tables using monotone piecewise constant functions. This allows us to store length-n DP table rows with entries in [0, W] using only polylog(n, W) bits, and to perform operations, such as (min, +)-convolution or rounding, on these functions in polylogarithmic time.
We further present several applications of our data structure. For bicriteria versions of k-balanced graph partitioning and simultaneous source location, we obtain the first dynamic algorithms with subpolynomial update times, as well as the first static algorithms using only near-linear time and space. Additionally, we obtain the currently fastest algorithm for fully dynamic knapsack.},
  author       = {Henzinger, Monika H and Neumann, Stefan and Räcke, Harald and Schmid, Stefan},
  booktitle    = {40th International Symposium on Theoretical Aspects of Computer Science},
  isbn         = {9783959772662},
  issn         = {1868-8969},
  location     = {Hamburg, Germany},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Dynamic maintenance of monotone dynamic programs and applications}},
  doi          = {10.4230/LIPIcs.STACS.2023.36},
  volume       = {254},
  year         = {2023},
}

@inproceedings{14083,
  abstract     = {In this work we consider the list-decodability and list-recoverability of arbitrary q-ary codes, for all integer values of q ≥ 2. A code is called (p,L)_q-list-decodable if every radius pn Hamming ball contains less than L codewords; (p,𝓁,L)_q-list-recoverability is a generalization where we place radius pn Hamming balls on every point of a combinatorial rectangle with side length 𝓁 and again stipulate that there be less than L codewords.
Our main contribution is to precisely calculate the maximum value of p for which there exist infinite families of positive rate (p,𝓁,L)_q-list-recoverable codes, the quantity we call the zero-rate threshold. Denoting this value by p_*, we in fact show that codes correcting a p_*+ε fraction of errors must have size O_ε(1), i.e., independent of n. Such a result is typically referred to as a "Plotkin bound." To complement this, a standard random code with expurgation construction shows that there exist positive rate codes correcting a p_*-ε fraction of errors. We also follow a classical proof template (typically attributed to Elias and Bassalygo) to derive from the zero-rate threshold other tradeoffs between rate and decoding radius for list-decoding and list-recovery.
Technically, proving the Plotkin bound boils down to demonstrating the Schur convexity of a certain function defined on the q-simplex as well as the convexity of a univariate function derived from it. We remark that an earlier argument claimed similar results for q-ary list-decoding; however, we point out that this earlier proof is flawed.},
  author       = {Resch, Nicolas and Yuan, Chen and Zhang, Yihan},
  booktitle    = {50th International Colloquium on Automata, Languages, and Programming},
  isbn         = {9783959772785},
  issn         = {1868-8969},
  location     = {Paderborn, Germany},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery}},
  doi          = {10.4230/LIPIcs.ICALP.2023.99},
  volume       = {261},
  year         = {2023},
}

@inproceedings{14084,
  abstract     = {A central problem in computational statistics is to convert a procedure for sampling combinatorial objects into a procedure for counting those objects, and vice versa. We will consider sampling problems which come from Gibbs distributions, which are families of probability distributions over a discrete space Ω with probability mass function of the form μ^Ω_β(ω) ∝ e^{β H(ω)} for β in an interval [β_min, β_max] and H(ω) ∈ {0} ∪ [1, n].
The partition function is the normalization factor Z(β) = ∑_{ω ∈ Ω} e^{β H(ω)}, and the log partition ratio is defined as q = (log Z(β_max))/Z(β_min)
We develop a number of algorithms to estimate the counts c_x using roughly Õ(q/ε²) samples for general Gibbs distributions and Õ(n²/ε²) samples for integer-valued distributions (ignoring some second-order terms and parameters), We show this is optimal up to logarithmic factors. We illustrate with improved algorithms for counting connected subgraphs and perfect matchings in a graph.},
  author       = {Harris, David G. and Kolmogorov, Vladimir},
  booktitle    = {50th International Colloquium on Automata, Languages, and Programming},
  isbn         = {9783959772785},
  issn         = {1868-8969},
  location     = {Paderborn, Germany},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Parameter estimation for Gibbs distributions}},
  doi          = {10.4230/LIPIcs.ICALP.2023.72},
  volume       = {261},
  year         = {2023},
}

@inproceedings{14085,
  abstract     = {We show an (1+ϵ)-approximation algorithm for maintaining maximum s-t flow under m edge insertions in m1/2+o(1)ϵ−1/2 amortized update time for directed, unweighted graphs. This constitutes the first sublinear dynamic maximum flow algorithm in general sparse graphs with arbitrarily good approximation guarantee.},
  author       = {Goranci, Gramoz and Henzinger, Monika H},
  booktitle    = {50th International Colloquium on Automata, Languages, and Programming},
  isbn         = {9783959772785},
  issn         = {1868-8969},
  location     = {Paderborn, Germany},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Efficient data structures for incremental exact and approximate maximum flow}},
  doi          = {10.4230/LIPIcs.ICALP.2023.69},
  volume       = {261},
  year         = {2023},
}

@inproceedings{14086,
  abstract     = {The maximization of submodular functions have found widespread application in areas such as machine learning, combinatorial optimization, and economics, where practitioners often wish to enforce various constraints; the matroid constraint has been investigated extensively due to its algorithmic properties and expressive power. Though tight approximation algorithms for general matroid constraints exist in theory, the running times of such algorithms typically scale quadratically, and are not practical for truly large scale settings. Recent progress has focused on fast algorithms for important classes of matroids given in explicit form. Currently, nearly-linear time algorithms only exist for graphic and partition matroids [Alina Ene and Huy L. Nguyen, 2019]. In this work, we develop algorithms for monotone submodular maximization constrained by graphic, transversal matroids, or laminar matroids in time near-linear in the size of their representation. Our algorithms achieve an optimal approximation of 1-1/e-ε and both generalize and accelerate the results of Ene and Nguyen [Alina Ene and Huy L. Nguyen, 2019]. In fact, the running time of our algorithm cannot be improved within the fast continuous greedy framework of Badanidiyuru and Vondrák [Ashwinkumar Badanidiyuru and Jan Vondrák, 2014].
To achieve near-linear running time, we make use of dynamic data structures that maintain bases with approximate maximum cardinality and weight under certain element updates. These data structures need to support a weight decrease operation and a novel Freeze operation that allows the algorithm to freeze elements (i.e. force to be contained) in its basis regardless of future data structure operations. For the laminar matroid, we present a new dynamic data structure using the top tree interface of Alstrup, Holm, de Lichtenberg, and Thorup [Stephen Alstrup et al., 2005] that maintains the maximum weight basis under insertions and deletions of elements in O(log n) time. This data structure needs to support certain subtree query and path update operations that are performed every insertion and deletion that are non-trivial to handle in conjunction. For the transversal matroid the Freeze operation corresponds to requiring the data structure to keep a certain set S of vertices matched, a property that we call S-stability. While there is a large body of work on dynamic matching algorithms, none are S-stable and maintain an approximate maximum weight matching under vertex updates. We give the first such algorithm for bipartite graphs with total running time linear (up to log factors) in the number of edges.},
  author       = {Henzinger, Monika H and Liu, Paul and Vondrák, Jan and Zheng, Da Wei},
  booktitle    = {50th International Colloquium on Automata, Languages, and Programming},
  isbn         = {9783959772785},
  issn         = {1868-8969},
  location     = {Paderborn, Germany},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Faster submodular maximization for several classes of matroids}},
  doi          = {10.4230/LIPIcs.ICALP.2023.74},
  volume       = {261},
  year         = {2023},
}

@inproceedings{14405,
  abstract     = {We introduce hypernode automata as a new specification formalism for hyperproperties of concurrent systems. They are finite automata with nodes labeled with hypernode logic formulas and transitions labeled with actions. A hypernode logic formula specifies relations between sequences of variable values in different system executions. Unlike HyperLTL, hypernode logic takes an asynchronous view on execution traces by constraining the values and the order of value changes of each variable without correlating the timing of the changes. Different execution traces are synchronized solely through the transitions of hypernode automata. Hypernode automata naturally combine asynchronicity at the node level with synchronicity at the transition level. We show that the model-checking problem for hypernode automata is decidable over action-labeled Kripke structures, whose actions induce transitions of the specification automata. For this reason, hypernode automaton is a suitable formalism for specifying and verifying asynchronous hyperproperties, such as declassifying observational determinism in multi-threaded programs.},
  author       = {Bartocci, Ezio and Henzinger, Thomas A and Nickovic, Dejan and Oliveira da Costa, Ana},
  booktitle    = {34th International Conference on Concurrency Theory},
  isbn         = {9783959772990},
  issn         = {1868-8969},
  location     = {Antwerp, Belgium},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Hypernode automata}},
  doi          = {10.4230/LIPIcs.CONCUR.2023.21},
  volume       = {279},
  year         = {2023},
}

@inproceedings{14485,
  abstract     = {Batching is a technique that stores multiple keys/values in each node of a data structure. In sequential search data structures, batching reduces latency by reducing the number of cache misses and shortening the chain of pointers to dereference. Applying batching to concurrent data structures is challenging, because it is difficult to maintain the search property and keep contention low in the presence of batching.
In this paper, we present a general methodology for leveraging batching in concurrent search data structures, called BatchBoost. BatchBoost builds a search data structure from distinct "data" and "index" layers. The data layer’s purpose is to store a batch of key/value pairs in each of its nodes. The index layer uses an unmodified concurrent search data structure to route operations to a position in the data layer that is "close" to where the corresponding key should exist. The requirements on the index and data layers are low: with minimal effort, we were able to compose three highly scalable concurrent search data structures based on three original data structures as the index layers with a batched version of the Lazy List as the data layer. The resulting BatchBoost data structures provide significant performance improvements over their original counterparts.},
  author       = {Aksenov, Vitaly and Anoprenko, Michael and Fedorov, Alexander and Spear, Michael},
  booktitle    = {37th International Symposium on Distributed Computing},
  isbn         = {9783959773010},
  issn         = {1868-8969},
  location     = {L'Aquila, Italy},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Brief announcement: BatchBoost: Universal batching for concurrent data structures}},
  doi          = {10.4230/LIPIcs.DISC.2023.35},
  volume       = {281},
  year         = {2023},
}

@inproceedings{14516,
  abstract     = {We revisit decentralized random beacons with a focus on practical distributed applications. Decentralized random beacons (Beaver and So, Eurocrypt'93) provide the functionality for n parties to generate an unpredictable sequence of bits in a way that cannot be biased, which is useful for any decentralized protocol requiring trusted randomness. Existing beacon constructions are highly inefficient in practical settings where protocol parties need to rejoin after crashes or disconnections, and more significantly where smart contracts may rely on arbitrary index points in high-volume streams. For this, we introduce a new notion of history-generating decentralized random beacons (HGDRBs). Roughly, the history-generation property of HGDRBs allows for previous beacon outputs to be efficiently generated knowing only the current value and the public key. At application layers, history-generation supports registering a sparser set of on-chain values if desired, so that apps like lotteries can utilize on-chain values without incurring high-frequency costs, enjoying all the benefits of DRBs implemented off-chain or with decoupled, special-purpose chains. Unlike rollups, HG is tailored specifically to recovering and verifying pseudorandom bit sequences and thus enjoys unique optimizations investigated in this work. We introduce STROBE: an efficient HGDRB construction which generalizes the original squaring-based RSA approach of Beaver and So. STROBE enjoys several useful properties that make it suited for practical applications that use beacons: 1) history-generating: it can regenerate and verify high-throughput beacon streams, supporting sparse (thus cost-effective) ledger entries; 2) concisely self-verifying: NIZK-free, with state and validation employing a single ring element; 3) eco-friendly: stake-based rather than work based; 4) unbounded: refresh-free, addressing limitations of Beaver and So; 5) delay-free: results are immediately available. 6) storage-efficient: the last beacon suffices to derive all past outputs, thus O(1) storage requirements for nodes serving the whole history.},
  author       = {Beaver, Donald and Kelkar, Mahimna and Lewi, Kevin and Nikolaenko, Valeria and Sonnino, Alberto and Chalkias, Konstantinos and Kokoris Kogias, Eleftherios and Naurois, Ladi De and Roy, Arnab},
  booktitle    = {5th Conference on Advances in Financial Technologies},
  isbn         = {9783959773034},
  issn         = {1868-8969},
  location     = {Princeton, NJ, United States},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{STROBE: Streaming Threshold Random Beacons}},
  doi          = {10.4230/LIPIcs.AFT.2023.7},
  volume       = {282},
  year         = {2023},
}

@inproceedings{22373,
  abstract     = {Data dissemination is a fundamental task in distributed computing. This paper studies broadcast problems in various innovative models where the communication network connecting n processes is dynamic (e.g., due to mobility or failures) and controlled by an adversary. 
In the first model, the processes transitively communicate their ids in synchronous rounds along a rooted tree given in each round by the adversary whose goal is to maximize the number of rounds until at least one id is known by all processes. Previous research has shown a ⌈(3n-1)/2⌉-2 lower bound and an O(nlog log n) upper bound. We show the first linear upper bound for this problem, namely ⌈(1+√2) n-1⌉ ≈ 2.4n.
We extend these results to the setting where the adversary gives in each round k-disjoint forests and their goal is to maximize the number of rounds until there is a set of k ids such that each process knows of at least one of them. We give a ⌈3(n-k)/2⌉-1 lower bound and a (π²+6)/6 n+1 ≈ 2.6n upper bound for this problem.
Finally, we study the setting where the adversary gives in each round a directed graph with k roots and their goal is to maximize the number of rounds until there exist k ids that are known by all processes. We give a ⌈3(n-3k)/2⌉+2 lower bound and a ⌈(1+√2)n⌉+k-1 ≈ 2.4n+k upper bound for this problem.
For the two latter problems no upper or lower bounds were previously known.},
  author       = {El-Hayek, Antoine and Henzinger, Monika H and Schmid, Stefan},
  booktitle    = {14th Innovations in Theoretical Computer Science Conference},
  editor       = {Tauman Kalai, Yael},
  isbn         = {9783959772631},
  issn         = {1868-8969},
  keywords     = {broadcast, cover, k-broadcast, dynamic radius, dynamic graphs, oblivious message adversary, time complexity, Theory of computation → Distributed algorithms, Networks → Network algorithms},
  location     = {Cambridge, Massachusetts, USA},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks}},
  doi          = {10.4230/LIPICS.ITCS.2023.47},
  volume       = {251},
  year         = {2023},
}

@inproceedings{11183,
  abstract     = {Subgraph detection has recently been one of the most studied problems in the CONGEST model of distributed computing. In this work, we study the distributed complexity of problems closely related to subgraph detection, mainly focusing on induced subgraph detection. The main line of this work presents lower bounds and parameterized algorithms w.r.t structural parameters of the input graph:
- On general graphs, we give unconditional lower bounds for induced detection of cycles and patterns of treewidth 2 in CONGEST. Moreover, by adapting reductions from centralized parameterized complexity, we prove lower bounds in CONGEST for detecting patterns with a 4-clique, and for induced path detection conditional on the hardness of triangle detection in the congested clique.
- On graphs of bounded degeneracy, we show that induced paths can be detected fast in CONGEST using techniques from parameterized algorithms, while detecting cycles and patterns of treewidth 2 is hard.
- On graphs of bounded vertex cover number, we show that induced subgraph detection is easy in CONGEST for any pattern graph. More specifically, we adapt a centralized parameterized algorithm for a more general maximum common induced subgraph detection problem to the distributed setting. In addition to these induced subgraph detection results, we study various related problems in the CONGEST and congested clique models, including for multicolored versions of subgraph-detection-like problems.},
  author       = {Nikabadi, Amir and Korhonen, Janne},
  booktitle    = {25th International Conference on Principles of Distributed Systems},
  editor       = {Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  isbn         = {9783959772198},
  issn         = {1868-8969},
  location     = {Strasbourg, France},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters}},
  doi          = {10.4230/LIPIcs.OPODIS.2021.15},
  volume       = {217},
  year         = {2022},
}

@inproceedings{11184,
  abstract     = {Let G be a graph on n nodes. In the stochastic population protocol model, a collection of n indistinguishable, resource-limited nodes collectively solve tasks via pairwise interactions. In each interaction, two randomly chosen neighbors first read each other’s states, and then update their local states. A rich line of research has established tight upper and lower bounds on the complexity of fundamental tasks, such as majority and leader election, in this model, when G is a clique. Specifically, in the clique, these tasks can be solved fast, i.e., in n polylog n pairwise interactions, with high probability, using at most polylog n states per node.
In this work, we consider the more general setting where G is an arbitrary regular graph, and present a technique for simulating protocols designed for fully-connected networks in any connected regular graph. Our main result is a simulation that is efficient on many interesting graph families: roughly, the simulation overhead is polylogarithmic in the number of nodes, and quadratic in the conductance of the graph. As a sample application, we show that, in any regular graph with conductance φ, both leader election and exact majority can be solved in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability, using at most φ^{-2} ⋅ polylog n states per node. This shows that there are fast and space-efficient population protocols for leader election and exact majority on graphs with good expansion properties. We believe our results will prove generally useful, as they allow efficient technology transfer between the well-mixed (clique) case, and the under-explored spatial setting.},
  author       = {Alistarh, Dan-Adrian and Gelashvili, Rati and Rybicki, Joel},
  booktitle    = {25th International Conference on Principles of Distributed Systems},
  editor       = {Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  isbn         = {9783959772198},
  issn         = {1868-8969},
  location     = {Strasbourg, France},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Fast graphical population protocols}},
  doi          = {10.4230/LIPIcs.OPODIS.2021.14},
  volume       = {217},
  year         = {2022},
}