135 Search Results for "Bonchi, Filippo"

Volume

LIPIcs, Volume 202

46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

MFCS 2021, August 23-27, 2021, Tallinn, Estonia

Editors: Filippo Bonchi and Simon J. Puglisi

Volume

LIPIcs, Volume 72

7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)

CALCO 2017, June 12-16, 2017, Ljubljana, Slovenia

Editors: Filippo Bonchi and Barbara König

Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.40
Diagrammatic Polyhedral Algebra

Authors: Filippo Bonchi, Alessandro Di Giorgio, and Paweł Sobociński

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
We extend the theory of Interacting Hopf algebras with an order primitive, and give a sound and complete axiomatisation of the prop of polyhedral cones. Next, we axiomatise an affine extension and prove soundness and completeness for the prop of polyhedra.
Cite as

Filippo Bonchi, Alessandro Di Giorgio, and Paweł Sobociński. Diagrammatic Polyhedral Algebra. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bonchi_et_al:LIPIcs.FSTTCS.2021.40,
  author =	{Bonchi, Filippo and Di Giorgio, Alessandro and Soboci\'{n}ski, Pawe{\l}},
  title =	{{Diagrammatic Polyhedral Algebra}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{40:1--40:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.40},
  URN =		{urn:nbn:de:0030-drops-155511},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.40},
  annote =	{Keywords: String diagrams, Polyhedral cones, Polyhedra}
}
Document
(Co)algebraic pearls
DOI: 10.4230/LIPIcs.CALCO.2021.9
From Farkas' Lemma to Linear Programming: an Exercise in Diagrammatic Algebra ((Co)algebraic pearls)

Authors: Filippo Bonchi, Alessandro Di Giorgio, and Fabio Zanasi

Published in: LIPIcs, Volume 211, 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)

Abstract
Farkas' lemma is a celebrated result on the solutions of systems of linear inequalities, which finds application pervasively in mathematics and computer science. In this work we show how to formulate and prove Farkas' lemma in diagrammatic polyhedral algebra, a sound and complete graphical calculus for polyhedra. Furthermore, we show how linear programs can be modeled within the calculus and how some famous duality results can be proved.
Cite as

Filippo Bonchi, Alessandro Di Giorgio, and Fabio Zanasi. From Farkas' Lemma to Linear Programming: an Exercise in Diagrammatic Algebra ((Co)algebraic pearls). In 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 211, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bonchi_et_al:LIPIcs.CALCO.2021.9,
  author =	{Bonchi, Filippo and Di Giorgio, Alessandro and Zanasi, Fabio},
  title =	{{From Farkas' Lemma to Linear Programming: an Exercise in Diagrammatic Algebra}},
  booktitle =	{9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-212-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{211},
  editor =	{Gadducci, Fabio and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2021.9},
  URN =		{urn:nbn:de:0030-drops-153643},
  doi =		{10.4230/LIPIcs.CALCO.2021.9},
  annote =	{Keywords: String diagrams, Farkas Lemma, Duality, Linear Programming}
}
Document
DOI: 10.4230/LIPIcs.CALCO.2021.10
On Doctrines and Cartesian Bicategories

Authors: Filippo Bonchi, Alessio Santamaria, Jens Seeber, and Paweł Sobociński

Published in: LIPIcs, Volume 211, 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)

Abstract
We study the relationship between cartesian bicategories and a specialisation of Lawvere’s hyperdoctrines, namely elementary existential doctrines. Both provide different ways of abstracting the structural properties of logical systems: the former in algebraic terms based on a string diagrammatic calculus, the latter in universal terms using the fundamental notion of adjoint functor. We prove that these two approaches are related by an adjunction, which can be strengthened to an equivalence by imposing further constraints on doctrines.
Cite as

Filippo Bonchi, Alessio Santamaria, Jens Seeber, and Paweł Sobociński. On Doctrines and Cartesian Bicategories. In 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 211, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bonchi_et_al:LIPIcs.CALCO.2021.10,
  author =	{Bonchi, Filippo and Santamaria, Alessio and Seeber, Jens and Soboci\'{n}ski, Pawe{\l}},
  title =	{{On Doctrines and Cartesian Bicategories}},
  booktitle =	{9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-212-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{211},
  editor =	{Gadducci, Fabio and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2021.10},
  URN =		{urn:nbn:de:0030-drops-153656},
  doi =		{10.4230/LIPIcs.CALCO.2021.10},
  annote =	{Keywords: Cartesian bicategories, elementary existential doctrines, string diagram}
}
Document
(Co)algebraic pearls
DOI: 10.4230/LIPIcs.CALCO.2021.11
Presenting Convex Sets of Probability Distributions by Convex Semilattices and Unique Bases ((Co)algebraic pearls)

Authors: Filippo Bonchi, Ana Sokolova, and Valeria Vignudelli

Published in: LIPIcs, Volume 211, 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)

Abstract
We prove that every finitely generated convex set of finitely supported probability distributions has a unique base. We apply this result to provide an alternative proof of a recent result: the algebraic theory of convex semilattices presents the monad of convex sets of probability distributions.
Cite as

Filippo Bonchi, Ana Sokolova, and Valeria Vignudelli. Presenting Convex Sets of Probability Distributions by Convex Semilattices and Unique Bases ((Co)algebraic pearls). In 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 211, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bonchi_et_al:LIPIcs.CALCO.2021.11,
  author =	{Bonchi, Filippo and Sokolova, Ana and Vignudelli, Valeria},
  title =	{{Presenting Convex Sets of Probability Distributions by Convex Semilattices and Unique Bases}},
  booktitle =	{9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)},
  pages =	{11:1--11:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-212-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{211},
  editor =	{Gadducci, Fabio and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2021.11},
  URN =		{urn:nbn:de:0030-drops-153666},
  doi =		{10.4230/LIPIcs.CALCO.2021.11},
  annote =	{Keywords: Convex sets of distributions monad, Convex semilattices, Unique base}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.MFCS.2021
LIPIcs, Volume 202, MFCS 2021, Complete Volume

Authors: Filippo Bonchi and Simon J. Puglisi

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
LIPIcs, Volume 202, MFCS 2021, Complete Volume
Cite as

46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 1-1560, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Proceedings{bonchi_et_al:LIPIcs.MFCS.2021,
  title =	{{LIPIcs, Volume 202, MFCS 2021, Complete Volume}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{1--1560},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021},
  URN =		{urn:nbn:de:0030-drops-144396},
  doi =		{10.4230/LIPIcs.MFCS.2021},
  annote =	{Keywords: LIPIcs, Volume 202, MFCS 2021, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.MFCS.2021.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Filippo Bonchi and Simon J. Puglisi

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

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

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

Copy BibTex To Clipboard

@InProceedings{bonchi_et_al:LIPIcs.MFCS.2021.0,
  author =	{Bonchi, Filippo and Puglisi, Simon J.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.0},
  URN =		{urn:nbn:de:0030-drops-144409},
  doi =		{10.4230/LIPIcs.MFCS.2021.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2021.1
Non-Axiomatizability of the Equational Theories of Positive Relation Algebras (Invited Talk)

Authors: Amina Doumane

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
In the literature, there are two ways to show that the equational theory of relations over a given signature is not finitely axiomatizable. The first-one is based on games and a construction called Rainbow construction. This method is very technical but it shows a strong result: the equational theory cannot be axiomatized by any finite set of first-order formulas. There is another method, based on a graph characterization of the equational theory of relations, which is easier to get and to understand, but proves a weaker result: the equational theory cannot be axiomatized by any finite set of equations. In this presentation, I will show how to complete the second technique to get the stronger result of non-axiomatizability by first-order formulas.
Cite as

Amina Doumane. Non-Axiomatizability of the Equational Theories of Positive Relation Algebras (Invited Talk). In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{doumane:LIPIcs.MFCS.2021.1,
  author =	{Doumane, Amina},
  title =	{{Non-Axiomatizability of the Equational Theories of Positive Relation Algebras}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.1},
  URN =		{urn:nbn:de:0030-drops-144417},
  doi =		{10.4230/LIPIcs.MFCS.2021.1},
  annote =	{Keywords: Relation algebra, Graph homomorphism, Equational theories, First-order logic}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2021.2
A Deep Dive into the Weisfeiler-Leman Algorithm (Invited Talk)

Authors: Martin Grohe

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
The Weisfeiler-Leman algorithm is a well-known combinatorial graph isomorphism test going back to work of Weisfeiler and Leman in the late 1960s. The algorithm has a surprising number of seemingly unrelated characterisations in terms of logic, algebra, linear and semi-definite programming, and graph homomorphisms. Due to its simplicity and efficiency, it is an important subroutine of all modern graph isomorphism tools. In recent years, further applications in linear optimisation, probabilistic inference, and machine learning have surfaced. In my talk, I will introduce the Weisfeiler-Leman algorithm and some extensions. I will discuss its expressiveness and the various characterisations, and I will speak about its applications.
Cite as

Martin Grohe. A Deep Dive into the Weisfeiler-Leman Algorithm (Invited Talk). In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{grohe:LIPIcs.MFCS.2021.2,
  author =	{Grohe, Martin},
  title =	{{A Deep Dive into the Weisfeiler-Leman Algorithm}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.2},
  URN =		{urn:nbn:de:0030-drops-144429},
  doi =		{10.4230/LIPIcs.MFCS.2021.2},
  annote =	{Keywords: Weisfeiler-Leman algorithm, graph isomorphism, counting homomorphisms, finite variable logics}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2021.3
Holonomic Techniques, Periods, and Decision Problems (Invited Talk)

Authors: Joël Ouaknine

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
Holonomic techniques have deep roots going back to Wallis, Euler, and Gauss, and have evolved in modern times as an important subfield of computer algebra, thanks in large part to the work of Zeilberger and others over the past three decades (see, e.g., [Doron Zeilberger, 1990; Petkovšek et al., 1997]). In this talk, I give an overview of the area, and in particular present a select survey of known and original results on decision problems for holonomic sequences and functions. I also discuss some surprising connections to the theory of periods and exponential periods, which are classical objects of study in algebraic geometry and number theory; in particular, I relate the decidability of certain decision problems for holonomic sequences to deep conjectures about periods and exponential periods, notably those due to Kontsevich and Zagier. Parts of this exposition draws upon [George Kenison et al., 2021].
Cite as

Joël Ouaknine. Holonomic Techniques, Periods, and Decision Problems (Invited Talk). In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ouaknine:LIPIcs.MFCS.2021.3,
  author =	{Ouaknine, Jo\"{e}l},
  title =	{{Holonomic Techniques, Periods, and Decision Problems}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.3},
  URN =		{urn:nbn:de:0030-drops-144431},
  doi =		{10.4230/LIPIcs.MFCS.2021.3},
  annote =	{Keywords: Holonomic and hypergeometric sequences, Inequality problems, Continued fractions, Periods}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2021.4
On Dynamic Graphs (Invited Talk)

Authors: Eva Rotenberg

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
In graph algorithms, many questions about a graph can be answered in time proportional to the size of the input, and such linear time algorithms are considered the epitome of efficiency. However, when the graph changes slightly, e.g. by the insertion or deletion of an edge or a vertex, it is undesirable to consider the entire input again. Rather, one would wish to keep some of the partial answers to questions about the old graph, and re-use them when computing answers to questions about the resulting graph. The art of handling such changes is studied in dynamic graph algorithms. In this talk, we will see some examples of ideas and techniques for efficiently maintaining knowledge about a dynamically changing graph. We will consider classical and natural graph properties such as connectivity and planarity, and we will focus on deterministic algorithms.
Cite as

Eva Rotenberg. On Dynamic Graphs (Invited Talk). In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, p. 4:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{rotenberg:LIPIcs.MFCS.2021.4,
  author =	{Rotenberg, Eva},
  title =	{{On Dynamic Graphs}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{4:1--4:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.4},
  URN =		{urn:nbn:de:0030-drops-144445},
  doi =		{10.4230/LIPIcs.MFCS.2021.4},
  annote =	{Keywords: Graph algorithms, dynamic graphs, connectivity, planarity, matching, online algorithms}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2021.5
Sublinear Algorithms for Edit Distance (Invited Talk)

Authors: Barna Saha

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
The edit distance is a way of quantifying how similar two strings are to one another by counting the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. A simple dynamic programming computes the edit distance between two strings of length n in O(n²) time, and a more sophisticated algorithm runs in time O(n+t²) where t is the distance (Landau, Myers and Schmidt, SICOMP 1998). In pursuit of obtaining faster running time, the last couple of decades have seen a flurry of research on approximating edit distance, including polylogarithmic approximation in near-linear time (Andoni, Krauthgamer and Onak, FOCS 2010), and a constant-factor approximation in subquadratic time (Chakrabarty, Das, Goldenberg, Koucký and Saks, FOCS 2018). In this talk, we will discuss recent progress that goes beyond linear time, and studies sublinear time algorithms for edit distance. We will also discuss the role preprocessing might play in designing fast algorithms. This is a joint work with Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, and Aviad Rubinstein.
Cite as

Barna Saha. Sublinear Algorithms for Edit Distance (Invited Talk). In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, p. 5:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{saha:LIPIcs.MFCS.2021.5,
  author =	{Saha, Barna},
  title =	{{Sublinear Algorithms for Edit Distance}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{5:1--5:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.5},
  URN =		{urn:nbn:de:0030-drops-144452},
  doi =		{10.4230/LIPIcs.MFCS.2021.5},
  annote =	{Keywords: Edit distance, sublinear algorithms, string processing}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.6
An Approximation Algorithm for the Matrix Tree Multiplication Problem

Authors: Mahmoud Abo-Khamis, Ryan Curtin, Sungjin Im, Benjamin Moseley, Hung Ngo, Kirk Pruhs, and Alireza Samadian

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We consider the Matrix Tree Multiplication problem. This problem is a generalization of the classic Matrix Chain Multiplication problem covered in the dynamic programming chapter of many introductory algorithms textbooks. An instance of the Matrix Tree Multiplication problem consists of a rooted tree with a matrix associated with each edge. The output is, for each leaf in the tree, the product of the matrices on the chain/path from the root to that leaf. Matrix multiplications that are shared between various chains need only be computed once, potentially being shared between different root to leaf chains. Algorithms are evaluated by the number of scalar multiplications performed. Our main result is a linear time algorithm for which the number of scalar multiplications performed is at most 15 times the optimal number of scalar multiplications.
Cite as

Mahmoud Abo-Khamis, Ryan Curtin, Sungjin Im, Benjamin Moseley, Hung Ngo, Kirk Pruhs, and Alireza Samadian. An Approximation Algorithm for the Matrix Tree Multiplication Problem. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{abokhamis_et_al:LIPIcs.MFCS.2021.6,
  author =	{Abo-Khamis, Mahmoud and Curtin, Ryan and Im, Sungjin and Moseley, Benjamin and Ngo, Hung and Pruhs, Kirk and Samadian, Alireza},
  title =	{{An Approximation Algorithm for the Matrix Tree Multiplication Problem}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.6},
  URN =		{urn:nbn:de:0030-drops-144464},
  doi =		{10.4230/LIPIcs.MFCS.2021.6},
  annote =	{Keywords: Matrix Multiplication, Approximation Algorithm}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.7
Depth-First Search in Directed Planar Graphs, Revisited

Authors: Eric Allender, Archit Chauhan, and Samir Datta

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class AC^1(UL∩co-UL), which is contained in AC². Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm for this problem was O(log^{10}n) (corresponding to the complexity class AC^{10} ⊆ NC^{11}). We also consider the problem of computing depth-first search trees in other classes of graphs, and obtain additional new upper bounds.
Cite as

Eric Allender, Archit Chauhan, and Samir Datta. Depth-First Search in Directed Planar Graphs, Revisited. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{allender_et_al:LIPIcs.MFCS.2021.7,
  author =	{Allender, Eric and Chauhan, Archit and Datta, Samir},
  title =	{{Depth-First Search in Directed Planar Graphs, Revisited}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{7:1--7:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.7},
  URN =		{urn:nbn:de:0030-drops-144478},
  doi =		{10.4230/LIPIcs.MFCS.2021.7},
  annote =	{Keywords: Depth-First Search, Planar Digraphs, Parallel Algorithms, Space-Bounded Complexity Classes}
}
  • Refine by Author
  • 18 Bonchi, Filippo
  • 5 König, Barbara
  • 4 Ouaknine, Joël
  • 3 Baldan, Paolo
  • 3 Milius, Stefan
  • Show More...

  • Refine by Classification
  • 10 Theory of computation → Formal languages and automata theory
  • 9 Theory of computation → Categorical semantics
  • 9 Theory of computation → Logic and verification
  • 9 Theory of computation → Problems, reductions and completeness
  • 7 Mathematics of computing → Graph theory
  • Show More...

  • Refine by Keyword
  • 8 coalgebra
  • 3 Graph homomorphism
  • 3 bisimulation
  • 3 coalgebras
  • 3 string diagrams
  • Show More...

  • Refine by Type
  • 133 document
  • 2 volume

  • Refine by Publication Year
  • 97 2021
  • 30 2017
  • 2 2015
  • 2 2018
  • 2 2019
  • 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 Imprint Privacy Contact