All reports by Author Omri Ben-Eliezer:

__
TR19-134
| 4th October 2019
__

Omri Ben-Eliezer, Clement Canonne, Shoham Letzter, Erik Waingarten#### Finding monotone patterns in sublinear time

__
TR18-196
| 19th November 2018
__

Omri Ben-Eliezer#### Testing local properties of arrays

__
TR18-021
| 30th January 2018
__

Omri Ben-Eliezer, Eldar Fischer#### Earthmover Resilience and Testing in Ordered Structures

__
TR17-058
| 7th April 2017
__

Noga Alon, Omri Ben-Eliezer, Eldar Fischer#### Testing hereditary properties of ordered graphs and matrices

Revisions: 1

Omri Ben-Eliezer, Clement Canonne, Shoham Letzter, Erik Waingarten

We study the problem of finding monotone subsequences in an array from the viewpoint of sublinear algorithms. For fixed $k \in \mathbb{N}$ and $\varepsilon > 0$, we show that the non-adaptive query complexity of finding a length-$k$ monotone subsequence of $f \colon [n] \to \mathbb{R}$, assuming that $f$ is $\varepsilon$-far ... more >>>

Omri Ben-Eliezer

We study testing of local properties in one-dimensional and multi-dimensional arrays. A property of $d$-dimensional arrays $f:[n]^d \to \Sigma$ is $k$-local if it can be defined by a family of $k \times \ldots \times k$ forbidden consecutive patterns. This definition captures numerous interesting properties. For example, monotonicity, Lipschitz continuity and ... more >>>

Omri Ben-Eliezer, Eldar Fischer

One of the main challenges in property testing is to characterize those properties that are testable with a constant number of queries. For unordered structures such as graphs and hypergraphs this task has been mostly settled. However, for ordered structures such as strings, images, and ordered graphs, the characterization problem ... more >>>

Noga Alon, Omri Ben-Eliezer, Eldar Fischer

We consider properties of edge-colored vertex-ordered graphs, i.e., graphs with a totally ordered vertex set and a finite set of possible edge colors. We show that any hereditary property of such graphs is strongly testable, i.e., testable with a constant number of queries.

We also explain how the proof can ...
more >>>