# Questions tagged [integer-lattice]

The tag has no usage guidance.

17 questions
Filter by
Sorted by
Tagged with
187 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 ...
185 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 ...
74 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) ...
11 views

94 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 $... 1answer 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 ... 1answer 263 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 ... 0answers 224 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 ... 1answer 745 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 ... 2answers 730 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 |...
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 ...