18 Search Results for "Gouleakis, Themis"

Document
DOI: 10.4230/LIPIcs.SoCG.2026.80
Hardness of High-Dimensional Linear Classification

Authors: Alexander Munteanu, Simon Omlor, and Jeff M. Phillips

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem, which models linear classification. Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms. However, only O(n^d) and respectively Õ(1/ε^d) upper bounds are known and complemented by polynomial lower bounds that do not support the exponential in dimension dependence. We close this gap up to polylogarithmic terms by reduction from widely-believed hardness conjectures for Affine Degeneracy testing and k-Sum problems. Our reductions yield matching lower bounds of Ω̃(n^d) and respectively Ω̃(1/ε^d) based on Affine Degeneracy testing, and Ω̃(n^{d/2}) and respectively Ω̃(1/ε^{d/2}) conditioned on k-Sum. The first bound also holds unconditionally if the computational model is restricted to make sidedness queries, which corresponds to a widely spread setting implemented and optimized in many contemporary algorithms and computing paradigms.
Cite as

Alexander Munteanu, Simon Omlor, and Jeff M. Phillips. Hardness of High-Dimensional Linear Classification. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 80:1-80:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{munteanu_et_al:LIPIcs.SoCG.2026.80,
  author =	{Munteanu, Alexander and Omlor, Simon and Phillips, Jeff M.},
  title =	{{Hardness of High-Dimensional Linear Classification}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{80:1--80:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.80},
  URN =		{urn:nbn:de:0030-drops-258871},
  doi =		{10.4230/LIPIcs.SoCG.2026.80},
  annote =	{Keywords: Conditional Hardness, k-Sum, Affine Degeneracy, Halfspace Discrepancy, Classification}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.86
The Secretary Problem with Predictions and a Chosen Order

Authors: Helia Karisani, Mohammadreza Daneshvaramoli, Hedyeh Beyhaghi, Mohammad Hajiesmaili, and Cameron Musco

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

Abstract
We study a learning-augmented variant of the secretary problem, recently introduced by Fujii and Yoshida (2023). In this variant, the decision-maker has access to machine-learned predictions of candidate values in advance. The key challenge is to balance consistency and robustness: when the predictions are accurate, the algorithm should hire a near-best secretary; however, if they are inaccurate, the algorithm should still achieve a bounded competitive ratio. We consider both the standard Random Order Secretary Problem (ROSP), where candidates arrive in a uniform random order, and a more natural model in the learning-augmented setting, where the decision-maker can choose the arrival order based on the predicted candidate values. This model, which we call the Chosen Order Secretary Problem (COSP), can capture scenarios such as an interview schedule that is set by the decision-maker. We propose a novel algorithm that applies to both ROSP and COSP. Building on the approach of Fujii and Yoshida, our method switches from fully trusting predictions to a threshold-based rule when a large deviation of a prediction is observed. Importantly, unlike the algorithm of Fujii and Yoshida, our algorithm uses randomization as part of its decision logic. We show that if ε ∈ [0,1] denotes the maximum multiplicative prediction error, then for ROSP our algorithm achieves competitive ratio max {0.221, (1-ε)/(1+ε)}, improving on a previous bound of max {0.215, (1-ε)/(1+ε)} due to Fujii and Yoshida [Fujii and Yoshida, 2023]. For COSP, our algorithm achieves max {0.262, (1-ε)/(1+ε)}. This surpasses a 0.25 upper bound on the worst-case competitive ratio that applies to the approach of Fujii and Yoshida, and gets closer to the classical secretary benchmark of 1/e ≈ 0.368, which is an upper bound for any algorithm. Our result for COSP highlights the benefit of integrating predictions with arrival-order control in online decision-making.
Cite as

Helia Karisani, Mohammadreza Daneshvaramoli, Hedyeh Beyhaghi, Mohammad Hajiesmaili, and Cameron Musco. The Secretary Problem with Predictions and a Chosen Order. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 86:1-86:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{karisani_et_al:LIPIcs.ITCS.2026.86,
  author =	{Karisani, Helia and Daneshvaramoli, Mohammadreza and Beyhaghi, Hedyeh and Hajiesmaili, Mohammad and Musco, Cameron},
  title =	{{The Secretary Problem with Predictions and a Chosen Order}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{86:1--86: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.86},
  URN =		{urn:nbn:de:0030-drops-253734},
  doi =		{10.4230/LIPIcs.ITCS.2026.86},
  annote =	{Keywords: Secretary problem, learning-augmented algorithms, online 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.OPODIS.2025.10
Computing in a Faulty Congested Clique

Authors: Keren Censor-Hillel and Pedro Soto

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

Abstract
We study a Faulty Congested Clique model, in which an adversary may fail nodes in the network throughout the computation. We show that any task of O(nlog{n})-bit input per node can be solved in roughly n rounds, where n is the size of the network. This nearly matches the linear upper bound on the complexity of the non-faulty Congested Clique model for such problems, by learning the entire input, and it holds in the faulty model even with a linear number of faults. Our main contribution is that we establish that one can do much better by looking more closely at the computation. Given a deterministic algorithm 𝒜 for the non-faulty Congested Clique model, we show how to transform it into an algorithm 𝒜' for the faulty model, with an overhead that could be as small as some logarithmic-in-n factor, by considering refined complexity measures of 𝒜. As an exemplifying application of our approach, we show that the O(n^{1/3})-round complexity of semi-ring matrix multiplication [Censor{-}Hillel, Kaski, Korhonen, Lenzen, Paz, Suomela, PODC 2015] remains the same up to polylog factors in the faulty model, even if the adversary can fail 99% of the nodes (or any other constant fraction).
Cite as

Keren Censor-Hillel and Pedro Soto. Computing in a Faulty Congested Clique. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.OPODIS.2025.10,
  author =	{Censor-Hillel, Keren and Soto, Pedro},
  title =	{{Computing in a Faulty Congested Clique}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{10:1--10:19},
  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.10},
  URN =		{urn:nbn:de:0030-drops-251833},
  doi =		{10.4230/LIPIcs.OPODIS.2025.10},
  annote =	{Keywords: distributed computing, graph algorithms, computing with faults}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.40
On the Randomized Locality of Matching Problems in Regular Graphs

Authors: Seri Khoury, Manish Purohit, Aaron Schild, and Joshua R. Wang

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

Abstract
The main goal in distributed symmetry-breaking is to understand the locality of problems: the radius of the neighborhood that a node must explore to determine its part of a global solution. In this work, we study the locality of matching problems in the family of regular graphs, which is one of the main benchmarks for establishing lower bounds on the locality of symmetry-breaking problems, as well as for obtaining classification results. Our main results are summarized as follows: 1) Approximate matching: We develop randomized algorithms to show that (1 + ε)-approximate matching in regular graphs is truly local, i.e., the locality depends only on ε and is independent of all other graph parameters. Furthermore, as long as the degree Δ is not very small (namely, as long as Δ ≥ poly(1/ε)), this dependence is only logarithmic in 1/ε. This stands in sharp contrast to maximal matching in regular graphs which requires some dependence on the number of nodes n or the degree Δ. 2) Maximal matching: Our techniques further allow us to establish a strong separation between the node-averaged complexity and worst-case complexity of maximal matching in regular graphs, by showing that the former is only O(1). Central to our main technical contribution is a novel martingale-based analysis for the ≈ 40-year-old algorithm by Luby. In particular, our analysis shows that applying one round of Luby’s algorithm on the line graph of a Δ-regular graph results in an almost Δ/2-regular graph.
Cite as

Seri Khoury, Manish Purohit, Aaron Schild, and Joshua R. Wang. On the Randomized Locality of Matching Problems in Regular Graphs. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 40:1-40:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{khoury_et_al:LIPIcs.DISC.2025.40,
  author =	{Khoury, Seri and Purohit, Manish and Schild, Aaron and Wang, Joshua R.},
  title =	{{On the Randomized Locality of Matching Problems in Regular Graphs}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{40:1--40: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.40},
  URN =		{urn:nbn:de:0030-drops-248570},
  doi =		{10.4230/LIPIcs.DISC.2025.40},
  annote =	{Keywords: regular graphs, maximum matching, augmenting paths, distributed algorithms, Luby’s algorithm, martingales}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.25
Model-Agnostic Approximation of Constrained Forest Problems

Authors: Corinna Coupette, Alipasha Montaseri, and Christoph Lenzen

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

Abstract
Constrained Forest Problems (CFPs) as introduced by Goemans and Williamson in 1995 capture a wide range of network design problems with edge subsets as solutions, such as Minimum Spanning Tree, Steiner Forest, and Point-to-Point Connection. While individual CFPs have been studied extensively in individual computational models, a unified approach to solving general CFPs in multiple computational models has been lacking. Against this background, we present the shell-decomposition algorithm, a model-agnostic meta-algorithm that efficiently computes a (2+ε)-approximation to CFPs for a broad class of forest functions. The shell-decomposition algorithm isolates the problem-specific hardness of individual CFPs in a single computational subroutine, breaking the remainder of the computation into fundamental tasks that are studied extensively in a wide range of computational models. In contrast to prior work, our framework is compatible with the use of approximate distances. To demonstrate the power and flexibility of this result, we instantiate our algorithm for three fundamental, NP-hard CFPs (Steiner Forest, Point-to-Point Connection, and Facility Placement and Connection) in three different computational models (Congest, PRAM, and Multi-Pass Streaming). For constant ε, we obtain the following (2+ε)-approximations in the Congest model: [(1)] 1) For Steiner Forest specified via input components (SF-IC), where each node knows the identifier of one of k disjoint subsets of V (the input components), we achieve a deterministic (2+ε)-approximation in 𝒪̃(√n+D+k) rounds, where D is the hop diameter of the graph, significantly improving over the state of the art. 2) For Steiner Forest specified via symmetric connection requests (SF-SCR), where connection requests are issued to pairs of nodes u,v ∈ V, we leverage randomized equality testing to reduce the running time to 𝒪̃(√n+D), succeeding with high probability. 3) For Point-to-Point Connection, we provide a (2+ε)-approximation in 𝒪̃(√n+D) rounds. 4) For Facility Placement and Connection, a relative of non-metric Uncapacitated Facility Location, we obtain a (2+ε)-approximation in 𝒪̃(√n + D) rounds. We further show how to replace the √n+D term by the complexity of solving Partwise Aggregation, achieving (near-)universal optimality in any setting in which a solution to Partwise Aggregation in near-shortcut-quality time is known. Notably, all of our concrete results can be derived with relative ease once our model-agnostic meta-algorithm has been specified. This demonstrates the power of our modularization approach to algorithm design.
Cite as

Corinna Coupette, Alipasha Montaseri, and Christoph Lenzen. Model-Agnostic Approximation of Constrained Forest Problems. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 25:1-25:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{coupette_et_al:LIPIcs.DISC.2025.25,
  author =	{Coupette, Corinna and Montaseri, Alipasha and Lenzen, Christoph},
  title =	{{Model-Agnostic Approximation of Constrained Forest Problems}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{25:1--25:24},
  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.25},
  URN =		{urn:nbn:de:0030-drops-248420},
  doi =		{10.4230/LIPIcs.DISC.2025.25},
  annote =	{Keywords: Distributed Graph Algorithms, Model-Agnostic Algorithms, Steiner Forest}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.58
A New Impossibility Result for Online Bipartite Matching Problems

Authors: Flavio Chierichetti, Mirko Giacchini, Alessandro Panconesi, and Andrea Vattani

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

Abstract
Online Bipartite Matching with random user arrival is a fundamental problem in the online advertisement ecosystem. Over the last 30 years, many algorithms and impossibility results have been developed for this problem. In particular, the latest impossibility result was established by Manshadi, Oveis Gharan and Saberi [Manshadi et al., 2011] in 2011. Since then, several algorithms have been published in an effort to narrow the gap between the upper and the lower bounds on the competitive ratio. In this paper we show that no algorithm can achieve a competitive ratio better than 1- e/(e^e) = 0.82062…, improving upon the 0.823 upper bound presented in [Manshadi et al., 2011]. Our construction is simple to state, accompanied by a fully analytic proof, and yields a competitive ratio bound intriguingly similar to 1 - 1/e, the optimal competitive ratio for the fully adversarial Online Bipartite Matching problem. Although the tightness of our upper bound remains an open question, we show that our construction is extremal in a natural class of instances.
Cite as

Flavio Chierichetti, Mirko Giacchini, Alessandro Panconesi, and Andrea Vattani. A New Impossibility Result for Online Bipartite Matching Problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 58:1-58:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chierichetti_et_al:LIPIcs.ICALP.2025.58,
  author =	{Chierichetti, Flavio and Giacchini, Mirko and Panconesi, Alessandro and Vattani, Andrea},
  title =	{{A New Impossibility Result for Online Bipartite Matching Problems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{58:1--58:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.58},
  URN =		{urn:nbn:de:0030-drops-234354},
  doi =		{10.4230/LIPIcs.ICALP.2025.58},
  annote =	{Keywords: Bipartite Matching, Random Graphs, Competitive Ratio}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.119
Faster Semi-Streaming Matchings via Alternating Trees

Authors: Slobodan Mitrović, Anish Mukherjee, Piotr Sankowski, and Wen-Horng Sheu

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

Abstract
We design a deterministic algorithm for the (1+ε)-approximate maximum matching problem. Our primary result demonstrates that this problem can be solved in O(ε^{-6}) semi-streaming passes, improving upon the O(ε^{-19}) pass-complexity algorithm by [Fischer, Mitrović, and Uitto, STOC'22]. This contributes substantially toward resolving Open question 2 from [Assadi, SOSA'24]. Leveraging the framework introduced in [FMU'22], our algorithm achieves an analogous round complexity speed-up for computing a (1+ε)-approximate maximum matching in both the Massively Parallel Computation (MPC) and CONGEST models. The data structures maintained by our algorithm are formulated using blossom notation and represented through alternating trees. This approach enables a simplified correctness analysis by treating specific components as if operating on bipartite graphs, effectively circumventing certain technical intricacies present in prior work.
Cite as

Slobodan Mitrović, Anish Mukherjee, Piotr Sankowski, and Wen-Horng Sheu. Faster Semi-Streaming Matchings via Alternating Trees. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 119:1-119:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mitrovic_et_al:LIPIcs.ICALP.2025.119,
  author =	{Mitrovi\'{c}, Slobodan and Mukherjee, Anish and Sankowski, Piotr and Sheu, Wen-Horng},
  title =	{{Faster Semi-Streaming Matchings via Alternating Trees}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{119:1--119:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.119},
  URN =		{urn:nbn:de:0030-drops-234965},
  doi =		{10.4230/LIPIcs.ICALP.2025.119},
  annote =	{Keywords: streaming algorithms, approximation algorithms, maximum matching}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.44
Learning-Augmented Streaming Algorithms for Approximating MAX-CUT

Authors: Yinhao Dong, Pan Peng, and Ali Vakilian

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We study learning-augmented streaming algorithms for estimating the value of MAX-CUT in a graph. In the classical streaming model, while a 1/2-approximation for estimating the value of MAX-CUT can be trivially achieved with O(1) words of space, Kapralov and Krachun [STOC’19] showed that this is essentially the best possible: for any ε > 0, any (randomized) single-pass streaming algorithm that achieves an approximation ratio of at least 1/2 + ε requires Ω(n / 2^poly(1/ε)) space. We show that it is possible to surpass the 1/2-approximation barrier using just O(1) words of space by leveraging a (machine learned) oracle. Specifically, we consider streaming algorithms that are equipped with an ε-accurate oracle that for each vertex in the graph, returns its correct label in {-1, +1}, corresponding to an optimal MAX-CUT solution in the graph, with some probability 1/2 + ε, and the incorrect label otherwise. Within this framework, we present a single-pass algorithm that approximates the value of MAX-CUT to within a factor of 1/2 + Ω(ε²) with probability at least 2/3 for insertion-only streams, using only poly(1/ε) words of space. We also extend our algorithm to fully dynamic streams while maintaining a space complexity of poly(1/ε,log n) words.
Cite as

Yinhao Dong, Pan Peng, and Ali Vakilian. Learning-Augmented Streaming Algorithms for Approximating MAX-CUT. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 44:1-44:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dong_et_al:LIPIcs.ITCS.2025.44,
  author =	{Dong, Yinhao and Peng, Pan and Vakilian, Ali},
  title =	{{Learning-Augmented Streaming Algorithms for Approximating MAX-CUT}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{44:1--44:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.44},
  URN =		{urn:nbn:de:0030-drops-226728},
  doi =		{10.4230/LIPIcs.ITCS.2025.44},
  annote =	{Keywords: Learning-Augmented Algorithms, Graph Streaming Algorithms, MAX-CUT}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.45
Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs

Authors: Jinfeng Dou, Thorsten Götte, Henning Hillebrandt, Christian Scheideler, and Julian Werthmann

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We consider the distributed and parallel construction of low-diameter decompositions with strong diameter. We present algorithms for arbitrary undirected, weighted graphs and also for undirected, weighted graphs that can be separated through k ∈ Õ(1) shortest paths. This class of graphs includes planar graphs, graphs of bounded treewidth, and graphs that exclude a fixed minor K_r. Our algorithms work in the PRAM, CONGEST, and the novel HYBRID communication model and are competitive in all relevant parameters. Given 𝒟 > 0, our low-diameter decomposition algorithm divides the graph into connected clusters of strong diameter 𝒟. For an arbitrary graph, an edge e ∈ E of length 𝓁_e is cut between two clusters with probability O(𝓁_e⋅log(n)/𝒟). If the graph can be separated by k ∈ Õ(1) paths, the probability improves to O(𝓁_e⋅log(log n)/𝒟). In either case, the decompositions can be computed in Õ(1) depth and Õ(m) work in the PRAM and Õ(1) time in the HYBRID model. In CONGEST, the runtimes are Õ(HD + √n) and Õ(HD) respectively. All these results hold w.h.p. Broadly speaking, we present distributed and parallel implementations of sequential divide-and-conquer algorithms where we replace exact shortest paths with approximate shortest paths. In contrast to exact paths, these can be efficiently computed in the distributed and parallel setting [STOC '22]. Further, and perhaps more importantly, we show that instead of explicitly computing vertex-separators to enable efficient parallelization of these algorithms, it suffices to sample a few random paths of bounded length and the nodes close to them. Thereby, we do not require complex embeddings whose implementation is unknown in the distributed and parallel setting.
Cite as

Jinfeng Dou, Thorsten Götte, Henning Hillebrandt, Christian Scheideler, and Julian Werthmann. Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 45:1-45:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dou_et_al:LIPIcs.ITCS.2025.45,
  author =	{Dou, Jinfeng and G\"{o}tte, Thorsten and Hillebrandt, Henning and Scheideler, Christian and Werthmann, Julian},
  title =	{{Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{45:1--45:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.45},
  URN =		{urn:nbn:de:0030-drops-226734},
  doi =		{10.4230/LIPIcs.ITCS.2025.45},
  annote =	{Keywords: Distributed Graph Algorithms, Network Decomposition, Excluded Minor}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.26
Settling the Complexity of Testing Grainedness of Distributions, and Application to Uniformity Testing in the Huge Object Model

Authors: Clément L. Canonne, Sayantan Sen, and Joy Qiping Yang

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
In this work, we study the problem of testing m-grainedness of probability distributions over an n-element universe 𝒰, or, equivalently, of whether a probability distribution is induced by a multiset S ⊆ 𝒰 of size |S| = m. Recently, Goldreich and Ron (Computational Complexity, 2023) proved that Ω(n^c) samples are necessary for testing this property, for any c < 1 and m = Θ(n). They also conjectured that Ω(m/(log m)) samples are necessary for testing this property when m = Θ(n). In this work, we positively settle this conjecture. Using a known connection to the Distribution over Huge objects (DoHo) model introduced by Goldreich and Ron (TheoretiCS, 2023), we leverage our results to provide improved bounds for uniformity testing in the DoHo model.
Cite as

Clément L. Canonne, Sayantan Sen, and Joy Qiping Yang. Settling the Complexity of Testing Grainedness of Distributions, and Application to Uniformity Testing in the Huge Object Model. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 26:1-26:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{canonne_et_al:LIPIcs.ITCS.2025.26,
  author =	{Canonne, Cl\'{e}ment L. and Sen, Sayantan and Yang, Joy Qiping},
  title =	{{Settling the Complexity of Testing Grainedness of Distributions, and Application to Uniformity Testing in the Huge Object Model}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{26:1--26:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.26},
  URN =		{urn:nbn:de:0030-drops-226543},
  doi =		{10.4230/LIPIcs.ITCS.2025.26},
  annote =	{Keywords: Distribution testing, Uniformity testing, Huge Object Model, Lower bounds}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.66
Graph Reconstruction via MIS Queries

Authors: Christian Konrad, Conor O'Sullivan, and Victor Traistaru

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
In the Graph Reconstruction (GR) problem, a player initially only knows the vertex set V of an input graph G = (V, E) and is required to learn its set of edges E. To this end, the player submits queries to an oracle and must deduce E from the oracle’s answers. Angluin and Chen [Journal of Computer and System Sciences, 2008] resolved the number of Independent Set (IS) queries necessary and sufficient for GR on m-edge graphs. In this setting, each query consists of a subset of vertices U ⊆ V, and the oracle responds with a boolean, indicating whether U is an independent set in G. They gave algorithms that use O(m ⋅ log n) IS queries, which is best possible. In this paper, we initiate the study of GR via Maximal Independent Set (MIS) queries, a more powerful variant of IS queries. Given a query U ⊆ V, the oracle responds with any, potentially adversarially chosen, maximal independent set I ⊆ U in the induced subgraph G[U]. We show that, for GR, MIS queries are strictly more powerful than IS queries when parametrized by the maximum degree Δ of the input graph. We give tight (up to poly-logarithmic factors) upper and lower bounds for this problem: 1) We observe that the simple strategy of taking uniform independent random samples of V and submitting those to the oracle yields a non-adaptive randomized algorithm that executes O(Δ² ⋅ log n) queries and succeeds with high probability. This should be contrasted with the fact that Ω(Δ ⋅ n ⋅ log(n/Δ)) IS queries are required for such graphs, which shows that MIS queries are strictly more powerful than IS queries. Interestingly, combining the strategy of taking uniform random samples of V with the probabilistic method, we show the existence of a deterministic non-adaptive algorithm that executes O(Δ³ ⋅ log(n/Δ)) queries. 2) Regarding lower bounds, we prove that the additional Δ factor when going from randomized non-adaptive algorithms to deterministic non-adaptive algorithms is necessary. We show that every non-adaptive deterministic algorithm requires Ω(Δ³ / log² Δ) queries. For arbitrary randomized adaptive algorithms, we show that Ω(Δ²) queries are necessary in graphs of maximum degree Δ, and that Ω(log n) queries are necessary, even when the input graph is an n-vertex cycle.
Cite as

Christian Konrad, Conor O'Sullivan, and Victor Traistaru. Graph Reconstruction via MIS Queries. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 66:1-66:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{konrad_et_al:LIPIcs.ITCS.2025.66,
  author =	{Konrad, Christian and O'Sullivan, Conor and Traistaru, Victor},
  title =	{{Graph Reconstruction via MIS Queries}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{66:1--66:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.66},
  URN =		{urn:nbn:de:0030-drops-226945},
  doi =		{10.4230/LIPIcs.ITCS.2025.66},
  annote =	{Keywords: Query Complexity, Graph Reconstruction, Maximal Independent Set Queries}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.12
Learning-Augmented Online TSP on Rings, Trees, Flowers and (Almost) Everywhere Else

Authors: Evripidis Bampis, Bruno Escoffier, Themis Gouleakis, Niklas Hahn, Kostas Lakis, Golnoosh Shahkarami, and Michalis Xefteris

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
We study the Online Traveling Salesperson Problem (OLTSP) with predictions. In OLTSP, a sequence of initially unknown requests arrive over time at points (locations) of a metric space. The goal is, starting from a particular point of the metric space (the origin), to serve all these requests while minimizing the total time spent. The server moves with unit speed or is "waiting" (zero speed) at some location. We consider two variants: in the open variant, the goal is achieved when the last request is served. In the closed one, the server additionally has to return to the origin. We adopt a prediction model, introduced for OLTSP on the line [Gouleakis et al., 2023], in which the predictions correspond to the locations of the requests and extend it to more general metric spaces. We first propose an oracle-based algorithmic framework, inspired by previous work [Bampis et al., 2023]. This framework allows us to design online algorithms for general metric spaces that provide competitive ratio guarantees which, given perfect predictions, beat the best possible classical guarantee (consistency). Moreover, they degrade gracefully along with the increase in error (smoothness), but always within a constant factor of the best known competitive ratio in the classical case (robustness). Having reduced the problem to designing suitable efficient oracles, we describe how to achieve this for general metric spaces as well as specific metric spaces (rings, trees and flowers), the resulting algorithms being tractable in the latter case. The consistency guarantees of our algorithms are tight in almost all cases, and their smoothness guarantees only suffer a linear dependency on the error, which we show is necessary. Finally, we provide robustness guarantees improving previous results.
Cite as

Evripidis Bampis, Bruno Escoffier, Themis Gouleakis, Niklas Hahn, Kostas Lakis, Golnoosh Shahkarami, and Michalis Xefteris. Learning-Augmented Online TSP on Rings, Trees, Flowers and (Almost) Everywhere Else. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bampis_et_al:LIPIcs.ESA.2023.12,
  author =	{Bampis, Evripidis and Escoffier, Bruno and Gouleakis, Themis and Hahn, Niklas and Lakis, Kostas and Shahkarami, Golnoosh and Xefteris, Michalis},
  title =	{{Learning-Augmented Online TSP on Rings, Trees, Flowers and (Almost) Everywhere Else}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.12},
  URN =		{urn:nbn:de:0030-drops-186659},
  doi =		{10.4230/LIPIcs.ESA.2023.12},
  annote =	{Keywords: TSP, Online algorithms, Learning-augmented algorithms, Algorithms with predictions, Competitive analysis}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.6
Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts

Authors: Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Zuzic, and Themis Gouleakis

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
In this paper, we refine the (almost) existentially optimal distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS `21) into an (almost) universally optimal distributed Laplacian solver. Specifically, when the topology is known (i.e., the Supported-CONGEST model), we show that any Laplacian system on an n-node graph with shortcut quality SQ(G) can be solved after n^{o(1)} SQ(G) log(1/ε) rounds, where ε is the required accuracy. This almost matches our lower bound that guarantees that any correct algorithm on G requires Ω̃(SQ(G)) rounds, even for a crude solution with ε ≤ 1/2. Several important implications hold in the unknown-topology (i.e., standard CONGEST) case: for excluded-minor graphs we get an almost universally optimal algorithm that terminates in D ⋅ n^{o(1)} log(1/ε) rounds, where D is the hop-diameter of the network; as well as n^{o(1)} log (1/ε)-round algorithms for the case of SQ(G) ≤ n^{o(1)}, which holds for most networks of interest. Conditioned on improvements in state-of-the-art constructions of low-congestion shortcuts, the CONGEST results will match the Supported-CONGEST ones. Moreover, following a recent line of work in distributed algorithms, we consider a hybrid communication model which enhances CONGEST with limited global power in the form of the node-capacitated clique (NCC) model. In this model, we show the existence of a Laplacian solver with round complexity n^{o(1)} log(1/ε). The unifying thread of these results, and our main technical contribution, is the study of a novel ρ-congested generalization of the standard part-wise aggregation problem. We develop near-optimal algorithms for this primitive in the Supported-CONGEST model, almost-optimal algorithms in (standard) CONGEST (with the additional overhead due to standard barriers), as well as a simple algorithm for bounded-treewidth graphs with a quadratic dependence on the congestion ρ. This primitive can be readily used to accelerate the Laplacian solver of Forster, Goranci, Liu, Peng, Sun, and Ye, and we believe it will find further independent applications in the future.
Cite as

Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Zuzic, and Themis Gouleakis. Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{anagnostides_et_al:LIPIcs.DISC.2022.6,
  author =	{Anagnostides, Ioannis and Lenzen, Christoph and Haeupler, Bernhard and Zuzic, Goran and Gouleakis, Themis},
  title =	{{Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{6:1--6:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.6},
  URN =		{urn:nbn:de:0030-drops-171978},
  doi =		{10.4230/LIPIcs.DISC.2022.6},
  annote =	{Keywords: Distributed algorithms, Laplacian solvers, low-congestion shortcuts}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.5
Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model

Authors: Ioannis Anagnostides and Themis Gouleakis

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
The HYBRID model was recently introduced by Augustine et al. [John Augustine et al., 2020] in order to characterize from an algorithmic standpoint the capabilities of networks which combine multiple communication modes. Concretely, it is assumed that the standard LOCAL model of distributed computing is enhanced with the feature of all-to-all communication, but with very limited bandwidth, captured by the node-capacitated clique (NCC). In this work we provide several new insights on the power of hybrid networks for fundamental problems in distributed algorithms. First, we present a deterministic algorithm which solves any problem on a sparse n-node graph in 𝒪̃(√n) rounds of HYBRID, where the notation 𝒪̃(⋅) suppresses polylogarithmic factors of n. We combine this primitive with several sparsification techniques to obtain efficient distributed algorithms for general graphs. Most notably, for the all-pairs shortest paths problem we give deterministic (1 + ε)- and log n/log log n-approximate algorithms for unweighted and weighted graphs respectively with round complexity 𝒪̃(√n) in HYBRID, closely matching the performance of the state of the art randomized algorithm of Kuhn and Schneider [Kuhn and Schneider, 2020]. Moreover, we make a connection with the Ghaffari-Haeupler framework of low-congestion shortcuts [Mohsen Ghaffari and Bernhard Haeupler, 2016], leading - among others - to a (1 + ε)-approximate algorithm for Min-Cut after 𝒪(polylog (n)) rounds, with high probability, even if we restrict local edges to transfer 𝒪(log n) bits per round. Finally, we prove via a reduction from the set disjointness problem that Ω̃(n^{1/3}) rounds are required to determine the radius of an unweighted graph, as well as a (3/2 - ε)-approximation for weighted graphs. As a byproduct, we show an Ω̃(n) round-complexity lower bound for computing a (4/3 - ε)-approximation of the radius in the broadcast variant of the congested clique, even for unweighted graphs.
Cite as

Ioannis Anagnostides and Themis Gouleakis. Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{anagnostides_et_al:LIPIcs.DISC.2021.5,
  author =	{Anagnostides, Ioannis and Gouleakis, Themis},
  title =	{{Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{5:1--5:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.5},
  URN =		{urn:nbn:de:0030-drops-148077},
  doi =		{10.4230/LIPIcs.DISC.2021.5},
  annote =	{Keywords: Distributed Computing, Hybrid Model, Sparse Graphs, Deterministic Algorithms, All-Pairs Shortest Paths, Minimum Cut, Radius}
}
  • Refine by Type
  • 18 Document/PDF
  • 12 Document/HTML

  • Refine by Publication Year
  • 4 2026
  • 8 2025
  • 1 2023
  • 1 2022
  • 1 2021
  • Show More...

  • Refine by Author
  • 6 Gouleakis, Themis
  • 2 Anagnostides, Ioannis
  • 2 Canonne, Clément L.
  • 2 Diakonikolas, Ilias
  • 2 Lenzen, Christoph
  • Show More...

  • Refine by Series/Journal
  • 18 LIPIcs

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

  • Refine by Keyword
  • 2 Distributed Graph Algorithms
  • 2 maximum matching
  • 2 property testing
  • 1 Affine Degeneracy
  • 1 Algorithms
  • 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