7 votes

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 ...
Huck Bennett's user avatar
  • 4,868
6 votes
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 ...
Sasho Nikolov's user avatar
3 votes
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]...
Martin Ekerå's user avatar
3 votes

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.
Cole_Franks's user avatar
3 votes
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 ...
Geoffroy Couteau's user avatar
2 votes
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 ...
Sasho Nikolov's user avatar
2 votes
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: ...
Huck Bennett's user avatar
  • 4,868
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 ...
Vidyadhar Rao's user avatar

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