Search Results

Documents authored by Schirneck, Martin

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.24
Fault-Tolerant ST-Diameter Oracles

Authors: Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, and Martin Schirneck

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

Abstract
We study the problem of estimating the ST-diameter of a graph that is subject to a bounded number of edge failures. An f-edge fault-tolerant ST-diameter oracle (f-FDO-ST) is a data structure that preprocesses a given graph G, two sets of vertices S,T, and positive integer f. When queried with a set F of at most f edges, the oracle returns an estimate D̂ of the ST-diameter diam(G-F,S,T), the maximum distance between vertices in S and T in G-F. The oracle has stretch σ ⩾ 1 if diam(G-F,S,T) ⩽ D̂ ⩽ σ diam(G-F,S,T). If S and T both contain all vertices, the data structure is called an f-edge fault-tolerant diameter oracle (f-FDO). An f-edge fault-tolerant distance sensitivity oracles (f-DSO) estimates the pairwise graph distances under up to f failures. We design new f-FDOs and f-FDO-STs by reducing their construction to that of all-pairs and single-source f-DSOs. We obtain several new tradeoffs between the size of the data structure, stretch guarantee, query and preprocessing times for diameter oracles by combining our black-box reductions with known results from the literature. We also provide an information-theoretic lower bound on the space requirement of approximate f-FDOs. We show that there exists a family of graphs for which any f-FDO with sensitivity f ⩾ 2 and stretch less than 5/3 requires Ω(n^{3/2}) bits of space, regardless of the query time.
Cite as

Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, and Martin Schirneck. Fault-Tolerant ST-Diameter Oracles. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ICALP.2023.24,
  author =	{Bil\`{o}, Davide and Choudhary, Keerti and Cohen, Sarel and Friedrich, Tobias and Krogmann, Simon and Schirneck, Martin},
  title =	{{Fault-Tolerant ST-Diameter Oracles}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{24:1--24:20},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.24},
  URN =		{urn:nbn:de:0030-drops-180762},
  doi =		{10.4230/LIPIcs.ICALP.2023.24},
  annote =	{Keywords: diameter oracles, distance sensitivity oracles, space lower bounds, fault-tolerant data structures}
}
Document
DOI: 10.4230/LIPIcs.FORC.2023.9
Fair Correlation Clustering in Forests

Authors: Katrin Casel, Tobias Friedrich, Martin Schirneck, and Simon Wietheger

Published in: LIPIcs, Volume 256, 4th Symposium on Foundations of Responsible Computing (FORC 2023)

Abstract
The study of algorithmic fairness received growing attention recently. This stems from the awareness that bias in the input data for machine learning systems may result in discriminatory outputs. For clustering tasks, one of the most central notions of fairness is the formalization by Chierichetti, Kumar, Lattanzi, and Vassilvitskii [NeurIPS 2017]. A clustering is said to be fair, if each cluster has the same distribution of manifestations of a sensitive attribute as the whole input set. This is motivated by various applications where the objects to be clustered have sensitive attributes that should not be over- or underrepresented. Most research on this version of fair clustering has focused on centriod-based objectives. In contrast, we discuss the applicability of this fairness notion to Correlation Clustering. The existing literature on the resulting Fair Correlation Clustering problem either presents approximation algorithms with poor approximation guarantees or severely limits the possible distributions of the sensitive attribute (often only two manifestations with a 1:1 ratio are considered). Our goal is to understand if there is hope for better results in between these two extremes. To this end, we consider restricted graph classes which allow us to characterize the distributions of sensitive attributes for which this form of fairness is tractable from a complexity point of view. While existing work on Fair Correlation Clustering gives approximation algorithms, we focus on exact solutions and investigate whether there are efficiently solvable instances. The unfair version of Correlation Clustering is trivial on forests, but adding fairness creates a surprisingly rich picture of complexities. We give an overview of the distributions and types of forests where Fair Correlation Clustering turns from tractable to intractable. As the most surprising insight, we consider the fact that the cause of the hardness of Fair Correlation Clustering is not the strictness of the fairness condition. We lift most of our results to also hold for the relaxed version of the fairness condition. Instead, the source of hardness seems to be the distribution of the sensitive attribute. On the positive side, we identify some reasonable distributions that are indeed tractable. While this tractability is only shown for forests, it may open an avenue to design reasonable approximations for larger graph classes.
Cite as

Katrin Casel, Tobias Friedrich, Martin Schirneck, and Simon Wietheger. Fair Correlation Clustering in Forests. In 4th Symposium on Foundations of Responsible Computing (FORC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 256, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{casel_et_al:LIPIcs.FORC.2023.9,
  author =	{Casel, Katrin and Friedrich, Tobias and Schirneck, Martin and Wietheger, Simon},
  title =	{{Fair Correlation Clustering in Forests}},
  booktitle =	{4th Symposium on Foundations of Responsible Computing (FORC 2023)},
  pages =	{9:1--9:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-272-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{256},
  editor =	{Talwar, Kunal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2023.9},
  URN =		{urn:nbn:de:0030-drops-179307},
  doi =		{10.4230/LIPIcs.FORC.2023.9},
  annote =	{Keywords: correlation clustering, disparate impact, fair clustering, relaxed fairness}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.22
Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances

Authors: Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, and Martin Schirneck

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
We construct data structures for extremal and pairwise distances in directed graphs in the presence of transient edge failures. Henzinger et al. [ITCS 2017] initiated the study of fault-tolerant (sensitivity) oracles for the diameter and vertex eccentricities. We extend this with a special focus on space efficiency. We present several new data structures, among them the first fault-tolerant eccentricity oracle for dual failures in subcubic space. We further prove lower bounds that show limits to approximation vs. space and diameter vs. space trade-offs for fault-tolerant oracles. They highlight key differences between data structures for undirected and directed graphs. Initially, our oracles are randomized leaning on a sampling technique frequently used in sensitivity analysis. Building on the work of Alon, Chechik, and Cohen [ICALP 2019] as well as Karthik and Parter [SODA 2021], we develop a hierarchical framework to derandomize fault-tolerant data structures. We first apply it to our own diameter and eccentricity oracles and then show its versatility by derandomizing algorithms from the literature: the distance sensitivity oracle of Ren [JCSS 2022] and the Single-Source Replacement Path algorithm of Chechik and Magen [ICALP 2020]. This way, we obtain the first deterministic distance sensitivity oracle with subcubic preprocessing time.
Cite as

Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ICALP.2022.22,
  author =	{Bil\`{o}, Davide and Choudhary, Keerti and Cohen, Sarel and Friedrich, Tobias and Schirneck, Martin},
  title =	{{Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{22:1--22:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.22},
  URN =		{urn:nbn:de:0030-drops-163633},
  doi =		{10.4230/LIPIcs.ICALP.2022.22},
  annote =	{Keywords: derandomization, diameter, eccentricity, fault-tolerant data structure, sensitivity oracle, space lower bound}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.23
Fixed-Parameter Sensitivity Oracles

Authors: Davide Bilò, Katrin Casel, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, J.A. Gregor Lagodzinski, Martin Schirneck, and Simon Wietheger

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We combine ideas from distance sensitivity oracles (DSOs) and fixed-parameter tractability (FPT) to design sensitivity oracles for FPT graph problems. An oracle with sensitivity f for an FPT problem Π on a graph G with parameter k preprocesses G in time O(g(f,k) ⋅ poly(n)). When queried with a set F of at most f edges of G, the oracle reports the answer to the Π - with the same parameter k - on the graph G-F, i.e., G deprived of F. The oracle should answer queries in a time that is significantly faster than merely running the best-known FPT algorithm on G-F from scratch. We design sensitivity oracles for the k-Path and the k-Vertex Cover problem. Our first oracle for k-Path has size O(k^{f+1}) and query time O(f min{f, log(f) + k}). We use a technique inspired by the work of Weimann and Yuster [FOCS 2010, TALG 2013] on distance sensitivity problems to reduce the space to O(({f+k}/f)^f ({f+k}/k)^k fk⋅log(n)) at the expense of increasing the query time to O(({f+k}/f)^f ({f+k}/k)^k f min{f,k}⋅log(n)). Both oracles can be modified to handle vertex-failures, but we need to replace k with 2k in all the claimed bounds. Regarding k-Vertex Cover, we design three oracles offering different trade-offs between the size and the query time. The first oracle takes O(3^{f+k}) space and has O(2^f) query time, the second one has a size of O(2^{f+k²+k}) and a query time of O(f+k²); finally, the third one takes O(fk+k²) space and can be queried in time O(1.2738^k + f). All our oracles are computable in time (at most) proportional to their size and the time needed to detect a k-path or k-vertex cover, respectively. We also provide an interesting connection between k-Vertex Cover and the fault-tolerant shortest path problem, by giving a DSO of size O(poly(f,k) ⋅ n) with query time in O(poly(f,k)), where k is the size of a vertex cover. Following our line of research connecting fault-tolerant FPT and shortest paths problems, we introduce parameterization to the computation of distance preservers. We study the problem, given a directed unweighted graph with a fixed source s and parameters f and k, to construct a polynomial-sized oracle that efficiently reports, for any target vertex v and set F of at most f edges, whether the distance from s to v increases at most by an additive term of k in G-F. The oracle size is O(2^k k²⋅n), while the time needed to answer a query is O(2^k f^ω k^ω), where ω < 2.373 is the matrix multiplication exponent. The second problem we study is about the construction of bounded-stretch fault-tolerant preservers. We construct a subgraph with O(2^{fk+f+k} k ⋅ n) edges that preserves those s-v-distances that do not increase by more than k upon failure of F. This improves significantly over the Õ(f n^{2-1/(2^f)}) bound in the unparameterized case by Bodwin et al. [ICALP 2017].
Cite as

Davide Bilò, Katrin Casel, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, J.A. Gregor Lagodzinski, Martin Schirneck, and Simon Wietheger. Fixed-Parameter Sensitivity Oracles. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ITCS.2022.23,
  author =	{Bil\`{o}, Davide and Casel, Katrin and Choudhary, Keerti and Cohen, Sarel and Friedrich, Tobias and Lagodzinski, J.A. Gregor and Schirneck, Martin and Wietheger, Simon},
  title =	{{Fixed-Parameter Sensitivity Oracles}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.23},
  URN =		{urn:nbn:de:0030-drops-156196},
  doi =		{10.4230/LIPIcs.ITCS.2022.23},
  annote =	{Keywords: data structures, distance preservers, distance sensitivity oracles, fault tolerance, fixed-parameter tractability, k-path, vertex cover}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.18
Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles

Authors: Davide Bilò, Sarel Cohen, Tobias Friedrich, and Martin Schirneck

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
Given a graph with a distinguished source vertex s, the Single Source Replacement Paths (SSRP) problem is to compute and output, for any target vertex t and edge e, the length d(s,t,e) of a shortest path from s to t that avoids a failing edge e. A Single-Source Distance Sensitivity Oracle (Single-Source DSO) is a compact data structure that answers queries of the form (t,e) by returning the distance d(s,t,e). We show how to deterministically compress the output of the SSRP problem on n-vertex, m-edge graphs with integer edge weights in the range [1,M] into a Single-Source DSO that has size O(M^{1/2} n^{3/2}) and query time Õ(1). We prove that the space requirement is optimal (up to the word size). Our techniques can also handle vertex failures within the same bounds. Chechik and Cohen [SODA 2019] presented a combinatorial, randomized Õ(m√n+n²) time SSRP algorithm for undirected and unweighted graphs. We derandomize their algorithm with the same asymptotic running time and apply our compression to obtain a deterministic Single-Source DSO with Õ(m√n+n²) preprocessing time, O(n^{3/2}) space, and Õ(1) query time. Our combinatorial Single-Source DSO has near-optimal space, preprocessing and query time for unweighted graphs, improving the preprocessing time by a √n-factor compared to previous results with o(n²) space. Grandoni and Vassilevska Williams [FOCS 2012, TALG 2020] gave an algebraic, randomized Õ(Mn^ω) time SSRP algorithm for (undirected and directed) graphs with integer edge weights in the range [1,M], where ω < 2.373 is the matrix multiplication exponent. We derandomize it for undirected graphs and apply our compression to obtain an algebraic Single-Source DSO with Õ(Mn^ω) preprocessing time, O(M^{1/2} n^{3/2}) space, and Õ(1) query time. This improves the preprocessing time of algebraic Single-Source DSOs by polynomial factors compared to previous o(n²)-space oracles. We also present further improvements of our Single-Source DSOs. We show that the query time can be reduced to a constant at the cost of increasing the size of the oracle to O(M^{1/3} n^{5/3}) and that all our oracles can be made path-reporting. On sparse graphs with m = O(n^{5/4-ε}/M^{7/4}) edges, for any constant ε > 0, we reduce the preprocessing to randomized Õ(M^{7/8} m^{1/2} n^{11/8}) = O(n^{2-ε/2}) time. To the best of our knowledge, this is the first truly subquadratic time algorithm for building Single-Source DSOs on sparse graphs.
Cite as

Davide Bilò, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ESA.2021.18,
  author =	{Bil\`{o}, Davide and Cohen, Sarel and Friedrich, Tobias and Schirneck, Martin},
  title =	{{Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.18},
  URN =		{urn:nbn:de:0030-drops-145999},
  doi =		{10.4230/LIPIcs.ESA.2021.18},
  annote =	{Keywords: derandomization, distance sensitivity oracle, single-source replacement paths, space lower bound}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.18
Space-Efficient Fault-Tolerant Diameter Oracles

Authors: Davide Bilò, Sarel Cohen, Tobias Friedrich, and Martin Schirneck

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

Abstract
We design f-edge fault-tolerant diameter oracles (f-FDO, or simply FDO if f = 1). For a given directed or undirected and possibly edge-weighted graph G with n vertices and m edges and a positive integer f, we preprocess the graph and construct a data structure that, when queried with a set F of edges, where |F| ⩽ f, returns the diameter of G-F. An f-FDO has stretch σ ⩾ 1 if the returned value D^ satisfies diam(G-F) ⩽ D^ ⩽ σ diam(G-F). For the case of a single edge failure (f = 1) in an unweighted directed graph, there exists an approximate FDO by Henzinger et al. [ITCS 2017] with stretch (1+ε), constant query time, space O(m), and a combinatorial preprocessing time of Õ(mn + n^{1.5} √{Dm/ε}), where D is the diameter. We present an FDO for directed graphs with the same stretch, query time, and space. It has a preprocessing time of Õ(mn + n²/ε), which is better for constant ε > 0. The preprocessing time nearly matches a conditional lower bound for combinatorial algorithms, also by Henzinger et al. With fast matrix multiplication, we achieve a preprocessing time of Õ(n^{2.5794} + n²/ε). We further prove an information-theoretic lower bound showing that any FDO with stretch better than 3/2 requires Ω(m) bits of space. Thus, for constant 0 < ε < 3/2, our combinatorial (1+ε)-approximate FDO is near-optimal in all parameters. In the case of multiple edge failures (f > 1) in undirected graphs with non-negative edge weights, we give an f-FDO with stretch (f+2), query time O(f²log²{n}), Õ(fn) space, and preprocessing time Õ(fm). We complement this with a lower bound excluding any finite stretch in o(fn) space. Many real-world networks have polylogarithmic diameter. We show that for those graphs and up to f = o(log n/ log log n) failures one can swap approximation for query time and space. We present an exact combinatorial f-FDO with preprocessing time mn^{1+o(1)}, query time n^o(1), and space n^{2+o(1)}. When using fast matrix multiplication instead, the preprocessing time can be improved to n^{ω+o(1)}, where ω < 2.373 is the matrix multiplication exponent.
Cite as

Davide Bilò, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. Space-Efficient Fault-Tolerant Diameter Oracles. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.MFCS.2021.18,
  author =	{Bil\`{o}, Davide and Cohen, Sarel and Friedrich, Tobias and Schirneck, Martin},
  title =	{{Space-Efficient Fault-Tolerant Diameter Oracles}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{18:1--18:16},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.18},
  URN =		{urn:nbn:de:0030-drops-144581},
  doi =		{10.4230/LIPIcs.MFCS.2021.18},
  annote =	{Keywords: derandomization, diameter, distance sensitivity oracle, fault-tolerant data structure, space lower bound}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.21
The Minimization of Random Hypergraphs

Authors: Thomas Bläsius, Tobias Friedrich, and Martin Schirneck

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
We investigate the maximum-entropy model B_{n,m,p} for random n-vertex, m-edge multi-hypergraphs with expected edge size pn. We show that the expected size of the minimization min(B_{n,m,p}), i.e., the number of inclusion-wise minimal edges of B_{n,m,p}, undergoes a phase transition with respect to m. If m is at most 1/(1-p)^{(1-p)n}, then E[|min(B_{n,m,p})|] is of order Θ(m), while for m ≥ 1/(1-p)^{(1-p+ε)n} for any ε > 0, it is Θ(2^{(H(α) + (1-α) log₂ p) n}/√n). Here, H denotes the binary entropy function and α = - (log_{1-p} m)/n. The result implies that the maximum expected number of minimal edges over all m is Θ((1+p)ⁿ/√n). Our structural findings have algorithmic implications for minimizing an input hypergraph. This has applications in the profiling of relational databases as well as for the Orthogonal Vectors problem studied in fine-grained complexity. We make several technical contributions that are of independent interest in probability. First, we improve the Chernoff-Hoeffding theorem on the tail of the binomial distribution. In detail, we show that for a binomial variable Y ∼ Bin(n,p) and any 0 < x < p, it holds that P[Y ≤ xn] = Θ(2^{-D(x‖p) n}/√n), where D is the binary Kullback-Leibler divergence between Bernoulli distributions. We give explicit upper and lower bounds on the constants hidden in the big-O notation that hold for all n. Secondly, we establish the fact that the probability of a set of cardinality i being minimal after m i.i.d. maximum-entropy trials exhibits a sharp threshold behavior at i^* = n + log_{1-p} m.
Cite as

Thomas Bläsius, Tobias Friedrich, and Martin Schirneck. The Minimization of Random Hypergraphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{blasius_et_al:LIPIcs.ESA.2020.21,
  author =	{Bl\"{a}sius, Thomas and Friedrich, Tobias and Schirneck, Martin},
  title =	{{The Minimization of Random Hypergraphs}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.21},
  URN =		{urn:nbn:de:0030-drops-128871},
  doi =		{10.4230/LIPIcs.ESA.2020.21},
  annote =	{Keywords: Chernoff-Hoeffding theorem, maximum entropy, maximization, minimization, phase transition, random hypergraphs}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2016.6
The Parameterized Complexity of Dependency Detection in Relational Databases

Authors: Thomas Bläsius, Tobias Friedrich, and Martin Schirneck

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

Abstract
We study the parameterized complexity of classical problems that arise in the profiling of relational data. Namely, we characterize the complexity of detecting unique column combinations (candidate keys), functional dependencies, and inclusion dependencies with the solution size as parameter. While the discovery of uniques and functional dependencies, respectively, turns out to be W[2]-complete, the detection of inclusion dependencies is one of the first natural problems proven to be complete for the class W[3]. As a side effect, our reductions give insights into the complexity of enumerating all minimal unique column combinations or functional dependencies.
Cite as

Thomas Bläsius, Tobias Friedrich, and Martin Schirneck. The Parameterized Complexity of Dependency Detection in Relational Databases. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{blasius_et_al:LIPIcs.IPEC.2016.6,
  author =	{Bl\"{a}sius, Thomas and Friedrich, Tobias and Schirneck, Martin},
  title =	{{The Parameterized Complexity of Dependency Detection in Relational Databases}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.6},
  URN =		{urn:nbn:de:0030-drops-69202},
  doi =		{10.4230/LIPIcs.IPEC.2016.6},
  annote =	{Keywords: parameterized complexity, unique column combination, functional dependency, inclusion dependency, profiling relational data}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.47
Towards an Atlas of Computational Learning Theory

Authors: Timo Kötzing and Martin Schirneck

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
A major part of our knowledge about Computational Learning stems from comparisons of the learning power of different learning criteria. These comparisons inform about trade-offs between learning restrictions and, more generally, learning settings; furthermore, they inform about what restrictions can be observed without losing learning power. With this paper we propose that one main focus of future research in Computational Learning should be on a structured approach to determine the relations of different learning criteria. In particular, we propose that, for small sets of learning criteria, all pairwise relations should be determined; these relations can then be easily depicted as a map, a diagram detailing the relations. Once we have maps for many relevant sets of learning criteria, the collection of these maps is an Atlas of Computational Learning Theory, informing at a glance about the landscape of computational learning just as a geographical atlas informs about the earth. In this paper we work toward this goal by providing three example maps, one pertaining to partially set-driven learning, and two pertaining to strongly monotone learning. These maps can serve as blueprints for future maps of similar base structure.
Cite as

Timo Kötzing and Martin Schirneck. Towards an Atlas of Computational Learning Theory. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kotzing_et_al:LIPIcs.STACS.2016.47,
  author =	{K\"{o}tzing, Timo and Schirneck, Martin},
  title =	{{Towards an Atlas of Computational Learning Theory}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{47:1--47:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.47},
  URN =		{urn:nbn:de:0030-drops-57483},
  doi =		{10.4230/LIPIcs.STACS.2016.47},
  annote =	{Keywords: computational learning, language learning, partially set-driven learning, strongly monotone learning}
}
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