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

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

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

Emanuele Viola

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

Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida

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