Skip to main content

All Questions

Filter by
Sorted by
Tagged with
1 vote
0 answers
92 views

Proof for non-existence of short integer program for squares

We do not know if $P=NP$ or not or if there is a superfast integer mutiplication algorithm. But I do not think either assumption is necessary to answer this question. Is there a way to show within an ...
Turbo's user avatar
  • 13.9k
2 votes
1 answer
339 views

Bit complexity of Barvinok's algorithm

I have seen many references which state Barvinok's algorithm has polynomial time complexity for counting integer points of polytopes in fixed dimension. What exactly is this arithmetic complexity? ...
Turbo's user avatar
  • 13.9k
4 votes
0 answers
242 views

Domination in Nice Lattices

Let an integer vector be nice when it has only two nonzero components, which sum to zero. So (0, 0, 3, 0, -3) and (-1, 0, 1, 0, 0) are examples of nice vectors in $n=5$ dimensions. Call a lattice ...
Dave Pritchard's user avatar