Tag Info

Hot answers tagged integer-lattice

8

You can try reading more recent papers such as Worst-case to Average-case Reductions based on Gaussian Measures by Miccancio and Regev, or Regev's lecture notes on the subject (you might want to read through the entire course).

7

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 show that $\lambda_1(\Lambda)\mu(\Lambda^*) \leq (0.1275 + o(1)) n$, which combined with the upper bound $\lambda_n(\Lambda^*) \leq 2 \mu(\Lambda^*)$ implies that $... 5 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 the coin to decide whether to keep$x_i$as$x_i$or to replace it by$\tau(x_i)$. This is done independently for each$x_i$, so, with very high probability, the ... 3 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 question seems much more closely related to questions in coding theory. I elaborate below. A good starting point is to observe that LPN with matrix$A$reduces to ... 2 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$i$, clause constraints for any clause$C$of$\phi$: for example if$C = x_i \vee \bar{x}_j \vee x_k$put the constraint$x_i + 1-x_j + x_k \ge 1\$. (I trust ...

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