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

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

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

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

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

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

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$ is {\it p-periodic}. ... more >>>

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 increasing ... more >>>

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

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