See what Radu has done with the permanent mod 2^k
Issue #5
new
Radu Curticapean and Mingji Xia just got
"Parameterizing the Permanent: genus, apices, minors, evaluation mod 2^k"
accepted for FOCS 2015. From what Radu told me earlier by email I think they show \OplusW[1]-hardness for permanent mod 2^k parameterized by k (The problem we first suggested Isak could look into as a farfetched possible result) I bet the proof is complicated....
We need to at least skim the paper to see what we need to cite.
Comments (4)
-
-
No copy is available yet, but here is his reply:
“Genau. Sogar auf Graphen, die nach Löschung von O(k) Knoten planar sind. Und wir schließen Algorithmen mit Laufzeit n^o(k/ log k) auf solchen Graphen aus.”
-
reporter
Hmm, I was under the impression that you could count perfect matchings in genus k graphs in time 2^{2k}poly(n) time [http://www.unige.ch/math/folks/cimasoni/KW.pdf].
-
I’m not sure that’s a contradiction. The genus of a k-apex graph needn’t be a function of k? (Or what? Drunk now, and no time tomorrow.)
- Log in to comment
Ah, we were kind of waiting for this. Good. Great that they’ve landed this on FOCS. I’ve asked him for a copy.