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 $...


6

I thought of this weird reduction (chances that it is wrong are high :-). Idea: reduction from Hamiltonian path on grid graphs with degree $\leq 3$; each node of the planar graph can be shifted in such a way that every "row" ($y$ value) and every "column" ($x$ value) contains at most one node. The graph can be scaled and each node can be replaced by a square ...


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