Search Results

Documents authored by Gil, Yuval

Document
DOI: 10.4230/LIPIcs.DISC.2024.22
On the Power of Graphical Reconfigurable Circuits

Authors: Yuval Emek, Yuval Gil, and Noga Harlev

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
We introduce the graphical reconfigurable circuits (GRC) model as an abstraction for distributed graph algorithms whose communication scheme is based on local mechanisms that collectively construct long-range reconfigurable channels (this is an extension to general graphs of a distributed computational model recently introduced by Feldmann et al. (JCB 2022) for hexagonal grids). The crux of the GRC model lies in its modest assumptions: (1) the individual nodes are computationally weak, with state space bounded independently of any global graph parameter; and (2) the reconfigurable communication channels are highly restrictive, only carrying information-less signals (a.k.a. beeps). Despite these modest assumptions, we prove that GRC algorithms can solve many important distributed tasks efficiently, i.e., in polylogarithmic time. On the negative side, we establish various runtime lower bounds, proving that for other tasks, GRC algorithms (if they exist) are doomed to be slow.
Cite as

Yuval Emek, Yuval Gil, and Noga Harlev. On the Power of Graphical Reconfigurable Circuits. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.DISC.2024.22,
  author =	{Emek, Yuval and Gil, Yuval and Harlev, Noga},
  title =	{{On the Power of Graphical Reconfigurable Circuits}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.22},
  URN =		{urn:nbn:de:0030-drops-212487},
  doi =		{10.4230/LIPIcs.DISC.2024.22},
  annote =	{Keywords: graphical reconfigurable circuits, bounded uniformity, beeping}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2023.16
Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs

Authors: Yuval Gil

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
We design new deterministic CONGEST approximation algorithms for maximum weight independent set (MWIS) in sparse graphs. As our main results, we obtain new Δ(1+ε)-approximation algorithms as well as algorithms whose approximation ratio depend strictly on α, in graphs with maximum degree Δ and arboricity α. For (deterministic) Δ(1+ε)-approximation, the current state-of-the-art is due to a recent breakthrough by Faour et al. [SODA 2023] that showed an O(log² (Δ W)⋅ log (1/ε)+log ^{*}n)-round algorithm, where W is the largest node-weight (this bound translates to O(log² n⋅log (1/ε)) under the common assumption that W = poly(n)). As for α-dependent approximations, a deterministic CONGEST (8(1+ε)⋅α)-approximation algorithm with runtime O(log³ n⋅log (1/ε)) can be derived by combining the aforementioned algorithm of Faour et al. with a method presented by Kawarabayashi et al. [DISC 2020]. As our main results, we show the following. - A deterministic CONGEST algorithm that computes an α^{1+τ}-approximation for MWIS in O(log nlog α) rounds for any constant τ > 0. To the best of our knowledge, this is the fastest runtime of any deterministic non-trivial approximation algorithm for MWIS to date. Furthermore, for the large class of graphs where α = Δ^{1-Θ(1)}, it implies a deterministic Δ^{1-Θ(1)}-approximation algorithm with a runtime of O(log nlog α) which improves upon the result of Faour et al. in both approximation ratio (by a Δ^{Θ(1)} factor) and runtime (by an O(log n/log α) factor). - A deterministic CONGEST algorithm that computes an O(α)-approximation for MWIS in O(α^{τ}log n) rounds for any (desirably small) constant τ > 0. This improves the runtime of the best known deterministic O(α)-approximation algorithm in the case that α = O(polylog n). This also leads to a deterministic Δ(1+ε)-approximation algorithm with a runtime of O(α^{τ}log nlog (1/ε)) which improves upon the runtime of Faour et al. in the case that α = O(polylog n). - A deterministic CONGEST algorithm that computes a (⌊(2+ε)α⌋)-approximation for MWIS in O(αlog n) rounds. This improves upon the best known α-dependent approximation ratio by a constant factor. - A deterministic CONGEST algorithm that computes a 2d²-approximation for MWIS in time O(d²+log ^{*}n) in a directed graph with out-degree at most d. The dependency on n is (asymptotically) optimal due to a lower bound by Czygrinow et al. [DISC 2008] and Lenzen and Wattenhofer [DISC 2008]. We note that a key ingredient to all of our algorithms is a novel deterministic method that computes a high-weight subset of nodes whose induced subgraph is sparse.
Cite as

Yuval Gil. Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gil:LIPIcs.OPODIS.2023.16,
  author =	{Gil, Yuval},
  title =	{{Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{16:1--16:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.16},
  URN =		{urn:nbn:de:0030-drops-195067},
  doi =		{10.4230/LIPIcs.OPODIS.2023.16},
  annote =	{Keywords: Approximation algorithms, Sparse graphs, The CONGEST model}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.44
Online Algorithms with Randomly Infused Advice

Authors: Yuval Emek, Yuval Gil, Maciej Pacut, and Stefan Schmid

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

Abstract
We introduce a novel method for the rigorous quantitative evaluation of online algorithms that relaxes the "radical worst-case" perspective of classic competitive analysis. In contrast to prior work, our method, referred to as randomly infused advice (RIA), does not make any assumptions about the input sequence and does not rely on the development of designated online algorithms. Rather, it can be applied to existing online randomized algorithms, introducing a means to evaluate their performance in scenarios that lie outside the radical worst-case regime. More concretely, an online algorithm ALG with RIA benefits from pieces of advice generated by an omniscient but not entirely reliable oracle. The crux of the new method is that the advice is provided to ALG by writing it into the buffer ℬ from which ALG normally reads its random bits, hence allowing us to augment it through a very simple and non-intrusive interface. The (un)reliability of the oracle is captured via a parameter 0 ≤ α ≤ 1 that determines the probability (per round) that the advice is successfully infused by the oracle; if the advice is not infused, which occurs with probability 1 - α, then the buffer ℬ contains fresh random bits (as in the classic online setting). The applicability of the new RIA method is demonstrated by applying it to three extensively studied online problems: paging, uniform metrical task systems, and online set cover. For these problems, we establish new upper bounds on the competitive ratio of classic online algorithms that improve as the infusion parameter α increases. These are complemented with (often tight) lower bounds on the competitive ratio of online algorithms with RIA for the three problems.
Cite as

Yuval Emek, Yuval Gil, Maciej Pacut, and Stefan Schmid. Online Algorithms with Randomly Infused Advice. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 44:1-44:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.ESA.2023.44,
  author =	{Emek, Yuval and Gil, Yuval and Pacut, Maciej and Schmid, Stefan},
  title =	{{Online Algorithms with Randomly Infused Advice}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{44:1--44:19},
  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.44},
  URN =		{urn:nbn:de:0030-drops-186970},
  doi =		{10.4230/LIPIcs.ESA.2023.44},
  annote =	{Keywords: Online algorithms, competitive analysis, advice}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.27
Design of Self-Stabilizing Approximation Algorithms via a Primal-Dual Approach

Authors: Yuval Emek, Yuval Gil, and Noga Harlev

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
Self-stabilization is an important concept in the realm of fault-tolerant distributed computing. In this paper, we propose a new approach that relies on the properties of linear programming duality to obtain self-stabilizing approximation algorithms for distributed graph optimization problems. The power of this new approach is demonstrated by the following results: - A self-stabilizing 2(1+ε)-approximation algorithm for minimum weight vertex cover that converges in O(logΔ /(εlog log Δ)) synchronous rounds. - A self-stabilizing Δ-approximation algorithm for maximum weight independent set that converges in O(Δ+log^* n) synchronous rounds. - A self-stabilizing ((2ρ+1)(1+ε))-approximation algorithm for minimum weight dominating set in ρ-arboricity graphs that converges in O((logΔ)/ε) synchronous rounds. In all of the above, Δ denotes the maximum degree. Our technique improves upon previous results in terms of time complexity while incurring only an additive O(log n) overhead to the message size. In addition, to the best of our knowledge, we provide the first self-stabilizing algorithms for the weighted versions of minimum vertex cover and maximum independent set.
Cite as

Yuval Emek, Yuval Gil, and Noga Harlev. Design of Self-Stabilizing Approximation Algorithms via a Primal-Dual Approach. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.OPODIS.2022.27,
  author =	{Emek, Yuval and Gil, Yuval and Harlev, Noga},
  title =	{{Design of Self-Stabilizing Approximation Algorithms via a Primal-Dual Approach}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{27:1--27:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.27},
  URN =		{urn:nbn:de:0030-drops-176474},
  doi =		{10.4230/LIPIcs.OPODIS.2022.27},
  annote =	{Keywords: self-stabilization, approximation algorithms, primal-dual}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.20
Locally Restricted Proof Labeling Schemes

Authors: Yuval Emek, Yuval Gil, and Shay Kutten

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

Abstract
Introduced by Korman, Kutten, and Peleg (PODC 2005), a proof labeling scheme (PLS) is a distributed verification system dedicated to evaluating if a given configured graph satisfies a certain property. It involves a centralized prover, whose role is to provide proof that a given configured graph is a yes-instance by means of assigning labels to the nodes, and a distributed verifier, whose role is to verify the validity of the given proof via local access to the assigned labels. In this paper, we introduce the notion of a locally restricted PLS in which the prover’s power is restricted to that of a LOCAL algorithm with a polylogarithmic number of rounds. To circumvent inherent impossibilities of PLSs in the locally restricted setting, we turn to models that relax the correctness requirements by allowing the verifier to accept some no-instances as long as they are not "too far" from satisfying the property in question. To this end, we evaluate (1) distributed graph optimization problems (OptDGPs) based on the notion of an approximate proof labeling scheme (APLS) (analogous to the type of relaxation used in sequential approximation algorithms); and (2) configured graph families (CGFs) based on the notion of a testing proof labeling schemes (TPLS) (analogous to the type of relaxation used in property testing algorithms). The main contribution of the paper comes in the form of two generic compilers, one for OptDGPs and one for CGFs: given a black-box access to an APLS (resp., PLS) for a large class of OptDGPs (resp., CGFs), the compiler produces a locally restricted APLS (resp., TPLS) for the same problem, while losing at most a (1 + ε) factor in the scheme’s relaxation guarantee. An appealing feature of the two compilers is that they only require a logarithmic additive label size overhead.
Cite as

Yuval Emek, Yuval Gil, and Shay Kutten. Locally Restricted Proof Labeling Schemes. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 20:1-20:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.DISC.2022.20,
  author =	{Emek, Yuval and Gil, Yuval and Kutten, Shay},
  title =	{{Locally Restricted Proof Labeling Schemes}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{20:1--20:22},
  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.20},
  URN =		{urn:nbn:de:0030-drops-172111},
  doi =		{10.4230/LIPIcs.DISC.2022.20},
  annote =	{Keywords: proof labeling schemes, generic compilers, SLOCAL algorithms}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.20
Twenty-Two New Approximate Proof Labeling Schemes

Authors: Yuval Emek and Yuval Gil

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
Introduced by Korman, Kutten, and Peleg (Distributed Computing 2005), a proof labeling scheme (PLS) is a system dedicated to verifying that a given configuration graph satisfies a certain property. It is composed of a centralized prover, whose role is to generate a proof for yes-instances in the form of an assignment of labels to the nodes, and a distributed verifier, whose role is to verify the validity of the proof by local means and accept it if and only if the property is satisfied. To overcome lower bounds on the label size of PLSs for certain graph properties, Censor-Hillel, Paz, and Perry (SIROCCO 2017) introduced the notion of an approximate proof labeling scheme (APLS) that allows the verifier to accept also some no-instances as long as they are not "too far" from satisfying the property. The goal of the current paper is to advance our understanding of the power and limitations of APLSs. To this end, we formulate the notion of APLSs in terms of distributed graph optimization problems (OptDGPs) and develop two generic methods for the design of APLSs. These methods are then applied to various classic OptDGPs, obtaining twenty-two new APLSs. An appealing characteristic of our APLSs is that they are all sequentially efficient in the sense that both the prover and the verifier are required to run in (sequential) polynomial time. On the negative side, we establish "combinatorial" lower bounds on the label size for some of the aforementioned OptDGPs that demonstrate the optimality of our corresponding APLSs. For other OptDGPs, we establish conditional lower bounds that exploit the sequential efficiency of the verifier alone (under the assumption that NP ≠ co-NP) or that of both the verifier and the prover (under the assumption that P ≠ NP, with and without the unique games conjecture).
Cite as

Yuval Emek and Yuval Gil. Twenty-Two New Approximate Proof Labeling Schemes. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.DISC.2020.20,
  author =	{Emek, Yuval and Gil, Yuval},
  title =	{{Twenty-Two New Approximate Proof Labeling Schemes}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.20},
  URN =		{urn:nbn:de:0030-drops-130983},
  doi =		{10.4230/LIPIcs.DISC.2020.20},
  annote =	{Keywords: proof labeling schemes, distributed graph problems, approximation algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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