Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > TESTING:
Reports tagged with testing:
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 >>>

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

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

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

TR07-103 | 28th September 2007
Emanuele Viola

#### Selected Results in Additive Combinatorics: An Exposition

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

TR22-051 | 18th April 2022
Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida

#### Low Degree Testing over the Reals

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

ISSN 1433-8092 | Imprint