Let $\mathbb F\_2^n$ denote the set of binary vectors of length $n$. A $k$-sparse parity function is a linear function $h:\mathbb F\_2^n\to\mathbb F\_2$ of the form $h(x)=u\cdot x$ for some $u$ of Hamming weight (number of positive entries) $k$. Let $\text{SPF}\_k$ denote the set of $k$-sparse parity functions.


I am interested in finding functions $f$ which look like $k$-SPFs at a glance, but are actually not. Specifically, for any subset $X$ of $\mathbb F\_2^n$ of cardinality $m$, there should exist some $k$-SPF $h$ such that $f(x)=h(x)$ for all $x\in X$. Subject to this constraint, the minimum $L\_1$ distance (i.e. the number of entries on which two functions differ) from $f$ to the set $\text{SPF}\_k$ is to be maximized.


For $m=1$ the problem is fairly easy, but for $m>1$ I am stuck and really am looking for any work which might contain useful ideas. For a concrete question, how about: what is the maximum $L\_1$ distance that can be achieved under the above constraints?



How far from a sparse parity function can a function be and still look like such a function on small sets?
For $k \geq m$, any linear function satisfies this condition. Any linear function that's not $k$-sparce has distance $2^{n-1}$ from the $k$-sparse functions.


For $m \geq 3$, any function satisfying this condition is linear (take $x, y ,x+y$, hence of the form $u \cdot x$ for some $u$). So if $n> k \geq m \geq 3$ then the maximum distance is $2^{n-1}$.


If $m>k$ and $m\geq 3$, then writing $f(x) = v\cdot x$, if $v$ has more than $k$ nonzero entries then we can take $X$ to consist of $k+1$ unit vectors on which $f$ is nonzero, showing that $f$ does not satisfy your condition. So in fact only $k$-sparse parity functions satisfy your condition.


If $m=2$ and $k=1$, then a function satisfies the condition if and only if it is monotone. Probably the majority function has the largest distance.


If $m=2$ and $k \geq 2$, then any function that is zero at $0$ satisfies the condition. Probably $1$ minus the majority function, then arbitrarily set to $0$ at $0$, has the largest distance.


