Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [integer-lattice]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
7 votes
1 answer
388 views

Comparing Shor's and Regev's Quantum Factoring algorithm

Regev's factoring algorithm works as follows: (Say, for factoring integer $N$; input bitsize $n$). Step I: Choose $a_1,\ ..., a_d$ small number (say, squares of first $d$ primes: (4, 9, 16, ...), ...
108_mk's user avatar
  • 225
0 votes
1 answer
37 views

Feature selection problem under promise

Are there well used examples of feature selection problem where the problem is defined under certain promise? Let's say the task is to select the minimum number of features such that the mutual ...
Omar Shehab's user avatar
0 votes
0 answers
33 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
2 votes
1 answer
176 views

CVP to SVP reduction?

The notes here provide a reduction from $SVP$ to $CVP$ https://people.csail.mit.edu/vinodv/COURSES/CSC2414-F11/L4.pdf. Is there a reduction in the reverse direction?
Turbo's user avatar
  • 12.9k
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
4 votes
1 answer
276 views

Banaszczyk's theorem

Banaszczyk's theorem states that if $\Lambda$ is a rank-$m$ lattice with dual lattice $\Lambda^*$, then $\lambda_1(\Lambda) \cdot \lambda_m(\Lambda^*) \leq m$. Can someone point me to a clean proof ...
user6584's user avatar
  • 1,242
6 votes
1 answer
242 views

Correctness of AKS algorithm for shortest vector problem

Short question In the end of section 1 of Regev's notes about the AKS algorithm for SVP, why is the following true? for each such $i$,$y_i− x_i$ remains $w$ with probability $1/2$ or otherwise ...
Hilder Vitor Lima Pereira's user avatar
3 votes
1 answer
124 views

Hardness of LWE on not-uniform vector samples

The "usual decisional LWE": The challenger and the adversary get a common random matrix $A \in F_{q}^{m \times n}$. The challenger chooses a secret $s \in F_{q}^{n}$ and generates random (small) ...
Bartolinio'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
  • 12.9k
0 votes
1 answer
179 views

On polytope lattice points

Given a convex polytope let the width of the polytope be $d$ and the farthest euclidean distance between any points in the polytope be $e$. Denote $\mathcal P(a,c)$ to be the set of convex polytopes ...
Turbo's user avatar
  • 12.9k
7 votes
0 answers
523 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
  • 12.9k
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
8 votes
2 answers
474 views

Ajtai's Proof of Theorem 1 in 'Generating Hard Instances of Lattice Problems'

My question pertains to the proof of Ajtai's main theorem in his groundbreaking 1996 paper, Generating hard instances of lattice problems, which indicates a connection between worst-case hard and ...
Krishnan Narayanan's user avatar
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,035
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
16 votes
1 answer
1k views

Solving a linear diophantine equation approximately

Consider the following problem: Input: a hyperplane $H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\}$, given by a vector $\mathbf{a} \in \mathbb{Z}^n$ and $b \in \mathbb{Z}$ in ...
Sasho Nikolov's user avatar
1 vote
1 answer
269 views

Most optimal parallel method for calculating the integral of a 2D function

I posted already this question to SO but got no answer so I try it now here: In some crunching number program, I have a function which can be just 1 or 0 in three dimensions. I do not know in advance ...
Open the way's user avatar
1 vote
0 answers
270 views

The Number of Short Vectors in a Lattice [closed]

Given a lattice $L = \bigoplus_{i=1}^{m} \mathbb{Z}v_i$ (the $v_i$ are linearly independent vectors in $\mathbb{R}^n$) and a number $c > 0$, can one quickly compute or find a good estimate on the ...
OSHE's user avatar
  • 11
25 votes
1 answer
780 views

Random self-avoiding lattice cycle within a given bounding box

In connection with the Slither Link puzzle, I've been wondering: Suppose that I have an $n\times n$ grid of square cells, and I want to find a simple cycle of grid edges, uniformly at random among all ...
David Eppstein's user avatar
13 votes
2 answers
915 views

What is the pathwidth of the 3D-grid (mesh or lattice) with sidelength k?

I asked this question some weeks ago at mathoverflow, but I got no reply. Here, by 3D-grid of sidelength $k$ I mean the graph $G=(V,E)$ with $V= \{1,\ldots,k\}^3$ and $E=\{( (a,b,c) ,(x,y,z) ) \mid |...
Riko Jacob's user avatar
10 votes
3 answers
1k views

Tree decomposition for planar graphs

First asked on math.SE with no replies. Suppose I have a planar graph, with a planar embedding, how do I find tree decomposition? What is the optimal tree decomposition of a $d$-by-$d$ square grid? ...
Yaroslav Bulatov's user avatar
10 votes
2 answers
566 views

Complexity of hidden polygon puzzle on square grids?

Hiroimono is a popular $NP$-complete puzzle. I'm interested in the computational complexity of a related puzzle. The problem is: Input: Given a set of points on on a $n$x$n$ square grid and integer $k$...
Mohammad Al-Turkistany's user avatar