Rajendra Kumar 0002

STOC Conference 2023 Conference Paper

Lattice Problems beyond Polynomial Time

• Divesh Aggarwal
• Huck Bennett
• Zvika Brakerski
• Alexander Golovnev
• Rajendra Kumar 0002
• Zeyong Li
• Spencer Peters
• Noah Stephens-Davidowitz

FOCS Conference 2023 Conference Paper

Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms!

• Divesh Aggarwal
• Rajendra Kumar 0002

Recent work has shown SETH hardness of CVP in the $\ell_{p}$ norm for any p that is not an even integer. This result was shown by giving a Karp reduction from k-SAT on n variables to CVP on a lattice of rank n. In this work, we show a barrier towards proving a similar result for CVP in the $\ell_{p}$ norm where p is an even integer. We show that for any $c\gt0$, if for every $k\gt0$, there exists an efficient reduction that maps a k-SAT instance on n variables to a CVP instance for a lattice of rank at most $n^{c}$ in the Euclidean norm, then coNP $\subset NP/Poly$. We prove a similar result for CVP for all even norms under a mild additional promise that the ratio of the distance of the target from the lattice and the shortest non-zero vector in the lattice is bounded by $\exp \left(n^{O(1)}\right)$. Furthermore, we show that for any $c\gt0$, and any even integer p, if for every $k\gt0$, there exists an efficient reduction that maps a k-SAT instance on n variables to a $SVP_{p}$ instance for a lattice of rank at most $n^{c}$, then coNP $\subset NP /$ Poly. 1 While prior results have indicated that lattice problems in the $\ell_{2}$ norm (Euclidean norm) are easier than lattice problems in other norms, this is the first result that shows a separation between these problems. We achieve this by using a result by Dell and van Melkebeek on the impossibility of the existence of a reduction that compresses an arbitrary k-SAT instance into a string of length $\mathcal{O}\left(n^{k-\varepsilon}\right)$ for any $\varepsilon\gt0$. In addition to CVP, we also show that the same result holds for the Subset-Sum problem using similar techniques. 1 The result for SVP does not require any additional promise.

SODA Conference 2021 Conference Paper

Dimension-Preserving Reductions Between SVP and CVP in Different p -Norms

• Divesh Aggarwal
• Yanlin Chen
• Rajendra Kumar 0002
• Zeyong Li
• Noah Stephens-Davidowitz

We show a number of reductions between the Shortest Vector Problem and the Closest Vector Problem over lattices in different ℓ p norms (SVP p and CVP p respectively). Specifically, we present the following 2 ∊m -time reductions for 1 ≤ p ≤ q ≤ ∞, which all increase the rank n and dimension m of the input lattice by at most one: • a reduction from Õ (1/ ∊ 1 / p ) γ -approximate SVP q to γ -approximate SVP p; • a reduction from Õ (1/ ∊ 1/ p ) γ -approximate CVP p to γ -approximate CVP q; and • a reduction from Õ (1/ ∊ 1+1/ p )-CVP q to (1 + ∊ )-unique SVP p (which in turn trivially reduces to (1 + ∊ )-approximate SVP p ). The last reduction is interesting even in the case p = q. In particular, this special case subsumes much prior work adapting 2 O ( m ) -time SVP p algorithms to solve O (1)-approximate CVP p. In fact, we show a stronger result in the special case when 1 ≤ p = q ≤ 2 and the SVP p oracle is exact: a reduction from O (1/ ∊ 1 / p )-CVP p to (exact) SVP p in 2 ∊m time. For example, taking ∊ = log m/m and p = 2 gives a slight improvement over Kannan's celebrated polynomial-time reduction from to SVP 2. We also note that the last two reductions can be combined to give a reduction from approximate-CVP p to SVP q for any p and q, regardless of whether p ≤ q or p > q. Our techniques combine those from the recent breakthrough work of Eisenbrand and Venzin [21] (which showed how to adapt the current fastest known algorithm for these problems in the ℓ 2 norm to all ℓ p norms) together with sparsification-based techniques.