DNF formulas are efficiently testable with relative error

Xi Chen, William Pires, Toniann Pitassi +1

We give a poly$(s,1/\epsilon )$-query algorithm for testing whether an unknown and arbitrary function $f:\{0,1{\}}^n\to \{0,1\}$ is an $s$-term DNF, in the challenging relative-error frame…