2021 [ nach oben ]

Bilò, Davide; Cohen, Sarel; Friedrich, Tobias; Schirneck, Martin Near-Optimal Deterministic Single-Source Distance Sensitivity OraclesEuropean Symposium on Algorithms (ESA) 2021: 18:1–18:17
[ Abstract ] [ BibTeX ] [ Download ]
 
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 compress the output of the SSRP problem on \(n\)-vertex, \(m\)-edge graphs with integer edge weights in the range \([1,M]\) into a deterministic Single-Source DSO that has size \(O(M^{1/2 n^{3/2})\) and query time \(\widetildeO(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 \(\widetildeO(m\sqrt{n}+n^2)\) 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 \(\widetildeO(m\sqrt{n}+n^2)\) preprocessing time, \(O(n^{3/2})\) space, and \(\widetildeO(1)\) query time. Our combinatorial Single-Source DSO has near-optimal space, preprocessing and query time for dense unweighted graphs, improving the preprocessing time by a \(\sqrt{n}\)-factor compared to previous results. Grandoni and Vassilevska Williams [FOCS 2012, TALG 2020] gave an algebraic randomized \(\widetildeO(Mn^\omega)\) time SSRP algorithm for (undirected and directed) graphs with integer edge weights in the range \([1,M]\), where \(\omega < 2.373\) is the matrix multiplication exponent. We derandomize their algorithm for undirected graphs and apply our compression to obtain an algebraic Single-Source DSO with \(\widetildeO(Mn^\omega)\) preprocessing time, \(O(M^{1/2 n^{3/2})\) space, and \(\widetildeO(1)\) query time. This improves the preprocessing time of algebraic Single-Source DSOs by polynomial factors compared to previous results. 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(\frac{n^{5/4-\varepsilon}}{M^{7/4}})\) edges, for any constant \(\varepsilon > 0\), we reduce the preprocessing to randomized \(\widetildeO(M^7/8 m^1/2 n^{11/8}) = O(n^{2-\varepsilon/2})\) time. To the best of our knowledge, this is the first truly subquadratic time algorithm for building Single-Source DSOs on sparse graphs.
@inproceedings{bilo2021nearoptimal, 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 compress the output of the SSRP problem on \(n\)-vertex, \(m\)-edge graphs with integer edge weights in the range \([1,M]\) into a deterministic Single-Source DSO that has size \(O(M^{1/2 n^{3/2})\) and query time \(\widetildeO(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 \(\widetildeO(m\sqrt{n}+n^2)\) 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 \(\widetildeO(m\sqrt{n}+n^2)\) preprocessing time, \(O(n^{3/2})\) space, and \(\widetildeO(1)\) query time. Our combinatorial Single-Source DSO has near-optimal space, preprocessing and query time for dense unweighted graphs, improving the preprocessing time by a \(\sqrt{n}\)-factor compared to previous results. Grandoni and Vassilevska Williams [FOCS 2012, TALG 2020] gave an algebraic randomized \(\widetildeO(Mn^\omega)\) time SSRP algorithm for (undirected and directed) graphs with integer edge weights in the range \([1,M]\), where \(\omega < 2.373\) is the matrix multiplication exponent. We derandomize their algorithm for undirected graphs and apply our compression to obtain an algebraic Single-Source DSO with \(\widetildeO(Mn^\omega)\) preprocessing time, \(O(M^{1/2 n^{3/2})\) space, and \(\widetildeO(1)\) query time. This improves the preprocessing time of algebraic Single-Source DSOs by polynomial factors compared to previous results. 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(\frac{n^{5/4-\varepsilon}}{M^{7/4}})\) edges, for any constant \(\varepsilon > 0\), we reduce the preprocessing to randomized \(\widetildeO(M^7/8 m^1/2 n^{11/8}) = O(n^{2-\varepsilon/2})\) time. To the best of our knowledge, this is the first truly subquadratic time algorithm for building Single-Source DSOs on sparse graphs.}, author = {Bilò, Davide and Cohen, Sarel and Friedrich, Tobias and Schirneck, Martin}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {sarelcohen davidebilo esa tobiasfriedrich year2021 martinschirneck}, pages = {18:1&ndash;18:17}, title = {Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles}, year = 2021 }

Berger, Julian; Bleidt, Tibor; Büßemeyer, Martin; Ding, Marcus; Feldmann, Moritz; Feuerpfeil, Moritz; Jacoby, Janusch; Schröter, Valentin; Sievers, Bjarne; Spranger, Moritz; Stadlinger, Simon; Wullenweber, Paul; Cohen, Sarel; Doskoč, Vanja; Friedrich, Tobias Fine-Grained Localization, Classification and Segmentation of Lungs with Various DiseasesCVPR Workshop on Fine-Grained Visual Categorization (FGVC@CVPR) 2021
[ BibTeX ] [ Download ]
 
@inproceedings{berger2021finegrained, author = {Berger, Julian and Bleidt, Tibor and Büßemeyer, Martin and Ding, Marcus and Feldmann, Moritz and Feuerpfeil, Moritz and Jacoby, Janusch and Schröter, Valentin and Sievers, Bjarne and Spranger, Moritz and Stadlinger, Simon and Wullenweber, Paul and Cohen, Sarel and Doskoč, Vanja and Friedrich, Tobias}, booktitle = {CVPR Workshop on Fine-Grained Visual Categorization (FGVC@CVPR)}, keywords = {sarelcohen vanjadoskoc martinbuessemeyer fgvc@cvpr tobiasfriedrich marcusding moritzfeuerpfeil paulwullenweber moritzspranger moritzfeldmann januschjacoby tiborbleidt valentinschroeter simonstadlinger julianberger year2021 bjarnesievers}, title = {Fine-Grained Localization, Classification and Segmentation of Lungs with Various Diseases}, year = 2021 }

Bilò, Davide; Cohen, Sarel; Friedrich, Tobias; Schirneck, Martin Space-Efficient Fault-Tolerant Diameter OraclesMathematical Foundations of Computer Science (MFCS) 2021: 18:1–18:16
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
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| \leq f\), returns the diameter of \(G - F\). An \(f\)-FDO has stretch \(\sigma \geq 1\) if the returned value \(\widehat D\) satisfies \(\operatornamediam(G - F) leq widehat D leq sigma \operatornamediam(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+\varepsilon)\), constant query time, space \(O(m)\), and a combinatorial preprocessing time of \(\widetildeO(mn + n^1.5 \sqrt{Dm/\varepsilon})\), where \(D\) is the diameter. We present a near-optimal FDO with the same stretch, query time, and space. It has a preprocessing time of \(\widetildeO(mn + n^2/\varepsilon)\), which is better for any constant \(\varepsilon > 0\). The preprocessing time nearly matches a conditional lower bound for combinatorial algorithms, also by Henzinger et al. When using fast matrix multiplication instead, we achieve a preprocessing time of \(\widetildeO(n^2.5794 + n^2/\varepsilon)\). We further prove an information-theoretic lower bound showing that any FDO with stretch better than \(3/2\) requires \(\Omega(m)\) bits of space. Thus, for constant \(0 < \varepsilon < 3/2\), our combinatorial \((1+ \varepsilon)\)-approximate FDO is near-optimal in all the 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^2\log^2{n})\), \(\widetildeO(fn)\) space, and preprocessing time \(\widetildeO(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)}\). With fast matrix multiplication, the preprocessing time can be improved to \(n^{\omega+o(1)}\), where \(\omega < 2.373\) is the matrix multiplication exponent.
@inproceedings{bilo2021spaceefficient, 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| \leq f\), returns the diameter of \(G - F\). An \(f\)-FDO has stretch \(\sigma \geq 1\) if the returned value \(\widehat D\) satisfies \(\operatornamediam(G - F) leq widehat D leq sigma \operatornamediam(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+\varepsilon)\), constant query time, space \(O(m)\), and a combinatorial preprocessing time of \(\widetildeO(mn + n^1.5 \sqrt{Dm/\varepsilon})\), where \(D\) is the diameter. We present a near-optimal FDO with the same stretch, query time, and space. It has a preprocessing time of \(\widetildeO(mn + n^2/\varepsilon)\), which is better for any constant \(\varepsilon > 0\). The preprocessing time nearly matches a conditional lower bound for combinatorial algorithms, also by Henzinger et al. When using fast matrix multiplication instead, we achieve a preprocessing time of \(\widetildeO(n^2.5794 + n^2/\varepsilon)\). We further prove an information-theoretic lower bound showing that any FDO with stretch better than \(3/2\) requires \(\Omega(m)\) bits of space. Thus, for constant \(0 < \varepsilon < 3/2\), our combinatorial \((1+ \varepsilon)\)-approximate FDO is near-optimal in all the 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^2\log^2{n})\), \(\widetildeO(fn)\) space, and preprocessing time \(\widetildeO(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)}\). With fast matrix multiplication, the preprocessing time can be improved to \(n^{\omega+o(1)}\), where \(\omega < 2.373\) is the matrix multiplication exponent.}, author = {Bilò, Davide and Cohen, Sarel and Friedrich, Tobias and Schirneck, Martin}, booktitle = {Mathematical Foundations of Computer Science (MFCS)}, keywords = {sarelcohen davidebilo tobiasfriedrich mfcs year2021 martinschirneck}, pages = {18:1&ndash;18:16}, title = {Space-Efficient Fault-Tolerant Diameter Oracles}, year = 2021 }

Kißig, Otto; Taraz, Martin; Cohen, Sarel; Doskoč, Vanja; Friedrich, Tobias Drug Repurposing for Multiple COVID Strains using Collaborative FilteringICLR Workshop on Machine Learning for Preventing and Combating Pandemics (MLPCP@ICLR) 2021
[ Abstract ] [ BibTeX ] [ Download ]
 
The ongoing COVID-19 pandemic demands for a swift discovery of suitable treatments. The development of completely new compounds for such a novel disease is a challenging, time intensive process. This amplifies the relevance of drug repurposing, a technique where existing drugs are used to treat other diseases. A common bioinformatical approach to this is based on knowledge graphs, which compile relationships between drugs, diseases, genes and other biomedical entities. Then, graph neural networks (GNNs) are used for the drug repurposing task as they provide a good link prediction performance on such knowledge graphs. Building on state-of-the-art GNN research, Doshi & Chepuri (2020) construct the remarkable model DR-COVID. We re-implement their model and extend the approach to perform significantly better. We propose and evaluate several strategies for the aggregation of link predictions into drug recommendation rankings. With the help of clustering of similar target diseases we improve the model by a substantial margin, compiling a top-100 ranking of candidates including 32 currently being in COVID-19-related clinical trials. Regarding the re-implementation, we offer more flexibility in the selection of the graph neighborhood sizes fed into the model and reduce the training time significantly by making use of data parallelism.
@inproceedings{kissig2021repurposingcollaborativefiltering, abstract = {The ongoing COVID-19 pandemic demands for a swift discovery of suitable treatments. The development of completely new compounds for such a novel disease is a challenging, time intensive process. This amplifies the relevance of drug repurposing, a technique where existing drugs are used to treat other diseases. A common bioinformatical approach to this is based on knowledge graphs, which compile relationships between drugs, diseases, genes and other biomedical entities. Then, graph neural networks (GNNs) are used for the drug repurposing task as they provide a good link prediction performance on such knowledge graphs. Building on state-of-the-art GNN research, Doshi & Chepuri (2020) construct the remarkable model DR-COVID. We re-implement their model and extend the approach to perform significantly better. We propose and evaluate several strategies for the aggregation of link predictions into drug recommendation rankings. With the help of clustering of similar target diseases we improve the model by a substantial margin, compiling a top-100 ranking of candidates including 32 currently being in COVID-19-related clinical trials. Regarding the re-implementation, we offer more flexibility in the selection of the graph neighborhood sizes fed into the model and reduce the training time significantly by making use of data parallelism.}, author = {Kißig, Otto and Taraz, Martin and Cohen, Sarel and Doskoč, Vanja and Friedrich, Tobias}, booktitle = {ICLR Workshop on Machine Learning for Preventing and Combating Pandemics (MLPCP@ICLR)}, keywords = {sarelcohen ottokissig vanjadoskoc mlpcp@iclr tobiasfriedrich martintaraz year2021}, title = {Drug Repurposing for Multiple COVID Strains using Collaborative Filtering}, year = 2021 }

Kißig, Otto; Taraz, Martin; Cohen, Sarel; Friedrich, Tobias Drug Repurposing Using Link Prediction on Knowledge GraphsICML Workshop on Computational Biology (WCB@ICML) 2021
[ BibTeX ]
 
@inproceedings{kissig2021repurposingknowledgegraph, author = {Kißig, Otto and Taraz, Martin and Cohen, Sarel and Friedrich, Tobias}, booktitle = {ICML Workshop on Computational Biology (WCB@ICML)}, keywords = {sarelcohen ottokissig tobiasfriedrich martintaraz year2021 wcp@icml}, title = {Drug Repurposing Using Link Prediction on Knowledge Graphs}, year = 2021 }

2020 [ nach oben ]

Fogel, Sharon; Averbuch-Elor, Hadar; Cohen, Sarel; Mazor, Shai; Litman, Roee ScrabbleGAN: Semi-Supervised Varying Length Handwritten Text GenerationConference on Computer Vision and Pattern Recognition (CVPR) 2020: 4323–4332
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Optical character recognition (OCR) systems performance have improved significantly in the deep learning era. This is especially true for handwritten text recognition (HTR), where each author has a unique style, unlike printed text, where the variation is smaller by design. That said, deep learning based HTR is limited, as in every other task, by the number of training examples. Gathering data is a challenging and costly task, and even more so, the labeling task that follows, of which we focus here. One possible approach to reduce the burden of data annotation is semi-supervised learning. Semi supervised methods use, in addition to labeled data, some unlabeled samples to improve performance, compared to fully supervised ones. Consequently, such methods may adapt to unseen images during test time. We present ScrabbleGAN, a semi-supervised approach to synthesize handwritten text images that are versatile both in style and lexicon. ScrabbleGAN relies on a novel generative model which can generate images of words with an arbitrary length. We show how to operate our approach in a semi-supervised manner, enjoying the aforementioned benefits such as performance boost over state of the art supervised HTR. Furthermore, our generator can manipulate the resulting text style. This allows us to change, for instance, whether the text is cursive, or how thin is the pen stroke.
@inproceedings{fogel2020scrabblegan, abstract = {Optical character recognition (OCR) systems performance have improved significantly in the deep learning era. This is especially true for handwritten text recognition (HTR), where each author has a unique style, unlike printed text, where the variation is smaller by design. That said, deep learning based HTR is limited, as in every other task, by the number of training examples. Gathering data is a challenging and costly task, and even more so, the labeling task that follows, of which we focus here. One possible approach to reduce the burden of data annotation is semi-supervised learning. Semi supervised methods use, in addition to labeled data, some unlabeled samples to improve performance, compared to fully supervised ones. Consequently, such methods may adapt to unseen images during test time. We present ScrabbleGAN, a semi-supervised approach to synthesize handwritten text images that are versatile both in style and lexicon. ScrabbleGAN relies on a novel generative model which can generate images of words with an arbitrary length. We show how to operate our approach in a semi-supervised manner, enjoying the aforementioned benefits such as performance boost over state of the art supervised HTR. Furthermore, our generator can manipulate the resulting text style. This allows us to change, for instance, whether the text is cursive, or how thin is the pen stroke.}, author = {Fogel, Sharon and Averbuch-Elor, Hadar and Cohen, Sarel and Mazor, Shai and Litman, Roee}, booktitle = {Conference on Computer Vision and Pattern Recognition (CVPR)}, keywords = {sarelcohen sys:relevantfor:ae shaimazor roeelitman cvpr sharonfogel hadaraverbuch-elor year2020}, pages = {4323-4332}, title = {ScrabbleGAN: Semi-Supervised Varying Length Handwritten Text Generation}, year = 2020 }

Chechik, Shiri; Cohen, Sarel Distance sensitivity oracles with subcubic preprocessing time and fast query timeSymposium Theory of Computing (STOC) 2020: 1375–1388
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We present the first distance sensitivity oracle (DSO) with subcubic preprocessing time and poly-logarithmic query time for directed graphs with integer weights in the range \([−M,M]\). Weimann and Yuster [FOCS 10] presented a distance sensitivity oracle for a single vertex/edge failure with subcubic preprocessing time of \(\mathcal{O(Mn^\omega+1− \alpha})\) and subquadratic query time of \(\tilde{\mathcal{O(n^{1+\alpha})\), where \(\alpha\) is any parameter in \([0,1]\), \(n\) is the number of vertices, \(m\) is the number of edges, the \(\tilde{\mathcal{O(·)\) notation hides poly-logarithmic factors in \(n\) and \(\omega<2.373\) is the matrix multiplication exponent.Later, Grandoni and Vassilevska Williams [FOCS 12] substantially improved the query time to sublinear in \(n\). In particular, they presented a distance sensitivity oracle for a single vertex/edge failure with \(\tilde{\mathcal{O}}\)\( (Mn^\omega +1/2}\) \(+ Mn^\omega+\alpha(4−\omega)})\) preprocessing time and \(\tilde{\mathcal{O(n^{1−\alpha})\) query time. Despite the substantial improvement in the query time, it still remains polynomial in the size of the graph, which may be undesirable in many settings where the graph is of large scale. A natural question is whether one can hope for a distance sensitivity oracle with subcubic preprocessing time and very fast query time (of poly-logarithmic in \(n\)). In this paper we answer this question affirmatively by presenting a distance sensitive oracle supporting a single vertex/edge failure in subcubic \(\tilde{\mathcal{O(Mn^{2.873})\) preprocessing time for \(\omega=2.373\), \(\tilde{\mathcal{O(n^{2.5})\) space and near optimal query time of \(\tilde{\mathcal{O(1)\). For comparison, with the same \(\tilde{\mathcal{O(Mn^{2.873})\) preprocessing time the DSO of Grandoni and Vassilevska Williams has \(\tilde{\mathcal{O(n^{0.693})\) query time. In fact, the best query time their algorithm can obtain is \(\tilde{\mathcal{O(Mn^{0.385})\) (with \(\tilde{\mathcal{O(Mn^3)\) preprocessing time).
@inproceedings{chechik2020distance, abstract = {We present the first distance sensitivity oracle (DSO) with subcubic preprocessing time and poly-logarithmic query time for directed graphs with integer weights in the range \([−M,M]\). Weimann and Yuster [FOCS 10] presented a distance sensitivity oracle for a single vertex/edge failure with subcubic preprocessing time of \(\mathcal{O(Mn^\omega+1− \alpha})\) and subquadratic query time of \(\tilde{\mathcal{O(n^{1+\alpha})\), where \(\alpha\) is any parameter in \([0,1]\), \(n\) is the number of vertices, \(m\) is the number of edges, the \(\tilde{\mathcal{O(·)\) notation hides poly-logarithmic factors in \(n\) and \(\omega<2.373\) is the matrix multiplication exponent.Later, Grandoni and Vassilevska Williams [FOCS 12] substantially improved the query time to sublinear in \(n\). In particular, they presented a distance sensitivity oracle for a single vertex/edge failure with \(\tilde{\mathcal{O}}\)\( (Mn^\omega +1/2}\) \(+ Mn^\omega+\alpha(4−\omega)})\) preprocessing time and \(\tilde{\mathcal{O(n^{1−\alpha})\) query time. Despite the substantial improvement in the query time, it still remains polynomial in the size of the graph, which may be undesirable in many settings where the graph is of large scale. A natural question is whether one can hope for a distance sensitivity oracle with subcubic preprocessing time and very fast query time (of poly-logarithmic in \(n\)). In this paper we answer this question affirmatively by presenting a distance sensitive oracle supporting a single vertex/edge failure in subcubic \(\tilde{\mathcal{O(Mn^{2.873})\) preprocessing time for \(\omega=2.373\), \(\tilde{\mathcal{O(n^{2.5})\) space and near optimal query time of \(\tilde{\mathcal{O(1)\). For comparison, with the same \(\tilde{\mathcal{O(Mn^{2.873})\) preprocessing time the DSO of Grandoni and Vassilevska Williams has \(\tilde{\mathcal{O(n^{0.693})\) query time. In fact, the best query time their algorithm can obtain is \(\tilde{\mathcal{O(Mn^{0.385})\) (with \(\tilde{\mathcal{O(Mn^3)\) preprocessing time).}, author = {Chechik, Shiri and Cohen, Sarel}, booktitle = {Symposium Theory of Computing (STOC)}, keywords = {sarelcohen sys:relevantfor:ae stoc shirichechik year2020}, pages = {1375-1388}, title = {Distance sensitivity oracles with subcubic preprocessing time and fast query time}, year = 2020 }

2019 [ nach oben ]

Alon, Noga; Chechik, Shiri; Cohen, Sarel Deterministic Combinatorial Replacement Paths and Distance Sensitivity OraclesInternational Colloquium on Automata, Languages and Programming (ICALP) 2019: 12:1–12:14
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In this work we derandomize two central results in graph algorithms, replacement paths and distance sensitivity oracles (DSOs) matching in both cases the running time of the randomized algorithms. For the replacement paths problem, let \(G = (V,E)\) be a directed unweighted graph with \(n\) vertices and m edges and let \(P\) be a shortest path from \(s\) to \(t\) in \(G\). The replacement paths problem is to find for every edge \(e\) in \(P\) the shortest path from \(s\) to \(t\) avoiding \(e\). Roditty and Zwick [ICALP 2005] obtained a randomized algorithm with running time of \(\mathcal{O(m \sqrt{n})\). Here we provide the first deterministic algorithm for this problem, with the same \(\mathcal{O(m \sqrt{n})\) time. Due to matching conditional lower bounds of Williams et al. [FOCS 2010], our deterministic combinatorial algorithm for the replacement paths problem is optimal up to polylogarithmic factors (unless the long standing bound of \(\mathcal{O(mn)\) for the combinatorial boolean matrix multiplication can be improved). This also implies a deterministic algorithm for the second simple shortest path problem in \(\mathcal{O(m \sqrt{n})\) time, and a deterministic algorithm for the \(k\)-simple shortest paths problem in \(\mathcal{O(k m sqrt{n})\) time (for any integer constant \(k > 0\)). For the problem of distance sensitivity oracles, let \(G = (V,E)\) be a directed graph with real-edge weights. An \(f\)-Sensitivity Distance Oracle (\(f\)-DSO) gets as input the graph \(G=(V,E)\) and a parameter \(f\), preprocesses it into a data-structure, such that given a query \((s,t,F)\) with \(s,t \in V\) and \(F \subseteq E \cup V\), \(|F| <=f\) being a set of at most \(f\) edges or vertices (failures), the query algorithm efficiently computes the distance from \(s\) to \(t\) in the graph \(G \setminus F\) (i.e., the distance from \(s\) to \(t\) in the graph \(G\) after removing from it the failing edges and vertices \(F\)). For weighted graphs with real edge weights, Weimann and Yuster [FOCS 2010] presented several randomized \(f\)-DSOs. In particular, they presented a combinatorial \(f\)-DSO with \(\mathcal{O(mn^{4-\alpha})\) preprocessing time and subquadratic \(\mathcal{O(n^2-2(1-\alpha)/f})\) query time, giving a tradeoff between preprocessing and query time for every value of \(0 < \alpha < 1\). We derandomize this result and present a combinatorial deterministic \(f\)-DSO with the same asymptotic preprocessing and query time.
@inproceedings{alon2019deterministic, abstract = {In this work we derandomize two central results in graph algorithms, replacement paths and distance sensitivity oracles (DSOs) matching in both cases the running time of the randomized algorithms. For the replacement paths problem, let \(G = (V,E)\) be a directed unweighted graph with \(n\) vertices and m edges and let \(P\) be a shortest path from \(s\) to \(t\) in \(G\). The replacement paths problem is to find for every edge \(e\) in \(P\) the shortest path from \(s\) to \(t\) avoiding \(e\). Roditty and Zwick [ICALP 2005] obtained a randomized algorithm with running time of \(\mathcal{O(m \sqrt{n})\). Here we provide the first deterministic algorithm for this problem, with the same \(\mathcal{O(m \sqrt{n})\) time. Due to matching conditional lower bounds of Williams et al. [FOCS 2010], our deterministic combinatorial algorithm for the replacement paths problem is optimal up to polylogarithmic factors (unless the long standing bound of \(\mathcal{O(mn)\) for the combinatorial boolean matrix multiplication can be improved). This also implies a deterministic algorithm for the second simple shortest path problem in \(\mathcal{O(m \sqrt{n})\) time, and a deterministic algorithm for the \(k\)-simple shortest paths problem in \(\mathcal{O(k m sqrt{n})\) time (for any integer constant \(k > 0\)). For the problem of distance sensitivity oracles, let \(G = (V,E)\) be a directed graph with real-edge weights. An \(f\)-Sensitivity Distance Oracle (\(f\)-DSO) gets as input the graph \(G=(V,E)\) and a parameter \(f\), preprocesses it into a data-structure, such that given a query \((s,t,F)\) with \(s,t \in V\) and \(F \subseteq E \cup V\), \(|F| <=f\) being a set of at most \(f\) edges or vertices (failures), the query algorithm efficiently computes the distance from \(s\) to \(t\) in the graph \(G \setminus F\) (i.e., the distance from \(s\) to \(t\) in the graph \(G\) after removing from it the failing edges and vertices \(F\)). For weighted graphs with real edge weights, Weimann and Yuster [FOCS 2010] presented several randomized \(f\)-DSOs. In particular, they presented a combinatorial \(f\)-DSO with \(\mathcal{O(mn^{4-\alpha})\) preprocessing time and subquadratic \(\mathcal{O(n^2-2(1-\alpha)/f})\) query time, giving a tradeoff between preprocessing and query time for every value of \(0 < \alpha < 1\). We derandomize this result and present a combinatorial deterministic \(f\)-DSO with the same asymptotic preprocessing and query time.}, author = {Alon, Noga and Chechik, Shiri and Cohen, Sarel}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {sarelcohen sys:relevantfor:ae shirichechik year2019 nogaalon icalp}, pages = {12:1-12:14}, title = {Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles}, year = 2019 }

Chechik, Shiri; Cohen, Sarel Near Optimal Algorithms For The Single Source Replacement Paths ProblemSymposium on Discrete Algorithms (SODA) 2019: 2090–2109
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The Single Source Replacement Paths (SSRP) problem is as follows; Given a graph \(G = (V, E)\), a source vertex \(s\) and a shortest paths tree \(T_s\) rooted in \(s\), output for every vertex \(t \in V\) and for every edge \(e\) in \(T_s\) the length of the shortest path from \(s\) to \(t\) avoiding \(e\). We present near optimal upper bounds, by providing \(\tilde{\mathcal{O(m \sqrt{n} + n^2) \) time randomized combinatorial algorithm for unweighted undirected graphs, and matching conditional lower bounds for the SSRP problem.
@inproceedings{chechik2019optimal, abstract = {The Single Source Replacement Paths (SSRP) problem is as follows; Given a graph \(G = (V, E)\), a source vertex \(s\) and a shortest paths tree \(T_s\) rooted in \(s\), output for every vertex \(t \in V\) and for every edge \(e\) in \(T_s\) the length of the shortest path from \(s\) to \(t\) avoiding \(e\). We present near optimal upper bounds, by providing \(\tilde{\mathcal{O(m \sqrt{n} + n^2) \) time randomized combinatorial algorithm for unweighted undirected graphs, and matching conditional lower bounds for the SSRP problem.}, author = {Chechik, Shiri and Cohen, Sarel}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {sarelcohen sys:relevantfor:ae shirichechik year2019 soda}, pages = {2090-2109}, title = {Near Optimal Algorithms For The Single Source Replacement Paths Problem}, year = 2019 }

2018 [ nach oben ]

Azar, Yossi; Cohen, Sarel An improved algorithm for online machine minimizationOperations Research Letters 2018: 128–133
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
 
The online machine minimization problem seeks to design a preemptive scheduling algorithm on multiple machines — each job \(j\) arrives at its release time \(r_j\), has to be processed for \(p_j\) time units, and must be completed by its deadline \(d_j\). The goal is to minimize the number of machines the algorithm uses. We improve the \(\mathcal{O(\log m)\)-competitive algorithm by Chen, Megow and Schewior (SODA 2016) and provide an \(\mathcal{O(\frac{\log m\log \log m})\)-competitive algorithm.
@article{azar2018improved, abstract = {The online machine minimization problem seeks to design a preemptive scheduling algorithm on multiple machines — each job \(j\) arrives at its release time \(r_j\), has to be processed for \(p_j\) time units, and must be completed by its deadline \(d_j\). The goal is to minimize the number of machines the algorithm uses. We improve the \(\mathcal{O(\log m)\)-competitive algorithm by Chen, Megow and Schewior (SODA 2016) and provide an \(\mathcal{O(\frac{\log m\log \log m})\)-competitive algorithm.}, author = {Azar, Yossi and Cohen, Sarel}, journal = {Operations Research Letters}, keywords = {sarelcohen sys:relevantfor:ae year2018 yossiazar orl}, pages = {128-133}, title = {An improved algorithm for online machine minimization}, year = 2018 }

Arar, Moab; Chechik, Shiri; Cohen, Sarel; Stein, Cliff; Wajc, David Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional AlgorithmsInternational Colloquium on Automata, Languages and Programming (ICALP) 2018: 7:1–7:16
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We present a simple randomized reduction from fully-dynamic integral matching algorithms to fully-dynamic "approximately-maximal" fractional matching algorithms. Applying this reduction to the recent fractional matching algorithm of Bhattacharya, Henzinger, and Nanongkai (SODA 2017), we obtain a novel result for the integral problem. Specifically, our main result is a randomized fully-dynamic \((2+\varepsilon)\)-approximate integral matching algorithm with small polylog worst-case update time. For the \((2+\varepsilon)\)-approximation regime only a fractional fully-dynamic \((2+\varepsilon)\)-matching algorithm with worst-case polylog update time was previously known, due to Bhattacharya et al. (SODA 2017). Our algorithm is the first algorithm that maintains approximate matchings with worst-case update time better than polynomial, for any constant approximation ratio. As a consequence, we also obtain the first constant-approximate worst-case polylogarithmic update time maximum weight matching algorithm.
@inproceedings{arar2018dynamic, abstract = {We present a simple randomized reduction from fully-dynamic integral matching algorithms to fully-dynamic "approximately-maximal" fractional matching algorithms. Applying this reduction to the recent fractional matching algorithm of Bhattacharya, Henzinger, and Nanongkai (SODA 2017), we obtain a novel result for the integral problem. Specifically, our main result is a randomized fully-dynamic \((2+\varepsilon)\)-approximate integral matching algorithm with small polylog worst-case update time. For the \((2+\varepsilon)\)-approximation regime only a fractional fully-dynamic \((2+\varepsilon)\)-matching algorithm with worst-case polylog update time was previously known, due to Bhattacharya et al. (SODA 2017). Our algorithm is the first algorithm that maintains approximate matchings with worst-case update time better than polynomial, for any constant approximation ratio. As a consequence, we also obtain the first constant-approximate worst-case polylogarithmic update time maximum weight matching algorithm.}, author = {Arar, Moab and Chechik, Shiri and Cohen, Sarel and Stein, Cliff and Wajc, David}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {sarelcohen sys:relevantfor:ae shirichechik davidwajc year2018 moabarar icalp cliffstein}, pages = {7:1-7:16}, title = {Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms}, year = 2018 }

2017 [ nach oben ]

Chechik, Shiri; Cohen, Sarel; Fiat, Amos; Kaplan, Haim \( (1 + \varepsilon)\)-Approximate \(f\)-Sensitive Distance OraclesSymposium on Discrete Algorithms (SODA) 2017: 1479–1496
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
An \(f\)-Sensitive Distance Oracle with stretch a preprocesses a graph \( G(V, E) \) and produces a small data structure that is used to answer subsequent queries. A query is a triple consisting of a set \( F \subset E \) of at most \(f\) edges, and vertices \(s\) and \(t\). The oracle answers a query \( (F,s.,t) \) by returning a value \(d\) which is equal to the length of some path between \(s\) and \(t\) in the graph \(G \setminus F\) (the graph obtained from \(G\) by discarding all edges in \(F\)). Moreover, d is at most a times the length of the shortest path between \(s\) and \(t\) in \(G \setminus F\). The oracle can also construct a path between \(s\) and \(t\) in \(G \setminus F\) of length \(d\). To the best of our knowledge we give the first nontrivial f-sensitive distance oracle with fast query time and small stretch capable of handling multiple edge failures. Specifically, for any \( \mathcal{O(\frac{\log n\log \log n ) \) and a fixed \( \varepsilon > 0 \) our oracle answers queries \( (F,s,t) \) in time \( \mathcal{O(l) \) with \( (1 + \varepsilon) \) stretch using a data structure of size \( n^2+ \mathcal{O(1) \) For comparison, the naive alternative requires \( m^f n^2 \) space for sublinear query time.
@inproceedings{chechik2017varepsilonapproximate, abstract = {An \(f\)-Sensitive Distance Oracle with stretch a preprocesses a graph \( G(V, E) \) and produces a small data structure that is used to answer subsequent queries. A query is a triple consisting of a set \( F \subset E \) of at most \(f\) edges, and vertices \(s\) and \(t\). The oracle answers a query \( (F,s.,t) \) by returning a value \(d\) which is equal to the length of some path between \(s\) and \(t\) in the graph \(G \setminus F\) (the graph obtained from \(G\) by discarding all edges in \(F\)). Moreover, d is at most a times the length of the shortest path between \(s\) and \(t\) in \(G \setminus F\). The oracle can also construct a path between \(s\) and \(t\) in \(G \setminus F\) of length \(d\). To the best of our knowledge we give the first nontrivial f-sensitive distance oracle with fast query time and small stretch capable of handling multiple edge failures. Specifically, for any \( \mathcal{O(\frac{\log n\log \log n ) \) and a fixed \( \varepsilon > 0 \) our oracle answers queries \( (F,s,t) \) in time \( \mathcal{O(l) \) with \( (1 + \varepsilon) \) stretch using a data structure of size \( n^2+ \mathcal{O(1) \) For comparison, the naive alternative requires \( m^f n^2 \) space for sublinear query time.}, author = {Chechik, Shiri and Cohen, Sarel and Fiat, Amos and Kaplan, Haim}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {sarelcohen amosfiat sys:relevantfor:ae haimkaplan shirichechik year2017 soda}, pages = {1479-1496}, title = {\( (1 + \varepsilon)\)-Approximate \(f\)-Sensitive Distance Oracles}, year = 2017 }

2015 [ nach oben ]

Cohen, Sarel; Fiat, Amos; Hershcovitch, Moshik; Kaplan, Haim Minimal indices for predecessor searchInformation and Computation 2015: 12–30
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We give a new predecessor data structure which improves upon the index size of the Pǎtraşcu–Thorup data structures, reducing the index size from \( \mathcal{O(n w^{4/5}) \) bits to \( \mathcal{O(n \log w) \) bits, with optimal probe complexity. Alternatively, our new data structure can be viewed as matching the space complexity of the (probe-suboptimal) z-fast trie of Belazzougui et al. Thus, we get the best of both approaches with respect to both probe count and index size. The penalty we pay is an extra \( \mathcal{O(\log w) \) inter-register operations. Our data structure can also be used to solve the weak prefix search problem, the index size of \( \mathcal{O(n \log w) \) bits is known to be optimal for any such data structure. The technical contributions include highly efficient single word indices, with out-degree \(w \log w \) (compared to \(w ^{1/5}\) of a fusion tree node). To construct these indices we device highly efficient bit selectors which, we believe, are of independent interest.
@article{cohen2015minimal, abstract = {We give a new predecessor data structure which improves upon the index size of the Pǎtraşcu–Thorup data structures, reducing the index size from \( \mathcal{O(n w^{4/5}) \) bits to \( \mathcal{O(n \log w) \) bits, with optimal probe complexity. Alternatively, our new data structure can be viewed as matching the space complexity of the (probe-suboptimal) z-fast trie of Belazzougui et al. Thus, we get the best of both approaches with respect to both probe count and index size. The penalty we pay is an extra \( \mathcal{O(\log w) \) inter-register operations. Our data structure can also be used to solve the weak prefix search problem, the index size of \( \mathcal{O(n \log w) \) bits is known to be optimal for any such data structure. The technical contributions include highly efficient single word indices, with out-degree \(w \log w \) (compared to \(w ^{1/5}\) of a fusion tree node). To construct these indices we device highly efficient bit selectors which, we believe, are of independent interest.}, author = {Cohen, Sarel and Fiat, Amos and Hershcovitch, Moshik and Kaplan, Haim}, journal = {Information and Computation}, keywords = {sarelcohen amosfiat sys:relevantfor:ae haimkaplan moshikhershcovitch year2015 ic}, pages = {12-30}, title = {Minimal indices for predecessor search}, year = 2015 }

2013 [ nach oben ]

Cohen, Sarel; Fiat, Amos; Hershcovitch, Moshik; Kaplan, Haim Minimal Indices for Successor Search - (Extended Abstract).Mathematical Foundations of Computer Science (MFCS) 2013: 278–289
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We give a new successor data structure which improves upon the index size of the Pǎtraşcu-Thorup data structures, reducing the index size from \( \mathcal{O(n w^4/5 \) bits to \( \mathcal{O(n \log w) \) bits, with optimal probe complexity. Alternatively, our new data structure can be viewed as matching the space complexity of the (probe-suboptimal) z-fast trie of Belazzougui et al. Thus, we get the best of both approaches with respect to both probe count and index size. The penalty we pay is an extra \( \mathcal{O(n \log w) \) inter-register operations. Our data structure can also be used to solve the weak prefix search problem, the index size of \( \mathcal{O(n \log w) \) bits is known to be optimal for any such data structure. The technical contributions include highly efficient single word indices, with out-degree \( w / \log w \) (compared to the \( w^1/5 \) out-degree of fusion tree based indices). To construct such high efficiency single word indices we device highly efficient bit selectors which, we believe, are of independent interest.
@inproceedings{cohen2013minimal, abstract = {We give a new successor data structure which improves upon the index size of the Pǎtraşcu-Thorup data structures, reducing the index size from \( \mathcal{O(n w^4/5 \) bits to \( \mathcal{O(n \log w) \) bits, with optimal probe complexity. Alternatively, our new data structure can be viewed as matching the space complexity of the (probe-suboptimal) z-fast trie of Belazzougui et al. Thus, we get the best of both approaches with respect to both probe count and index size. The penalty we pay is an extra \( \mathcal{O(n \log w) \) inter-register operations. Our data structure can also be used to solve the weak prefix search problem, the index size of \( \mathcal{O(n \log w) \) bits is known to be optimal for any such data structure. The technical contributions include highly efficient single word indices, with out-degree \( w / \log w \) (compared to the \( w^1/5 \) out-degree of fusion tree based indices). To construct such high efficiency single word indices we device highly efficient bit selectors which, we believe, are of independent interest.}, author = {Cohen, Sarel and Fiat, Amos and Hershcovitch, Moshik and Kaplan, Haim}, booktitle = {Mathematical Foundations of Computer Science (MFCS)}, keywords = {sarelcohen amosfiat sys:relevantfor:ae haimkaplan moshikhershcovitch mfcs year2013}, pages = {278-289}, title = {Minimal Indices for Successor Search - (Extended Abstract).}, year = 2013 }