Publications (22)
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…
A characterization of one-sided error testable graph properties in bounded degeneracy graphs
Oded Lachish, Amit Levi, Ilan Newman +1
We consider graph property testing in -degenerate graphs under the random neighbor oracle model (Czumaj and Sohler, FOCS 2019). In this framework, a tester explores a graph by s…
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…
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…
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…
No Ascending Auction can find Equilibrium for SubModular valuations
Oren Ben-Zwi, Ilan Newman
We show that no efficient ascending auction can guarantee to find even a minimal envy-free price vector if all valuations are submodular, assuming a basic complexity theory's assum…