Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

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

Testing Basic Boolean Formulae Revision of: TR01-063

Revision #1
Authors: Michal Parnas, Dana Ron, Alex Samorodnitsky
Accepted on: 23rd July 2004 00:00
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 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
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.
The classes of functions we consider are singleton (dictatorship'')