ECCC-Report TR01-063https://eccc.weizmann.ac.il/report/2001/063Comments and Revisions published for TR01-063en-usFri, 23 Jul 2004 00:00:00 +0300
Revision 1
| Testing Basic Boolean Formulae Revision of: TR01-063 |
Michal Parnas,
Dana Ron,
Alex Samorodnitsky
https://eccc.weizmann.ac.il/report/2001/063#revision1
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./
Fri, 23 Jul 2004 00:00:00 +0300https://eccc.weizmann.ac.il/report/2001/063#revision1
Paper TR01-063
| Proclaiming Dictators and Juntas or Testing Boolean Formulae |
Michal Parnas,
Dana Ron,
Alex Samorodnitsky
https://eccc.weizmann.ac.il/report/2001/063We 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.
Mon, 10 Sep 2001 15:31:40 +0300https://eccc.weizmann.ac.il/report/2001/063