All Questions
Tagged with computational-complexity lattices
16 questions
8
votes
1
answer
3k
views
Polynomial-time quantum algorithms for lattice problems (GapSVP, SIVP, LWE)
The author of a recent preprint claims to have found polynomial-time quantum algorithms for solving the following lattice problems: the Decisional Shortest Vector Problem (GapSVP), the Shortest ...
- 157
3
votes
1
answer
287
views
On shortest vector problem
Assume we have an oracle which gives the length of the shortest vector in a lattice. Given this oracle can we find the shortest vector in polynomial time?
- 13.9k
1
vote
0
answers
34
views
Does $2$ variable linear Diophantine equation in $NC$ imply $2$ dimensional shortest vector is in $NC$?
Consider the Linear Diophantine in known $a,b,c\in\mathbb Z$
$$ax+by=c.$$
Above can be solve by Extended Euclidean which is not in $NC$ as far as we know. It is clear if Extended Euclidean is in $NC$ ...
- 13.9k
2
votes
0
answers
221
views
Modular inverse computation - avoiding Euclidean algorithm
Modular inverse is known to be computable by Extended Euclidean algorithm which is the reaping the rewards of computing the GCD of two numbers or proving two numbers are coprime.
If we already know ...
- 13.9k
5
votes
2
answers
312
views
Is it still not known whether the construction of shortest nonzero vector of a lattice w.r.t. $l^2$-norm is NP-hard?
It was shown in
P. van Emde Boas, Another NP-complete partition problem and the complexity of computing short
vectors in a lattice
that the construction of a shortest nonzero vector of a Euclidean ...
- 457
4
votes
0
answers
137
views
Lattice reduction of basis with non-integer coefficients
Suppose I have an ordered basis $\{b_1, \dots, b_n\}$ of a lattice in $\mathbb{R}^n$, but I do not assume that $b_i \in \mathbb{Z}^n$ for all $1 \leq i \leq n$.
I would like to perform lattice ...
- 554
2
votes
1
answer
180
views
Intersection of a $\mathbb{Q}$-affine space with $\mathbb{Z}^n$
Let $E$, a $\mathbb{Q}$-affine space of arbitrary dimension included in $\mathbb{Q}^n$. Is it possible to check efficiently if $E \cap \mathbb{Z}^n$ is empty or not?
If is an hard problem could give ...
- 215
1
vote
0
answers
70
views
Shortest Lattice Vector with restricted $x$
Let $\Lambda$ be a lattice with basis, $B$ consisting of vectors $b_i$, so that the elements of $\Lambda$ are of form, $y\in \Lambda \iff y=Bx=\sum_i b_ix_i$ for some $x_i\in\mathbb{Z}$.
My questions ...
- 1,096
2
votes
1
answer
159
views
Counting lattice points can some give all?
Given convex polytope $\mathcal P\subseteq\Bbb R^n$ with $\mathcal P_\Bbb Z\leq2^n$ integer points and given locations of $O(\log \mathcal P_\Bbb Z)$ integer points in some positions can we obtain $\...
- 13.9k
10
votes
3
answers
985
views
Approximate volume computation and lattice point enumeration - hardness
Both volume computation and lattice point enumeration of convex polyhedron are $\#P$ hard. However there is a randomized polytime algorithm for constant factor approximation for volume computation.
...
- 13.9k
7
votes
3
answers
416
views
Checking a generating set of $\mathbb{Z}^k$
Let $a_1, \ldots, a_n \in \mathbb{Z}^k$. I need to check if $a_1, \ldots, a_n$ is a generating set of $\mathbb{Z}^k$, that is, every vector $v \in \mathbb{Z}^k$ can be represented as an integer linear ...
- 5,590
6
votes
1
answer
304
views
Shortest vector problem over polynomials
In shortest vector problem, given a lattice in $\Bbb Z^n$, we seek the shortest non-zero vector in the lattice. This problem is computationally difficult.
Answer in Evidence for integer factorization ...
- 13.9k
3
votes
2
answers
501
views
Lattice reduction on an orthonormal lattice?
Suppose you are given an inner product on a vector space and given a set of linearly independent vectors, and that you have been promised that the lattice they span has an orthonormal basis. Can you (...
- 8,688
5
votes
1
answer
2k
views
Lovász $\delta$ condition for LLL Algorithm
http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm
What is the importance of the $\delta$ parameter for LLL bases called Lovász condition?
...
- 13.9k
8
votes
2
answers
3k
views
How to find nearest lattice point to given point in R^n ? Is it NP ?
Consider some lattice in R^n.
Take some point "P" in R^n (which does not belong to this lattice in general).
What are the algorithms to find some nearest lattice point to "P" ?
"Nearest" - means in ...
- 24.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 ...
- 1,288