The 2024 Developer Survey results are live! See the results

# Questions tagged [integer-lattice]

The tag has no usage guidance.

24 questions
Filter by
Sorted by
Tagged with
465 views

### Why can't CVP be trivially reduced to SVP by shifting?

I'm dipping my toes into lattice-based cryptography, but the difference between the SVP and CVP confuses me. I'm most definitely missing something big here, but I still couldn't figure it out, so I'm ...
• 43
476 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, ...), ...
• 245
43 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 ...
• 651
37 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$ ...
• 91
262 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?
• 13.1k
67 views

289 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 ...
• 1,242
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 ...
129 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) ...
• 203
1 vote
17 views

• 2,045
1 vote
99 views

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 $... • 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 ... • 18.2k 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 ... • 321 1 vote 0 answers 271 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 ... • 11 25 votes 1 answer 782 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 ... • 51.1k 13 votes 2 answers 920 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 |...
• 990
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? ...
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$...