55 Search Results for "B�cker, Sebastian"

Document
DOI: 10.4230/LIPIcs.CSL.2024.31
Remarks on Parikh-Recognizable Omega-languages

Authors: Mario Grobler, Leif Sabellek, and Sebastian Siebertz

Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)

Abstract
Several variants of Parikh automata on infinite words were recently introduced by Guha et al. [FSTTCS, 2022]. We show that one of these variants coincides with blind counter machine as introduced by Fernau and Stiebe [Fundamenta Informaticae, 2008]. Fernau and Stiebe showed that every ω-language recognized by a blind counter machine is of the form ⋃_iU_iV_i^ω for Parikh recognizable languages U_i, V_i, but blind counter machines fall short of characterizing this class of ω-languages. They posed as an open problem to find a suitable automata-based characterization. We introduce several additional variants of Parikh automata on infinite words that yield automata characterizations of classes of ω-language of the form ⋃_iU_iV_i^ω for all combinations of languages U_i, V_i being regular or Parikh-recognizable. When both U_i and V_i are regular, this coincides with Büchi’s classical theorem. We study the effect of ε-transitions in all variants of Parikh automata and show that almost all of them admit ε-elimination. Finally we study the classical decision problems with applications to model checking.
Cite as

Mario Grobler, Leif Sabellek, and Sebastian Siebertz. Remarks on Parikh-Recognizable Omega-languages. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 31:1-31:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{grobler_et_al:LIPIcs.CSL.2024.31,
  author =	{Grobler, Mario and Sabellek, Leif and Siebertz, Sebastian},
  title =	{{Remarks on Parikh-Recognizable Omega-languages}},
  booktitle =	{32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)},
  pages =	{31:1--31:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-310-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{288},
  editor =	{Murano, Aniello 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.CSL.2024.31},
  URN =		{urn:nbn:de:0030-drops-196743},
  doi =		{10.4230/LIPIcs.CSL.2024.31},
  annote =	{Keywords: Parikh automata, blind counter machines, infinite words, B\"{u}chi’s theorem}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.25
Funnelselect: Cache-Oblivious Multiple Selection

Authors: Gerth Stølting Brodal and Sebastian Wild

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

Abstract
We present the algorithm funnelselect, the first optimal randomized cache-oblivious algorithm for the multiple-selection problem. The algorithm takes as input an unsorted array of N elements and q query ranks r_1 < ⋯ < r_q, and returns in sorted order the q input elements of rank r_1, …, r_q, respectively. The algorithm uses expected and with high probability O(∑_{i = 1}^{q+1} Δ_i/B ⋅ log_{M/B} N/(Δ_i) + N/B) I/Os, where B is the external memory block size, M ≥ B^{1+ε} is the internal memory size, for some constant ε > 0, and Δ_i = r_i - r_{i-1} (assuming r_0 = 0 and r_{q+1} = N + 1). This is the best possible I/O bound in the cache-oblivious and external memory models. The result is achieved by reversing the computation of the cache-oblivious sorting algorithm funnelsort by Frigo, Leiserson, Prokop and Ramachandran [FOCS 1999], using randomly selected pivots for distributing elements, and pruning computations that with high probability are not expected to contain any query ranks.
Cite as

Gerth Stølting Brodal and Sebastian Wild. Funnelselect: Cache-Oblivious Multiple Selection. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{brodal_et_al:LIPIcs.ESA.2023.25,
  author =	{Brodal, Gerth St{\o}lting and Wild, Sebastian},
  title =	{{Funnelselect: Cache-Oblivious Multiple Selection}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{25:1--25: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.25},
  URN =		{urn:nbn:de:0030-drops-186789},
  doi =		{10.4230/LIPIcs.ESA.2023.25},
  annote =	{Keywords: Multiple selection, cache-oblivious algorithm, randomized algorithm, entropy bounds}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2023.125
Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes

Authors: Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, and Szymon Toruńczyk

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
Monadically stable and monadically NIP classes of structures were initially studied in the context of model theory and defined in logical terms. They have recently attracted attention in the area of structural graph theory, as they generalize notions such as nowhere denseness, bounded cliquewidth, and bounded twinwidth. Our main result is the - to the best of our knowledge first - purely combinatorial characterization of monadically stable classes of graphs, in terms of a property dubbed flip-flatness. A class C of graphs is flip-flat if for every fixed radius r, every sufficiently large set of vertices of a graph G ∈ C contains a large subset of vertices with mutual distance larger than r, where the distance is measured in some graph G' that can be obtained from G by performing a bounded number of flips that swap edges and non-edges within a subset of vertices. Flip-flatness generalizes the notion of uniform quasi-wideness, which characterizes nowhere dense classes and had a key impact on the combinatorial and algorithmic treatment of nowhere dense classes. To obtain this result, we develop tools that also apply to the more general monadically NIP classes, based on the notion of indiscernible sequences from model theory. We show that in monadically stable and monadically NIP classes indiscernible sequences impose a strong combinatorial structure on their definable neighborhoods. All our proofs are constructive and yield efficient algorithms.
Cite as

Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, and Szymon Toruńczyk. Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 125:1-125:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dreier_et_al:LIPIcs.ICALP.2023.125,
  author =	{Dreier, Jan and M\"{a}hlmann, Nikolas and Siebertz, Sebastian and Toru\'{n}czyk, Szymon},
  title =	{{Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{125:1--125:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.125},
  URN =		{urn:nbn:de:0030-drops-181779},
  doi =		{10.4230/LIPIcs.ICALP.2023.125},
  annote =	{Keywords: stability, NIP, combinatorial characterization, first-order model checking}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2023.128
Flipper Games for Monadically Stable Graph Classes

Authors: Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokołowski, and Szymon Toruńczyk

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
A class of graphs C is monadically stable if for every unary expansion Ĉ of C, one cannot encode - using first-order transductions - arbitrarily long linear orders in graphs from C. It is known that nowhere dense graph classes are monadically stable; these include classes of bounded maximum degree and classes that exclude a fixed topological minor. On the other hand, monadic stability is a property expressed in purely model-theoretic terms that is also suited for capturing structure in dense graphs. In this work we provide a characterization of monadic stability in terms of the Flipper game: a game on a graph played by Flipper, who in each round can complement the edge relation between any pair of vertex subsets, and Localizer, who in each round is forced to restrict the game to a ball of bounded radius. This is an analog of the Splitter game, which characterizes nowhere dense classes of graphs (Grohe, Kreutzer, and Siebertz, J. ACM '17). We give two different proofs of our main result. The first proof is based on tools borrowed from model theory, and it exposes an additional property of monadically stable graph classes that is close in spirit to definability of types. Also, as a byproduct, we show that monadic stability for graph classes coincides with monadic stability of existential formulas with two free variables, and we provide another combinatorial characterization of monadic stability via forbidden patterns. The second proof relies on the recently introduced notion of flip-flatness (Dreier, Mählmann, Siebertz, and Toruńczyk, arXiv 2206.13765) and provides an efficient algorithm to compute Flipper’s moves in a winning strategy.
Cite as

Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokołowski, and Szymon Toruńczyk. Flipper Games for Monadically Stable Graph Classes. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 128:1-128:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.ICALP.2023.128,
  author =	{Gajarsk\'{y}, Jakub and M\"{a}hlmann, Nikolas and McCarty, Rose and Ohlmann, Pierre and Pilipczuk, Micha{\l} and Przybyszewski, Wojciech and Siebertz, Sebastian and Soko{\l}owski, Marek and Toru\'{n}czyk, Szymon},
  title =	{{Flipper Games for Monadically Stable Graph Classes}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{128:1--128:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.128},
  URN =		{urn:nbn:de:0030-drops-181804},
  doi =		{10.4230/LIPIcs.ICALP.2023.128},
  annote =	{Keywords: Stability theory, structural graph theory, games}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.4
Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities

Authors: Susanne Albers and Sebastian Schubert

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We study the b-matching problem in bipartite graphs G = (S,R,E). Each vertex s ∈ S is a server with individual capacity b_s. The vertices r ∈ R are requests that arrive online and must be assigned instantly to an eligible server. The goal is to maximize the size of the constructed matching. We assume that G is a (k,d)-graph [J. Naor and D. Wajc, 2018], where k specifies a lower bound on the degree of each server and d is an upper bound on the degree of each request. This setting models matching problems in timely applications. We present tight upper and lower bounds on the performance of deterministic online algorithms. In particular, we develop a new online algorithm via a primal-dual analysis. The optimal competitive ratio tends to 1, for arbitrary k ≥ d, as the server capacities increase. Hence, nearly optimal solutions can be computed online. Our results also hold for the vertex-weighted problem extension, and thus for AdWords and auction problems in which each bidder issues individual, equally valued bids. Our bounds improve the previous best competitive ratios. The asymptotic competitiveness of 1 is a significant improvement over the previous factor of 1-1/e^{k/d}, for the interesting range where k/d ≥ 1 is small. Recall that 1-1/e ≈ 0.63. Matching problems that admit a competitive ratio arbitrarily close to 1 are rare. Prior results rely on randomization or probabilistic input models.
Cite as

Susanne Albers and Sebastian Schubert. Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:LIPIcs.ESA.2022.4,
  author =	{Albers, Susanne and Schubert, Sebastian},
  title =	{{Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.4},
  URN =		{urn:nbn:de:0030-drops-169420},
  doi =		{10.4230/LIPIcs.ESA.2022.4},
  annote =	{Keywords: online algorithms, deterministic algorithms, primal-dual analysis, b-matching, bounded-degree graph, variable vertex capacities, unweighted matching, vertex-weighted matching}
}
Document
DOI: 10.4230/DagRep.11.6.1
Computational Proteomics (Dagstuhl Seminar 21271)

Authors: Sebastian Böcker, Rebekah Gundry, Lennart Martens, and Magnus Palmblad

Published in: Dagstuhl Reports, Volume 11, Issue 6 (2021)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 21271 "Computational Proteomics". The Seminar, which took place in a hybrid fashion with both local as well as online participation due to the COVID pandemic, was built around three topics: the rapid uptake of advanced machine learning in proteomics; computational challenges across the various rapidlly evolving approaches for structural and top-down proteomics; and the computational analysis of glycoproteomics data. These three topics were the focus of three corresponding breakout sessions, which ran in parallel throughout the seminar. A fourth breakout session was created during the seminar, on the specific topic of creating a Kaggle competition based on proteomics data. The abstracts presented here first describe the three introduction talks, one for each topic. These talk abstracts are then followed by one abstract each per breakout session, documenting that breakout’s discussion and outcomes. An Executive Summary is also provided, which details the overall seminar structure alongside the most important conclusions for the three topic-derived breakouts.
Cite as

Sebastian Böcker, Rebekah Gundry, Lennart Martens, and Magnus Palmblad. Computational Proteomics (Dagstuhl Seminar 21271). In Dagstuhl Reports, Volume 11, Issue 6, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{bocker_et_al:DagRep.11.6.1,
  author =	{B\"{o}cker, Sebastian and Gundry, Rebekah and Martens, Lennart and Palmblad, Magnus},
  title =	{{Computational Proteomics (Dagstuhl Seminar 21271)}},
  pages =	{1--13},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2021},
  volume =	{11},
  number =	{6},
  editor =	{B\"{o}cker, Sebastian and Gundry, Rebekah and Martens, Lennart and Palmblad, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.11.6.1},
  URN =		{urn:nbn:de:0030-drops-155775},
  doi =		{10.4230/DagRep.11.6.1},
  annote =	{Keywords: bioinformatics, computational mass spectrometry, machine learning, proteomics}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.2
Optimal Algorithms for Online b-Matching with Variable Vertex Capacities

Authors: Susanne Albers and Sebastian Schubert

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
We study the b-matching problem, which generalizes classical online matching introduced by Karp, Vazirani and Vazirani (STOC 1990). Consider a bipartite graph G = (S ̇∪ R,E). Every vertex s ∈ S is a server with a capacity b_s, indicating the number of possible matching partners. The vertices r ∈ R are requests that arrive online and must be matched immediately to an eligible server. The goal is to maximize the cardinality of the constructed matching. In contrast to earlier work, we study the general setting where servers may have arbitrary, individual capacities. We prove that the most natural and simple online algorithms achieve optimal competitive ratios. As for deterministic algorithms, we give a greedy algorithm RelativeBalance and analyze it by extending the primal-dual framework of Devanur, Jain and Kleinberg (SODA 2013). In the area of randomized algorithms we study the celebrated Ranking algorithm by Karp, Vazirani and Vazirani. We prove that the original Ranking strategy, simply picking a random permutation of the servers, achieves an optimal competitiveness of 1-1/e, independently of the server capacities. Hence it is not necessary to resort to a reduction, replacing every server s by b_s vertices of unit capacity and to then run Ranking on this graph with ∑_{s ∈ S} b_s vertices on the left-hand side. From a theoretical point of view our result explores the power of randomization and strictly limits the amount of required randomness. From a practical point of view it leads to more efficient allocation algorithms. Technically, we show that the primal-dual framework of Devanur, Jain and Kleinberg cannot establish a competitiveness better than 1/2 for the original Ranking algorithm, choosing a permutation of the servers. Therefore, we formulate a new configuration LP for the b-matching problem and then conduct a primal-dual analysis. We extend this analysis approach to the vertex-weighted b-matching problem. Specifically, we show that the algorithm PerturbedGreedy by Aggarwal, Goel, Karande and Mehta (SODA 2011), again with a sole randomization over the set of servers, is (1-1/e)-competitive. Together with recent work by Huang and Zhang (STOC 2020), our results demonstrate that configuration LPs can be strictly stronger than standard LPs in the analysis of more complex matching problems.
Cite as

Susanne Albers and Sebastian Schubert. Optimal Algorithms for Online b-Matching with Variable Vertex Capacities. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 2:1-2:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:LIPIcs.APPROX/RANDOM.2021.2,
  author =	{Albers, Susanne and Schubert, Sebastian},
  title =	{{Optimal Algorithms for Online b-Matching with Variable Vertex Capacities}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{2:1--2:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.2},
  URN =		{urn:nbn:de:0030-drops-146957},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.2},
  annote =	{Keywords: Online algorithms, primal-dual analysis, configuration LP, b-matching, variable vertex capacities, unweighted matching, vertex-weighted matching}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.73
Recursive Backdoors for SAT

Authors: Nikolas Mählmann, Sebastian Siebertz, and Alexandre Vigny

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

Abstract
A strong backdoor in a formula φ of propositional logic to a tractable class C of formulas is a set B of variables of φ such that every assignment of the variables in B results in a formula from C. Strong backdoors of small size or with a good structure, e.g. with small backdoor treewidth, lead to efficient solutions for the propositional satisfiability problem SAT. In this paper we propose the new notion of recursive backdoors, which is inspired by the observation that in order to solve SAT we can independently recurse into the components that are created by partial assignments of variables. The quality of a recursive backdoor is measured by its recursive backdoor depth. Similar to the concept of backdoor treewidth, recursive backdoors of bounded depth include backdoors of unbounded size that have a certain treelike structure. However, the two concepts are incomparable and our results yield new tractability results for SAT.
Cite as

Nikolas Mählmann, Sebastian Siebertz, and Alexandre Vigny. Recursive Backdoors for SAT. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 73:1-73:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{mahlmann_et_al:LIPIcs.MFCS.2021.73,
  author =	{M\"{a}hlmann, Nikolas and Siebertz, Sebastian and Vigny, Alexandre},
  title =	{{Recursive Backdoors for SAT}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{73:1--73:18},
  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.73},
  URN =		{urn:nbn:de:0030-drops-145138},
  doi =		{10.4230/LIPIcs.MFCS.2021.73},
  annote =	{Keywords: Propositional satisfiability SAT, Backdoors, Parameterized Algorithms}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2021.120
Datalog-Expressibility for Monadic and Guarded Second-Order Logic

Authors: Manuel Bodirsky, Simon Knäuer, and Sebastian Rudolph

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We characterise the sentences in Monadic Second-order Logic (MSO) that are over finite structures equivalent to a Datalog program, in terms of an existential pebble game. We also show that for every class C of finite structures that can be expressed in MSO and is closed under homomorphisms, and for all 𝓁,k ∈ , there exists a canonical Datalog program Π of width (𝓁,k), that is, a Datalog program of width (𝓁,k) which is sound for C (i.e., Π only derives the goal predicate on a finite structure 𝔄 if 𝔄 ∈ C) and with the property that Π derives the goal predicate whenever some Datalog program of width (𝓁,k) which is sound for C derives the goal predicate. The same characterisations also hold for Guarded Second-order Logic (GSO), which properly extends MSO. To prove our results, we show that every class C in GSO whose complement is closed under homomorphisms is a finite union of constraint satisfaction problems (CSPs) of ω-categorical structures.
Cite as

Manuel Bodirsky, Simon Knäuer, and Sebastian Rudolph. Datalog-Expressibility for Monadic and Guarded Second-Order Logic. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 120:1-120:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bodirsky_et_al:LIPIcs.ICALP.2021.120,
  author =	{Bodirsky, Manuel and Kn\"{a}uer, Simon and Rudolph, Sebastian},
  title =	{{Datalog-Expressibility for Monadic and Guarded Second-Order Logic}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{120:1--120:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.120},
  URN =		{urn:nbn:de:0030-drops-141897},
  doi =		{10.4230/LIPIcs.ICALP.2021.120},
  annote =	{Keywords: Monadic Second-order Logic, Guarded Second-order Logic, Datalog, constraint satisfaction, homomorphism-closed, conjunctive query, primitive positive formula, pebble game, \omega-categoricity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.62
Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration

Authors: Michael B. Cohen, Aaron Sidford, and Kevin Tian

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We show that standard extragradient methods (i.e. mirror prox [Arkadi Nemirovski, 2004] and dual extrapolation [Yurii Nesterov, 2007]) recover optimal accelerated rates for first-order minimization of smooth convex functions. To obtain this result we provide fine-grained characterization of the convergence rates of extragradient methods for solving monotone variational inequalities in terms of a natural condition we call relative Lipschitzness. We further generalize this framework to handle local and randomized notions of relative Lipschitzness and thereby recover rates for box-constrained 𝓁_∞ regression based on area convexity [Jonah Sherman, 2017] and complexity bounds achieved by accelerated (randomized) coordinate descent [Zeyuan {Allen Zhu} et al., 2016; Yurii Nesterov and Sebastian U. Stich, 2017] for smooth convex function minimization.
Cite as

Michael B. Cohen, Aaron Sidford, and Kevin Tian. Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 62:1-62:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ITCS.2021.62,
  author =	{Cohen, Michael B. and Sidford, Aaron and Tian, Kevin},
  title =	{{Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{62:1--62:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.62},
  URN =		{urn:nbn:de:0030-drops-136011},
  doi =		{10.4230/LIPIcs.ITCS.2021.62},
  annote =	{Keywords: Variational inequalities, minimax optimization, acceleration, 𝓁\underline∞ regression}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.72
Lower Bounds for Off-Chain Protocols: Exploring the Limits of Plasma

Authors: Stefan Dziembowski, Grzegorz Fabiański, Sebastian Faust, and Siavash Riahi

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
Blockchain is a disruptive new technology introduced around a decade ago. It can be viewed as a method for recording timestamped transactions in a public database. Most of blockchain protocols do not scale well, i.e., they cannot process quickly large amounts of transactions. A natural idea to deal with this problem is to use the blockchain only as a timestamping service, i.e., to hash several transactions tx_1,…,tx_m into one short string, and just put this string on the blockchain, while at the same time posting the hashed transactions tx_1,…,tx_m to some public place on the Internet ("off-chain"). In this way the transactions tx_i remain timestamped, but the amount of data put on the blockchain is greatly reduced. This idea was introduced in 2017 under the name Plasma by Poon and Buterin. Shortly after this proposal, several variants of Plasma have been proposed. They are typically built on top of the Ethereum blockchain, as they strongly rely on so-called smart contracts (in order to resolve disputes between the users if some of them start cheating). Plasmas are an example of so-called off-chain protocols. In this work we initiate the study of the inherent limitations of Plasma protocols. More concretely, we show that in every Plasma system the adversary can either (a) force the honest parties to communicate a lot with the blockchain, even though they did not intend to (this is traditionally called mass exit); or (b) an honest party that wants to leave the system needs to quickly communicate large amounts of data to the blockchain. What makes these attacks particularly hard to handle in real life is that these attacks do not have so-called uniquely attributable faults, i.e. the smart contract cannot determine which party is malicious, and hence cannot force it to pay the fees for the blockchain interaction. An important implication of our result is that the benefits of two of the most prominent Plasma types, called Plasma Cash and Fungible Plasma, cannot be achieved simultaneously. Besides of the direct implications on real-life cryptocurrency research, we believe that this work may open up a new line of theoretical research, as, up to our knowledge, this is the first work that provides an impossibility result in the area of off-chain protocols.
Cite as

Stefan Dziembowski, Grzegorz Fabiański, Sebastian Faust, and Siavash Riahi. Lower Bounds for Off-Chain Protocols: Exploring the Limits of Plasma. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 72:1-72:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{dziembowski_et_al:LIPIcs.ITCS.2021.72,
  author =	{Dziembowski, Stefan and Fabia\'{n}ski, Grzegorz and Faust, Sebastian and Riahi, Siavash},
  title =	{{Lower Bounds for Off-Chain Protocols: Exploring the Limits of Plasma}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{72:1--72:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.72},
  URN =		{urn:nbn:de:0030-drops-136113},
  doi =		{10.4230/LIPIcs.ITCS.2021.72},
  annote =	{Keywords: blockchain, lower bounds, off-chain protocol, commit chain, plasma}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2020.134
When Is a Bottom-Up Deterministic Tree Translation Top-Down Deterministic?

Authors: Sebastian Maneth and Helmut Seidl

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We consider two natural subclasses of deterministic top-down tree-to-tree transducers, namely, linear and uniform-copying transducers. For both classes we show that it is decidable whether the translation of a transducer with look-ahead can be realized by a transducer without look-ahead. The transducers constructed in this way, may still make use of inspection, i.e., have an additional tree automaton restricting the domain. We provide a second procedure which decides whether inspection can be removed and if so, constructs an equivalent transducer without inspection. The construction relies on a fixpoint algorithm that determines inspection requirements and on dedicated earliest normal forms for linear as well as uniform-copying transducers which can be constructed in polynomial time. As a consequence, equivalence of these transducers can be decided in polynomial time. Applying these results to deterministic bottom-up transducers, we obtain that it is decidable whether or not their translations can be realized by deterministic uniform-copying top-down transducers without look-ahead (but with inspection) - or without both look-ahead and inspection.
Cite as

Sebastian Maneth and Helmut Seidl. When Is a Bottom-Up Deterministic Tree Translation Top-Down Deterministic?. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 134:1-134:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{maneth_et_al:LIPIcs.ICALP.2020.134,
  author =	{Maneth, Sebastian and Seidl, Helmut},
  title =	{{When Is a Bottom-Up Deterministic Tree Translation Top-Down Deterministic?}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{134:1--134:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.134},
  URN =		{urn:nbn:de:0030-drops-125416},
  doi =		{10.4230/LIPIcs.ICALP.2020.134},
  annote =	{Keywords: Top-Down Tree Transducers, Earliest Transformation, Linear Transducers, Uniform-copying Transucers, Removal of Look-ahead, Removal of Inspection}
}
Document
DOI: 10.4230/DagRep.10.1.144
Computational Metabolomics: From Cheminformatics to Machine Learning (Dagstuhl Seminar 20051)

Authors: Sebastian Böcker, Corey Broeckling, Emma Schymanski, and Nicola Zamboni

Published in: Dagstuhl Reports, Volume 10, Issue 1 (2020)

Abstract
Dagstuhl Seminar 20051 on Computational Metabolomics is the third edition of seminars on this topic and focused on Cheminformatics and Machine Learning. With the advent of higher precision instrumentation, application of metabolomics to a wider variety of small molecules, and ever increasing amounts of raw and processed data available, developments in cheminformatics and machine learning are sorely needed to facilitate interoperability and leverage further insights from these data. Following on from Seminars 17491 and 15492, this edition convened both experimental and computational experts, many of whom had attended the previous sessions and brought much-valued perspective to the week’s proceedings and discussions. Throughout the week, participants first debated on what topics to discuss in detail, before dispersing into smaller, focused working groups for more in-depth discussions. This dynamic format was found to be most productive and ensured active engagement amongst the participants. The abstracts in this report reflect these working group discussions, in addition to summarising several informal evening sessions. Action points to follow-up on after the seminar were also discussed, including future workshops and possibly another Dagstuhl seminar in late 2021 or 2022.
Cite as

Sebastian Böcker, Corey Broeckling, Emma Schymanski, and Nicola Zamboni. Computational Metabolomics: From Cheminformatics to Machine Learning (Dagstuhl Seminar 20051). In Dagstuhl Reports, Volume 10, Issue 1, pp. 144-159, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Article{bocker_et_al:DagRep.10.1.144,
  author =	{B\"{o}cker, Sebastian and Broeckling, Corey and Schymanski, Emma and Zamboni, Nicola},
  title =	{{Computational Metabolomics: From Cheminformatics to Machine Learning (Dagstuhl Seminar 20051)}},
  pages =	{144--159},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2020},
  volume =	{10},
  number =	{1},
  editor =	{B\"{o}cker, Sebastian and Broeckling, Corey and Schymanski, Emma and Zamboni, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.10.1.144},
  URN =		{urn:nbn:de:0030-drops-124036},
  doi =		{10.4230/DagRep.10.1.144},
  annote =	{Keywords: bioinformatics, chemoinformatics, computational mass spectrometry, computational metabolomics, machine learning}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.16
One-Dimensional Guarded Fragments

Authors: Emanuel Kieroński

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
We call a first-order formula one-dimensional if every maximal block of existential (or universal) quantifiers in it leaves at most one variable free. We consider the one-dimensional restrictions of the guarded fragment, GF, and the tri-guarded fragment, TGF, the latter being a recent extension of GF in which quantification for subformulas with at most two free variables need not be guarded, and which thus may be seen as a unification of GF and the two-variable fragment, FO^2. We denote the resulting formalisms, resp., GF_1, and TGF_1. We show that GF_1 has an exponential model property and NExpTime-complete satisfiability problem (that is, it is easier than full GF). For TGF_1 we show that it is decidable, has the finite model property, and its satisfiability problem is 2-ExpTime-complete (NExpTime-complete in the absence of equality). All the above-mentioned results are obtained for signatures with no constants. We finally discuss the impact of their addition, observing that constants do not spoil the decidability but increase the complexity of the satisfiability problem.
Cite as

Emanuel Kieroński. One-Dimensional Guarded Fragments. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kieronski:LIPIcs.MFCS.2019.16,
  author =	{Kiero\'{n}ski, Emanuel},
  title =	{{One-Dimensional Guarded Fragments}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{16:1--16:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.16},
  URN =		{urn:nbn:de:0030-drops-109608},
  doi =		{10.4230/LIPIcs.MFCS.2019.16},
  annote =	{Keywords: guarded fragment, two-variable logic, satisfiability, finite model property}
}
Document
DOI: 10.4230/LIPIcs.WABI.2018.23
Heuristic Algorithms for the Maximum Colorful Subtree Problem

Authors: Kai Dührkop, Marie A. Lataretu, W. Timothy J. White, and Sebastian Böcker

Published in: LIPIcs, Volume 113, 18th International Workshop on Algorithms in Bioinformatics (WABI 2018)

Abstract
In metabolomics, small molecules are structurally elucidated using tandem mass spectrometry (MS/MS); this computational task can be formulated as the Maximum Colorful Subtree problem, which is NP-hard. Unfortunately, data from a single metabolite requires us to solve hundreds or thousands of instances of this problem - and in a single Liquid Chromatography MS/MS run, hundreds or thousands of metabolites are measured. Here, we comprehensively evaluate the performance of several heuristic algorithms for the problem. Unfortunately, as is often the case in bioinformatics, the structure of the (chemically) true solution is not known to us; therefore we can only evaluate against the optimal solution of an instance. Evaluating the quality of a heuristic based on scores can be misleading: Even a slightly suboptimal solution can be structurally very different from the optimal solution, but it is the structure of a solution and not its score that is relevant for the downstream analysis. To this end, we propose a different evaluation setup: Given a set of candidate instances of which exactly one is known to be correct, the heuristic in question solves each instance to the best of its ability, producing a score for each instance, which is then used to rank the instances. We then evaluate whether the correct instance is ranked highly by the heuristic. We find that one particular heuristic consistently ranks the correct instance in a top position. We also find that the scores of the best heuristic solutions are very close to the optimal score; in contrast, the structure of the solutions can deviate significantly from the optimal structures. Integrating the heuristic allowed us to speed up computations in practice by a factor of 100-fold.
Cite as

Kai Dührkop, Marie A. Lataretu, W. Timothy J. White, and Sebastian Böcker. Heuristic Algorithms for the Maximum Colorful Subtree Problem. In 18th International Workshop on Algorithms in Bioinformatics (WABI 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 113, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{duhrkop_et_al:LIPIcs.WABI.2018.23,
  author =	{D\"{u}hrkop, Kai and Lataretu, Marie A. and White, W. Timothy J. and B\"{o}cker, Sebastian},
  title =	{{Heuristic Algorithms for the Maximum Colorful Subtree Problem}},
  booktitle =	{18th International Workshop on Algorithms in Bioinformatics (WABI 2018)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-082-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{113},
  editor =	{Parida, Laxmi and Ukkonen, Esko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2018.23},
  URN =		{urn:nbn:de:0030-drops-93256},
  doi =		{10.4230/LIPIcs.WABI.2018.23},
  annote =	{Keywords: Fragmentation trees, Computational mass spectrometry}
}
  • Refine by Author
  • 11 Böcker, Sebastian
  • 5 Siebertz, Sebastian
  • 4 Bonifati, Angela
  • 4 Böttcher, Stefan
  • 4 Hufsky, Franziska
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Finite Model Theory
  • 3 Theory of computation → Logic
  • 2 Software and its engineering → Real-time schedulability
  • 2 Theory of computation → Online algorithms
  • 1 Applied computing → Bioinformatics
  • Show More...

  • Refine by Keyword
  • 5 computational mass spectrometry
  • 4 bioinformatics
  • 3 XML compression
  • 3 computational metabolomics
  • 2 algorithms
  • Show More...

  • Refine by Type
  • 55 document

  • Refine by Publication Year
  • 14 2008
  • 13 2012
  • 6 2018
  • 6 2021
  • 3 2016
  • 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