2
$\begingroup$

I want to solve the following coNP-complete problem efficiently in practice: Given a linear matroid represented as $k \times n$ matrix over a finite field $\mathbb{F}_p$ (where $p$ is large prime), test if the matroid is isomorphic to the uniform matroid with $n$ elements and rank $k$. In other words, test if all $k \times k$ submatrices have rank $k$.

Is there some algebraic software that can solve this problem potentially much faster than brute-force? In particular I am interested in methods that are able to beat the ${n\choose k}$ brute-force on at least some yes-instances.

I have tried reducing to integer programming and solving with CPLEX, but it is worse than brute-force already on two-digit primes.

$\endgroup$
4
  • $\begingroup$ Do you want worst-case, or just in practice? Brute force is ~$\binom{n}{k}$, and UMI is W[1]-hard when parametrized by k (see eg paragraph before Thm 4 here, so while you might be able to do better than brute force, there's unlikely to be an algorithm that completely pulls k out of the exponent (unless W[1]=FPT). $\endgroup$ Mar 31, 2021 at 3:49
  • 1
    $\begingroup$ Just in practice. To me it seems quite difficult to beat ${n}\choose{k}$ even in the best case if the answer is yes. Also thanks for the reference, I hadn't seen that before. $\endgroup$
    – Laakeri
    Mar 31, 2021 at 5:12
  • 1
    $\begingroup$ On further reflection, maybe an interesting way to frame this as a completely theoretical question would be to ask if we can solve isomorphism to $U_{2n,n}$ in time $O(1.999^n)$, or would it violate SETH? $\endgroup$
    – Laakeri
    May 28, 2021 at 9:36
  • $\begingroup$ Interesting Q. But if you're interested in practice, one of the key things to take advantage of is that practical cases often aren't the worst cases. $\endgroup$ May 28, 2021 at 14:30

1 Answer 1

2
$\begingroup$

You can get a square-root speed-up with a time-space tradeoff if you are working in $\mathbb{F}_2$.

The matrix $M$ is a no-instance iff there exists a non-zero vector $v$ of Hamming weight $\le k$ (i.e., with at most $k$ non-zero coordinates) such that $Mv=0$. This is equivalent to saying that there exist $t,u$ of Hamming weight $\le k/2$ such that $Mt=Mu$ (since then $M(t-u)=0$ and $t-u$ has Hamming weight $\le k$).

Now you can enumerate all such $t$ and store $Mt$ in a hashtable, and look for collisions (or, sort the values $Mt$ and look for repeats). This requires approximately ${n \choose k/2}$ time and space, which is better than your brute-force method. But again it only works over $\mathbb{F}_2$.

You can improve this a bit further as follows. Randomly partition the $n$ coordinates into two groups of $n/2$ coordinates, and restrict $t$ to be non-zero only on the first group (its zero on the second group), and $u$ to be non-zero only on the second group (it is zero on the first group). Then if such $v$ exists, with probability ${k \choose k/2}/2^k \approx 1/\sqrt{\pi k/2}$, there exist $t,u$ that satisfy this restriction. So, enumerate all such $t$, store $Mt$ in a hashtable, and for each $u$, look up $Mu$ in the hashtable (or, merge a sorted list of $Mt$ values and a sorted list of $Mu$ values). If you repeat $40 \sqrt{\pi k/2}$ times, with a different partition each time, then you'll have an overwhelming probability of finding a solution if one exists. This requires $40 \sqrt{\pi k/2} {n/2 \choose k/2}$ time and space, which is better than the above.

It's possible you might be able to apply other algorithms for finding a low-weight codeword in a linear code to this problem, if you are working in $\mathbb{F}_2$.

If you are working over $\mathbb{F}_p$ with $p>2$, then you can still do this method, and the running time will be something like $40 \sqrt{\pi k/2} {n/2 \choose k/2} (p-1)^{k/2}$ time and space. We can compare this to the brute-force approach of enumerating all subsets of $k$ of the columns, then using Gaussian elimination to compute its rank; that will have running time ${n \choose k} k^3$. The brute-force approach is better when $n/k \ll p$, and my approach is better when $n/k \gg p$.

$\endgroup$
4
  • 1
    $\begingroup$ Thanks, but I'm afraid that the case of $\mathbb{F}_2$ is not relevant to me. In particular the problem is originally over rationals, but to avoid big numbers I work on $\mathbb{F}_p$ for a randomly chosen large prime $p$. (I hope that this does not make the problem harder.) I'll look into SVP. $\endgroup$
    – Laakeri
    Mar 31, 2021 at 8:15
  • 1
    $\begingroup$ @Laakeri, OK, sorry about that. I'll delete this answer shortly. On further reflection, I doubt SVP is going to be useful. $\endgroup$
    – D.W.
    Mar 31, 2021 at 8:47
  • $\begingroup$ What goes wrong if you try to do your first trick over Fp? Seems to work in time and space roughly $\binom{n}{k/2}p^{k/2}$. $\endgroup$ Apr 1, 2021 at 5:21
  • $\begingroup$ @JoshuaGrochow, good point. I've updated the answer with that idea. I doubt it will be useful unless $p$ is small, but who knows. $\endgroup$
    – D.W.
    Apr 1, 2021 at 6:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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