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