The 2024 Developer Survey results are live! See the results

# Tag Info

### Banaszczyk's theorem

Divesh Aggarwal and Noah Stephens-Davidowitz very recently posted a preprint improving the constant in the upper bound of Banaszczyk's theorem: https://arxiv.org/abs/1907.09020. Specifically, they ...
• 5,023
Accepted

### Correctness of AKS algorithm for shortest vector problem

What you seem to be missing is that $\tau$ is not applied to all "green" vectors. Instead, think of every point $x_i$ as having a coin attached to it. Before you use $x_i$ in the algorithm, you toss ...
• 18.2k
Accepted

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

Let's shift the origin to the target vector, solve SVP there and shift the answer back. Why doesn't this give a solution to a CVP? It does---CVP on a lattice $L$ and target vector $t$ is equivalent ...
• 5,023
Accepted

### CVP to SVP reduction?

The short answer is "yes," but with several caveats, maybe the most important of which is that all known such reductions from CVP to SVP in the Euclidean norm are randomized. Self promotion: ...
• 5,023

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

Replying very late, I really like the exposition of Ajtai's proof in this paper of Goldreich, Goldwasser and Halevi.
Accepted

### Comparing Shor's and Regev's Quantum Factoring algorithm

First some background (that does not fit the comments section) since you asked for pointers: The continued fractions-based post-processing algorithm in Shor's order-finding algorithm [Shor94] [Shor97]...
• 196
Accepted

### Hardness of LWE on not-uniform vector samples

Since you are specifically interested in $q=2$, I will focus on this case in my answer. A note on your choice of tags: you tagged your question with "lattice" and "lattice-theory"; however, your ...
Accepted

### On polytope lattice points

Let's just take the reduction from SAT to IP and see if it works. For a 3-CNF $\phi$, define a polytope $P$ which contains all $x \in \mathbb{R}^n$ satisfying the constraints $0\le x_i \le 1$ for all ...
• 18.2k
1 vote
Accepted

### Feature selection problem under promise

Yes. The problem of feature selection under constraints is relevant and was studied very well in multiple scenarios. You may want to look at these papers for reference. Beyond distributive fairness ...

Only top scored, non community-wiki answers of a minimum length are eligible