# Questions tagged [integer-lattice]

The tag has no usage guidance.

23 questions
Filter by
Sorted by
Tagged with
424 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, ...), ...
38 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 ...
34 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$ ...
191 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?
67 views

281 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 ...
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 ...
125 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) ...
1 vote