All reports by Author Michal Parnas:

__
TR05-094
| 9th August 2005
__

Michal Parnas, Dana Ron#### On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms

Revisions: 1

__
TR04-010
| 26th January 2004
__

Michal Parnas, Dana Ron, Ronitt Rubinfeld#### Tolerant Property Testing and Distance Approximation

__
TR01-063
| 5th August 2001
__

Michal Parnas, Dana Ron, Alex Samorodnitsky#### Proclaiming Dictators and Juntas or Testing Boolean Formulae

Revisions: 1

Michal Parnas, Dana Ron

We consider the problem of estimating the size, $VC(G)$, of a

minimum vertex cover of a graph $G$, in sublinear time,

by querying the incidence relation of the graph. We say that

an algorithm is an $(\alpha,\eps)$-approximation algorithm

if it outputs with high probability an estimate $\widehat{VC}$

such that ...
more >>>

Michal Parnas, Dana Ron, Ronitt Rubinfeld

A standard property testing algorithm is required to determine

with high probability whether a given object has property

P or whether it is \epsilon-far from having P, for any given

distance parameter \epsilon. An object is said to be \epsilon-far

from having ...
more >>>

Michal Parnas, Dana Ron, Alex Samorodnitsky

We consider the problem of determining whether a given

function f : {0,1}^n -> {0,1} belongs to a certain class

of Boolean functions F or whether it is far from the class.

More precisely, given query access to the function f and given

a distance parameter epsilon, we would ...
more >>>