13 citations · 32 across the 10 of their papers we have counts for
11 papers
Deterministic Online Embedding of Metric Spaces into Low Dimensional Spaces
Noam Licht, Ilan Newman, Yuri Rabinovich
We study online embeddings of metric spaces into Euclidean spaces of a constant dimension , against an adaptive adversary. While the case of is well understood, for high…
Online embedding of metrics
Ilan Newman, Yuri Rabinovich
We study deterministic online embeddings of metrics spaces into normed spaces and into trees against an adaptive adversary. Main results include a polynomial lower bound on the (mu…
Large Simple d-Cycles in Simplicial Complexes
Roy Meshulam, Ilan Newman, Yuri Rabinovich
We show that the size of the largest simple d-cycle in a simplicial d-complex is at least a square root of 's density. This generalizes a well-known classical result of Erdő…
Hamiltonian and Pseudo-Hamiltonian Cycles and Fillings In Simplicial Complexes
Rogers Mathew, Ilan Newman, Yuri Rabinovich +1
We introduce and study a -dimensional generalization of Hamiltonian cycles in graphs - the Hamiltonian -cycles in (the complete simplicial -complex over a vertex s…
Rational Polygons: Odd Compression Ratio and Odd Plane Coverings
Rom Pinchasi, Yuri Rabinovich
Let P be a polygon with rational vertices in the plane. We show that for any finite odd-sized collection of translates of P, the area of the set of points lying in an odd number of…
Boundaries of Hypertrees, and Hamiltonian Cycles in Simplicial Complexes
Rogers Mathew, Ilan Newman, Yuri Rabinovich +1
A -hypertree on is a maximal acyclic -dimensional simplicial complex with full -skeleton on the vertex set . Alternatively, in the language of algebraic top…
On Connectivity of the Facet Graphs of Simplicial Complexes
Ilan I. Newman, Yuri Rabinovich
The paper studies the connectivity properties of facet graphs of simplicial complexes of combinatorial interest. In particular, it is shown that the facet graphs of -cycles, …
Extremal problems on shadows and hypercuts in simplicial complexes
Nati Linial, Ilan Newman, Yuval Peled +1
Let be an -vertex forest. We say that an edge is in the shadow of if contains a cycle. It is easy to see that if is "almost a tree", that is…
Binary Jumbled Pattern Matching via All-Pairs Shortest Paths
Danny Hermelin, Gad M. Landau, Yuri Rabinovich +1
In binary jumbled pattern matching we wish to preprocess a binary string in order to answer queries which ask for a substring of that is of size and has exactly…
Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs
Victor Chepoi, Feodor Dragan, Ilan Newman +2
In this paper, we present a simple factor 6 algorithm for approximating the optimal multiplicative distortion of embedding a graph metric into a tree metric (thus improving and sim…
Finite Volume Spaces and Sparsification
Ilan Newman, Yuri Rabinovich
We introduce and study finite -volumes - the high dimensional generalization of finite metric spaces. Having developed a suitable combinatorial machinery, we define -vol…