41 Search Results for "Nelson, Jelani"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.40
A Simple and Robust Protocol for Distributed Counting

Authors: Edith Cohen, Moshe Shechner, and Uri Stemmer

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We revisit the distributed counting problem, where a server must continuously approximate the total number of events occurring across k sites while minimizing communication. The communication complexity of this problem is known to be Θ(k/(ε)log N) for deterministic protocols. Huang, Yi, and Zhang (2012) showed that randomization can reduce this to Θ((√k)/ε log N), but their analysis is restricted to the oblivious setting, where the stream of events is independent of the protocol’s outputs. Xiong, Zhu, and Huang (2023) presented a robust protocol for distributed counting that removes the oblivious assumption. However, their communication complexity is suboptimal by a polylog(k) factor and their protocol is substantially more complex than the oblivious protocol of Huang et al. (2012). This left open a natural question: could it be that the simple protocol of Huang et al. (2012) is already robust? We resolve this question with two main contributions. First, we show that the protocol of Huang et al. (2012) is itself not robust by constructing an explicit adaptive attack that forces it to lose its accuracy. Second, we present a new, surprisingly simple, robust protocol for distributed counting that achieves the optimal communication complexity of O((√k)/ε log N). Our protocol is simpler than that of Xiong et al. (2023), perhaps even simpler than that of Huang et al. (2012), and is the first to match the optimal oblivious complexity in the adaptive setting.
Cite as

Edith Cohen, Moshe Shechner, and Uri Stemmer. A Simple and Robust Protocol for Distributed Counting. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 40:1-40:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ITCS.2026.40,
  author =	{Cohen, Edith and Shechner, Moshe and Stemmer, Uri},
  title =	{{A Simple and Robust Protocol for Distributed Counting}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{40:1--40:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.40},
  URN =		{urn:nbn:de:0030-drops-253272},
  doi =		{10.4230/LIPIcs.ITCS.2026.40},
  annote =	{Keywords: Distributed Streaming, Adversarial Streaming}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.82
Dimension Reduction for Clustering: The Curious Case of Discrete Centers

Authors: Shaofeng H.-C. Jiang, Robert Krauthgamer, Shay Sapir, Sandeep Silwal, and Di Yue

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
The Johnson-Lindenstrauss transform is a fundamental method for dimension reduction in Euclidean spaces, that can map any dataset of n points into dimension O(log n) with low distortion of their distances. This dimension bound is tight in general, but one can bypass it for specific problems. Indeed, tremendous progress has been made for clustering problems, especially in the continuous setting where centers can be picked from the ambient space ℝ^d. Most notably, for k-median and k-means, the dimension bound was improved to O(log k) [Makarychev, Makarychev and Razenshteyn, STOC 2019]. We explore dimension reduction for clustering in the discrete setting, where centers can only be picked from the dataset, and present two results that are both parameterized by the doubling dimension of the dataset, denoted as ddim. The first result shows that dimension O_{ε}(ddim + log k + log log n) suffices, and is moreover tight, to guarantee that the cost is preserved within factor 1±ε for every set of centers. Our second result eliminates the log log n term in the dimension through a relaxation of the guarantee (namely, preserving the cost only for all approximately-optimal sets of centers), which maintains its usefulness for downstream applications. Overall, we achieve strong dimension reduction in the discrete setting, and find that it differs from the continuous setting not only in the dimension bound, which depends on the doubling dimension, but also in the guarantees beyond preserving the optimal value, such as which clusterings are preserved.
Cite as

Shaofeng H.-C. Jiang, Robert Krauthgamer, Shay Sapir, Sandeep Silwal, and Di Yue. Dimension Reduction for Clustering: The Curious Case of Discrete Centers. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 82:1-82:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{jiang_et_al:LIPIcs.ITCS.2026.82,
  author =	{Jiang, Shaofeng H.-C. and Krauthgamer, Robert and Sapir, Shay and Silwal, Sandeep and Yue, Di},
  title =	{{Dimension Reduction for Clustering: The Curious Case of Discrete Centers}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{82:1--82:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.82},
  URN =		{urn:nbn:de:0030-drops-253698},
  doi =		{10.4230/LIPIcs.ITCS.2026.82},
  annote =	{Keywords: dimension reduction, clustering, k-median, k-means, doubling dimension}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.16
Robust Streaming Against Low-Memory Adversaries

Authors: Omri Ben-Eliezer, Krzysztof Onak, and Sandeep Silwal

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Robust streaming, the study of streaming algorithms that provably work when the stream is generated by an adaptive adversary, has seen tremendous progress in recent years. However, fundamental barriers remain: the best known algorithm for turnstile F_p-estimation in the robust streaming setting is exponentially worse than in the oblivious setting, and closing this gap seems difficult. Arguably, one possible cause of this barrier is the adversarial model, which may be too strong: unlike the space-bounded streaming algorithm, the adversary can memorize the entire history of the interaction with the algorithm. Can we then close the exponential gap if we insist that the adversary itself is an adaptive but low-memory entity, roughly as powerful as (or even weaker than) the algorithm? In this work we present the first set of models and results aimed towards this question. We design efficient robust streaming algorithms against adversaries that are fully adaptive but have no long-term memory ("memoryless") or very little memory of the history of interaction. Roughly speaking, a memoryless adversary only sees, at any given round, the last output of the algorithm (and does not even know the current time) and can generate an unlimited number of independent coin tosses. A low-memory adversary is similar, but maintains an additional small buffer. While these adversaries may seem quite limited at first glance, we show that this adversarial model is strong enough to produce streams that have high flip number and density in the context of F₂-estimation, which rules out most known robustification techniques. We then design a new simple approach, similar to the computation paths framework, to obtain efficient algorithms against memoryless and low-memory adversaries for a wide class of order-invariant problems. We conclude by posing various open questions proposing further exploration of the landscape of robust streaming against fully adaptive but computationally constrained adversaries.
Cite as

Omri Ben-Eliezer, Krzysztof Onak, and Sandeep Silwal. Robust Streaming Against Low-Memory Adversaries. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{beneliezer_et_al:LIPIcs.ITCS.2026.16,
  author =	{Ben-Eliezer, Omri and Onak, Krzysztof and Silwal, Sandeep},
  title =	{{Robust Streaming Against Low-Memory Adversaries}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{16:1--16:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.16},
  URN =		{urn:nbn:de:0030-drops-253037},
  doi =		{10.4230/LIPIcs.ITCS.2026.16},
  annote =	{Keywords: robust streaming, adaptive robustness, bounded-space adversaries}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.21
Overlay Network Construction: Improved Overall and Node-Wise Message Complexity

Authors: Yi-Jun Chang, Yanyu Chen, and Gopinath Mishra

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
We consider the problem of constructing distributed overlay networks, where nodes in a reconfigurable system can create or sever connections with nodes whose identifiers they know. Initially, each node knows only its own and its neighbors' identifiers, forming a local channel, while the evolving structure is termed the global channel. The goal is to reconfigure any connected graph into a desired topology, such as a bounded-degree expander graph or a well-formed tree (WFT) with a constant maximum degree and logarithmic diameter, minimizing the total number of rounds and message complexity. This problem mirrors real-world peer-to-peer network construction, where creating robust and efficient systems is desired. We study the overlay reconstruction problem in a network of n nodes in two models: GOSSIP-reply and HYBRID. In the GOSSIP-reply model, each node can send a message and receive a corresponding reply message in one round. In the HYBRID model, a node can send O(1) messages to each neighbor in the local channel and a total of O(log n) messages in the global channel. In both models, we propose protocols for WFT construction with O (n log n) message complexities using messages of O(log n) bits. In the GOSSIP-reply model, our protocol takes O(log n) rounds while in the HYBRID model, our protocol takes O(log² n) rounds. Both protocols use O (n log² n) bits of communication. We obtain improved bounds over prior work: GOSSIP-reply: A recent result by Dufoulon et al. (ITCS 2024) achieved O(log⁵ n) round complexity and O (n log⁵ n) message complexity using messages of at least Ω(log² n) bits in GOSSIP-reply. With messages of size O(log n), our protocol achieves an optimal round complexity of O(log n) and an improved message complexity of O(n log n). HYBRID: Götte et al. (Distributed Computing 2023) showed an optimal O(log n)-round algorithm with O(log² n) global messages per round which incurs a message complexity of Ω(m), where m is the number of edges in the initial topology. At the cost of increasing the round complexity to O(log² n) while using only O(log n) messages globally, our protocol achieves a message complexity that is independent of m. Our approach ensures that the total number of messages for node v, with degree deg(v) in the initial topology, is bounded by O(deg(v) + log n), while the algorithm of Götte et al. requires O(deg(v) + (log⁴ n)/(log log n)) messages per node.
Cite as

Yi-Jun Chang, Yanyu Chen, and Gopinath Mishra. Overlay Network Construction: Improved Overall and Node-Wise Message Complexity. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 21:1-21:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.FSTTCS.2025.21,
  author =	{Chang, Yi-Jun and Chen, Yanyu and Mishra, Gopinath},
  title =	{{Overlay Network Construction: Improved Overall and Node-Wise Message Complexity}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{21:1--21:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.21},
  URN =		{urn:nbn:de:0030-drops-251025},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.21},
  annote =	{Keywords: Distributed algorithms, Overlay networks, Expander graphs}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.13
Optimal Online Bipartite Matching in Degree-2 Graphs

Authors: Amey Bhangale, Arghya Chakraborty, and Prahladh Harsha

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Online bipartite matching is a classical problem in online algorithms and we know that both the deterministic fractional and randomized integral online matchings achieve the same competitive ratio of 1-1/e. In this work, we study classes of graphs where the online degree is restricted to 2. As expected, one can achieve a competitive ratio of better than 1-1/e in both the deterministic fractional and randomized integral cases, but surprisingly, these ratios are not the same. It was already known that for fractional matching, a 0.75 competitive ratio algorithm is optimal. We show that the folklore Half-Half algorithm achieves a competitive ratio of η ≈ 0.717772… and more surprisingly, show that this is optimal by giving a matching lower-bound. This yields a separation between the two problems: deterministic fractional and randomized integral, showing that it is impossible to obtain a perfect rounding scheme.
Cite as

Amey Bhangale, Arghya Chakraborty, and Prahladh Harsha. Optimal Online Bipartite Matching in Degree-2 Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhangale_et_al:LIPIcs.ISAAC.2025.13,
  author =	{Bhangale, Amey and Chakraborty, Arghya and Harsha, Prahladh},
  title =	{{Optimal Online Bipartite Matching in Degree-2 Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.13},
  URN =		{urn:nbn:de:0030-drops-249216},
  doi =		{10.4230/LIPIcs.ISAAC.2025.13},
  annote =	{Keywords: Online Algorithm, Bipartite matching}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.82
Buffered Partially-Persistent External-Memory Search Trees

Authors: Gerth Stølting Brodal, Casper Moldrup Rysgaard, and Rolf Svenning

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We present an optimal partially-persistent external-memory search tree with amortized I/O bounds matching those achieved by the non-persistent B^{ε}-tree by Brodal and Fagerberg [SODA 2003]. In a partially-persistent data structure, each update creates a new version. All past versions can be queried, but only the current version can be updated. Operations should be efficient with respect to the size N_v of the accessed version v. For any parameter 0 < ε < 1, our data structure supports insertions and deletions in amortized 𝒪(1/(ε B^{1 - ε}) log_B N_v) I/Os, where B is the external-memory block size. It also supports successor and range reporting queries in amortized 𝒪(1/ε log_B N_v + K/B) I/Os, where K is the number of keys reported. The space usage of the data structure is linear in the total number of updates. We make the standard and minimal assumption that the internal memory has size M ≥ 2B. The previous state-of-the-art external-memory partially-persistent search tree by Arge, Danner and Teh [JEA 2003] supports all operations in worst-case 𝒪(log_B N_v + K/B) I/Os, matching the bounds achieved by the classical B-tree by Bayer and McCreight [Acta Informatica 1972]. Our data structure successfully combines buffering updates with partial persistence. The I/O bounds can also be achieved in the worst-case sense, by slightly modifying our data structure and under the requirement that the memory size M = Ω(B^{1-ε} log₂(max_v N_v)). For updates, where the I/O bound is o(1), we assume that the I/Os are performed evenly spread out among the updates (by performing buffer-overflows incrementally). The worst-case result slightly improves the memory requirement over the previous ephemeral external-memory dictionary by Das, Iacono, and Nekrich (ISAAC 2022), who achieved matching worst-case I/O bounds but required M = Ω(B log_B N), where N is the size of the current dictionary.
Cite as

Gerth Stølting Brodal, Casper Moldrup Rysgaard, and Rolf Svenning. Buffered Partially-Persistent External-Memory Search Trees. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 82:1-82:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{brodal_et_al:LIPIcs.ESA.2025.82,
  author =	{Brodal, Gerth St{\o}lting and Rysgaard, Casper Moldrup and Svenning, Rolf},
  title =	{{Buffered Partially-Persistent External-Memory Search Trees}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{82:1--82:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.82},
  URN =		{urn:nbn:de:0030-drops-245507},
  doi =		{10.4230/LIPIcs.ESA.2025.82},
  annote =	{Keywords: B-tree, buffered updates, partial persistence, external memory}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.36
Simplifying Armoni’s PRG

Authors: Ben Chen and Amnon Ta-Shma

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We propose a simple variant of the INW pseudo-random generator, where blocks have varying lengths, and prove it gives the same parameters as the more complicated construction of Armoni’s PRG. This shows there is no need for the specialized PRGs of Nisan and Zuckerman and Armoni, and they can be obtained as simple variants of INW. For the construction to work we need space-efficient extractors with tiny entropy loss. We use the extractors from [Chattopadhyay and Liao, 2020] instead of [Guruswami et al., 2009] taking advantage of the very high min-entropy regime we work with. We remark that using these extractors has the additional benefit of making the dependence on the branching program alphabet Σ correct.
Cite as

Ben Chen and Amnon Ta-Shma. Simplifying Armoni’s PRG. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 36:1-36:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.APPROX/RANDOM.2025.36,
  author =	{Chen, Ben and Ta-Shma, Amnon},
  title =	{{Simplifying Armoni’s PRG}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{36:1--36:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.36},
  URN =		{urn:nbn:de:0030-drops-244024},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.36},
  annote =	{Keywords: PRG, ROBP, read-once, random, psuedorandom, armoni, derandomization}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.57
List-Recovery of Random Linear Codes over Small Fields

Authors: Dean Doron, Jonathan Mosheiff, Nicolas Resch, and João Ribeiro

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We study list-recoverability of random linear codes over small fields, both from errors and from erasures. We consider codes of rate ε-close to capacity, and aim to bound the dependence of the output list size L on ε, the input list size 𝓁, and the alphabet size q. Prior to our work, the best upper bound was L = q^O(𝓁/ε) (Zyablov and Pinsker, Prob. Per. Inf. 1981). Previous work has identified cases in which linear codes provably perform worse than non-linear codes with respect to list-recovery. While there exist non-linear codes that achieve L = O(𝓁/ε), we know that L ≥ 𝓁^Ω(1/ε) is necessary for list recovery from erasures over fields of small characteristic, and for list recovery from errors over large alphabets. We show that in other relevant regimes there is no significant price to pay for linearity, in the sense that we get the correct dependence on the gap-to-capacity ε and go beyond the Zyablov-Pinsker bound for the first time. Specifically, when q is constant and ε approaches zero, - For list-recovery from erasures over prime fields, we show that L ≤ C₁/ε. By prior work, such a result cannot be obtained for low-characteristic fields. - For list-recovery from errors over arbitrary fields, we prove that L ≤ C₂/ε. Above, C₁ and C₂ depend on the decoding radius, input list size, and field size. We provide concrete bounds on the constants above, and the upper bounds on L improve upon the Zyablov-Pinsker bound whenever q ≤ 2^{(1/ε)^c} for some small universal constant c > 0.
Cite as

Dean Doron, Jonathan Mosheiff, Nicolas Resch, and João Ribeiro. List-Recovery of Random Linear Codes over Small Fields. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 57:1-57:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{doron_et_al:LIPIcs.APPROX/RANDOM.2025.57,
  author =	{Doron, Dean and Mosheiff, Jonathan and Resch, Nicolas and Ribeiro, Jo\~{a}o},
  title =	{{List-Recovery of Random Linear Codes over Small Fields}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{57:1--57:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.57},
  URN =		{urn:nbn:de:0030-drops-244239},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.57},
  annote =	{Keywords: List recovery, random linear codes}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.53
Near-Optimal List-Recovery of Linear Code Families

Authors: Ray Li and Nikhil Shagrithaya

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We prove several results on linear codes achieving list-recovery capacity. We show that random linear codes achieve list-recovery capacity with constant output list size (independent of the alphabet size and length). That is, over alphabets of size at least 𝓁^Ω(1/ε), random linear codes of rate R are (1-R-ε, 𝓁, (𝓁/ε)^O(𝓁/ε))-list-recoverable for all R ∈ (0,1) and 𝓁. Together with a result of Levi, Mosheiff, and Shagrithaya, this implies that randomly punctured Reed-Solomon codes also achieve list-recovery capacity. We also prove that our output list size is near-optimal among all linear codes: all (1-R-ε, 𝓁, L)-list-recoverable linear codes must have L ≥ 𝓁^{Ω(R/ε)}. Our simple upper bound combines the Zyablov-Pinsker argument with recent bounds from Kopparty, Ron-Zewi, Saraf, Wootters, and Tamo on the maximum intersection of a "list-recovery ball" and a low-dimensional subspace with large distance. Our lower bound is inspired by a recent lower bound of Chen and Zhang.
Cite as

Ray Li and Nikhil Shagrithaya. Near-Optimal List-Recovery of Linear Code Families. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.APPROX/RANDOM.2025.53,
  author =	{Li, Ray and Shagrithaya, Nikhil},
  title =	{{Near-Optimal List-Recovery of Linear Code Families}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{53:1--53:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.53},
  URN =		{urn:nbn:de:0030-drops-244199},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.53},
  annote =	{Keywords: Error-Correcting Codes, Randomness, List-Recovery, Reed-Solomon Codes, Random Linear Codes}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.4
Streaming Algorithms for Network Design

Authors: Chandra Chekuri, Rhea Jain, Sepideh Mahabadi, and Ali Vakilian

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We consider the Survivable Network Design problem (SNDP) in the single-pass insertion-only streaming model. The input to SNDP is an edge-weighted graph G = (V, E) and an integer connectivity requirement r(uv) for each u, v ∈ V. The objective is to find a minimum-weight subgraph H ⊆ G such that, for every pair of vertices u, v ∈ V, u and v are r(uv)-edge/vertex-connected. Recent work by [Ce Jin et al., 2024] obtained approximation algorithms for edge-connectivity augmentation, and via that, also derived algorithms for edge-connectivity SNDP (EC-SNDP). In this work we consider vertex-connectivity setting (VC-SNDP) and obtain several results for it as well as improved results for EC-SNDP. - We provide a general framework for solving connectivity problems including SNDP and others in streaming; this is based on a connection to fault-tolerant spanners. For VC-SNDP we provide an O(tk)-approximation in Õ(k^{1-1/t}n^{1 + 1/t}) space, where k is the maximum connectivity requirement, assuming an exact algorithm at the end of the stream. Using a refined LP-based analysis, we provide an O(β t)-approximation where β is the integrality gap of the natural cut-based LP relaxation. These are the first approximation algorithms in the streaming model for VC-SNDP. When applied to the EC-SNDP, our framework provides an O(t)-approximation in Õ(k^{1/2-1/(2t)}n^{1 + 1/t} + kn) space, improving the O(t log k)-approximation of [Ce Jin et al., 2024] using Õ(kn^{1+1/t}) space; this also extends to element-connectivity SNDP. - We consider vertex connectivity-augmentation in the link-arrival model. The input is a k-vertex-connected spanning subgraph G, and additional weighted links L arrive in the stream; the goal is to store the min-weight set of links such that G ∪ L is (k+1)-vertex-connected. We obtain constant-factor approximations in near-linear space for k = 1, 2. Our result for k = 2 is based on using the SPQR tree, a novel application for this well-known representation of 2-connected graphs.
Cite as

Chandra Chekuri, Rhea Jain, Sepideh Mahabadi, and Ali Vakilian. Streaming Algorithms for Network Design. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chekuri_et_al:LIPIcs.APPROX/RANDOM.2025.4,
  author =	{Chekuri, Chandra and Jain, Rhea and Mahabadi, Sepideh and Vakilian, Ali},
  title =	{{Streaming Algorithms for Network Design}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{4:1--4:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.4},
  URN =		{urn:nbn:de:0030-drops-243709},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.4},
  annote =	{Keywords: Streaming Algorithms, Survivable Network Design, Fault-Tolerant Spanners}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.8
Multipass Linear Sketches for Geometric LP-Type Problems

Authors: N. Efe Çekirge, William Gay, and David P. Woodruff

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
LP-type problems such as the Minimum Enclosing Ball (MEB), Linear Support Vector Machine (SVM), Linear Programming (LP), and Semidefinite Programming (SDP) are fundamental combinatorial optimization problems, with many important applications in machine learning applications such as classification, bioinformatics, and noisy learning. We study LP-type problems in several streaming and distributed big data models, giving ε-approximation linear sketching algorithms with a focus on the high accuracy regime with low dimensionality d, that is, when d < (1/ε)^0.999. Our main result is an O(ds) pass algorithm with O(s(√d/ε)^{3d/s}) ⋅ poly(d, log (1/ε)) space complexity in words, for any parameter s ∈ [1, d log (1/ε)], to solve ε-approximate LP-type problems of O(d) combinatorial and VC dimension. Notably, by taking s = d log (1/ε), we achieve space complexity polynomial in d and polylogarithmic in 1/ε, presenting exponential improvements in 1/ε over current algorithms. We complement our results by showing lower bounds of (1/ε)^Ω(d) for any 1-pass algorithm solving the (1 + ε)-approximation MEB and linear SVM problems, further motivating our multi-pass approach.
Cite as

N. Efe Çekirge, William Gay, and David P. Woodruff. Multipass Linear Sketches for Geometric LP-Type Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 8:1-8:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cekirge_et_al:LIPIcs.APPROX/RANDOM.2025.8,
  author =	{\c{C}ekirge, N. Efe and Gay, William and Woodruff, David P.},
  title =	{{Multipass Linear Sketches for Geometric LP-Type Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{8:1--8:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.8},
  URN =		{urn:nbn:de:0030-drops-243741},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.8},
  annote =	{Keywords: Streaming, sketching, LP-type problems}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.47
B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load

Authors: Roodabeh Safavi and Martin P. Seybold

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Uniquely represented (UR) data structures represent each logical state with a unique storage state. We study the problem of maintaining a dynamic set of n keys from a totally ordered universe in this context. UR structures are also called "strongly history independent" structures in the literature. We introduce a two-layer data structure called (α,ε)-Randomized Block Search Tree (RBST) that is uniquely represented and suitable for external memory (EM). Though RBSTs naturally generalize the well-known binary Treaps, several new ideas are needed to analyze the expected search, update, and storage efficiency in terms of block-reads, block-writes, and blocks stored. We prove that searches have O(ε^{-1} + log_α n) block-reads, that dynamic updates perform O(ε^{-1} + log_α(n)/α) block-writes and O(ε^{-2}+(1+(ε^{-1}+log n)/α)log_α n) block-reads, and that (α, ε)-RBSTs have an asymptotic load-factor of at least (1-ε) for every ε ∈ (0,1/2]. Thus (α, ε)-RBSTs improve on the known, uniquely represented B-Treap [Golovin; ICALP'09]. Compared with non-UR structures, the RBST is also, to the best of our knowledge, the first external memory structure that is storage-efficient and has a non-amortized, write-efficient update bound.
Cite as

Roodabeh Safavi and Martin P. Seybold. B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 47:1-47:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{safavi_et_al:LIPIcs.WADS.2025.47,
  author =	{Safavi, Roodabeh and Seybold, Martin P.},
  title =	{{B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{47:1--47:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.47},
  URN =		{urn:nbn:de:0030-drops-242786},
  doi =		{10.4230/LIPIcs.WADS.2025.47},
  annote =	{Keywords: Unique Representation, Randomization, Top-Down Analysis, Block Search Tree, Write-Efficiency, Storage-Efficiency}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.55
Optimal Oblivious Subspace Embeddings with Near-Optimal Sparsity

Authors: Shabarish Chenakkod, Michał Dereziński, and Xiaoyu Dong

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
An oblivious subspace embedding is a random m× n matrix Π such that, for any d-dimensional subspace, with high probability Π preserves the norms of all vectors in that subspace within a 1±ε factor. In this work, we give an oblivious subspace embedding with the optimal dimension m = Θ(d/ε²) that has a near-optimal sparsity of Õ(1/ε) non-zero entries per column of Π. This is the first result to nearly match the conjecture of Nelson and Nguyen [FOCS 2013] in terms of the best sparsity attainable by an optimal oblivious subspace embedding, improving on a prior bound of Õ(1/ε⁶) non-zeros per column [Chenakkod et al., STOC 2024]. We further extend our approach to the non-oblivious setting, proposing a new family of Leverage Score Sparsified embeddings with Independent Columns, which yield faster runtimes for matrix approximation and regression tasks. In our analysis, we develop a new method which uses a decoupling argument together with the cumulant method for bounding the edge universality error of isotropic random matrices. To achieve near-optimal sparsity, we combine this general-purpose approach with new trace inequalities that leverage the specific structure of our subspace embedding construction.
Cite as

Shabarish Chenakkod, Michał Dereziński, and Xiaoyu Dong. Optimal Oblivious Subspace Embeddings with Near-Optimal Sparsity. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 55:1-55:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chenakkod_et_al:LIPIcs.ICALP.2025.55,
  author =	{Chenakkod, Shabarish and Derezi\'{n}ski, Micha{\l} and Dong, Xiaoyu},
  title =	{{Optimal Oblivious Subspace Embeddings with Near-Optimal Sparsity}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{55:1--55:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.55},
  URN =		{urn:nbn:de:0030-drops-234324},
  doi =		{10.4230/LIPIcs.ICALP.2025.55},
  annote =	{Keywords: Randomized linear algebra, matrix sketching, subspace embeddings}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.77
Minimizing Recourse in an Adaptive Balls and Bins Game

Authors: Adi Fine, Haim Kaplan, and Uri Stemmer

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We consider a simple load-balancing game between an algorithm and an adaptive adversary. In a simplified version of this game, the adversary observes the assignment of jobs to machines and selects a machine to kill. The algorithm must then restart the jobs from the failed machine on other machines. The adversary repeats this process, observing the new assignment and eliminating another machine, and so on. The adversary aims to force the algorithm to perform many restarts, while we seek a robust algorithm that minimizes restarts regardless of the adversary’s strategy. This game was recently introduced by Bhattacharya et al. for designing a 3-spanner with low recourse against an adaptive adversary. We prove that a simple algorithm, which assigns each job to a randomly chosen live bin, incurs O(n log n) recourse against an adaptive adversary. This enables us to construct a much simpler 3-spanner with a recourse that is smaller by a factor of O(log² n) compared to the previous construction, without increasing the update time or the size of the spanner. This motivates a careful examination of the range of attacks an adaptive adversary can deploy against simple algorithms before resorting to more complex ones. As our case study demonstrates, this attack space may not be as large as it initially appears, enabling the development of robust algorithms that are both simpler and easier to analyze.
Cite as

Adi Fine, Haim Kaplan, and Uri Stemmer. Minimizing Recourse in an Adaptive Balls and Bins Game. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 77:1-77:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fine_et_al:LIPIcs.ICALP.2025.77,
  author =	{Fine, Adi and Kaplan, Haim and Stemmer, Uri},
  title =	{{Minimizing Recourse in an Adaptive Balls and Bins Game}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{77:1--77:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.77},
  URN =		{urn:nbn:de:0030-drops-234544},
  doi =		{10.4230/LIPIcs.ICALP.2025.77},
  annote =	{Keywords: Adaptive adversary, load-balancing game, balls-and-bins, randomized algorithms, dynamic 3-spanner, dynamic graph algorithms, adversarial robustness}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.75
Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model

Authors: Shiyuan Feng, William Swartworth, and David Woodruff

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We consider the heavy-hitters and F_p moment estimation problems in the sliding window model. For F_p moment estimation with 1 < p ≤ 2, we show that it is possible to give a (1± ε) multiplicative approximation to the F_p moment with 2/3 probability on any given window of size n using Õ(1/(ε^p)log² n + 1/(ε²)log n) bits of space. We complement this result with a lower bound showing that our algorithm gives tight bounds up to factors of log log n and log1/(ε). As a consequence of our F₂ moment estimation algorithm, we show that the heavy-hitters problem can be solved on an arbitrary window using O(1/(ε²)log² n) space which is tight.
Cite as

Shiyuan Feng, William Swartworth, and David Woodruff. Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 75:1-75:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.ICALP.2025.75,
  author =	{Feng, Shiyuan and Swartworth, William and Woodruff, David},
  title =	{{Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{75:1--75:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.75},
  URN =		{urn:nbn:de:0030-drops-234524},
  doi =		{10.4230/LIPIcs.ICALP.2025.75},
  annote =	{Keywords: sketching, streaming, heavy hitters, sliding window, moment estimation}
}
  • Refine by Type
  • 41 Document/PDF
  • 22 Document/HTML

  • Refine by Publication Year
  • 3 2026
  • 20 2025
  • 2 2024
  • 3 2023
  • 1 2022
  • Show More...

  • Refine by Author
  • 11 Nelson, Jelani
  • 3 Doron, Dean
  • 3 Stemmer, Uri
  • 3 Woodruff, David P.
  • 2 Blasiok, Jaroslaw
  • Show More...

  • Refine by Series/Journal
  • 40 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 7 Theory of computation → Sketching and sampling
  • 5 Theory of computation → Pseudorandomness and derandomization
  • 4 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 3 Theory of computation → Random projections and metric embeddings
  • 2 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 4 Differential Privacy
  • 4 sketching
  • 3 streaming
  • 2 Johnson-Lindenstrauss
  • 2 differential privacy
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact