31 citations · 95 across the 16 of their papers we have counts for
19 papers
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…
Parameterized Convexity Testing
Abhiruk Lahiri, Ilan Newman, Nithin Varma
In this work, we develop new insights into the fundamental problem of convexity testing of real-valued functions over the domain . Specifically, we present a nonadaptive algor…
Coresets for Decision Trees of Signals
Ibrahim Jubran, Ernesto Evgeniy Sanches Shayda, Ilan Newman +1
A -decision tree (or -tree) is a recursive partition of a matrix (2D-signal) into block matrices (axis-parallel rectangles, leaves) where each rectangle is assi…
Strongly Sublinear Algorithms for Testing Pattern Freeness
Ilan Newman, Nithin Varma
For a permutation , a function contains a -appearance if there exists such that for all $s,t \in [k…
New Sublinear Algorithms and Lower Bounds for LIS Estimation
Ilan Newman, Nithin Varma
Estimating the length of the longest increasing subsequence (LIS) in an array is a problem of fundamental importance. Despite the significance of the LIS estimation problem and the…
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ő…