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?

Improve this question
$\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
    Commented Apr 4, 2018 at 9:18
  • 1
    $\begingroup$ '.. for counting integer points of polytopes in fixed dimension'. $\endgroup$
    – Turbo
    Commented Apr 4, 2018 at 9:53

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Do you know the constant which goes in $O(d\log d)$? $\endgroup$
    – Turbo
    Commented Apr 28, 2023 at 18:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .