Abstract: Let f: F_2^n -> {+1, -1} be a Boolean function with the first Fourier norm A and Fourier sparsity s. We will prove that there is an affine subspace of the vector space F_2^n, of dimension O(A), on which the f is constant.
In SocG 2009, Mustafa and Ray showed that a local search algorithm is, somewhat surprisingly, a PTAS for certain geometric set cover/hitting set problems.
