36 Search Results for "Onak, Krzysztof"

Document
DOI: 10.4230/LIPIcs.SEA.2026.26
Engineering Algorithms for Dynamic Greedy Set Cover

Authors: Amitai Uzrad

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
In the dynamic set cover problem, the input is a dynamic universe of elements and a fixed collection of sets. As elements are inserted or deleted, the goal is to efficiently maintain an approximate minimum set cover. While the past decade has seen significant theoretical breakthroughs for this problem, a notable gap remains between theoretical design and practical performance, as no comprehensive experimental study currently exists to validate these results. In this paper, we bridge this gap by implementing and evaluating four greedy-based dynamic algorithms across a diverse range of real-world instances. We derive our implementations from state-of-the-art frameworks - such as [GKKP(STOC'17); SU(STOC'23); SUZ(FOCS'24)] - which we simplify by identifying and modifying intricate subroutines that optimize asymptotic bounds but hinder practical performance. We evaluate these algorithms based on solution quality (set cover size) and efficiency, which comprises update time - the time required to update the solution following each insertion/deletion - and recourse - the number of changes made to the solution per update. Each algorithm uses a parameter β to balance quality against efficiency; we investigate the influence of this tradeoff parameter on each algorithm and then perform a comparative analysis to evaluate the algorithms against each other. Our results provide the first practical insights into which algorithmic strategies provide the most value in realistic scenarios.
Cite as

Amitai Uzrad. Engineering Algorithms for Dynamic Greedy Set Cover. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{uzrad:LIPIcs.SEA.2026.26,
  author =	{Uzrad, Amitai},
  title =	{{Engineering Algorithms for Dynamic Greedy Set Cover}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{26:1--26:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.26},
  URN =		{urn:nbn:de:0030-drops-260308},
  doi =		{10.4230/LIPIcs.SEA.2026.26},
  annote =	{Keywords: Dynamic graphs, set cover, recourse}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.19
Asymmetric Streaming Approximate Pattern Matching

Authors: Wojciech Janczewski and Tatiana Starikovskaya

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract
We study the space complexity of pattern matching in the asymmetric streaming model, focusing on approximate pattern matching under the Hamming and edit distances. In this problem, we are given an m-length pattern and an n-length text and must compute, for every position of the text, the smallest distance between the pattern and a substring of the text which ends at this position. In the asymmetric streaming model, we assume to have constant-time random access to the pattern, while the text arrives as a stream, one letter at a time. It is known that computing all distances exactly in the asymmetric streaming model requires Ω(m) space (for the edit distance see Li and Zheng [FSTTCS 2021]). Hence, to achieve sublinear space, a relaxation of the problem is necessary. One possible variant is to consider the small distance regime, where the algorithm must compute only those distances that are bounded by a small integer parameter k. In this case, existing algorithms in a more restrictive fully streaming model (Kociumaka, Clifford, Porat [SODA'19], Bhattacharya, Koucký [ICALP'23]) straightforwardly imply the existence of poly(k, log n)-space asymmetric streaming algorithms. Another possible relaxation is computing all distances approximately. For this variant, we don't have small-space algorithms in the fully streaming model: the best known algorithm solves pattern matching under the Hamming distance (1+ε)-approximately using 𝒪̃(ε^{-2}√m) space (Starikovskaya, Svagerka, Uznański [APPROX'20]). For the edit distance, no efficient approximation algorithms are known. In this work, we show approximation algorithms for pattern matching under the Hamming and edit distances in the asymmetric streaming model for any constant ε > 0: 1) We show that there is a simple randomised asymmetric streaming algorithm that solves approximate pattern matching under the Hamming distance (1+ε)-approximately using 𝒪(ε^{-3}log³n) bits. 2) As our second and main contribution, we extend the result of Cheng et al. [ICALP 2021] and show that for any integer k there is a deterministic asymmetric streaming algorithm that solves pattern matching under the edit distance (2^k-1+ε)-approximately using 𝒪̃(m^{1/k}) space.
Cite as

Wojciech Janczewski and Tatiana Starikovskaya. Asymmetric Streaming Approximate Pattern Matching. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{janczewski_et_al:LIPIcs.CPM.2026.19,
  author =	{Janczewski, Wojciech and Starikovskaya, Tatiana},
  title =	{{Asymmetric Streaming Approximate Pattern Matching}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{19:1--19:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.19},
  URN =		{urn:nbn:de:0030-drops-259458},
  doi =		{10.4230/LIPIcs.CPM.2026.19},
  annote =	{Keywords: Asymmetric streaming, Pattern matching, Approximation, Edit distance, Hamming distance}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.21
Dynamic MIS Revisited: Incremental, Fault Tolerant and Fully Dynamic

Authors: Manoj Gupta, Shahbaz Khan, and Madhu Surendra

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
Given a dynamic graph G, we aim to maintain a maximal independent set (MIS). This problem admits a deterministic solution in O(m^{2/3}) time [SOSA21], while randomized algorithms for oblivious adversary take O(polylog n) [FOCS19] time. Recently, Bernstein et al. [SODA26] proved a conditional lower bound of Ω(n^{1-o(1)}) amortized update time even for incremental MIS with adaptive adversary. In this paper, we establish similar deterministic bounds through the lens of incremental and fault tolerant algorithms for MIS, and show the following: 1) Incremental: MIS can be maintained under edge insertions in O(√m) amortized update time. 2) Fault Tolerant: Using O(m) preprocessing time, the MIS can be reported after k edge deletions in O(k+ ̅{n}²) time, where ̅{n} is the number of vertices on which deleted edges are incident. 3) Fully Dynamic: MIS can be maintained under fully dynamic edge updates (insertions and deletions) in O(m^{2/3}) amortized update time. Our incremental result is thus polynomially optimal even on allowing randomization with an adaptive adversary. Our fully dynamic result matches the state-of-the-art [SOSA21], and uses our incremental and fault tolerant algorithms as a black box. Although our fully dynamic algorithm does not improve the existing bounds, it provides additional insights into the harder edge-insertion case. We believe these insights may potentially be useful for improving the bounds for fully dynamic MIS in the future to match the incremental MIS bounds.
Cite as

Manoj Gupta, Shahbaz Khan, and Madhu Surendra. Dynamic MIS Revisited: Incremental, Fault Tolerant and Fully Dynamic. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 21:1-21:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.SWAT.2026.21,
  author =	{Gupta, Manoj and Khan, Shahbaz and Surendra, Madhu},
  title =	{{Dynamic MIS Revisited: Incremental, Fault Tolerant and Fully Dynamic}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{21:1--21:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.21},
  URN =		{urn:nbn:de:0030-drops-260577},
  doi =		{10.4230/LIPIcs.SWAT.2026.21},
  annote =	{Keywords: Maximal Independent Set, MIS, Incremental, Fault Tolerant, Fully dynamic}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.30
Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions

Authors: Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Given Boolean functions f, g : 𝔽₂ⁿ → {-1,+1}, we say they are linearly isomorphic if there exists A ∈ GL_n(𝔽₂) such that f(x) = g(Ax) for all x. We study this problem in the tolerant property testing framework under the known-unknown model, where g is given explicitly and f is accessible only via oracle queries, meaning the algorithm may adaptively request the value of f(x) for inputs x ∈ 𝔽₂ⁿ of its choice. Given parameters ε ≥ 0 and ω > 0, the goal is to distinguish whether there exists A ∈ GL_n(𝔽₂) such that the normalized Hamming distance between f and g(Ax) is at most ε, or whether for every A ∈ GL_n(𝔽₂) the distance is at least ε+ω. Our main result is a tolerant tester making Õ ((m/ω) ⁴) queries to f, where m is an upper bound on the spectral norm of g, improving the previous Õ ((m/ω) ^{24}) bound of Wimmer and Yoshida. We complement this with a nearly matching lower bound of Ω(m²) for constant ω (for example, ω = 1/4), improving the prior Ω(log m) lower bound of Grigorescu, Wimmer and Xie. A key technical ingredient on the algorithmic side is a query-efficient local list corrector. For the lower bound, we give a reduction from communication complexity using a novel subclass of Maiorana-McFarland functions from symmetric-key cryptography.
Cite as

Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy. Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 30:1-30:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.STACS.2026.30,
  author =	{Datta, Swarnalipa and Ghosh, Arijit and Kayal, Chandrima and Paraashar, Manaswi and Roy, Manmatha},
  title =	{{Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{30:1--30:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.30},
  URN =		{urn:nbn:de:0030-drops-255194},
  doi =		{10.4230/LIPIcs.STACS.2026.30},
  annote =	{Keywords: Boolean Function, Isomorphism of Boolean Function, Fourier Analysis, Sublinear Algorithm, Property Testing}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.55
Testing H-Freeness on Sparse Graphs, the Case of Bounded Expansion

Authors: Samuel Humeau, Mamadou Moustapha Kanté, Daniel Mock, Timothé Picavet, and Alexandre Vigny

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
In property testing, a tester makes queries to (an oracle for) a graph and, on a graph having or being far from having a property P, it decides with high probability whether the graph satisfies P or not. Often, testers are restricted to a constant number of queries. While the graph properties for which there exists such a tester are somewhat well characterized in the dense graph model, it is not the case for sparse graphs. In this area, Czumaj and Sohler (FOCS’19) proved that H-freeness (i.e. the property of excluding the graph H as a subgraph) can be tested with constant queries on planar graphs as well as on graph classes excluding a minor. Using results from the sparsity toolkit, we propose a simpler alternative to the proof of Czumaj and Sohler, for a statement generalized to the broader notion of bounded expansion. That is, we prove that for any class 𝒞 with bounded expansion and any graph H, testing H-freeness can be done with constant query complexity on any graph G in 𝒞, where the constant depends on H and 𝒞, but is independent of G. While classes excluding a minor are prime examples of classes with bounded expansion, so are, for example, cubic graphs, graph classes with bounded maximum degree, or graphs of bounded book thickness. Additionally, random graphs with bounded average degree almost surely have bounded expansion.
Cite as

Samuel Humeau, Mamadou Moustapha Kanté, Daniel Mock, Timothé Picavet, and Alexandre Vigny. Testing H-Freeness on Sparse Graphs, the Case of Bounded Expansion. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{humeau_et_al:LIPIcs.STACS.2026.55,
  author =	{Humeau, Samuel and Kant\'{e}, Mamadou Moustapha and Mock, Daniel and Picavet, Timoth\'{e} and Vigny, Alexandre},
  title =	{{Testing H-Freeness on Sparse Graphs, the Case of Bounded Expansion}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{55:1--55:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.55},
  URN =		{urn:nbn:de:0030-drops-255441},
  doi =		{10.4230/LIPIcs.STACS.2026.55},
  annote =	{Keywords: Property testing, Sparsity, Bounded expansion, Treedepth}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.53
Average Sensitivity of Geometric Algorithms

Authors: Matthijs Ebbens and Yuichi Yoshida

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

Abstract
In modern applications of geometric algorithms, it is often unrealistic to assume that the input representation fully captures all relevant aspects of the problem, because the input data is often large and dynamic. To address this challenge, we consider the notion of average sensitivity, which is defined as the average earth mover’s distance between the output distributions of the algorithm when run on an input and the same input with one point removed, where the average is over removed points and the distance between two outputs is measured using the symmetric difference size. We start by showing that a number of classical problems from computational geometry, in particular the convex hull, Delaunay triangulation, and Voronoi diagram problems, are "simple" from the viewpoint of average sensitivity by proving tight bounds for the average sensitivity of any algorithm for these problems. Then, we continue by constructing an algorithm with low average sensitivity that computes, for any ε > 0, a set of (1/3+ε)n guards for the art gallery problem. This is the main technical contribution of this work, which combines algorithms from computational geometry with results from the theory of local computation algorithms (LCAs) and property testing.
Cite as

Matthijs Ebbens and Yuichi Yoshida. Average Sensitivity of Geometric Algorithms. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ebbens_et_al:LIPIcs.ITCS.2026.53,
  author =	{Ebbens, Matthijs and Yoshida, Yuichi},
  title =	{{Average Sensitivity of Geometric Algorithms}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{53:1--53:16},
  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.53},
  URN =		{urn:nbn:de:0030-drops-253409},
  doi =		{10.4230/LIPIcs.ITCS.2026.53},
  annote =	{Keywords: Average Sensitivity, Convex Hull, Delaunay Triangulation, Voronoi Diagram, Art Gallery}
}
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.ITCS.2026.18
Interactive Proofs for Distribution Testing with Conditional Oracles

Authors: Ari Biswas, Mark Bun, Clément L. Canonne, and Satchit Sivakumar

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

Abstract
We revisit the framework of interactive proofs for distribution testing, first introduced by Chiesa and Gur (ITCS 2018), which has recently experienced a surge in interest, accompanied by notable progress (e.g., Herman and Rothblum, STOC 2022, FOCS 2023; Herman, RANDOM 2024). In this model, a data-poor verifier determines whether a probability distribution has a property of interest by interacting with an all-powerful, data-rich but untrusted prover bent on convincing them that it has the property. While prior work gave sample-, time-, and communication-efficient protocols for testing and estimating a range of distribution properties, they all suffer from an inherent issue: for most interesting properties of distributions over a domain of size N, the verifier must draw at least Ω(√N) samples of its own. While sublinear in N, this is still prohibitive for large domains encountered in practice. In this work, we circumvent this limitation by augmenting the verifier with the ability to perform an exponentially smaller number of more powerful (but reasonable) pairwise conditional queries, effectively enabling them to perform "local comparison checks" of the prover’s claims. We systematically investigate the landscape of interactive proofs in this new setting, giving poly-logarithmic query and sample protocols for (tolerantly) testing all label-invariant properties, thus demonstrating exponential savings without compromising on communication, for this large and fundamental class of testing tasks.
Cite as

Ari Biswas, Mark Bun, Clément L. Canonne, and Satchit Sivakumar. Interactive Proofs for Distribution Testing with Conditional Oracles. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{biswas_et_al:LIPIcs.ITCS.2026.18,
  author =	{Biswas, Ari and Bun, Mark and Canonne, Cl\'{e}ment L. and Sivakumar, Satchit},
  title =	{{Interactive Proofs for Distribution Testing with Conditional Oracles}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{18:1--18:13},
  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.18},
  URN =		{urn:nbn:de:0030-drops-253059},
  doi =		{10.4230/LIPIcs.ITCS.2026.18},
  annote =	{Keywords: Distribution Testing, Interactive Proofs}
}
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.DISC.2025.22
The Complexity Landscape of Dynamic Distributed Subgraph Finding

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

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Bonne and Censor-Hillel (ICALP 2019) initiated the study of distributed subgraph finding in dynamic networks of limited bandwidth. For the case where the target subgraph is a clique, they determined the tight bandwidth complexity bounds in nearly all settings. However, several open questions remain, and very little is known about finding subgraphs beyond cliques. In this work, we consider these questions and explore subgraphs beyond cliques in the deterministic setting. For finding cliques, we establish an Ω(log log n) bandwidth lower bound for one-round membership-detection under edge insertions only and an Ω(log log log n) bandwidth lower bound for one-round detection under both edge insertions and node insertions. Moreover, we demonstrate new algorithms to show that our lower bounds are tight in bounded-degree networks when the target subgraph is a triangle. Prior to our work, no lower bounds were known for these problems. For finding subgraphs beyond cliques, we present a complete characterization of the bandwidth complexity of the membership-listing problem for every target subgraph, every number of rounds, and every type of topological change: node insertions, node deletions, edge insertions, and edge deletions. We also show partial characterizations for one-round membership-detection and listing.
Cite as

Yi-Jun Chang, Lyuting Chen, Yanyu Chen, Gopinath Mishra, and Mingyang Yang. The Complexity Landscape of Dynamic Distributed Subgraph Finding. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.DISC.2025.22,
  author =	{Chang, Yi-Jun and Chen, Lyuting and Chen, Yanyu and Mishra, Gopinath and Yang, Mingyang},
  title =	{{The Complexity Landscape of Dynamic Distributed Subgraph Finding}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{22:1--22:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.22},
  URN =		{urn:nbn:de:0030-drops-248399},
  doi =		{10.4230/LIPIcs.DISC.2025.22},
  annote =	{Keywords: Distributed algorithms, dynamic algorithms, subgraph finding}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.78
Testing Depth First Search Numbering

Authors: Artur Czumaj, Christian Sohler, and Stefan Walzer

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

Abstract
Property Testing is a formal framework to study the computational power and complexity of sampling from combinatorial objects. A central goal in standard graph property testing is to understand which graph properties are testable with sublinear query complexity. Here, a graph property P is testable with a sublinear query complexity if there is an algorithm that makes a sublinear number of queries to the input graph and accepts with probability at least 2/3, if the graph has property P, and rejects with probability at least 2/3 if it is ε-far from every graph that has property P. In this paper, we introduce a new variant of the bounded degree graph model. In this variant, in addition to the standard representation of a bounded degree graph, we assume that every vertex v has a unique label num(v) from {1, … , |V|}, and in addition to the standard queries in the bounded degree graph model, we also allow a property testing algorithm to query for the label of a vertex (but not for a vertex with a given label). Our new model is motivated by certain graph processes such as a DFS traversal, which assign consecutive numbers (labels) to the vertices of the graph. We want to study which of these numberings can be tested in sublinear time. As a first step in understanding such a model, we develop a property testing algorithm for discovery times of a DFS traversal with query complexity O(n^{1/3}/ε) and for constant ε > 0 we give a matching lower bound.
Cite as

Artur Czumaj, Christian Sohler, and Stefan Walzer. Testing Depth First Search Numbering. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 78:1-78:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{czumaj_et_al:LIPIcs.ESA.2025.78,
  author =	{Czumaj, Artur and Sohler, Christian and Walzer, Stefan},
  title =	{{Testing Depth First Search Numbering}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{78:1--78:16},
  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.78},
  URN =		{urn:nbn:de:0030-drops-245466},
  doi =		{10.4230/LIPIcs.ESA.2025.78},
  annote =	{Keywords: Randomized Algorithms, Graph Algorithms, Property Testing}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.62
Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering

Authors: Sina Bagheri Nezhad, Sayan Bandyapadhyay, and Tianzhi Chen

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

Abstract
In a seminal work, Chierichetti et al. [Chierichetti et al., 2017] introduced the (t,k)-fair clustering problem: Given a set of red points and a set of blue points in a metric space, a clustering is called fair if the number of red points in each cluster is at most t times and at least 1/t times the number of blue points in that cluster. The goal is to compute a fair clustering with at most k clusters that optimizes certain objective function. Considering this problem, they designed a polynomial-time O(1)- and O(t)-approximation for the k-center and the k-median objective, respectively. Recently, Carta et al. [Carta et al., 2024] studied this problem with the sum-of-radii objective and obtained a (6+ε)-approximation with running time O((k log_{1+ε}(k/ε))^k n^O(1)), i.e., fixed-parameter tractable in k. Here n is the input size. In this work, we design the first polynomial-time O(1)-approximation for (t,k)-fair clustering with the sum-of-radii objective, improving the result of Carta et al. Our result places sum-of-radii in the same group of objectives as k-center, that admit polynomial-time O(1)-approximations. This result also implies a polynomial-time O(1)-approximation for the Euclidean version of the problem, for which an f(k)⋅n^O(1)-time (1+ε)-approximation was known due to Drexler et al. [Drexler et al., 2023]. Here f is an exponential function of k. We are also able to extend our result to any arbitrary 𝓁 ≥ 2 number of colors when t = 1. This matches known results for the k-center and k-median objectives in this case. The significant disparity of sum-of-radii compared to k-center and k-median presents several complex challenges, all of which we successfully overcome in our work. Our main contribution is a novel cluster-merging-based analysis technique for sum-of-radii that helps us achieve the constant-approximation bounds.
Cite as

Sina Bagheri Nezhad, Sayan Bandyapadhyay, and Tianzhi Chen. Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 62:1-62:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bagherinezhad_et_al:LIPIcs.ESA.2025.62,
  author =	{Bagheri Nezhad, Sina and Bandyapadhyay, Sayan and Chen, Tianzhi},
  title =	{{Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{62:1--62:16},
  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.62},
  URN =		{urn:nbn:de:0030-drops-245309},
  doi =		{10.4230/LIPIcs.ESA.2025.62},
  annote =	{Keywords: fair clustering, sum-of-radii clustering, approximation algorithms}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.45
Local Computation Algorithms for Knapsack: Impossibility Results, and How to Avoid Them

Authors: Clément L. Canonne, Yun Li, and Seeun William Umboh

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

Abstract
Local Computation Algorithms (LCA), as introduced by Rubinfeld, Tamir, Vardi, and Xie (2011), are a type of ultra-efficient algorithms which, given access to a (large) input for a given computational task, are required to provide fast query access to a consistent output solution, without maintaining a state between queries. This paradigm of computation in particular allows for hugely distributed algorithms, where independent instances of a given LCA provide consistent access to a common output solution. The past decade has seen a significant amount of work on LCAs, by and large focusing on graph problems. In this paper, we initiate the study of Local Computation Algorithms for perhaps the archetypal combinatorial optimization problem, Knapsack. We first establish strong impossibility results, ruling out the existence of any non-trivial LCA for Knapsack as several of its relaxations. We then show how equipping the LCA with additional access to the Knapsack instance, namely, weighted item sampling, allows one to circumvent these impossibility results, and obtain sublinear-time and query LCAs. Our positive result draws on a connection to the recent notion of reproducibility for learning algorithms (Impagliazzo, Lei, Pitassi, and Sorrell, 2022), a connection we believe to be of independent interest for the design of LCAs.
Cite as

Clément L. Canonne, Yun Li, and Seeun William Umboh. Local Computation Algorithms for Knapsack: Impossibility Results, and How to Avoid Them. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 45:1-45:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{canonne_et_al:LIPIcs.APPROX/RANDOM.2025.45,
  author =	{Canonne, Cl\'{e}ment L. and Li, Yun and Umboh, Seeun William},
  title =	{{Local Computation Algorithms for Knapsack: Impossibility Results, and How to Avoid Them}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{45:1--45:21},
  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.45},
  URN =		{urn:nbn:de:0030-drops-244111},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.45},
  annote =	{Keywords: Local computation algorithms, Knapsack, algorithms, lower bounds}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.61
A Fast Coloring Oracle for Average Case Hypergraphs

Authors: Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, and Shlomo Tauber

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

Abstract
Hypergraph 2-colorability is one of the classical NP-hard problems. Person and Schacht [SODA'09] designed a deterministic algorithm whose expected running time is polynomial over a uniformly chosen 2-colorable 3-uniform hypergraph. Lee, Molla, and Nagle recently extended this to k-uniform hypergraphs for all k ≥ 3. Both papers relied heavily on the regularity lemma, hence their analysis was involved and their running time hid tower-type constants. Our first result in this paper is a new simple and elementary deterministic 2-coloring algorithm that reproves the theorems of Person-Schacht and Lee-Molla-Nagle while avoiding the use of the regularity lemma. We also show how to turn our new algorithm into a randomized one with average expected running time of only O(n). Our second and main result gives what we consider to be the ultimate evidence of just how easy it is to find a 2-coloring of an average 2-colorable hypergraph. We define a coloring oracle to be an algorithm which, given vertex v, assigns color red/blue to v while inspecting as few edges as possible, so that the answers to any sequence of queries to the oracle are consistent with a single legal 2-coloring of the input. Surprisingly, we show that there is a coloring oracle that, on average, can answer every vertex query in time O(1).
Cite as

Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, and Shlomo Tauber. A Fast Coloring Oracle for Average Case Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 61:1-61:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{marcussen_et_al:LIPIcs.APPROX/RANDOM.2025.61,
  author =	{Marcussen, Cassandra and Pyne, Edward and Rubinfeld, Ronitt and Shapira, Asaf and Tauber, Shlomo},
  title =	{{A Fast Coloring Oracle for Average Case Hypergraphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{61:1--61:13},
  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.61},
  URN =		{urn:nbn:de:0030-drops-244272},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.61},
  annote =	{Keywords: average-case algorithms, local computation algorithms, graph coloring}
}
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}
}
  • Refine by Type
  • 36 Document/PDF
  • 32 Document/HTML

  • Refine by Publication Year
  • 9 2026
  • 23 2025
  • 1 2024
  • 1 2022
  • 1 2020
  • Show More...

  • Refine by Author
  • 3 Mahabadi, Sepideh
  • 3 Onak, Krzysztof
  • 2 Canonne, Clément L.
  • 2 Czumaj, Artur
  • 2 Mao, Xinyu
  • Show More...

  • Refine by Series/Journal
  • 36 LIPIcs

  • Refine by Classification
  • 13 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 6 Theory of computation → Distributed algorithms
  • 6 Theory of computation → Dynamic graph algorithms
  • 4 Theory of computation → Graph algorithms analysis
  • 3 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 3 Sublinear Algorithms
  • 3 communication complexity
  • 2 Approximation Algorithm
  • 2 Graph Algorithms
  • 2 Maximum Matching
  • 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