2022 [ nach oben ]

Böther, Maximilian; Kißig, Otto; Taraz, Martin; Cohen, Sarel; Seidel, Karen; Friedrich, Tobias What’s Wrong with Deep Learning in Tree Search for Combinatorial OptimizationInternational Conference on Learning Representations (ICLR) 2022
[ Abstract ] [ BibTeX ] [ Download ]
 
Combinatorial optimization lies at the core of many real-world problems. Especially since the rise of graph neural networks (GNNs), the deep learning community has been developing solvers that derive solutions to NP-hard problems by learning the problem-specific solution structure. However, reproducing the results of these publications proves to be difficult. We make three contributions. First, we present an open-source benchmark suite for the NP-hard Maximum Independent Set problem, in both its weighted and unweighted variants. The suite offers a unified interface to various state-of-the-art traditional and machine learning-based solvers. Second, using our benchmark suite, we conduct an in-depth analysis of the popular guided tree search algorithm by Li et al. [NeurIPS 2018], testing various configurations on small and large synthetic and real-world graphs. By re-implementing their algorithm with a focus on code quality and extensibility, we show that the graph convolution network used in the tree search does not learn a meaningful representation of the solution structure, and can in fact be replaced by random values. Instead, the tree search relies on algorithmic techniques like graph kernelization to find good solutions. Thus, the results from the original publication are not reproducible. Third, we extend the analysis to compare the tree search implementations to other solvers, showing that the classical algorithmic solvers often are faster, while providing solutions of similar quality. Additionally, we analyze a recent solver based on reinforcement learning and observe that for this solver, the GNN is responsible for the competitive solution quality.
@inproceedings{bother2022whats, abstract = {Combinatorial optimization lies at the core of many real-world problems. Especially since the rise of graph neural networks (GNNs), the deep learning community has been developing solvers that derive solutions to NP-hard problems by learning the problem-specific solution structure. However, reproducing the results of these publications proves to be difficult. We make three contributions. First, we present an open-source benchmark suite for the NP-hard Maximum Independent Set problem, in both its weighted and unweighted variants. The suite offers a unified interface to various state-of-the-art traditional and machine learning-based solvers. Second, using our benchmark suite, we conduct an in-depth analysis of the popular guided tree search algorithm by Li et al. [NeurIPS 2018], testing various configurations on small and large synthetic and real-world graphs. By re-implementing their algorithm with a focus on code quality and extensibility, we show that the graph convolution network used in the tree search does not learn a meaningful representation of the solution structure, and can in fact be replaced by random values. Instead, the tree search relies on algorithmic techniques like graph kernelization to find good solutions. Thus, the results from the original publication are not reproducible. Third, we extend the analysis to compare the tree search implementations to other solvers, showing that the classical algorithmic solvers often are faster, while providing solutions of similar quality. Additionally, we analyze a recent solver based on reinforcement learning and observe that for this solver, the GNN is responsible for the competitive solution quality.}, author = {Böther, Maximilian and Kißig, Otto and Taraz, Martin and Cohen, Sarel and Seidel, Karen and Friedrich, Tobias}, booktitle = {International Conference on Learning Representations (ICLR)}, keywords = {maximilianboether sarelcohen ottokissig tobiasfriedrich martintaraz year2022 iclr karenseidel}, title = {What’s Wrong with Deep Learning in Tree Search for Combinatorial Optimization}, year = 2022 }

Bilò, Davide; Casel, Katrin; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Lagodzinski, J.A. Gregor; Schirneck, Martin; Wietheger, Simon Fixed-Parameter Sensitivity OraclesInnovations in Theoretical Computer Science (ITCS) 2022: 23:1–23:18
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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 \(\Pi\) 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 \(\Pi\)-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})\) size 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\big(\big(\frac{f+k}{f}\big)^f \big(\frac{f+k}{k}\big)^k fk \cdot \log n\big)\) at the expense of increasing the query time to \(O\big(\big(\frac{f+k}{f}\big)^f \big(\frac{f+k}{k}\big)^k f \min\{f,k\} \cdot \log n \big)\). 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^2+k})\) and a query time of \(O(f{+}k^2)\); finally, the third one takes \(O(fk+k^2)\) space and can be queried in time \(O(1.2738^k + fk^2)\). 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) \cdot 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. Given a graph with a fixed source \(s\) and parameters \(f\),\(k\), we study the problem of constructing polynomial-sized oracles that reports efficiently, for any target vertex \(v\) and set \(F\) of at most \(f\) edge failures, 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^2 \cdot n)\), while the time needed to answer a query is \(O(2^k f^\omega k^\omega)\), where \(\omega<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 \cdot 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 \(\widetildeO(f n^{2-\frac{1}{2^f}})\) bound in the unparameterized case by Bodwin et al. [ICALP 2017].
@inproceedings{bilo2022fixedparameter, 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 \(\Pi\) 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 \(\Pi\)-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})\) size 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\big(\big(\frac{f+k}{f}\big)^f \big(\frac{f+k}{k}\big)^k fk \cdot \log n\big)\) at the expense of increasing the query time to \(O\big(\big(\frac{f+k}{f}\big)^f \big(\frac{f+k}{k}\big)^k f \min\{f,k\} \cdot \log n \big)\). 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^2+k})\) and a query time of \(O(f{+}k^2)\); finally, the third one takes \(O(fk+k^2)\) space and can be queried in time \(O(1.2738^k + fk^2)\). 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) \cdot 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. Given a graph with a fixed source \(s\) and parameters \(f\),\(k\), we study the problem of constructing polynomial-sized oracles that reports efficiently, for any target vertex \(v\) and set \(F\) of at most \(f\) edge failures, 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^2 \cdot n)\), while the time needed to answer a query is \(O(2^k f^\omega k^\omega)\), where \(\omega<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 \cdot 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 \(\widetilde{O}(f n^{2-\frac{1}{2^f}})\) bound in the unparameterized case by Bodwin et al. [ICALP 2017].}, author = {Bilò, Davide and Casel, Katrin and Choudhary, Keerti and Cohen, Sarel and Friedrich, Tobias and Lagodzinski, J.A. Gregor and Schirneck, Martin and Wietheger, Simon}, booktitle = {Innovations in Theoretical Computer Science (ITCS)}, keywords = {sarelcohen gregorlagodzinski davidebilo katrincasel simonwietheger tobiasfriedrich itcs keertichoudhary year2022 martinschirneck}, pages = {23:1-23:18}, title = {Fixed-Parameter Sensitivity Oracles}, year = 2022 }

2021 [ nach oben ]

Cohen, Sarel; Hershcovitch, Moshik; Taraz, Martin; Kißig, Otto; Wood, Andrew; Waddington, Daniel; Chin, Peter; Friedrich, Tobias Drug Repurposing using Link Prediction on Knowledge Graphs with Applications to Non-Volatile MemoryComplex Networks and their Applications (ComplexNetworks) 2021
[ Abstract ] [ BibTeX ] [ Download ]
 
The active global SARS-CoV-2 pandemic caused more than 167 million cases and 3.4 million deaths worldwide. The development of completely new drugs for such a novel disease is a challenging, time intensive process and despite researchers around the world working on this task, no effective treatments have been developed yet. This emphasizes the importance of \emph{drug repurposing, where treatments are found among existing drugs that are meant for different diseases. A common approach to this is based on \emph{knowledge graphs, that condense relationships between entities like drugs, diseases and genes. Graph neural networks (GNNs) can then be used for the task at hand by predicting links in such knowledge graphs. Expanding on state-of-the-art GNN research, Doshi et al. recently developed the Dr-COVID model. We further extend their work using additional output interpretation strategies. The best aggregation strategy derives a top-100 ranking of candidate drugs, 32 of which currently being in COVID-19-related clinical trials. Moreover, we present an alternative application for the model, the generation of additional candidates based on a given pre-selection of drug candidates using collaborative filtering. In addition, we improved the implementation of the Dr-COVID model by significantly shortening the inference and pre-processing time by exploiting data-parallelism. As drug repurposing is a task that requires high computation and memory resources, we further accelerate the post-processing phase using a new emerging hardware --- we propose a new approach to leverage the use of high-capacity Non-Volatile Memory for aggregate drug ranking.
@inproceedings{cohen2021repurposing, abstract = {The active global SARS-CoV-2 pandemic caused more than 167 million cases and 3.4 million deaths worldwide. The development of completely new drugs for such a novel disease is a challenging, time intensive process and despite researchers around the world working on this task, no effective treatments have been developed yet. This emphasizes the importance of \emph{drug repurposing}, where treatments are found among existing drugs that are meant for different diseases. A common approach to this is based on \emph{knowledge graphs}, that condense relationships between entities like drugs, diseases and genes. Graph neural networks (GNNs) can then be used for the task at hand by predicting links in such knowledge graphs. Expanding on state-of-the-art GNN research, Doshi et al. recently developed the Dr-COVID model. We further extend their work using additional output interpretation strategies. The best aggregation strategy derives a top-100 ranking of candidate drugs, 32 of which currently being in COVID-19-related clinical trials. Moreover, we present an alternative application for the model, the generation of additional candidates based on a given pre-selection of drug candidates using collaborative filtering. In addition, we improved the implementation of the Dr-COVID model by significantly shortening the inference and pre-processing time by exploiting data-parallelism. As drug repurposing is a task that requires high computation and memory resources, we further accelerate the post-processing phase using a new emerging hardware &mdash; we propose a new approach to leverage the use of high-capacity Non-Volatile Memory for aggregate drug ranking.}, author = {Cohen, Sarel and Hershcovitch, Moshik and Taraz, Martin and Kißig, Otto and Wood, Andrew and Waddington, Daniel and Chin, Peter and Friedrich, Tobias}, booktitle = {Complex Networks and their Applications (ComplexNetworks)}, keywords = {sarelcohen ottokissig danielwaddington moshikhershcovitch tobiasfriedrich martintaraz andrewwood complexnetworks peterchin year2021}, title = {Drug Repurposing using Link Prediction on Knowledge Graphs with Applications to Non-Volatile Memory}, year = 2021 }

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 ] [ URL ] [ DOI ] [ 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 \(\widetilde{O}(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 \(\widetilde{O}(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 \(\widetilde{O}(m\sqrt{n}+n^2)\) preprocessing time, \(O(n^{3/2})\) space, and \(\widetilde{O}(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 \(\widetilde{O}(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 \(\widetilde{O}(Mn^\omega)\) preprocessing time, \(O(M^{1/2} n^{3/2})\) space, and \(\widetilde{O}(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 \(\widetilde{O}(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
[ Abstract ] [ BibTeX ] [ Download ]
 
The fine-grained localization and classification of various lung abnormalities is a challenging yet important task for combating diseases and, also, pandemics. In this paper, we present one way to detect and classify abnormalities within chest X-ray scans. In particular, we investigate the use of binary image classification (to distinguish between healthy and infected chests) and the weighted box fusion (which constructs a detection box using the proposed boxes within range). We observe that both methods increase the performance of a base model significantly. Furthermore, we improve state of the art on lung segmentation, even in the presence of abnormalities. We do so using transfer learning to fine-tune a UNet model on the Montgomery and Shenzhen datasets. In our experiments, we compare standard augmentations (like crop, pad, rotate, warp, zoom, brightness, and contrast variations) to more complex ones (for example, block masking and diffused noise augmentations). This way, we obtain a state-of-the-art model with a dice score of 97.9%. In particular, we show that simple augmentations outperform complex ones in our setting.
@inproceedings{berger2021finegrained, abstract = {The fine-grained localization and classification of various lung abnormalities is a challenging yet important task for combating diseases and, also, pandemics. In this paper, we present one way to detect and classify abnormalities within chest X-ray scans. In particular, we investigate the use of binary image classification (to distinguish between healthy and infected chests) and the weighted box fusion (which constructs a detection box using the proposed boxes within range). We observe that both methods increase the performance of a base model significantly. Furthermore, we improve state of the art on lung segmentation, even in the presence of abnormalities. We do so using transfer learning to fine-tune a UNet model on the Montgomery and Shenzhen datasets. In our experiments, we compare standard augmentations (like crop, pad, rotate, warp, zoom, brightness, and contrast variations) to more complex ones (for example, block masking and diffused noise augmentations). This way, we obtain a state-of-the-art model with a dice score of 97.9\%. In particular, we show that simple augmentations outperform complex ones in our setting.}, 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 }

Wood, Andrew; Hershcovitch, Moshik; Waddington, Daniel; Cohen, Sarel; Chin, Peter Non-Volatile Memory Accelerated Posterior EstimationHigh Performance and Embedded Computing (HPEC) 2021
[ Abstract ] [ BibTeX ] [ Download ]
 
Bayesian inference allows machine learning models to express uncertainty. Current machine learning models use only a single learnable parameter combination when making predictions, and as a result are highly overconfident when their predictions are wrong. To use more learnable parameter combinations efficiently, these samples must be drawn from the posterior distribution. Unfortunately computing the posterior directly is infeasible, so often researchers approximate it with a well known distribution such as a Gaussian. In this paper, we show that through the use of high-capacity persistent storage, models whose posterior distribution was too big to approximate are now feasible, leading to improved predictions in downstream tasks.
@inproceedings{wood2021nonvolatile, abstract = {Bayesian inference allows machine learning models to express uncertainty. Current machine learning models use only a single learnable parameter combination when making predictions, and as a result are highly overconfident when their predictions are wrong. To use more learnable parameter combinations efficiently, these samples must be drawn from the posterior distribution. Unfortunately computing the posterior directly is infeasible, so often researchers approximate it with a well known distribution such as a Gaussian. In this paper, we show that through the use of high-capacity persistent storage, models whose posterior distribution was too big to approximate are now feasible, leading to improved predictions in downstream tasks.}, author = {Wood, Andrew and Hershcovitch, Moshik and Waddington, Daniel and Cohen, Sarel and Chin, Peter}, booktitle = {High Performance and Embedded Computing (HPEC)}, keywords = {sarelcohen danielwaddington hpec moshikhershcovitch andrewwood peterchin year2021}, title = {Non-Volatile Memory Accelerated Posterior Estimation}, year = 2021 }

Wood, Andrew; Hershcovitch, Moshik; Waddington, Daniel; Cohen, Sarel; Wolf, Meredith; Suh, Hongjun; Zong, Weiyu; Chin, Peter Non-Volatile Memory Accelerated Geometric Multi-Scale Resolution AnalysisHigh Performance and Embedded Computing (HPEC) 2021: 1–7
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Dimensionality reduction algorithms are standard tools in a researcher's toolbox. Dimensionality reduction algorithms are frequently used to augment downstream tasks such as machine learning, data science, and also are exploratory methods for understanding complex phenomena. For instance, dimensionality reduction is commonly used in Biology as well as Neuroscience to understand data collected from biological subjects. However, dimensionality reduction techniques are limited by the von-Neumann architectures that they execute on. Specifically, data intensive algorithms such as dimensionality reduction techniques often require fast, high capacity, persistent memory which historically hardware has been unable to provide at the same time. In this paper, we present a re-implementation of an existing dimensionality reduction technique called Geometric Multi-Scale Resolution Analysis (GMRA) which has been accelerated via novel persistent memory technology called Memory Centric Active Storage (MCAS). Our implementation uses a specialized version of MCAS called PyMM that provides native support for Python datatypes including NumPy arrays and PyTorch tensors. We compare our PyMM implementation against a DRAM implementation, and show that when data fits in DRAM, PyMM offers competitive runtimes. When data does not fit in DRAM, our PyMM implementation is still able to process the data.
@inproceedings{wood2021nonvolatile, abstract = {Dimensionality reduction algorithms are standard tools in a researcher's toolbox. Dimensionality reduction algorithms are frequently used to augment downstream tasks such as machine learning, data science, and also are exploratory methods for understanding complex phenomena. For instance, dimensionality reduction is commonly used in Biology as well as Neuroscience to understand data collected from biological subjects. However, dimensionality reduction techniques are limited by the von-Neumann architectures that they execute on. Specifically, data intensive algorithms such as dimensionality reduction techniques often require fast, high capacity, persistent memory which historically hardware has been unable to provide at the same time. In this paper, we present a re-implementation of an existing dimensionality reduction technique called Geometric Multi-Scale Resolution Analysis (GMRA) which has been accelerated via novel persistent memory technology called Memory Centric Active Storage (MCAS). Our implementation uses a specialized version of MCAS called PyMM that provides native support for Python datatypes including NumPy arrays and PyTorch tensors. We compare our PyMM implementation against a DRAM implementation, and show that when data fits in DRAM, PyMM offers competitive runtimes. When data does not fit in DRAM, our PyMM implementation is still able to process the data.}, author = {Wood, Andrew and Hershcovitch, Moshik and Waddington, Daniel and Cohen, Sarel and Wolf, Meredith and Suh, Hongjun and Zong, Weiyu and Chin, Peter}, booktitle = {High Performance and Embedded Computing (HPEC)}, keywords = {sarelcohen danielwaddington hpec moshikhershcovitch hongjunsuh weiyuzong andrewwood meredithwolf peterchin year2021}, pages = {1-7}, title = {Non-Volatile Memory Accelerated Geometric Multi-Scale Resolution Analysis}, 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 \(\operatorname{diam}(G - F) \leq \widehat D \leq \sigma \operatorname{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+\varepsilon)\), constant query time, space \(O(m)\), and a combinatorial preprocessing time of \(\widetilde{O}(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 \(\widetilde{O}(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 \(\widetilde{O}(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})\), \(\widetilde{O}(fn)\) space, and preprocessing time \(\widetilde{O}(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 }