All reports by Author Oded Lachish:

__
TR15-089
| 31st May 2015
__

Eldar Fischer, Oded Lachish, Yadu Vadusev#### Trading query complexity for sample-based testing and multi-testing scalability}

__
TR13-082
| 6th June 2013
__

Eldar Fischer, Yonatan Goldhirsh, Oded Lachish#### Some properties are not even partially testable

__
TR07-127
| 22nd November 2007
__

Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish#### Sound 3-query PCPPs are Long

__
TR07-054
| 25th May 2007
__

Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur#### Testing Properties of Constraint-Graphs

__
TR06-103
| 5th July 2006
__

Oded Lachish, Ilan Newman, Asaf Shapira#### Space Complexity vs. Query Complexity

__
TR05-153
| 9th December 2005
__

Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur#### Testing Orientation Properties

__
TR05-152
| 9th December 2005
__

Oded Lachish, Ilan Newman#### Languages that are Recognized by Simple Counter Automata are not necessarily Testable

__
TR04-092
| 3rd November 2004
__

Oded Lachish, Ilan Newman#### Testing Periodicity

Eldar Fischer, Oded Lachish, Yadu Vadusev

We show here that every non-adaptive property testing algorithm making a constant number of queries, over a fixed alphabet, can be converted to a sample-based (as per [Goldreich and Ron, 2015]) testing algorithm whose average number of queries is a fixed, smaller than $1$, power of $n$. Since the query ... more >>>

Eldar Fischer, Yonatan Goldhirsh, Oded Lachish

For a property $P$ and a sub-property $P'$, we say that $P$ is $P'$-partially testable with $q$ queries if there exists an algorithm that distinguishes, with high probability, inputs in $P'$ from inputs $\epsilon$-far from $P$ by using $q$ queries. There are natural properties that require many queries to test, ... more >>>

Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish

We initiate the study of the tradeoff between the {\em length} of a

probabilistically checkable proof of proximity (PCPP) and the

maximal {\em soundness} that can be guaranteed by a $3$-query

verifier with oracle access to the proof. Our main observation is

that a verifier limited to querying a short ...
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 >>>

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

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

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