Marco Cadoli, Francesco Donini, Paolo Liberatore, Marco Schaerf

In this paper we study the problem of approximating a boolean

function using the Hamming distance as the approximation measure.

Namely, given a boolean function f, its k-approximation is the

function f^k returning true on the same points in which f does,

plus all points whose Hamming distance from the ...
more >>>

C. Seshadhri, Deeparnab Chakrabarty

The problem of testing monotonicity

of a Boolean function $f:\{0,1\}^n \to \{0,1\}$ has received much attention

recently. Denoting the proximity parameter by $\varepsilon$, the best tester is the non-adaptive $\widetilde{O}(\sqrt{n}/\varepsilon^2)$ tester

of Khot-Minzer-Safra (FOCS 2015). Let $I(f)$ denote the total influence

of $f$. We give an adaptive tester whose running ...
more >>>