All reports by Author Ilan Newman:

__
TR08-097
| 14th November 2008
__

Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg#### Hierarchy Theorems for Property Testing

Revisions: 1

__
TR07-054
| 25th May 2007
__

Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur#### Testing Properties of Constraint-Graphs

__
TR06-103
| 5th July 2006
__

Oded Lachish, Ilan Newman, Asaf Shapira#### Space Complexity vs. Query Complexity

__
TR05-153
| 9th December 2005
__

Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur#### Testing Orientation Properties

__
TR05-152
| 9th December 2005
__

Oded Lachish, Ilan Newman#### Languages that are Recognized by Simple Counter Automata are not necessarily Testable

__
TR05-095
| 26th August 2005
__

Noga Alon, Ilan Newman, Alexander Shen, GĂˇbor Tardos, Nikolay Vereshchagin#### Partitioning multi-dimensional sets in a small number of ``uniform'' parts

__
TR04-092
| 3rd November 2004
__

Oded Lachish, Ilan Newman#### Testing Periodicity

__
TR04-081
| 9th September 2004
__

Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolay Vereshchagin#### Increasing Kolmogorov Complexity

__
TR96-053
| 6th August 1996
__

Yosi Ben-Asher, Ilan Newman#### Geometric Approach for Optimal Routing on Mesh with Buses

Revisions: 1

__
TR96-044
| 6th August 1996
__

Yosi Ben-Asher, Ilan Newman#### Optimal Search in Trees

Revisions: 1

Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg

Referring to the query complexity of property testing,

we prove the existence of a rich hierarchy of corresponding

complexity classes. That is, for any relevant function $q$,

we prove the existence of properties that have testing

complexity Theta(q).

Such results are proven in three standard

domains often considered in property ...
more >>>

Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur

We study a model of graph related formulae that we call

the \emph{Constraint-Graph model}. A

constraint-graph is a labeled multi-graph (a graph where loops

and parallel edges are allowed), where each edge $e$ is labeled

by a distinct Boolean variable and every vertex is

associate with a Boolean function over ...
more >>>

Oded Lachish, Ilan Newman, Asaf Shapira

Combinatorial property testing deals with the following relaxation

of decision problems: Given a fixed property and an input $x$, one

wants to decide whether $x$ satisfies the property or is ``far''

from satisfying it. The main focus of property testing is in

identifying large families of properties that can be ...
more >>>

Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur

We propose a new model for studying graph related problems

that we call the \emph{orientation model}. In this model, an undirected

graph $G$ is fixed, and the input is any possible edge orientation

of $G$. A property is now a property of the directed graph that is

obtained by a ...
more >>>

Oded Lachish, Ilan Newman

Combinatorial property testing deals with the following relaxation of

decision problems: Given a fixed property and an input $f$, one wants

to decide whether $f$ satisfies the property or is `far' from satisfying

the property.

It has been shown that regular languages are testable,

and that there exist context free ...
more >>>

Noga Alon, Ilan Newman, Alexander Shen, GĂˇbor Tardos, Nikolay Vereshchagin

Our main result implies the following easily formulated statement. The set of edges E of every finite bipartite graph can be split into poly(log |E|) subsets so the all the resulting bipartite graphcs are almost regular. The latter means that the ratio between the maximal and minimal non-zero degree of ... more >>>

Oded Lachish, Ilan Newman

A string $\alpha\in\Sigma^n$ is called {\it p-periodic},

if for every $i,j \in \{1,\dots,n\}$, such that $i\equiv j \bmod p$,

$\alpha_i = \alpha_{j}$, where $\alpha_i$ is the $i$-th place of $\alpha$.

A string $\alpha\in\Sigma^n$ is said to be $period(\leq g)$,

if there exists $p\in \{1,\dots,g\}$ such that $\alpha$ ...
more >>>

Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolay Vereshchagin

How much do we have to change a string to increase its Kolmogorov complexity. We show that we can

increase the complexity of any non-random string of length n by flipping O(sqrt(n)) bits and some strings

require

Omega(sqrt(n)) bit flips. For a given m, we also give bounds for ...
more >>>

Yosi Ben-Asher, Ilan Newman

The architecture of 'mesh of buses' is an important model in parallel computing. Its main advantage is that the additional broadcast capability can be used to overcome the main disadvantage of the mesh, namely its relatively large diameter. We show that the addition of buses indeed accelerates routing times. Furthermore, ... more >>>

Yosi Ben-Asher, Ilan Newman

It is well known that the optimal solution for

searching in

a finite total order set is the binary search.

In the binary search we

divide the set into two ``halves'', by querying the middle

element, and continue the search on the suitable half.

What is the equivalent of binary ...
more >>>