Revision #1 Authors: Michal Parnas, Dana Ron, Alex Samorodnitsky

Accepted on: 23rd July 2004 00:00

Downloads: 2403

Keywords:

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 like to decide whether f belongs to F or whether it differs from

every g in F on more than an epsilon-fraction of the domain elements.

The classes of functions we consider are singleton (``dictatorship'')

functions, monomials, and monotone DNF functions with a bounded number of

terms. In all cases we provide algorithms whose query complexity is

independent of n (the number of variables), and linear in 1/\epsilon./

TR01-063 Authors: Michal Parnas, Dana Ron, Alex Samorodnitsky

Publication: 10th September 2001 15:31

Downloads: 2433

Keywords:

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 like to decide whether

f belongs to F or whether it differs from every g in F

on more than an epsilon-fraction of the domain elements.

The classes of functions we consider are singleton (``dictatorship'')

functions, monomials, and monotone DNF functions with a bounded

number of terms. In all cases we provide algorithms whose

query complexity is independent of n (the number of function

variables), and polynomial in the other relevant parameters.