1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.