114 Search Results for "Peleg, David"

Volume

LIPIcs, Volume 272

48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

MFCS 2023, August 28 to September 1, 2023, Bordeaux, France

Editors: Jérôme Leroux, Sylvain Lombardy, and David Peleg

Document
DOI: 10.4230/LIPIcs.DISC.2024.3
Byzantine Resilient Distributed Computing on External Data

Authors: John Augustine, Jeffin Biju, Shachar Meir, David Peleg, Srikkanth Ramachandran, and Aishwarya Thiruvengadam

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

Abstract
We study a class of problems we call retrieval problems in which a distributed network has read-only access to a trusted external data source through queries, and each peer is required to output some computable function of the data. To formalize this, we propose the Data Retrieval Model comprising two parts: (1) a congested clique network with k peers, up to β k of which can be Byzantine in every execution (for suitable values of β ∈ [0,1)); (2) a trusted source of data with no computational abilities, called the External Data Source (or just source for short). This source stores an array 𝒳 of n bits (n ≫ k), providing every peer in the congested clique read-only access to 𝒳 through queries. It is assumed that a query to the source is significantly more expensive than a message between two peers in the network. Hence, we prioritize minimizing the number of queries a peer performs over the number of messages it sends. Retrieval problems are easily solved by having each peer query all of 𝒳, so we focus on designing non-trivial query-efficient protocols for retrieval problems in the DR network that achieve low query performance per peer. Specifically, to initiate this study, we present deterministic and randomized upper and lower bounds for two fundamental problems. The first is the Download problem that requires every peer to output an array of n bits identical to 𝒳. The second problem of focus, Disjunction, requires nodes to learn if some bit in 𝒳 is set to 1.
Cite as

John Augustine, Jeffin Biju, Shachar Meir, David Peleg, Srikkanth Ramachandran, and Aishwarya Thiruvengadam. Byzantine Resilient Distributed Computing on External Data. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{augustine_et_al:LIPIcs.DISC.2024.3,
  author =	{Augustine, John and Biju, Jeffin and Meir, Shachar and Peleg, David and Ramachandran, Srikkanth and Thiruvengadam, Aishwarya},
  title =	{{Byzantine Resilient Distributed Computing on External Data}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{3:1--3:23},
  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.3},
  URN =		{urn:nbn:de:0030-drops-212304},
  doi =		{10.4230/LIPIcs.DISC.2024.3},
  annote =	{Keywords: Byzantine Fault Tolerance, Blockchain Oracle, Congested Clique, Data Retrieval Model}
}
Document
DOI: 10.4230/LIPIcs.ITP.2024.30
A Coq Formalization of Taylor Models and Power Series for Solving Ordinary Differential Equations

Authors: Sewon Park and Holger Thies

Published in: LIPIcs, Volume 309, 15th International Conference on Interactive Theorem Proving (ITP 2024)

Abstract
In exact real computation real numbers are manipulated exactly without round-off errors, making it well-suited for high precision verified computation. In recent work we propose an axiomatic formalization of exact real computation in the Coq theorem prover. The formalization admits an extended extraction mechanism that lets us extract computational content from constructive parts of proofs to efficient programs built on top of AERN, a Haskell library for exact real computation. Many processes in science and engineering are modeled by ordinary differential equations (ODEs), and often safety-critical applications depend on computing their solutions correctly. The primary goal of the current work is to extend our framework to spaces of functions and to support computation of solutions to ODEs and other essential operators. In numerical mathematics, the most common way to represent continuous functions is to use polynomial approximations. This can be modeled by so-called Taylor models, that encode a function as a polynomial and a rigorous error-bound over some domain. We define types of classical functions that do not hold any computational content and formalize Taylor models to computationally approximate those classical functions. Classical functions are defined in a way to admit classical principles in their constructions and verification. We define various basic operations on Taylor models and verify their correctness based on the classical functions that they approximate. We then shift our interest to analytic functions as a generalization of Taylor models where polynomials are replaced by infinite power series. We use the formalization to develop a theory of non-linear polynomial ODEs. From the proofs we can extract certified exact real computation programs that compute solutions of ODEs on some time interval up to any precision.
Cite as

Sewon Park and Holger Thies. A Coq Formalization of Taylor Models and Power Series for Solving Ordinary Differential Equations. In 15th International Conference on Interactive Theorem Proving (ITP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 309, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{park_et_al:LIPIcs.ITP.2024.30,
  author =	{Park, Sewon and Thies, Holger},
  title =	{{A Coq Formalization of Taylor Models and Power Series for Solving Ordinary Differential Equations}},
  booktitle =	{15th International Conference on Interactive Theorem Proving (ITP 2024)},
  pages =	{30:1--30:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-337-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{309},
  editor =	{Bertot, Yves and Kutsia, Temur and Norrish, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2024.30},
  URN =		{urn:nbn:de:0030-drops-207581},
  doi =		{10.4230/LIPIcs.ITP.2024.30},
  annote =	{Keywords: Exact real computation, Taylor models, Analytic functions, Computable analysis, Program extraction}
}
Document
Invited Paper
DOI: 10.4230/LIPIcs.MFCS.2024.1
On Key Parameters Affecting the Realizability of Degree Sequences (Invited Paper)

Authors: Amotz Bar-Noy, Toni Böhnlein, David Peleg, Yingli Ran, and Dror Rawitz

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Call a sequence d = (d_1,d_2, …, d_n) of positive integers graphic, planaric, outer-planaric, or forestic if it is the degree sequence of some arbitrary, planar, outer-planar, or cycle-free graph G, respectively. The two extreme classes of graphic and forestic sequences were given full characterizations. (The latter has a particularly simple criterion: d is forestic if and only if its volume, ∑ d ≡ ∑_i d_i, satisfies ∑ d ≤ 2n - 2.) In contrast, the problems of fully characterizing planaric and outer-planaric degree sequences are still open. In this paper, we discuss the parameters affecting the realizability of degree sequences by restricted classes of sparse graph, including planar graphs, outerplanar graphs, and some of their subclasses (e.g., 2-trees and cactus graphs). A key parameter is the volume of the sequence d, namely, ∑ d which is twice the number of edges in the realizing graph. For planar graphs, for example, an obvious consequence of Euler’s theorem is that an n-element sequence d satisfying ∑ d > 4n-6 cannot be planaric. Hence, ∑ d ≤ 4n-6 is a necessary condition for d to be planaric. What about the opposite direction? Is there an upper bound on ∑ d that guarantees that if d is graphic then it is also planaric. Does the answer depend on additional parameters? The same questions apply also to sub-classes of the planar graphs. A concrete example that is illustrated in the technical part of the paper is the class of outer-planaric degree sequences. Denoting the number of 1’s in d by ω₁, we show that for a graphic sequence d, if ω₁ = 0 then d is outer-planaric when ∑ d ≤ 3n-3, and if ω₁ > 0 then d is outer-planaric when ∑ d ≤ 3n-ω₁-2. Conversely, we show that there are graphic sequences that are not outer-planaric with ω₁ = 0 and ∑ d = 3n-2, as well as ones with ω₁ > 0 and ∑ d = 3n-ω₁-1.
Cite as

Amotz Bar-Noy, Toni Böhnlein, David Peleg, Yingli Ran, and Dror Rawitz. On Key Parameters Affecting the Realizability of Degree Sequences (Invited Paper). In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.MFCS.2024.1,
  author =	{Bar-Noy, Amotz and B\"{o}hnlein, Toni and Peleg, David and Ran, Yingli and Rawitz, Dror},
  title =	{{On Key Parameters Affecting the Realizability of Degree Sequences}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{1:1--1:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.1},
  URN =		{urn:nbn:de:0030-drops-205573},
  doi =		{10.4230/LIPIcs.MFCS.2024.1},
  annote =	{Keywords: Degree Sequences, Graph Algorithms, Graph Realization, Outer-planar Graphs}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.18
Sparse Graphic Degree Sequences Have Planar Realizations

Authors: Amotz Bar-Noy, Toni Böhnlein, David Peleg, Yingli Ran, and Dror Rawitz

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
A sequence d = (d_1,d_2, …, d_n) of positive integers is graphic if it is the degree sequence of some simple graph G, and planaric if it is the degree sequence of some simple planar graph G. It is known that if ∑ d ≤ 2n - 2, then d has a realization by a forest, hence it is trivially planaric. In this paper, we seek bounds on ∑ d that guarantee that if d is graphic then it is also planaric. We show that this holds true when ∑ d ≤ 4n-4-2ω₁, where ω₁ is the number of 1’s in d. Conversely, we show that there are graphic sequences with ∑ d = 4n-2ω₁ that are non-planaric. For the case ω₁ = 0, we show that d is planaric when ∑ d ≤ 4n-4. Conversely, we show that there is a graphic sequence with ∑ d = 4n-2 that is non-planaric. In fact, when ∑ d ≤ 4n-6-2ω₁, d can be realized by a graph with a 2-page book embedding.
Cite as

Amotz Bar-Noy, Toni Böhnlein, David Peleg, Yingli Ran, and Dror Rawitz. Sparse Graphic Degree Sequences Have Planar Realizations. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.MFCS.2024.18,
  author =	{Bar-Noy, Amotz and B\"{o}hnlein, Toni and Peleg, David and Ran, Yingli and Rawitz, Dror},
  title =	{{Sparse Graphic Degree Sequences Have Planar Realizations}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.18},
  URN =		{urn:nbn:de:0030-drops-205745},
  doi =		{10.4230/LIPIcs.MFCS.2024.18},
  annote =	{Keywords: Degree Sequences, Graph Algorithms, Graph Realization, Planar Graphs}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2023.22
Local Recurrent Problems in the SUPPORTED Model

Authors: Akanksha Agrawal, John Augustine, David Peleg, and Srikkanth Ramachandran

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

Abstract
We study the SUPPORTED model of distributed computing introduced by Schmid and Suomela [Schmid and Suomela, 2013], which generalizes the LOCAL and CONGEST models. In this framework, multiple instances of the same problem, differing from each other by the subnetwork to which they apply. recur over time, and need to be solved efficiently online. To do that, one may rely on an initial preprocessing phase for computing some useful information. This preprocessing phase makes it possible, in some cases, to obtain improved distributed algorithms, overcoming locality-based time lower bounds. Our main contribution is to expand the class of problems to which the SUPPORTED model applies, by handling also multiple recurring instances of the same problem that differ from each other by some problem specific input, and not only the subnetwork to which they apply. We illustrate this by considering two extended problem classes. The first class, denoted PCS, concerns problems where client nodes of the network need to be served, and each recurring instance applies to some Partial Client Set. The second class, denoted PFO, concerns situations where each recurrent instance of the problem includes a partially fixed output, which needs to be completed to a full consistent solution. Specifically, we propose some natural recurrent variants of the dominating set problem and the coloring problem that are of interest particularly in the distributed setting. For these problems, we show that information about the topology can be used to overcome locality-based lower bounds. We also categorize the round complexity of Locally Checkable Labellings in the SUPPORTED model for the simple case of paths. Finally we present some interesting open problems and some partial results towards resolving them.
Cite as

Akanksha Agrawal, John Augustine, David Peleg, and Srikkanth Ramachandran. Local Recurrent Problems in the SUPPORTED Model. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.OPODIS.2023.22,
  author =	{Agrawal, Akanksha and Augustine, John and Peleg, David and Ramachandran, Srikkanth},
  title =	{{Local Recurrent Problems in the SUPPORTED Model}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{22:1--22:19},
  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.22},
  URN =		{urn:nbn:de:0030-drops-195124},
  doi =		{10.4230/LIPIcs.OPODIS.2023.22},
  annote =	{Keywords: Distributed Algorithms, LOCAL Model, SUPPORTED Model}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.MFCS.2023
LIPIcs, Volume 272, MFCS 2023, Complete Volume

Authors: Jérôme Leroux, Sylvain Lombardy, and David Peleg

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
LIPIcs, Volume 272, MFCS 2023, Complete Volume
Cite as

48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 1-1302, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Proceedings{leroux_et_al:LIPIcs.MFCS.2023,
  title =	{{LIPIcs, Volume 272, MFCS 2023, Complete Volume}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{1--1302},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023},
  URN =		{urn:nbn:de:0030-drops-185332},
  doi =		{10.4230/LIPIcs.MFCS.2023},
  annote =	{Keywords: LIPIcs, Volume 272, MFCS 2023, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.MFCS.2023.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Jérôme Leroux, Sylvain Lombardy, and David Peleg

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{leroux_et_al:LIPIcs.MFCS.2023.0,
  author =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{0:i--0:xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.0},
  URN =		{urn:nbn:de:0030-drops-185349},
  doi =		{10.4230/LIPIcs.MFCS.2023.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2023.1
Exploring the Space of Colourings with Kempe Changes (Invited Talk)

Authors: Marthe Bonamy

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Kempe changes were introduced in 1879 in an attempt to prove the 4-colour theorem. They are a convenient if not crucial tool to prove various colouring theorems. Here, we consider how to navigate from a colouring to another through Kempe changes. When is it possible? How fast?
Cite as

Marthe Bonamy. Exploring the Space of Colourings with Kempe Changes (Invited Talk). In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 1:1-1:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bonamy:LIPIcs.MFCS.2023.1,
  author =	{Bonamy, Marthe},
  title =	{{Exploring the Space of Colourings with Kempe Changes}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{1:1--1:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.1},
  URN =		{urn:nbn:de:0030-drops-185350},
  doi =		{10.4230/LIPIcs.MFCS.2023.1},
  annote =	{Keywords: Graph theory, graph coloring, reconfiguration}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2023.2
Online Algorithms with Predictions (Invited Talk)

Authors: Joan Boyar

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We give an introduction to online algorithms with predictions, from an algorithms researcher’s perspective, concentrating on minimization problems.
Cite as

Joan Boyar. Online Algorithms with Predictions (Invited Talk). In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{boyar:LIPIcs.MFCS.2023.2,
  author =	{Boyar, Joan},
  title =	{{Online Algorithms with Predictions}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{2:1--2:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.2},
  URN =		{urn:nbn:de:0030-drops-185368},
  doi =		{10.4230/LIPIcs.MFCS.2023.2},
  annote =	{Keywords: Online algorithms with predictions, online algorithms with advice, random order analysis}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2023.3
Modern Parallel Algorithms (Invited Talk)

Authors: Artur Czumaj

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Recent advances in the design of efficient parallel algorithms have been largely focusing on the nowadays classical model of parallel computing called Massive Parallel Computation (MPC), which follows the framework of MapReduce systems. In this talk we will survey recent advances in the design of algorithms for graph problems for the MPC model and will mention some interesting open questions in this area.
Cite as

Artur Czumaj. Modern Parallel Algorithms (Invited Talk). In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 3:1-3:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{czumaj:LIPIcs.MFCS.2023.3,
  author =	{Czumaj, Artur},
  title =	{{Modern Parallel Algorithms}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{3:1--3:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.3},
  URN =		{urn:nbn:de:0030-drops-185378},
  doi =		{10.4230/LIPIcs.MFCS.2023.3},
  annote =	{Keywords: Distributed computing, parallel computing}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2023.4
Algebraic Reasoning for (Un)Solvable Loops (Invited Talk)

Authors: Laura Kovács

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Loop invariants describe valid program properties that hold before and after every loop iteration. As such, loop invariants are the workhorses in formalizing loop semantics and automating the formal analysis and verification of programs with loops. While automatically synthesizing loop invariants is, in general, an uncomputable problem, when considering only single-path loops with linear updates (linear loops), the strongest polynomial invariant is in fact computable [Michael Karr, 1976; Markus Müller-Olm and Helmut Seidl, 2004; Laura Kovács, 2008; Ehud Hrushovski et al., 2018]. Yet, already for loops with "only" polynomial updates, computing the strongest invariant has been an open challenge since 2004 [Markus Müller-Olm and Helmut Seidl, 2004]. In this invited talk, we first present computability results on polynomial invariant synthesis for restricted polynomial loops, called solvable loops [Rodríguez-Carbonell and Kapur, 2004]. Key to solvable loops is that one can automatically compute invariants from closed-form solutions of algebraic recurrence equations that model the loop behaviour [Laura Kovács, 2008; Andreas Humenberger et al., 2017]. We also establish a technique for invariant synthesis for classes of loops that are not solvable, termed unsolvable loops [Daneshvar Amrollahi et al., 2022]. We next study the limits of computability in deriving the (strongest) polynomial invariants for arbitrary polynomial loops. We prove that computing the strongest polynomial invariant of arbitrary, single-path polynomial loops is very hard [Julian Müllner, 2023] - namely, it is at least as hard as the Skolem problem [Graham Everest et al., 2003; Terrence Tao, 2008], a prominent algebraic problem in the theory of linear recurrences. Going beyond single-path loops, we show that the strongest polynomial invariant is uncomputable already for multi-path polynomial loops with arbitrary quadratic polynomial updates [Laura Kovács and Anton Varonka, 2023].
Cite as

Laura Kovács. Algebraic Reasoning for (Un)Solvable Loops (Invited Talk). In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 4:1-4:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kovacs:LIPIcs.MFCS.2023.4,
  author =	{Kov\'{a}cs, Laura},
  title =	{{Algebraic Reasoning for (Un)Solvable Loops}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{4:1--4:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.4},
  URN =		{urn:nbn:de:0030-drops-185385},
  doi =		{10.4230/LIPIcs.MFCS.2023.4},
  annote =	{Keywords: Symbolic Computation, Formal Methods, Loop Analysis, Polynomial Invariants}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2023.5
Sliding into the Future: Investigating Sliding Windows in Temporal Graphs (Invited Talk)

Authors: Nina Klobas, George B. Mertzios, and Paul G. Spirakis

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Graphs are fundamental tools for modelling relations among objects in various scientific fields. However, traditional static graphs have limitations when it comes to capturing the dynamic nature of real-world systems. To overcome this limitation, temporal graphs have been introduced as a framework to model graphs that change over time. In temporal graphs the edges among vertices appear and disappear at specific time steps, reflecting the temporal dynamics of the observed system, which allows us to analyse time dependent patterns and processes. In this paper we focus on the research related to sliding time windows in temporal graphs. Sliding time windows offer a way to analyse specific time intervals within the lifespan of a temporal graph. By sliding the window along the timeline, we can examine the graph’s characteristics and properties within different time periods. This paper provides an overview of the research on sliding time windows in temporal graphs. Although progress has been made in this field, there are still many interesting questions and challenges to be explored. We discuss some of the open problems and highlight their potential for future research.
Cite as

Nina Klobas, George B. Mertzios, and Paul G. Spirakis. Sliding into the Future: Investigating Sliding Windows in Temporal Graphs (Invited Talk). In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 5:1-5:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{klobas_et_al:LIPIcs.MFCS.2023.5,
  author =	{Klobas, Nina and Mertzios, George B. and Spirakis, Paul G.},
  title =	{{Sliding into the Future: Investigating Sliding Windows in Temporal Graphs}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{5:1--5:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.5},
  URN =		{urn:nbn:de:0030-drops-185397},
  doi =		{10.4230/LIPIcs.MFCS.2023.5},
  annote =	{Keywords: Temporal Graphs, Sliding Time Windows}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.6
Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes

Authors: Faisal N. Abu-Khzam, Henning Fernau, and Kevin Mann

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
The concept of Roman domination has recently been studied concerning enumerating and counting in F. N. Abu-Khzam et al. (WG 2022). More technically speaking, a function that assigns 0,1,2 to the vertices of an undirected graph is called a Roman dominating function if each vertex assigned zero has a neighbor assigned two. Such a function is called minimal if decreasing any assignment to any vertex would yield a function that is no longer a Roman dominating function. It has been shown that minimal Roman dominating functions can be enumerated with polynomial delay, i.e., between any two outputs of a solution, no more than polynomial time will elapse. This contrasts what is known about minimal dominating sets, where the question whether or not these can be enumerated with polynomial delay is open for more than 40 years. This makes the concept of Roman domination rather special and interesting among the many variants of domination problems studied in the literature, as it has been shown for several of these variants that the question of enumerating minimal solutions is tightly linked to that of enumerating minimal dominating sets, see M. Kanté et al. in SIAM J. Disc. Math., 2014. The running time of the mentioned enumeration algorithm for minimal Roman dominating functions (Abu-Khzam et al., WG 2022) could be estimated as 𝒪(1.9332ⁿ) on general graphs of order n. Here, we focus on special graph classes, as has been also done for enumerating minimal dominating sets before. More specifically, for chordal graphs, we present an enumeration algorithm running in time 𝒪(1.8940ⁿ). It is unknown if this gives a tight bound on the maximum number of minimal Roman dominating functions in chordal graphs. For interval graphs, we can lower this time bound further to 𝒪(1.7321ⁿ), which also matches the known lower bound concerning the maximum number of minimal Roman dominating functions. We can also provide a matching lower and upper bound for forests, which is (incidentally) the same, namely 𝒪^*(√3ⁿ). Furthermore, we present an optimal enumeration algorithm running in time 𝒪^*(∛3ⁿ) for split graphs and for cobipartite graphs, i.e., we can also give a matching lower bound example for these graph classes. Hence, our enumeration algorithms for interval graphs, forests, split graphs and cobipartite graphs are all optimal. The importance of our results stems from the fact that, for other types of domination problems, optimal enumeration algorithms are not always found. Interestingly, we use a different form of analysis for the running times of our different algorithms, and the branchings had to be tailored and tweaked to obtain the intended optimality results. Our Roman dominating functions enumeration algorithm for trees and forests is distinctively different from the one for minimal dominating sets by Rote (SODA 2019).Our approach also allows to give concrete formulas for counting minimal Roman dominating functions on more concrete graph families like paths.
Cite as

Faisal N. Abu-Khzam, Henning Fernau, and Kevin Mann. Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abukhzam_et_al:LIPIcs.MFCS.2023.6,
  author =	{Abu-Khzam, Faisal N. and Fernau, Henning and Mann, Kevin},
  title =	{{Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{6:1--6:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.6},
  URN =		{urn:nbn:de:0030-drops-185400},
  doi =		{10.4230/LIPIcs.MFCS.2023.6},
  annote =	{Keywords: special graph classes, counting problems, enumeration problems, domination problems, Roman domination}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.7
Counting Computations with Formulae: Logical Characterisations of Counting Complexity Classes

Authors: Antonis Achilleos and Aggeliki Chalki

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We present quantitative logics with two-step semantics based on the framework of quantitative logics introduced by Arenas et al. (2020) and the two-step semantics defined in the context of weighted logics by Gastin & Monmege (2018). We show that some of the fragments of our logics augmented with a least fixed point operator capture interesting classes of counting problems. Specifically, we answer an open question in the area of descriptive complexity of counting problems by providing logical characterisations of two subclasses of #P, namely SpanL and TotP, that play a significant role in the study of approximable counting problems. Moreover, we define logics that capture FPSPACE and SpanPSPACE, which are counting versions of PSPACE.
Cite as

Antonis Achilleos and Aggeliki Chalki. Counting Computations with Formulae: Logical Characterisations of Counting Complexity Classes. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{achilleos_et_al:LIPIcs.MFCS.2023.7,
  author =	{Achilleos, Antonis and Chalki, Aggeliki},
  title =	{{Counting Computations with Formulae: Logical Characterisations of Counting Complexity Classes}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.7},
  URN =		{urn:nbn:de:0030-drops-185412},
  doi =		{10.4230/LIPIcs.MFCS.2023.7},
  annote =	{Keywords: descriptive complexity, quantitative logics, counting problems, #P}
}
  • Refine by Author
  • 21 Peleg, David
  • 10 Bar-Noy, Amotz
  • 10 Rawitz, Dror
  • 5 Böhnlein, Toni
  • 4 Choudhary, Keerti
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 5 Graph Realization
  • 4 Degree Sequences
  • 3 Bipartite Graphs
  • 3 Graph realization
  • 2 Asynchronous networks
  • Show More...

  • Refine by Type
  • 113 document
  • 1 volume

  • Refine by Publication Year
  • 91 2023
  • 5 2021
  • 5 2022
  • 5 2024
  • 3 2020
  • Show More...

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 About DROPS Imprint Privacy Contact