10 citations · 15 across the 17 of their papers we have counts for
24 papers
Near-Optimal Replacement Path Coverings
Davide Bilò, Keerti Choudhary, Sarel Cohen +1
Let and be positive integers. An -replacement path covering (RPC) for a graph is a family of subgraphs such that, for every set of at most …
Simpler and Improved Replacement Path Coverings
Davide Bilò, Shiri Chechik, Keerti Choudhary +2
An important tool in the design of fault-tolerant graph data structures are -replacement path coverings (RPCs). An RPC is a family of subgraphs of a given grap…
Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks
Davide Bilò, Keerti Choudhary, Sarel Cohen +2
We design sensitivity oracles for error-prone networks. For a network problem , the data structure preprocesses a network and sensitivity parameter such that, for…
Temporal Network Creation Games: The Impact of Non-Locality and Terminals
Davide Bilò, Sarel Cohen, Tobias Friedrich +4
We live in a world full of networks where our economy, our communication, and even our social life crucially depends on them. These networks typically emerge from the interaction o…
Improved Distance (Sensitivity) Oracles with Subquadratic Space
Davide Bilò, Shiri Chechik, Keerti Choudhary +3
A distance oracle (DO) with stretch for a graph is a data structure that, when queried with vertices and , returns a value such that $d(s,t)…
A New Approach for Approximating Directed Rooted Networks
Sarel Cohen, Lior Kamma, Aikaterini Niklanovits
We consider the k-outconnected directed Steiner tree problem (k-DST). Given a directed edge-weighted graph , where , and an integer , the goal i…
Robust Parameter Fitting to Realistic Network Models via Iterative Stochastic Approximation
Thomas Bläsius, Sarel Cohen, Philipp Fischbeck +2
Random graph models are widely used to understand network properties and graph algorithms. Key to such analyses are the different parameters of each model, which affect various net…
Improved Approximate Distance Oracles: Bypassing the Thorup-Zwick Bound in Dense Graphs
Davide Bilò, Shiri Chechik, Keerti Choudhary +3
Despite extensive research on distance oracles, there are still large gaps between the best constructions for spanners and distance oracles. Notably, there exist sparse spanners wi…
Temporal Network Creation Games
Davide Bilò, Sarel Cohen, Tobias Friedrich +4
Most networks are not static objects, but instead they change over time. This observation has sparked rigorous research on temporal graphs within the last years. In temporal graphs…
Approximate Distance Sensitivity Oracles in Subquadratic Space
Davide Bilò, Shiri Chechik, Keerti Choudhary +4
An -edge fault-tolerant distance sensitive oracle (-DSO) with stretch is a data structure that preprocesses a given undirected, unweighted graph with vertice…
Fault-Tolerant ST-Diameter Oracles
Davide Bilò, Keerti Choudhary, Sarel Cohen +3
Given two vertex sets and in a graph, the -diameter is the maximum --distance between vertices and . We study the problem of estimating the $ST…
Compact Distance Oracles with Large Sensitivity and Low Stretch
Davide Bilò, Keerti Choudhary, Sarel Cohen +3
An -edge fault-tolerant distance sensitive oracle (-DSO) with stretch is a data structure that preprocesses an input graph . When queried with the triple $(s,t,F…
Deep Distance Sensitivity Oracles
Davin Jeong, Allison Gunby-Mann, Sarel Cohen +5
One of the most fundamental graph problems is finding a shortest path from a source to a target node. While in its basic forms the problem has been studied extensively and efficien…
Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances
Davide Bilò, Keerti Choudhary, Sarel Cohen +2
We construct data structures for extremal and pairwise distances in directed graphs in the presence of transient edge failures. Henzinger et al. [ITCS 2017] initiated the study of…
Non-Volatile Memory Accelerated Geometric Multi-Scale Resolution Analysis
Andrew Wood, Moshik Hershcovitch, Daniel Waddington +5
Dimensionality reduction algorithms are standard tools in a researcher's toolbox. Dimensionality reduction algorithms are frequently used to augment downstream tasks such as machin…
Fast Feature Selection with Fairness Constraints
Francesco Quinzan, Rajiv Khanna, Moshik Hershcovitch +4
We study the fundamental problem of selecting optimal features for model construction. This problem is computationally challenging on large datasets, even with the use of greedy al…
What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization
Maximilian Böther, Otto Kißig, Martin Taraz +3
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…
Fixed-Parameter Sensitivity Oracles
Davide Bilò, Katrin Casel, Keerti Choudhary +5
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…
Space-Efficient Fault-Tolerant Diameter Oracles
Davide Bilò, Sarel Cohen, Tobias Friedrich +1
We design -edge fault-tolerant diameter oracles (-FDOs). We preprocess a given graph on vertices and edges, and a positive integer , to construct a data struct…
Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles
Davide Bilò, Sarel Cohen, Tobias Friedrich +1
Given a graph with a source vertex , the Single Source Replacement Paths (SSRP) problem is to compute, for every vertex and edge , the length of a shortest pat…
ScrabbleGAN: Semi-Supervised Varying Length Handwritten Text Generation
Sharon Fogel, Hadar Averbuch-Elor, Sarel Cohen +2
Optical character recognition (OCR) systems performance have improved significantly in the deep learning era. This is especially true for handwritten text recognition (HTR), where…
Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
Noga Alon, Shiri Chechik, Sarel Cohen
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 random…
Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms
Moab Arar, Shiri Chechik, Sarel Cohen +2
We present a simple randomized reduction from fully-dynamic integral matching algorithms to fully-dynamic "approximately-maximal" fractional matching algorithms. Applying this redu…
Minimal Indices for Successor Search
Sarel Cohen, Amos Fiat, Moshik Hershcovitch +1
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 bits to …