4
$\begingroup$

In the course of my research, I stumbled upon a problem which can be recast as the following decision problem:


First some notation:

Let $\mathbb{F}=\{0,1\}$ be the binary field. For $x\in\mathbb{F}^N$, $N\in\mathbb{N}$ arbitrary, let $w(x)$ denote the Hamming weight of $x$, i.e., the number of non-zero components.

Let $B\subset \mathbb{F}^N$ be an arbitrary set of binary vectors. Define the Hamming weight of $B$ as $w(B)\equiv \max_{b\in B}w(b)$.

Now the problem:

Given a linear subspace $V\leq \mathbb{F}^N$ and a positive integer $C\leq N$.

Is there a basis $B$ of $V$ such that $w(B)\leq C$ ?

The "size" of a particular instance is the dimension $\rm{dim} V=K\leq N$, as the brute-force solution requires the computation of $w$ for all possible bases of $V$.

Clearly, the evaluation of $w(B)$ requires $\mathcal{O}(KN)$ steps; therefore the problem is in NP.

As an example: If $V=\mathbb{F}^N$ and $C\geq 1$, the answer is positive as the standard basis ($e_i=(0,\dots,1,\dots,0$) has hamming weight 1. Obviously this is not the case for generic, non-trivial subspaces $V$.


I think the problem is closely related to the theory of linear binary codes (in fact, $V$ is one). In this context, however, people seem to be more interested in the minimum Hamming weights as these relate to the Hamming distance of the code.

As my understanding of and experience in complexity theory is rather sparse (my background is condensed matter physics), I do not know wheter this problem is known in complexity theory. If so, what is its complexity class (time complexity) ? Are there any relevant publications for this particular problem? Maybe it's even a simple textbook problem?

Any hint is welcome. Thanks in advance.

$\endgroup$
  • $\begingroup$ I wonder if you might be able to reduce this to the problem of finding the minimum-weight codeword of linear code. Let $M$ be a matrix such that $Mv=0$ iff $v \in V$ (i.e., find a basis of $V^\perp = \{u : u.v=0\}$ and put each basis element in a row of $M$). Find a minimum-weight codeword $b$ for $M$, and add this to $B$. Replace $V$ with $V/b$ ($\{u \in V : u.b=0\}$) and repeat. After $K$ iterations, you'll have a basis $B$. Can we prove that this will find a basis $B$ of the form desired, if one exists? I realize this reduction goes the wrong way, though, so it's probably not helpful. $\endgroup$ – D.W. Nov 25 '16 at 17:08
2
$\begingroup$

This is background, rather than a complete solution of your specific question.

What you're looking at are called linear anticodes in the literature, while Ahlswede uses the term "diameter" for the maximum distance of a code. Like normal codes, there are some bounds on maximum size, given length and distance.

The problem may also be stated in terms of the minimum number of coordinates where two codewords agree. If the alphabet is nonbinary, it gets much more complicated, and [1] has an upper bound for that case, but also discusses the result from [2] which is the following:

Given a binary anticode with diameter (maximum distance) $n-t$ over the binary alphabet (which need not be linear), letting $N_2(n,t)$ be the maximum cardinality of such a code we have $$N_2(n,t)=\left\{ \begin{array}{lrr} \sum_{i=0}^{(n-t)/2} \binom{n}{i},&\quad& if~n-t~is~even,\\ & & \\ 2 \sum_{i=0}^{(n-t-1)/2} \binom{n-1}{i},&\quad& if~n-t~is~odd. \end{array} \right. $$

See the reference [1] for details. Apparently the binary diametric theorem above was proved by Kleitman in [2]. This bound applies to all anticodes and would apply to your linear anticode as well.

Farrell had an earlier article on anticodes which considered linear anticodes obtained by deleting columns from a simplex code, which may also be of interest, it shouldn't be hard to locate the reference.

[1] Ahlswede and Khachtarian, The Diametric Theorem in Hamming Spaces:Optimal Anticodes, Adv. Appl. Math:20, 429:449 1998.

[2] D. J. Kleitman, On a combinatorial conjecture of Erdos, J. Combin. Theory, Volume 1, pp.209-214, 1966.

$\endgroup$
  • 1
    $\begingroup$ Thanks a lot for bringing up anticodes. I'll have a look at the references you mentioned to understand how this concept relates to my particular problem. $\endgroup$ – NcLang Jan 9 '17 at 7:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.