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

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