35 citations · 114 across the 25 of their papers we have counts for
6 papers · 1 filter
Local treewidth of random and noisy graphs with applications to stopping contagion in networks
Hermish Mehta, Daniel Reichman
We study the notion of local treewidth in sparse random graphs: the maximum treewidth over all -vertex subgraphs of an -vertex graph. When is not too large, we give nearl…
Multitasking Capacity: Hardness Results and Improved Constructions
Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths +5
We consider the problem of determining the maximal such that every matching of size (or at most ) in a bipartite graph contains an induced matching of s…
Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays
Omri Ben-Eliezer, Simon Korman, Daniel Reichman
Understanding the local behaviour of structured multi-dimensional data is a fundamental problem in various areas of computer science. As the amount of data is often huge, it is des…
LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs
Nikhil Bansal, Daniel Reichman, Seeun William Umboh
We give a general approach for solving optimization problems on noisy minor free graphs, where a δ-fraction of edges and vertices are adversarially corrupted. The noisy setting was…
Tight Approximation of Image Matching
Simon Korman, Daniel Reichman, Gilad Tsur
In this work we consider the {\em image matching} problem for two grayscale images, and (where pixel values range from 0 to 1). Our goal is to find an affi…
Recoverable Values for Independent Sets
Uriel Feige, Daniel Reichman
The notion of {\em recoverable value} was advocated in work of Feige, Immorlica, Mirrokni and Nazerzadeh [Approx 2009] as a measure of quality for approximation algorithms. There t…