Skip to main content

Questions tagged [integer-lattice]

The tag has no usage guidance.

8 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7 votes
0 answers
524 views

On the shortest vector problem (is it $NP$-complete?)

Ajtai has shown that shortest vector problem is $NP$-hard by using randomized reduction from subset sum. Has this been derandomized?
Turbo's user avatar
  • 13k
7 votes
0 answers
173 views

Simplified lattices

Consider the following question: Let $N$ be some large prime number, and suppose we are given $n$ uniformly independent samples $g_i$ from $0...,N-1$. Think of $N$ as being exponentially large in $n$...
Lior Eldar's user avatar
  • 1,224
2 votes
0 answers
67 views

Efficient algorithm for finding closest point for rotated and scaled $\mathbb{Z}_n$ lattice

Suppose we have a $\mathbb{Z}_n$ lattice generated by the identity matrix $I_n$. Here I would like to consider a rotated and scaled $\mathbb{Z}_n$ lattice $\Lambda$ with the generator matrix $M=I_n*O*...
fagd's user avatar
  • 121
2 votes
0 answers
30 views

Finding shortest calculation of the sum of a subset of a group, given sums for other previously summed subsets

Say $S=\{g\in G\}$ is a set of elements in an abelian group $G$ whose group operation $(+)$ is expensive to compute. Given a subset $T\subset S$, we want to compute the sum of $T$'s elements, $\...
Alex Coventry's user avatar
1 vote
0 answers
17 views

Size of solutions in integer programming

Given a linear integer program $Ax\leq b$ with $A\in\mathbb Z^{m\times n}$ and $b\in\mathbb Z^m$ known is there a polynomial time algorithm to give tight upper bounds for $\log_2\|x\|_\infty$ and $\...
Turbo's user avatar
  • 13k
1 vote
0 answers
100 views

Nearly-uniformally sampling lattice points from a basis that lie on the interior of a polytope

Definitions: Consider a polytope $P \subset \mathbb{R}^n$ with a nonempty interior to be $P : \{x \in \mathbb{R}^n | Ax \le B\}$ for appropriate real $n \times m$ matrix $A$ and $m \times 1$ vector $...
Ross Snider's user avatar
  • 2,045
1 vote
0 answers
99 views

Complexity for computing weighted number of paths on integer lattice

Our input is a $(n+1)\times (n+1)$ table filled with some value (integer) for each leftmost and bottom cell $l_i,b_i$ as in the figure. We wish to compute the value of all upper and rightmost cells $...
Joseph Stack's user avatar
  • 1,095
0 votes
0 answers
34 views

doubt about volume packing lemma for intersection of convex sets and lattices (repost from math SE)

Lemma 3.24 of Additive Combinatorics by Tao and Vu states the following: Let $\Gamma \subset \mathbb{R}^d$ be a lattice of full rank, let $V$ be a bounded open subset of $\mathbb{R}^d$, and let $P$ ...
aba's user avatar
  • 91