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

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

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

We give a self-contained exposition of selected results in additive
combinatorics over the group {0,1}^n. In particular, we prove the
celebrated theorems known as the Balog-Szemeredi-Gowers theorem ('94 and '98) and
the
Freiman-Ruzsa theorem ('73 and '99), leading to the remarkable result
by Samorodnitsky ('07) that linear transformations are efficiently ... more >>>

We study the problem of testing whether a function $f: \mathbb{R}^n \to \mathbb{R}$ is a polynomial of degree at most $d$ in the distribution-free testing model. Here, the distance between functions is measured with respect to an unknown distribution $\mathcal{D}$ over $\mathbb{R}^n$ from which we can draw samples. In contrast ... more >>>