  In this work, we give provable sieving algorithms for the Shortest Vector
Problem (SVP) and the Closest Vector Problem (CVP) on lattices in $\ell_p$ norm
($1\leq p\leq\infty$). The running time we obtain is better than existing
provable sieving algorithms. We give a new linear sieving procedure that works
for all $\ell_p$ norm ($1\leq p\leq\infty$). The main idea is to divide the
space into hypercubes such that each vector can be mapped efficiently to a
sub-region. We achieve a time complexity of $2^{2.751n+o(n)}$, which is much
less than the $2^{3.849n+o(n)}$ complexity of the previous best algorithm.
  We also introduce a mixed sieving procedure, where a point is mapped to a
hypercube within a ball and then a quadratic sieve is performed within each
hypercube. This improves the running time, especially in the $\ell_2$ norm,
where we achieve a time complexity of $2^{2.25n+o(n)}$, while the List Sieve
Birthday algorithm has a running time of $2^{2.465n+o(n)}$.
  We adopt our sieving techniques to approximation algorithms for SVP and CVP
in $\ell_p$ norm ($1\leq p\leq\infty$) and show that our algorithm has a
running time of $2^{2.001n+o(n)}$, while previous algorithms have a time
complexity of $2^{3.169n+o(n)}$.

Data Structures and Algorithms