Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ILAN NEWMAN:
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

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 >>>


TR07-054 | 25th May 2007
Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur

Testing Properties of Constraint-Graphs

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 >>>


TR06-103 | 5th July 2006
Oded Lachish, Ilan Newman, Asaf Shapira

Space Complexity vs. Query Complexity

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 >>>


TR05-153 | 9th December 2005
Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur

Testing Orientation Properties

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 >>>


TR05-152 | 9th December 2005
Oded Lachish, Ilan Newman

Languages that are Recognized by Simple Counter Automata are not necessarily Testable

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 >>>


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

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 >>>


TR04-092 | 3rd November 2004
Oded Lachish, Ilan Newman

Testing Periodicity

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 >>>


TR04-081 | 9th September 2004
Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolay Vereshchagin

Increasing Kolmogorov Complexity

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 >>>


TR96-053 | 6th August 1996
Yosi Ben-Asher, Ilan Newman

Geometric Approach for Optimal Routing on Mesh with Buses

Revisions: 1

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 >>>


TR96-044 | 6th August 1996
Yosi Ben-Asher, Ilan Newman

Optimal Search in Trees

Revisions: 1

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 >>>




ISSN 1433-8092 | Imprint