Jin-Yi Cai

We survey some recent developments in the study of

the complexity of lattice problems. After a discussion of some

problems on lattices which can be algorithmically solved

efficiently, our main focus is the recent progress on complexity

results of intractability. We will discuss Ajtai's worst-case/

average-case connections, NP-hardness and non-NP-hardness,

more >>>

Irit Dinur

This paper shows SVP_\infty and CVP_\infty to be NP-hard to approximate

to within any factor up to $n^{1/\log\log n}$. This improves on the

best previous result \cite{ABSS} that showed quasi-NP-hardness for

smaller factors, namely $2^{\log^{1-\epsilon}n}$ for any constant

$\epsilon>0$. We show a direct reduction from SAT to these

problems, that ...
more >>>

Huck Bennett, Surendra Ghentiyala, Noah Stephens-Davidowitz

We study the problem of finding multicollisions, that is, the total search problem in which the input is a function $\mathcal{C} : [A] \to [B]$ (represented as a circuit) and the goal is to find $L \leq \lceil A/B \rceil$ distinct elements $x_1,\ldots, x_L \in A$ such that $\mathcal{C}(x_1) = ... more >>>