# Tagged Questions

The tag has no usage guidance.

0answers
139 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$...
0answers
40 views

### Integer sublattice of unit hyperplane

Consider the polytope $\mathcal{H}=\{(x_1,\dots,x_n)| \ell_i\leq x_i\leq u_i\; i=1,\dots,n; \sum_{i=1}^n x_i=1\}$ where $\ell_i,u_i\in [0,1]$ for $i=1,\dots,n$. It is easy to see that $\mathcal{H}$ ...
1answer
144 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 ...
0answers
80 views

1answer
932 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
227 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
192 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
707 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
594 views