62 Search Results for "King, Valerie"

Document
DOI: 10.4230/LIPIcs.SWAT.2026.38
New Algorithms for Girth and Cycle Detection

Authors: Liam Roditty and Plia Trabelsi

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

Abstract
Let G = (V,E) be an unweighted undirected graph with n vertices and m edges. Let g be the girth of G, that is, the length of a shortest cycle in G. We present a randomized algorithm with a running time of Õ(𝓁 ⋅ n^{1 + 1/(𝓁-ε)}) that returns a cycle of length at most 2𝓁 ⌈g/2⌉ - 2 ⌊ε⌈g/2⌉⌋, where 𝓁 ≥ 2 is an integer and ε ∈ [0,1], for every graph with g = polylog(n). Our algorithm generalizes an algorithm of Kadria et al. [SODA'22] that computes a cycle of length at most 4 ⌈g/2⌉ - 2 ⌊ε⌈g/2⌉⌋ in Õ(n^{1 + 1/(2 - ε)}) time. Kadria et al. presented also an algorithm that finds a cycle of length at most 2𝓁 ⌈g/2⌉ in Õ(n^{1 + 1/(𝓁)}) time, where 𝓁 must be an integer. Our algorithm generalizes this algorithm, as well, by replacing the integer parameter 𝓁 in the running time exponent with a real-valued parameter 𝓁 - ε, thereby offering greater flexibility in parameter selection and enabling a broader spectrum of combinations between running times and cycle lengths. We also show that for sparse graphs a better tradeoff is possible, by presenting an Õ(𝓁⋅ m^{1+ 1/(𝓁-ε)}) time randomized algorithm that returns a cycle of length at most 2𝓁(⌊(g-1)/2⌋) - 2(⌊ε⌊(g-1)/2⌋⌋+1), where 𝓁 ≥ 3 is an integer and ε ∈ [0,1), for every graph with g = polylog(n). To obtain our algorithms we develop several techniques and introduce a formal definition of hybrid cycle detection algorithms. Both may prove useful in broader contexts, including other cycle detection and approximation problems. Among our techniques is a new cycle searching technique, in which we search for a cycle from a given vertex and possibly all its neighbors in linear time. Using this technique together with more ideas we develop two hybrid algorithms. The first allows us to obtain an Õ(m^{2-2/(⌈g/2⌉+1))-time, (+1)-approximation of g. The second is used to obtain our Õ(𝓁⋅ n^{1+ 1/(𝓁-ε)})-time and Õ(𝓁⋅ m^{1+ 1/(𝓁-ε)})-time approximation algorithms.
Cite as

Liam Roditty and Plia Trabelsi. New Algorithms for Girth and Cycle Detection. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 38:1-38:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{roditty_et_al:LIPIcs.SWAT.2026.38,
  author =	{Roditty, Liam and Trabelsi, Plia},
  title =	{{New Algorithms for Girth and Cycle Detection}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{38:1--38:17},
  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.38},
  URN =		{urn:nbn:de:0030-drops-260742},
  doi =		{10.4230/LIPIcs.SWAT.2026.38},
  annote =	{Keywords: Graph algorithms, All pairs shortest path, Girth, Cycle approximation}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.9
QPTAS for MWIS and Finding Large Sparse Induced Subgraphs in Graphs with Few Independent Long Holes

Authors: Édouard Bonnet, Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk, and Paweł Rzążewski

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

Abstract
We present a quasipolynomial-time approximation scheme (QPTAS) for the Maximum Independent Set (MWIS) in graphs with a bounded number of pairwise vertex-disjoint and non-adjacent long induced cycles. More formally, for every fixed s and t, we show a QPTAS for MWIS in graphs that exclude sC_t as an induced minor. Combining this with known results, we obtain a QPTAS for the problem of finding a largest induced subgraph of bounded treewidth with given hereditary property definable in Counting Monadic Second Order Logic, in the same classes of graphs. This is a step towards a conjecture of Gartland and Lokshtanov which asserts that for any planar graph H, graphs that exclude H as an induced minor admit a polynomial-time algorithm for the latter problem. This conjecture is notoriously open and even its weaker variants are confirmed only for very restricted graphs H.
Cite as

Édouard Bonnet, Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk, and Paweł Rzążewski. QPTAS for MWIS and Finding Large Sparse Induced Subgraphs in Graphs with Few Independent Long Holes. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.SWAT.2026.9,
  author =	{Bonnet, \'{E}douard and Czy\.{z}ewska, Jadwiga and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Pilipczuk, Marcin and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{QPTAS for MWIS and Finding Large Sparse Induced Subgraphs in Graphs with Few Independent Long Holes}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{9:1--9:14},
  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.9},
  URN =		{urn:nbn:de:0030-drops-260454},
  doi =		{10.4230/LIPIcs.SWAT.2026.9},
  annote =	{Keywords: independent set, long holes, QPTAS, induced subgraphs}
}
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.73
Colouring Probe H-Free Graphs

Authors: Daniël Paulusma, Johannes Rauch, and Erik Jan van Leeuwen

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

Abstract
The NP-complete problems Colouring and k-Colouring (k ≥ 3) are well studied on H-free graphs, i.e., graphs that do not contain some fixed graph H as an induced subgraph. We research to what extent the known polynomial-time algorithms for H-free graphs can be generalized if we only know some of the edges of the input graph. We do this by considering the classical probe graph model introduced in the early nineties. For a graph H, a partitioned probe H-free graph (G,P,N) consists of a graph G = (V,E), together with a set P ⊆ V of probes and an independent set N = V ⧵ P of non-probes, such that G+F is H-free for some edge set F ⊆ binom(N,2). We show the following: - We fully classify Colouring on partitioned probe H-free graphs and show that the obtained complexity dichotomy differs from the known dichotomy of Colouring for H-free graphs. - We fully classify 3-Colouring on partitioned probe P_t-free graphs: we prove polynomial-time solvability for t ≤ 5 and NP-completeness for t ≥ 6. In contrast, 3-Colouring on P_t-free graphs is known to be polynomial-time solvable for t ≤ 7 and quasi-polynomial-time solvable for t ≥ 8. Our main result is our polynomial-time algorithm for 3-Colouring on partitioned P₅-free graphs. For this result, and also for all our other polynomial-time results, we do not need to know the edge set F; we only need to know its existence. Moreover, the class of probe P₅-free graphs includes not only paths of arbitrary length but even all bipartite graphs and is much richer than the class of P₅-free graphs. The latter is also evidenced by the fact that there exist graph problems, such as Matching Cut, that are known to be polynomial-time solvable for P₅-free graphs but NP-complete for partitioned probe P₅-free graphs. In particular, unlike the class of 3-colourable P₅-free graphs, the class of 3-colourable probe P₅-free graphs has unbounded mim-width. Hence, our polynomial-time result for 3-Colouring for probe P₅-free graphs suggests that there may be another, deeper overarching reason why 3-Colouring is polynomial-time solvable for P₅-free graphs.
Cite as

Daniël Paulusma, Johannes Rauch, and Erik Jan van Leeuwen. Colouring Probe H-Free Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 73:1-73:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{paulusma_et_al:LIPIcs.STACS.2026.73,
  author =	{Paulusma, Dani\"{e}l and Rauch, Johannes and van Leeuwen, Erik Jan},
  title =	{{Colouring Probe H-Free Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{73:1--73:20},
  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.73},
  URN =		{urn:nbn:de:0030-drops-255621},
  doi =		{10.4230/LIPIcs.STACS.2026.73},
  annote =	{Keywords: colouring, probe graph, forbidden induced subgraph, complexity dichotomy}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.74
List Coloring Ordered Graphs with Forbidden Induced Subgraphs

Authors: Marta Piecyk and Paweł Rzążewski

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

Abstract
In the List k-Coloring problem we are given a graph whose every vertex is equipped with a list, which is a subset of {1,…,k}. We need to decide if G admits a proper coloring, where every vertex receives a color from its list. The complexity of the problem in classes defined by forbidding induced subgraphs is a widely studied topic in algorithmic graph theory. Recently, Hajebi, Li, and Spirkl [SIAM J. Discr. Math. 38 (2024)] initiated the study of List 3-Coloring in ordered graphs, i.e., graphs with fixed linear ordering of vertices. Forbidding ordered induced subgraphs allows us to investigate the boundary of tractability more closely. We continue this direction of research, focusing mostly on the case of List 4-Coloring. We present several algorithmic and hardness results, which altogether provide an almost complete dichotomy for classes defined by forbidding one fixed ordered graph: our investigations leave one minimal open case.
Cite as

Marta Piecyk and Paweł Rzążewski. List Coloring Ordered Graphs with Forbidden Induced Subgraphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 74:1-74:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{piecyk_et_al:LIPIcs.STACS.2026.74,
  author =	{Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{List Coloring Ordered Graphs with Forbidden Induced Subgraphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{74:1--74:17},
  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.74},
  URN =		{urn:nbn:de:0030-drops-255634},
  doi =		{10.4230/LIPIcs.STACS.2026.74},
  annote =	{Keywords: coloring, ordered graphs, forbidden induced subgraphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.78
Protrusion Decompositions Revisited: Uniform Lossy Kernels for Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors

Authors: Roohani Sharma and Michał Włodarczyk

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

Abstract
Let ℱ be a finite family of graphs. In the ℱ-Deletion problem, one is given a graph G and an integer k, and the goal is to find k vertices whose deletion results in a graph with no minor from the family ℱ. This may be regarded as a far-reaching generalization of Vertex Cover and Feedback vertex Set. In their seminal work, Fomin, Lokshtanov, Misra & Saurabh [FOCS 2012] gave a polynomial kernel for this problem when the family ℱ contains a planar graph. As the size of their kernel is g(ℱ) ⋅ k^{f(ℱ)}, a natural follow-up question was whether the dependence on ℱ in the exponent of k can be avoided. The answer turned out to be negative: Giannopoulou, Jansen, Lokshtanov & Saurabh [TALG 2017] proved that this is already inevitable for the special case of the Treewidth-η-Deletion problem. In this work, we show that this non-uniformity can be avoided at the expense of a small loss. First, we present a simple 2-approximate kernelization algorithm for Treewidth-η-Deletion with a kernel size g(η) ⋅ k⁶. Next, we show that the approximation factor can be made arbitrarily close to 1, if we settle for a kernelization protocol with 𝒪(1) calls to an oracle that solves instances of size bounded by a uniform polynomial in k. We extend the above results to general ℱ-Deletion, whenever ℱ contains a planar graph, as long as an oracle for Treewidth-η-Deletion is available for small instances. Notably, all our constants are computable functions of ℱ and our techniques work also when some graphs in ℱ may be disconnected. Our results rely on two novel techniques. First, we transform so-called "near-protrusion decompositions" into true protrusion decompositions by sacrificing a small accuracy loss. Secondly, we show how to optimally compress such a decomposition with respect to general ℱ-Deletion. Using our second technique, we also obtain linear kernels on sparse graph classes when ℱ contains a planar graph, whereas the previously known theorems required all graphs in ℱ to be connected. Specifically, we generalize the kernelization algorithm by Kim, Langer, Paul, Reidl, Rossmanith, Sau & Sikdar [TALG 2015] on graph classes that exclude a topological minor.
Cite as

Roohani Sharma and Michał Włodarczyk. Protrusion Decompositions Revisited: Uniform Lossy Kernels for Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 78:1-78:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{sharma_et_al:LIPIcs.STACS.2026.78,
  author =	{Sharma, Roohani and W{\l}odarczyk, Micha{\l}},
  title =	{{Protrusion Decompositions Revisited: Uniform Lossy Kernels for Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{78:1--78: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.78},
  URN =		{urn:nbn:de:0030-drops-255674},
  doi =		{10.4230/LIPIcs.STACS.2026.78},
  annote =	{Keywords: kernelization, graph minors, treewidth, uniform kernels, minor hitting}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.38
Fully Dynamic Spectral Sparsification for Directed Hypergraphs

Authors: Sebastian Forster, Gramoz Goranci, and Ali Momeni

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

Abstract
There has been a surge of interest in spectral hypergraph sparsification, a natural generalization of spectral sparsification for graphs. In this paper, we present a simple fully dynamic algorithm for maintaining spectral hypergraph sparsifiers of directed hypergraphs. Our algorithm achieves a near-optimal size of O(n² / ε ² log ⁷ m) and amortized update time of O(r² log ³ m), where n is the number of vertices, and m and r respectively upper bound the number of hyperedges and the rank of the hypergraph at any time. We also extend our approach to the parallel batch-dynamic setting, where a batch of any k hyperedge insertions or deletions can be processed with O(kr² log ³ m) amortized work and O(log ² m) depth. This constitutes the first spectral-based sparsification algorithm in this setting.
Cite as

Sebastian Forster, Gramoz Goranci, and Ali Momeni. Fully Dynamic Spectral Sparsification for Directed Hypergraphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 38:1-38:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{forster_et_al:LIPIcs.STACS.2026.38,
  author =	{Forster, Sebastian and Goranci, Gramoz and Momeni, Ali},
  title =	{{Fully Dynamic Spectral Sparsification for Directed Hypergraphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{38:1--38:20},
  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.38},
  URN =		{urn:nbn:de:0030-drops-255272},
  doi =		{10.4230/LIPIcs.STACS.2026.38},
  annote =	{Keywords: Spectral sparsification, Dynamic algorithms, (Directed) hypergraphs, Data structures}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.4
Pseudodeterministic Algorithms for Minimum Cut Problems

Authors: Aryan Agarwala and Nithin Varma

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

Abstract
In this paper we present efficient pseudodeterministic algorithms for both the global minimum cut and minimum s-t cut problems. The running time of our algorithm for the global minimum cut problem is asymptotically better than the fastest sequential deterministic global minimum cut algorithm (Henzinger, Li, Rao, Wang; SODA 2024). Furthermore, we implement our algorithm in streaming, PRAM, and cut-query models, where no efficient deterministic global minimum cut algorithms are known.
Cite as

Aryan Agarwala and Nithin Varma. Pseudodeterministic Algorithms for Minimum Cut Problems. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{agarwala_et_al:LIPIcs.ITCS.2026.4,
  author =	{Agarwala, Aryan and Varma, Nithin},
  title =	{{Pseudodeterministic Algorithms for Minimum Cut Problems}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{4:1--4:15},
  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.4},
  URN =		{urn:nbn:de:0030-drops-252917},
  doi =		{10.4230/LIPIcs.ITCS.2026.4},
  annote =	{Keywords: Minimum Cut, Pseudodeterministic Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.54
Testable Algorithms for Approximately Counting Edges and Triangles in Sublinear Time and Space

Authors: Talya Eden, Ronitt Rubinfeld, and Arsen Vasilyan

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

Abstract
We consider the fundamental problems of approximately counting the numbers of edges and triangles in a graph in sublinear time. Previous algorithms for these tasks are significantly more efficient under a promise that the arboricity of the graph is bounded by some parameter ̅α. However, when this promise is violated, the estimates given by these algorithms are no longer guaranteed to be correct. For the triangle counting task, we give an algorithm that requires no promise on the input graph G, and computes a (1±ε)-approximation for the number of triangles t in G in time O^*((m⋅ α(G))/t + m/(t^{2/3)}), where α(G) is the arboricity of the graph. The algorithm can be used on any graph G (no prior knowledge of the arboricity α(G) is required), and the algorithm adapts its run-time on the fly based on the graph G. We accomplish this by trying a sequence of candidate values α̃ for α(G) and using a novel algorithm in the framework of testable algorithms. This ensures that wrong candidates α̃ cannot lead to wrong estimates: if the advice is incorrect, the algorithm either succeeds despite this or detects this and continues with a new candidate. Once the algorithm accepts the candidate, its output is guaranteed to be correct with high probability. We prove that this approach preserves - up to an additive overhead - the dramatic efficiency gains obtainable when good arboricity bounds are known in advance, while ensuring robustness against misleading advice. We further complement this result with a lower bound, showing that such an overhead is unavoidable whenever the advice may be faulty. We further demonstrate implications of our results for triangle counting in the streaming model.
Cite as

Talya Eden, Ronitt Rubinfeld, and Arsen Vasilyan. Testable Algorithms for Approximately Counting Edges and Triangles in Sublinear Time and Space. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 54:1-54:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{eden_et_al:LIPIcs.ITCS.2026.54,
  author =	{Eden, Talya and Rubinfeld, Ronitt and Vasilyan, Arsen},
  title =	{{Testable Algorithms for Approximately Counting Edges and Triangles in Sublinear Time and Space}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{54:1--54: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.54},
  URN =		{urn:nbn:de:0030-drops-253417},
  doi =		{10.4230/LIPIcs.ITCS.2026.54},
  annote =	{Keywords: Sublinear Algorithms, Triangle Counting, Edge Counting, Arboricity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.3
Linear Matroid Intersection Is in Catalytic Logspace

Authors: Aryan Agarwala, Yaroslav Alekseev, and Antoine Vinciguerra

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

Abstract
Linear matroid intersection is an important problem in combinatorial optimization. Given two linear matroids over the same ground set, the linear matroid intersection problem asks you to find a common independent set of maximum size. The deep interest in linear matroid intersection is due to the fact that it generalises many classical problems in theoretical computer science, such as bipartite matching, edge disjoint spanning trees, rainbow spanning tree, and many more. We study this problem in the model of catalytic computation: space-bounded machines are granted access to catalytic space, which is additional working memory that is full with arbitrary data that must be preserved at the end of its computation. Although linear matroid intersection has had a polynomial time algorithm for over 50 years, it remains an important open problem to show that linear matroid intersection belongs to any well studied subclass of {P}. We address this problem for the class catalytic logspace (CL) with a polynomial time bound (CLP). Recently, Agarwala and Mertz (2025) showed that bipartite maximum matching can be computed in the class CLP ⊆ {P}. This was the first subclass of {P} shown to contain bipartite matching, and additionally the first problem outside TC¹ shown to be contained in CL. We significantly improve the result of Agarwala and Mertz by showing that linear matroid intersection can be computed in CLP.
Cite as

Aryan Agarwala, Yaroslav Alekseev, and Antoine Vinciguerra. Linear Matroid Intersection Is in Catalytic Logspace. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{agarwala_et_al:LIPIcs.ITCS.2026.3,
  author =	{Agarwala, Aryan and Alekseev, Yaroslav and Vinciguerra, Antoine},
  title =	{{Linear Matroid Intersection Is in Catalytic Logspace}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{3:1--3: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.3},
  URN =		{urn:nbn:de:0030-drops-252908},
  doi =		{10.4230/LIPIcs.ITCS.2026.3},
  annote =	{Keywords: Catalytic Computing, Computational Complexity, Matroid Theory, Algorithms}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.26
Recognizing Hereditary Properties in the Presence of Byzantine Nodes

Authors: David Cifuentes-Núñez, Pedro Montealegre, and Ivan Rapaport

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
Augustine et al. [DISC 2022] initiated the study of distributed graph algorithms in the presence of Byzantine nodes in the congested clique model. In this model, there is a set B of Byzantine nodes, where |B| is less than a third of the total number of nodes. These nodes have complete knowledge of the network and the state of other nodes, and they conspire to alter the output of the system. The authors addressed the connectivity problem, showing that it is solvable under the promise that either the subgraph induced by the honest nodes is connected, or the graph has 2|B|+1 connected components. In the current work, we continue the study of the Byzantine congested clique model by considering the recognition of other graph properties, specifically hereditary properties. A graph property is hereditary if it is closed under taking induced subgraphs. Examples of hereditary properties include acyclicity, bipartiteness, planarity, and bounded (chromatic, independence) number, etc. For each class of graphs 𝒢 satisfying a hereditary property (a hereditary graph-class), we propose a randomized algorithm which, with high probability, (1) accepts if the input graph G belongs to 𝒢, and (2) rejects if G contains at least |B| + 1 disjoint subgraphs not belonging to 𝒢. The round complexity of our algorithm is 𝒪(((log (|𝒢_n|))/n) +|B|) ⋅polylog(n)) , where 𝒢_n is the set of n-node graphs in 𝒢. Finally, we obtain an impossibility result that proves that our result is tight. Indeed, we consider the hereditary class of acyclic graphs, and we prove that there is no algorithm that can distinguish between a graph being acyclic and a graph having |B| disjoint cycles.
Cite as

David Cifuentes-Núñez, Pedro Montealegre, and Ivan Rapaport. Recognizing Hereditary Properties in the Presence of Byzantine Nodes. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cifuentesnunez_et_al:LIPIcs.OPODIS.2025.26,
  author =	{Cifuentes-N\'{u}\~{n}ez, David and Montealegre, Pedro and Rapaport, Ivan},
  title =	{{Recognizing Hereditary Properties in the Presence of Byzantine Nodes}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.26},
  URN =		{urn:nbn:de:0030-drops-251990},
  doi =		{10.4230/LIPIcs.OPODIS.2025.26},
  annote =	{Keywords: Byzantine protocols, congested clique, hereditary properties}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.19
Orientation Does Not Help with 3-Coloring a Grid in Online-LOCAL

Authors: Thomas Boudier, Filippo Casagrande, Avinandan Das, Massimo Equi, Henrik Lievonen, Augusto Modanese, and Ronja Stimpert

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
The online-LOCAL and SLOCAL models are extensions of the LOCAL model where nodes are processed in a sequential but potentially adversarial order. So far, the only problem we know of where the global memory of the online-LOCAL model has an advantage over SLOCAL is 3-coloring bipartite graphs. Recently, Chang et al. [PODC 2024] showed that even in grids, 3-coloring requires Ω(log n) locality in deterministic online-LOCAL. This result was subsequently extended by Akbari et al. [STOC 2025] to also hold in randomized online-LOCAL. However, both proofs heavily rely on the assumption that the algorithm does not have access to the orientation of the underlying grid. In this paper, we show how to lift this requirement and obtain the same lower bound (against either model) even when the algorithm is explicitly given a globally consistent orientation of the grid.
Cite as

Thomas Boudier, Filippo Casagrande, Avinandan Das, Massimo Equi, Henrik Lievonen, Augusto Modanese, and Ronja Stimpert. Orientation Does Not Help with 3-Coloring a Grid in Online-LOCAL. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{boudier_et_al:LIPIcs.OPODIS.2025.19,
  author =	{Boudier, Thomas and Casagrande, Filippo and Das, Avinandan and Equi, Massimo and Lievonen, Henrik and Modanese, Augusto and Stimpert, Ronja},
  title =	{{Orientation Does Not Help with 3-Coloring a Grid in Online-LOCAL}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.19},
  URN =		{urn:nbn:de:0030-drops-251925},
  doi =		{10.4230/LIPIcs.OPODIS.2025.19},
  annote =	{Keywords: coloring, locally checkable labeling problems, online algorithms}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.18
Distributed Download from an External Data Source in Asynchronous Faulty Settings

Authors: John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, and David Peleg

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
The distributed Data Retrieval (DR) model consists of k peers connected by a complete peer-to-peer communication network, and a trusted external data source that stores an array X of n bits (n ≫ k). Up to β k of the peers might fail in any execution (for β ∈ [0, 1)). Peers can obtain the information either by inexpensive messages passed among themselves or through expensive queries to the source array X. In the DR model, we focus on designing protocols that minimize the number of queries performed by any nonfaulty peer (a measure referred to as the query complexity) while maximizing the resiliency parameter β. The Download problem requires each nonfaulty peer to correctly learn the entire array X. Earlier work on this problem focused on synchronous communication networks and established several deterministic and randomized upper and lower bounds. Our work is the first to extend the study of distributed data retrieval to asynchronous communication networks. We address the Download problem under both the Byzantine and crash failure models. We present query-optimal deterministic solutions in an asynchronous model that can tolerate any fixed fraction β < 1 of crash faults. In the Byzantine failure model, it is known that deterministic protocols incur a query complexity of Ω(n) per peer, even under synchrony. We extend this lower bound to randomized protocols in the asynchronous model for β ≥ 1/2, and further show that for β < 1/2, a randomized protocol exists with near-optimal query complexity.
Cite as

John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, and David Peleg. Distributed Download from an External Data Source in Asynchronous Faulty Settings. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{augustine_et_al:LIPIcs.OPODIS.2025.18,
  author =	{Augustine, John and Chatterjee, Soumyottam and King, Valerie and Kumar, Manish and Meir, Shachar and Peleg, David},
  title =	{{Distributed Download from an External Data Source in Asynchronous Faulty Settings}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.18},
  URN =		{urn:nbn:de:0030-drops-251915},
  doi =		{10.4230/LIPIcs.OPODIS.2025.18},
  annote =	{Keywords: Byzantine Fault Tolerance, Blockchain Oracle, Data Retrieval Model, Distributed Download, asynchrony}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.14
A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma

Authors: Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman, and Meirav Zehavi

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
We present an algorithm for a class of n-fold ILPs whose existing algorithms in literature are often either (1) based on the augmentation framework where one starts with an arbitrary solution and then iteratively moves towards an optimal solution by solving appropriate programs; or (2) require solving a linear relaxation of the program; or (3) are based on decomposition/proximity based arguments. Combinatorial n-fold ILPs is a class of n-fold ILPs introduced and studied by Knop et al. [MP2020] that captures several other problems in a variety of domains. We present a simple and direct algorithm that solves combinatorial n-fold ILPs with unbounded non-negative variables via an application of the Steinitz lemma. Depending on the structure of the input ILP, we also improve upon the existing algorithms in the literature in terms of the running time, thereby showing an improvement that mirrors the one shown by Rohwedder [ICALP2025] contemporaneously and independently.
Cite as

Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman, and Meirav Zehavi. A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.IPEC.2025.14,
  author =	{Gupta, Sushmita and Jain, Pallavi and Seetharaman, Sanjay and Zehavi, Meirav},
  title =	{{A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.14},
  URN =		{urn:nbn:de:0030-drops-251467},
  doi =		{10.4230/LIPIcs.IPEC.2025.14},
  annote =	{Keywords: n-fold integer linear program, parameterized algorithms}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.51
Randomized Black-Box PIT for Small Depth +-Regular Non-Commutative Circuits

Authors: G. V. Sumukha Bharadwaj and S. Raja

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

Abstract
In this paper, we address the black-box polynomial identity testing (PIT) problem for non-commutative polynomials computed by +-regular circuits, a class of homogeneous circuits introduced by Arvind, Joglekar, Mukhopadhyay, and Raja (STOC 2017, Theory of Computing 2019). These circuits can compute polynomials with a number of monomials that are doubly exponential in the circuit size. They gave an efficient randomized PIT algorithm for +-regular circuits of depth 3 and posed the problem of developing an efficient black-box PIT for higher depths as an open problem. Our work makes progress on this open problem by resolving it for constant-depth +-regular circuits. We present a randomized black-box polynomial-time algorithm for +-regular circuits of any constant depth. Specifically, our algorithm runs in s^{O(d²)} time, where s and d represent the size and the depth of the +-regular circuit, respectively. Our approach combines several key techniques in a novel way. We employ a nondeterministic substitution automaton that transforms the polynomial into a structured form and utilizes polynomial sparsification along with commutative transformations to maintain non-zeroness. Additionally, we introduce matrix composition, coefficient modification via the automaton, and multi-entry outputs - methods that have not previously been applied in the context of black-box PIT. Together, these techniques enable us to effectively handle exponential degrees and doubly exponential sparsity in non-commutative settings, enabling polynomial identity testing for higher-depth circuits. In particular, we show that if f is a non-zero non-commutative polynomial in n variables over the field 𝔽, computed by a depth-d +-regular circuit of size s, then f cannot be a polynomial identity for the matrix algebra 𝕄_{N}(𝔽), where N = s^{O(d²)} and the size of the field 𝔽 depends on the degree of f. Interestingly, the size of the matrices does not depend on the degree of f. Our result can be interpreted as an Amitsur-Levitzki-type result [Amitsur and Levitzki, 1950] for polynomials computed by small-depth +-regular circuits.
Cite as

G. V. Sumukha Bharadwaj and S. Raja. Randomized Black-Box PIT for Small Depth +-Regular Non-Commutative Circuits. 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. 51:1-51:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sumukhabharadwaj_et_al:LIPIcs.FSTTCS.2025.51,
  author =	{Sumukha Bharadwaj, G. V. and Raja, S.},
  title =	{{Randomized Black-Box PIT for Small Depth +-Regular Non-Commutative Circuits}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{51:1--51:16},
  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.51},
  URN =		{urn:nbn:de:0030-drops-250949},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.51},
  annote =	{Keywords: Polynomial Identity Testing, Non-commutative Circuits, Algebraic Circuits, +-Regular Circuits, Black-Box}
}
  • Refine by Type
  • 62 Document/PDF
  • 52 Document/HTML

  • Refine by Publication Year
  • 13 2026
  • 39 2025
  • 1 2024
  • 1 2023
  • 1 2021
  • Show More...

  • Refine by Author
  • 7 King, Valerie
  • 4 Augustine, John
  • 4 Modanese, Augusto
  • 4 Rzążewski, Paweł
  • 3 Chatterjee, Soumyottam
  • Show More...

  • Refine by Series/Journal
  • 59 LIPIcs
  • 1 OASIcs
  • 2 TGDK

  • Refine by Classification
  • 15 Theory of computation → Distributed algorithms
  • 9 Mathematics of computing → Graph algorithms
  • 7 Theory of computation → Graph algorithms analysis
  • 5 Theory of computation → Dynamic graph algorithms
  • 4 Theory of computation → Computational complexity and cryptography
  • Show More...

  • Refine by Keyword
  • 4 Distributed algorithms
  • 3 Blockchain Oracle
  • 3 Byzantine Fault Tolerance
  • 3 Data Retrieval Model
  • 3 Distributed Computing
  • 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