On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut

First we will define $\gamma \text{-}\mathrm{CVP}$. Given a lattice $ℒ$, a target vector $𝒕$, and a distance $r$, $\gamma \text{-}\mathrm{CVP}$ is the problem of deciding if $ℒ$ is $r$ close to $𝒕$. If $ℒ$ is not $r$ close to $𝒕$, then it is promised to be more than $\gamma r$ far from $𝒕$. A lattice $ℒ\subset {ℝ}^d$ is a set of all the linear combinations of linearly independent basis vectors ${𝒃}^{(1)},\mathrm{\dots },{𝒃}^{(n)}\in {ℝ}^d$ with integer coefficients,

Here $n$ is known as the rank of the lattice $ℒ$ and $d$ is known as the ambient dimension of the lattice $ℒ$; they are main parameters governing the input size of $\gamma \text{-}\mathrm{CVP}$. The usual way we specify a lattice $ℒ$ in the input to $\gamma \text{-}\mathrm{CVP}$ is by a choice of basis vectors for $ℒ$, which we represent as a matrix that relates every lattice point $𝒗\in ℒ(B)$ to its coordinates $𝒚\in {\mathbb{Z}}^n$ by $𝒗=B𝒚$. The distance $\mathrm{dist}(ℒ,𝒕)$ from a lattice $ℒ$ to a target $𝒕$ is given by the distance of the closest point in $ℒ$ to $𝒕$ in the ${\mathrm{\ell }}_p$-norm. From now on we will call the problem $\gamma \text{-}$${\mathrm{CVP}}_p$ and the distance function ${\mathrm{dist}}_p$ to emphasize that different ${\mathrm{\ell }}_p$-norms give us different problems. $\gamma \text{-}$${\mathrm{CVP}}_p$ is known to be NP-complete for $\gamma ⩽n^{c/\log \log n}$ (where is a constant) [14], to NOT be NP-complete (unless P=NP) for all $\gamma >\sqrt{n}$ [7], and to be in P for $\gamma ⩾2^n$ [30].

Next we will define $(\epsilon ,\varsigma )\text{-}\mathrm{gap}$ $\mathrm{Min}$-$\mathrm{UnCut}$. Given a weighted list of pairs between binary variables and two constants , $(\epsilon ,\varsigma )\text{-}\mathrm{gap}$ $\mathrm{Min}$-$\mathrm{UnCut}$ is the problem of deciding if there is an assignment to the variables such that at most a $\epsilon$-fraction (by weight) of the variable pairs have equal values. If there is no such assignment, then it is promised that for every possible variable assignment at least a $\varsigma$-fraction of pairs have equal values. This makes $(\epsilon ,\varsigma )\text{-}\mathrm{gap}$ $\mathrm{Min}$-$\mathrm{UnCut}$ a weighted 2-CSP (constraint satisfaction problem) where either at most an $\epsilon$-fraction of the constraints are unsatisfiable or at least a $\varsigma$-fraction of the constraints are unsatisfiable. $\mathrm{Min}$-$\mathrm{UnCut}$ is a long-studied problem – the exact case was on Karp’s original list of 21 NP-complete problems [22]. $(\epsilon ,\varsigma )\text{-}\mathrm{gap}$ $\mathrm{Min}$-$\mathrm{UnCut}$ is known to be NP-hard for constant and $\varsigma ⩽\sqrt{\epsilon }$ under a widely accepted conjecture about the hardness of approximation [24], but in P when $\epsilon ⩽\frac{1}{\log n}$ or when $\varsigma >C\sqrt{\epsilon }$ (for some constant $C$) [12, 13]. Note that CSPs are sometimes framed in terms of maximizing satisfied constraints instead of minimizing unsatisfied constraints, in which case the gap is given as the fraction of satisfied constraints. For example, $(1-\epsilon ,1-\varsigma )\text{-}\mathrm{gap}$ $\mathrm{Max}$-$\mathrm{Cut}$ is an alternate name which refers to the same problem as $(\epsilon ,\varsigma )\text{-}\mathrm{gap}$ $\mathrm{Min}$-$\mathrm{UnCut}$.

Our main theorem actually works with a slight generalization of $(\epsilon ,\varsigma )\text{-}\mathrm{gap}$ $\mathrm{Min}$-$\mathrm{UnCut}$ known as $(1-\epsilon ,1-\varsigma )\text{-}\mathrm{gap}$ Max-2-Lin(2), which allows each constraint to specify whether the variables should be equal or unequal. Now we are ready to state our main theorem:

This reduction has the remarkable property that, for any fixed instance size, the approximation factor $\gamma$ of the output instance increases without limit as the gap of the input instance increases. This means our reduction can produce $\gamma \text{-}$${\mathrm{CVP}}_p$ instances of any size with any approximation factor! Previous reductions to $\gamma \text{-}$${\mathrm{CVP}}_p$ had some inherent upper limit on the $\gamma$ of the instances they can produce with $n$ basis vectors for each $n$. See Section 1.6 for a summary of the difficulties involved in overcoming this longstanding limitation. Note also that our reduction maps $(1-\epsilon ,1-\varsigma )\text{-}\mathrm{gap}$ Max-2-Lin(2) instances with $n$ variables to $\sqrt[p]{\varsigma /\epsilon }$-${\mathrm{CVP}}_p$ instances with exactly $n$ basis vectors; this fact is critical for the tightness of our conditional time bounds on $\gamma \text{-}$${\mathrm{CVP}}_p$, which we will describe next. After that, we will describe our two other major advancements and their related works.

Exact $\mathrm{Min}$-$\mathrm{UnCut}$ was one of Karp’s first 21 NP-complete problems [22]. The current best classical algorithm for it is due to [33], who gave an exponential-sized reduction from $\mathrm{Min}$-$\mathrm{UnCut}$ and $\mathrm{Max}\text{-}2\text{-}\mathrm{SAT}$ to a graph problem in P and a way to solve that problem using matrix multiplication. This means that the time complexity of [33]’s algorithm is given in terms of the matrix multiplication exponent $2⩽\omega$. The complexity of [33]’s algorithm is $O(2^{\omega n/3})$ which is approximately $O(2^{0.79n})$ using the current best exponent $\omega \approx 2.371$ due to [8]. The current best algorithm for $(\epsilon ,\varsigma )\text{-}\mathrm{gap}$ $\mathrm{Min}$-$\mathrm{UnCut}$ with constant approximation factors $\alpha =\varsigma /\epsilon$ in the conjectured NP-hard regime is $\exp (n/2^{\mathrm{\Omega }({\alpha }^2)})$-time [26]⁷⁷7Note that a $\mathrm{Min}$-$\mathrm{UnCut}$ algorithm is listed as an open question in the published version of this article and is present in the arXiv version which was submitted later.. [10] give a sub-exponential algorithm for gap Max-2-Lin(2) in the region where $\varsigma =C\sqrt{\epsilon }$ for some constant $C$ which gets slower as $C\to 1$, reaching $O(2^n)$ time when $C=1$. The current best quantum algorithm for exact $\mathrm{Min}$-$\mathrm{UnCut}$ and Max-2-Lin(2) is naive search over the variable assignments using Grover’s algorithm [19], which takes $O(2^{n/2})$ time. For more about $(\epsilon ,\varsigma )\text{-}\mathrm{gap}$ $\mathrm{Min}$-$\mathrm{UnCut}$, Max-2-Lin(2), or the Unique Games Conjecture, see Section 2.4 of the full version of this paper or the survey [23].

We give a new $O\left(2^{\left(\frac{1}{3}+\frac{2}{6{\gamma }^2-3}+o(1)\right)n}\right)$-time quantum algorithm for a special case of $\gamma \text{-}$${\mathrm{CVP}}_2$ and then use our reduction from Theorem 1.1 to give an almost $O(2^{n(\frac{1}{3}+\frac{\epsilon }{6\varsigma }+o(1))})$-time algorithm for $(1-\epsilon ,1-\varsigma )\text{-}\mathrm{gap}$ Max-2-Lin(2). This is the first quantum algorithm to improve upon naive search for $(1-\epsilon ,1-\varsigma )\text{-}\mathrm{gap}$ Max-2-Lin(2). We also get an almost $O(2^{n(\frac{1}{2}+\frac{\epsilon }{4\varsigma }+o(1))})$-time classical algorithm for $(1-\epsilon ,1-\varsigma )\text{-}\mathrm{gap}$ Max-2-Lin(2) by starting with a $O(2^{\left(\frac{1}{2}+\frac{1}{4{\gamma }^2-2}+o(1)\right)n})$-time classical algorithm from [25].

Our classical algorithm is faster than [10] when $\varsigma ⩽\sqrt{\epsilon }$ and it is faster than [33] when for some constant $c_0\approx 3$ which depends on the sub-constant factors in the exponent and on $\omega$. Due to large implicit constants in [26], our algorithm is faster when for some large constant $c_1$. That makes it the best known classical algorithm for $(1-\epsilon ,1-\varsigma )\text{-}\mathrm{gap}$ Max-2-Lin(2) or $(\epsilon ,\varsigma )\text{-}\mathrm{gap}$ $\mathrm{Min}$-$\mathrm{UnCut}$ when . Our quantum algorithm is faster than our classical algorithm, and is faster than naive search when $\varsigma >c_q\epsilon$ for some constant $c_q$ dependent on the sub-constant factors in the exponent, so it is the best known algorithm for .

When $\epsilon =o(1)$, our quantum and classical algorithms have complexities $O\left(2^{\left(\frac{1}{3}+o(1)\right)n}\right)$ and $O\left(2^{\left(\frac{1}{2}+o(1)\right)n}\right)$ respectively. So our algorithms are also faster than all other known algorithms when $\epsilon =1/f(n)$ for $f(n)⩽\log n$ and $\varsigma ⩽\sqrt{\epsilon }$.

Next we will give an overview of our last major advancement: the no-go results against quantum reductions from $k\text{-}\mathrm{SAT}$ to ${\mathrm{CVP}}_2$ or $\mathrm{Min}$-$\mathrm{UnCut}$.

After [11], attempts were made to circumvent the barriers against extending those reductions so that they are able to produce $\gamma \text{-}$${\mathrm{CVP}}_p$ instances with greater approximation factors $\gamma$ or with even $p$. Although those attempts failed, they also found good reasons why the barriers are likely insurmountable and created a new area of fine-grained complexity in the process. The focus was first on extending the reduction from $k\text{-}\mathrm{SAT}$ to ${\mathrm{CVP}}_2$; [3] found that the geometric gadget used in the reduction ($(p,k)$-isolating parallelepipeds) to represent $k\text{-}\mathrm{SAT}$ clauses does not exist for even ${\mathrm{\ell }}_p$-norms when $k>p$, then [5] found that (most) reductions from $k\text{-}\mathrm{SAT}$ on $n$ variables to ${\mathrm{CVP}}_2$ on $\mathrm{poly}(n)$ basis vectors would collapse the polynomial hierarchy! This also helped explain the difficulty in extending the reduction to work for larger $\gamma$: [5] found that since for every $p$ there is a constant ${\gamma }_p$ such that ${\gamma }_p$-${\mathrm{CVP}}_p$ can be reduced to ${\mathrm{CVP}}_2$ (a result due to [16]), any reduction which produces $\gamma \text{-}$${\mathrm{CVP}}_p$ instances with $\gamma ⩾{\gamma }_p$ could still be subject to no-go theorems for ${\mathrm{CVP}}_2$.

Although $\mathrm{unweighted}\mathrm{Max}\text{-}2\text{-}\mathrm{SAT}$ isn’t $k\text{-}\mathrm{SAT}$, these no-go results can also help explain the limitations of the [11] reduction from $(1-\epsilon ,1-\varsigma )\text{-}\mathrm{gap}$ $\mathrm{unweighted}\mathrm{Max}\text{-}2\text{-}\mathrm{SAT}$ to $\gamma \text{-}$${\mathrm{CVP}}_p$. If $k\text{-}\mathrm{SAT}$ can’t be reduced to $\gamma \text{-}$${\mathrm{CVP}}_p$ with larger $\gamma$, then the geometric gadgets which could be used to represent $k\text{-}\mathrm{SAT}$ must fail for larger $\gamma$ just like how [3] found that they fail for even $p$. Since the [11] reduction from $\mathrm{unweighted}\mathrm{Max}\text{-}2\text{-}\mathrm{SAT}$ is reliant on the same geometric gadgets (isolating parallelepipeds) used in their reduction from $k\text{-}\mathrm{SAT}$, it makes sense that it would face limitations similar to what it would face if it were a reduction from $k\text{-}\mathrm{SAT}$.

[5] realized that since tight conditional lower bounds (CLBs) hinge on reductions with a specific numerical relationship between instance size of the input problem and the instance size of the output problem (also known as fine-grained reductions, which we explain in more detail in Section 1.2), their no-go theorems mean that conditions about the time complexity of $k\text{-}\mathrm{SAT}$ like the Strong Exponential Time Hypothesis (SETH) probably can’t be applied to ${\mathrm{CVP}}_2$.

We show that there are no polynomial-sized, non-adaptive, quantum polynomial-time reductions from $k\text{-}\mathrm{SAT}$ to ${\mathrm{CVP}}_2$ with two-sided error unless there are quantum statistical zero-knowledge proofs for all languages in $\mathrm{NP}$. This result shows a substantial barrier against proving the fine-grained complexity of ${\mathrm{CVP}}_2$ using the Quantum Strong Exponential Time Hypothesis and fills a gap in [5], which only showed no-go results for classical reductions. Somewhat counter-intuitively, because we were able to avoid these limitations with our fine-grained reduction from $(1-\epsilon ,1-\varsigma )\text{-}\mathrm{gap}$ Max-2-Lin(2) to $\gamma \text{-}$${\mathrm{CVP}}_p$, we can show that these limitations must apply to quantum fine-grained reductions from $k\text{-}\mathrm{SAT}$ to Max-2-Lin(2) no matter how complex the weights are. Note that since there is a trivial reduction from $(1-\epsilon ,1-\varsigma )\text{-}\mathrm{gap}$ Max-2-Lin(2), exact $\mathrm{Min}$-$\mathrm{UnCut}$, and $(\epsilon ,\varsigma )\text{-}\mathrm{gap}$ $\mathrm{Min}$-$\mathrm{UnCut}$ to Max-2-Lin(2), the no-go theorem applies to them as well.

Our reduction also allows us to directly rule out classical reductions from $k\text{-}\mathrm{SAT}$ to $\mathrm{Min}$-$\mathrm{UnCut}$ based on the results of [5]. In particular, we rule out all fine-grained reductions with one-sided error and all non-adaptive fine-grained reductions with two-sided error. Surprisingly, these barriers seem to close off the most tempting approaches toward understanding the fine-grained complexity of Max-Cut. However, they might help explain the lack of results in this area. These results could also be derived indirectly from a corollary in [11] and [5], although this seems to have been unnoticed despite its significance for such a well-studied problem.

These results mean that there is now a group of problems with fine-grained reductions to ${\mathrm{CVP}}_2$ in addition to the existing group of problems with fine-grained reductions from $k\text{-}\mathrm{SAT}$, and that there (probably) cannot be fine-grained reductions from the latter group to the former group. This suggests that the two groups can be considered as two distinct fine-grained complexity classes. Note that these fine-grained complexity classes are independent of regular complexity classes since, as demonstrated by [33]’s algorithm described in Section 1.3, problems in P and problems that are NP-complete can reside in the same fine-grained complexity class.

We also show that all “natural” reductions from $n$-variable 3-SAT to $\mathrm{Min}$-$\mathrm{UnCut}$ must use $\frac{4}{3}(n-2)$ vertices for a definition of “natural” given by [3].

Now we have completed an overview of all of our advancements. Next we will give a brief overview of our reduction.

We first show an abridged reduction from unweighted Max-Cut to ${\mathrm{CVP}}_p$ for $p\in [1,\mathrm{\infty })$ and how the approximation factor for the output ${\mathrm{CVP}}_p$ instances follows from the gap of the input Max-Cut instances, without needing to handle the complexity of the full proof for Max-2-Lin(2). For the full reduction, see the full version of this paper [21].

Given a Max-Cut instance as an ordered set of unordered pairs $E\subseteq {[n]}^2$ representing $m$ inequality constraints on $n$ variables $v_1,\mathrm{\dots },v_n$, we produce a basis $B$ with $n$ vectors on $2m$ dimensions and a target $𝒕\in {ℝ}^{2m}$. We represent $B$ as a matrix in ${ℝ}^{2m\times n}$ with the basis vectors as its columns. We construct $B$ and $𝒕$ as a series of $m$ vertically stacked blocks, where each block is 2 rows tall:

Each pair of blocks (one in $B$ and one in $𝒕$) makes up one gadget, and each gadget encodes one constraint from $E$; specifically, we construct the gadget $B_{2k-1:2k},{𝒕}_{2k-1:2k}$ to implement the $k^{\text{th}}$ constraint of $E$ as follows:

where only the $i^{\text{th}}$ and $j^{\text{th}}$ columns of $B_{2k-1:2k}$ are shown with $(i,j):=E_k$, , and the remaining columns are filled with 0s. We show the columns in order with column $i$ first. $\iota >1$ is a parameter we use to ensure that the distance to the target is greater when the constraint is unsatisfied than when the constraint is satisfied. We use two rows per constraint to ensure that the basis vectors for our lattice are linearly independent – otherwise our reduction wouldn’t produce valid $\gamma \text{-}$${\mathrm{CVP}}_p$ instances. We visualize the block in Figure 2 by plotting the ${(2k-1)}^{\text{th}}$ and $2k^{\text{th}}$ rows of the vectors $B_{\cdot ,i},B_{\cdot ,j},𝒕,$ and $B_{\cdot ,i}+B_{\cdot ,j}$. $B_{\cdot ,i}$ represents the $i^{\text{th}}$ column of $B$, which is also the $i^{\text{th}}$ basis vector.

As you can see from Figure 2, $B_{\cdot ,i}$ and $B_{\cdot ,j}$ are equidistant from the target $𝒕$, $\mathrm{𝟎}$ and $B_{\cdot ,i}+B_{\cdot ,j}$ are also equidistant from $𝒕$, and $B_{\cdot ,i}$ and $B_{\cdot ,j}$ are closer to $𝒕$. If we interpret the coefficient of $B_{\cdot ,i}$ as the assigned value of $v_i$, we find that the gadget matches the preferences of the constraint $v_i\ne v_j$ exactly: it prefers $(v_i,v_j)\in \{(0,1),(1,0)\}$ over $(v_i,v_j)\in \{(0,0),(1,1)\}$ and it has no preference between $(0,0)$ and $(1,1)$ and no preference between $(0,1)$ and $(1,0)$.

Our reduction overcomes a longstanding technical difficulty for past reductions to lattice problems: producing an instance that has a large approximation factor while maintaining a small number of basis vectors. As you may have noticed in Section 1.2, all past reductions to $\gamma \text{-}$${\mathrm{CVP}}_p$ have either produced many basis vectors to get large $\gamma$ or produced few basis vectors with small $\gamma$. We will try to give some intuition as to why this double-bind occurred.

One way to think about how reductions to $\gamma \text{-}$${\mathrm{CVP}}_p$ with large $\gamma$ such as [9, 14, 20]⁸⁸8Again, while some of these reductions as written are to a slightly different problem $\gamma$-SVP, by [18] they are also reductions to $\gamma \text{-}$${\mathrm{CVP}}_p$ and the principles described here are the same. work is that they increase the number of dimensions polynomially while also increasing the number of basis vectors polynomially. In general, increasing the number of basis vectors produced by a reduction from a CSP to $\gamma \text{-}$${\mathrm{CVP}}_p$ decreases the distance to the target, while increasing the number of dimensions produced by a reduction increases the distance to the target. These reductions construct their additional basis vectors in a systematic manner which reduces the distance much more if the input instance is good than if it is bad. When combined with the fact that the bad instances have a long distance to reduce from this provides a large approximation factor (remember that the approximation factor is the long distance divided by the short distance). However, we know from Section 1.7 that this strategy doesn’t produce fine-grained reductions because it uses too many basis vectors.

Ideally, we would like to produce a reduction from a problem on $n$ variables to $\gamma \text{-}$${\mathrm{CVP}}_p$ with exactly $n$ basis vectors. Such reductions to exact ${\mathrm{CVP}}_p$ were known at least as far back as [9], but extending them to work for larger $\gamma$ is difficult.

To describe these difficulties in constructing problems to $\gamma \text{-}$${\mathrm{CVP}}_p$, it is helpful to have a generalization for the problems we are reducing from. We will use Constraint Satisfaction Problems (CSPs), which neatly generalize all the well-studied problems mentioned in this paper. CSPs are about deciding if there is a combination of variable assignments that is good enough at satisfying a set of constraints (restrictions on variable assignments). An assignment is considered good enough if it satisfies a $1-\epsilon$ fraction of the constraints; if no assignment is good enough, then it is promised that all assignments can only satisfy at most a $1-\varsigma$ fraction of constraints. The input size is given by the number of variables $n$ and the number of constraints $m$.

One difficulty is as follows: these reductions (including our own) always represent the CSP variables as basis vectors so that they can correspond the integer coefficients of the lattice points to the values of variables in the CSP⁹⁹9This is in contrast to, for example, [14] where there were enough basis vectors to have them represent every possible combination of constraint and variable assignment.. There are infinitely many integer coefficients, but only a finite number of possible values for each variable, so to prove that the reduction faithfully implements the CSP we must show that the valid integer coefficients that correspond to possible CSP variable values are always further away than the invalid coefficients. This is usually done by adding a “leashing gadget”: one or more dimensions where the value of basis vectors and target forces lattice points to be far away when a basis vector is assigned an invalid integer coefficient. For example, to force a basis vector to only have valid coefficients 0 and 1 we might set the target to $\alpha$ in the leashing gadget’s dimension and the basis vector to $2\alpha$ for some very large $\alpha$. Since the basis vectors must be allowed at least two valid integer coefficients but the target can only have one value, the leashing gadgets must add some distance to every $\gamma \text{-}$${\mathrm{CVP}}_p$ instance, which we can again call $\alpha$. To prove that the leashing gadget always works, $\alpha$ must exceed the gap between close and far instances of $\gamma \text{-}$${\mathrm{CVP}}_p$ for all the other dimensions combined which caps the approximation factor at 2.

This specific difficulty was first overcome by [11] which showed a ${\mathrm{CVP}}_p$ gadget (2-dimensional isolating parallelepipeds) that they proved will faithfully implement a CSP constraint (2-ary binary conjunction) even when “unleashed”, breaking the $\gamma =2$ barrier. However, the double-bind remained, due to another difficulty: the factor of the distances of far and close lattice points on an isolating parallelepiped is inherently limited by a small explicit constant. Even with the most favorable parameters, unsatisfied constraints are limited to 3 times the distance of satisfied constraints, limiting the overall approximation factor to .

Reductions from some Problem A to some Problem B are commonly used in both “coarse-grained” complexity, to establish that B is in the same complexity class as A, and “fine-grained” complexity, to establish a specific numerical relationship between the complexities of A and B. In general, a reduction from A to B is a procedure which solves an instance of A using the solutions to instances of B. A reduction R from Problem A to Problem B which solves any size-$n$ instance of A using the solution(s) to $c_R(n)$ many size-$s_R(n)$ instance(s) of $B$ in time $T_R(n)$ naturally gives the following upper-bound on time complexity of A $T_A$ in terms of the time complexity of B $T_B$:

What makes reductions so useful in complexity theory is that this inequality is also a lower-bound on $T_B$ in terms of $T_A$. We can make this clearer by rearranging the inequality and introducing a change of variables $n^{\prime }=s_R(n)$:

Note that $s_R$, commonly known as the size of the reduction R, is present in every term.

A common practice is to give a polynomial-size, polynomial-time, many-to-one reduction and assume that problem A requires super-polynomial time; plugging these parameters into our inequality gives $T_B(n)⩾\mathrm{superpoly}({\mathrm{poly}}^{-1}(n))$ which is a super-polynomial lower-bound on $T_B$ (since $T_R(n)\in o(T_A(n))$ it does not contribute to the asymptotic complexity of $T_B$). Thus polynomial-size reductions are an effective way to place Problem B in the same complexity class as Problem A.

While such reductions can answer some coarse-grained complexity questions, they are too large to convert a good algorithm for B into a good algorithm for A or a good lower-bound for A into a good lower-bound for B. This is because the large reduction size converts large changes on one side of the inequality to small changes on the other side.

Let us demonstrate by a lower-bound example: assume that Problem A requires $2^{n/2}$-time and let C be a many-to-one reduction from A to B with size $2^k{n}^k$ for some $k>1$ in polynomial time, and let R also be a reduction from A to B in polynomial time with size $2n$. To emphasize the point, let R also use $n^{10}$ many instances of B instead of just one. Then by our inequality, reduction C establishes a $\mathrm{\Omega }\left(2^{\sqrt[k]{n}/4}\right)$ lower-bound on B while reduction R establishes a $\mathrm{\Omega }(2^{n/4}{n}^{-10})$ lower-bound. Since $k>1$, it’s clear that R gives a much, much better asymptotic lower-bound than C does. Now imagine that a celebrated result shows large improvement in the lower-bound for A, from $2^{n/2}$-time to $2^n$. How does that change our lower-bound results for B? The bound given by C improves by only a factor of $2^{\sqrt[k]{n}/4}$ (to $\mathrm{\Omega }\left(2^{\sqrt[k]{n}/2}\right)$) while the bound given by R improves by a factor of $2^{n/4}$ (to $\mathrm{\Omega }(2^{n/2}{n}^{-10})$)!

Next we will demonstrate the importance of the exact constant factor of our linear-sized reduction. Let reduction R stay as before, and consider another reduction F which is exactly like R except that it has size $n$ instead of $2n$ and takes time $2^{\sqrt[4]{n}}$ instead of $\mathrm{poly}(n)$. Then reduction F gives a lower bound of

on B instead of the $\mathrm{\Omega }(2^{n/2}{n}^{-10})$ bound given by R! The above comparisons demonstrate that a reduction which can give good fine-grained complexity results (a fine-grained reduction) for potentially exponential-time problems must be a linear-sized reduction, that the constant factor in the reduction size is more important than the complexity of other aspects of the reduction, and that the constant factor is ideally 1 or less.

We leave the following questions to future research.

1. 1.

   Can the fine-grained hardness of $\gamma \text{-}$${\mathrm{CVP}}_2$ be further extended to show that there are no $O(2^{n^{1-\delta }})$-time algorithms with $\delta >0$ for $\gamma \text{-}$${\mathrm{CVP}}_2$ with approximation factors further into the $\mathrm{poly}(\log n)$ regime and even beyond it towards $\sqrt{n}$ regime used by modern cryptography?

2. 2.

   Now that we have identified that fine-grained approximation-ratio preserving reductions are achievable, can we create other fine-grained approximation-ratio preserving reductions that help answer questions in the hardness of approximation?

3. 3.

   Can the fine-grained hardness results shown in this work also be applied to the approximate Shortest Vector Problem?

4. 4.

   Do fine-grained reductions to $\gamma \text{-}$${\mathrm{CVP}}_p$ which utilize the “full power” of $\gamma \text{-}$${\mathrm{CVP}}_p$ by using lattice coordinates with many different coefficients instead of just two lead to stronger lower bounds? Or maybe $\gamma \text{-}$${\mathrm{CVP}}_p$ is fully characterized by existing reductions, since for any line formed by a basis vector can only be closest to the target at two points in the ${\mathrm{\ell }}_p$-norm¹⁰¹⁰10[3] give a good technical argument for this possibility.? If the former is true, then hopefully we can prove much higher fine-grained lower bounds on $\gamma \text{-}$${\mathrm{CVP}}_p$. If the latter is true, then we can use existing algorithms to match our current lower bounds. See Section 2.3 of the full version of this paper [21] for how $\gamma \text{-}$${\mathrm{CVP}}_p$ problems with different lattice coefficients relate to each other.

5. 5.

   The “no-go” results and reductions discussed in this paper suggest that $\mathrm{Min}$-$\mathrm{UnCut}$ and $\gamma \text{-}$${\mathrm{CVP}}_2$ belong together in a certain fine-grained complexity class, and that this class is separate from the much better understood fine-grained complexity class to which $k\text{-}\mathrm{SAT}$ belongs. What is the true fine-grained complexity lower bound for this class? How should we formulate a fine-grained lower bound conjecture for this class, and which problem should the conjecture be formulated for? One candidate is that there is no $O(2^{n^{1-\delta }})$-time Max-Cut algorithm for $\delta >0$; another candidate in use by some cryptographers is that there is no $O(2^{0.2075n})$-time algorithm for $\gamma \text{-}$${\mathrm{CVP}}_2$.

Our theorems and their proofs are presented in the full version of this paper [21]. What follows will be the structure of the full paper for the reader’s convenience.

In Section 2 of [21] we introduce the notation used in this paper. We also present the necessary definitions and known results for fine-grained complexity, lattice problems, Max-Cut, and approximate nearest neighbor. In Section 3 of [21] we prove our main theorem Theorem 1.1. In Section 4 of [21] we use this theorem to apply classical and quantum fine-grained lower bounds on the hardness of $\gamma \text{-}$${\mathrm{CVP}}_p$. In Section 5 of [21] we use our reduction to show barriers against quantum and classical fine-grained hardness results for ${\mathrm{CVP}}_p$, Max-2-Lin(2), and $\mathrm{Min}$-$\mathrm{UnCut}$ based on (Q)SETH. In Section 6 of [21] we show faster classical and quantum algorithms for $(1-\epsilon ,1-\varsigma )\text{-}\mathrm{gap}$ Max-2-Lin(2) including $(\epsilon ,\varsigma )\text{-}\mathrm{gap}$ $\mathrm{Min}$-$\mathrm{UnCut}$.