2
$\begingroup$

I have seen many references which state Barvinok's algorithm has polynomial time complexity for counting integer points of polytopes in fixed dimension.

  1. What exactly is this arithmetic complexity?

  2. What exactly is the bit complexity?

Is there a reference that considers this in detail?

$\endgroup$
2
  • $\begingroup$ Maybe if you told us what Barvinok's algorithm is, it would help. You have tags but you need to specify your questions better. $\endgroup$
    – kodlu
    Apr 4 '18 at 9:18
  • 1
    $\begingroup$ '.. for counting integer points of polytopes in fixed dimension'. $\endgroup$
    – Turbo
    Apr 4 '18 at 9:53
4
$\begingroup$

I looked into that at some point. The original paper says $N^{O(d^2)}$, where $d$ is the dimension and $N$ is the size of the input (sum of bit lengths of matrix entries in $A\overline x\le \overline b$). A followup paper by Barvinok says that more careful analysis improves it down to $N^{O(d)}$, but it seems there is a mistake in the calculation. According to Barvinok himself (personal communication), the correct estimate is $N^{O(d \log d)}$. This is the bound we used in this paper (I. Pak, G. Panova, "On the complexity of computing Kronecker coefficients"), see Thm. 2.3.

$\endgroup$

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.