Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR01-063 | 23rd July 2004 00:00

Testing Basic Boolean Formulae Revision of: TR01-063

RSS-Feed

Abstract:


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


Paper:

TR01-063 | 5th August 2001 00:00

Proclaiming Dictators and Juntas or Testing Boolean Formulae





TR01-063
Authors: Michal Parnas, Dana Ron, Alex Samorodnitsky
Publication: 10th September 2001 15:31
Downloads: 3179
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint