4 Fine-grained complexity: hypotheses and intermediate problems

Definition 20 \(k\)-SAT

\(k\mathsf{SAT}\) is the satisfiability problem for Boolean formulas in conjunctive normal form in which every clause has at most \(k\) literals; \(n\) denotes the number of variables. Recalled to state SETH.

Assumption 21 Strong Exponential Time Hypothesis (SETH), Definition 2.4 / A.1

For every \(\varepsilon {\gt} 0\) there exists a positive integer \(k\) such that \(k\mathsf{SAT}\) requires \(\Omega \! \left(2^{(1-\varepsilon )n}\right)\) time, where \(n\) is the number of variables in the CNF. (A popular strengthening of \(\mathrm P \ne \mathrm{NP}\).)

Definition 22 Orthogonal Vectors, \(\mathsf{OV}_{n,\ell }\), Definition 2.5 / A.2

Given binary vectors \(v_1, \ldots , v_n \in \{ 0,1\} ^{\ell }\), \(\mathsf{OV}_{n,\ell }\) asks to determine whether there exists a pair \(i \ne j\) with \(\langle v_i, v_j \rangle = 0\).

Definition 23 Bichromatic Orthogonal Vectors

Given two sets \(A = \{ a_1, \ldots , a_n\} \) and \(B = \{ b_1, \ldots , b_n\} \) of vectors in \(\{ 0,1\} ^{\ell }\), bichromatic \(\mathsf{OV}_{n,\ell }\) asks whether there exist \(i,j\) with \(\langle a_i, b_j \rangle = 0\).

Conjecture 24 Orthogonal Vectors Conjecture (OVC), Conjecture 2.6 / A.3

For any \(\varepsilon {\gt} 0\) there exists a constant \(c {\gt} 0\) such that \(\mathsf{OV}_{n, c \log n}\) cannot be solved in \(O(n^{2-\varepsilon })\) time.

Theorem 25 SETH implies OVC, Williams (2005)

If SETH (Assumption 21) holds, then OVC (Conjecture 24) holds. Consequently all hardness results below can be stated under SETH or OVC.

Definition 26 Minimum Inner Product, \(\mathsf{Min\text{-}IP}_{n,\ell }\), Definition 2.7 / A.5

Given \(v_1, \ldots , v_n \in \{ 0,1\} ^{\ell }\), \(\mathsf{Min\text{-}IP}_{n,\ell }\) asks to find a pair \(i \ne j\) such that \(\langle v_i, v_j \rangle \) is minimum.

Definition 27 \(\gamma \)-Min-IP, Definition 2.8 / A.6

Given \(v_1, \ldots , v_n \in \{ 0,1\} ^{\ell }\), \(\gamma \text{-}\mathsf{Min\text{-}IP}_{n,\ell }\) asks to find \(i \ne j\) such that \(\langle v_i, v_j \rangle \) is a \(\gamma \)-approximation of the minimal inner product.

Definition 28 Min-IP decision version, \(\mathsf{Min\text{-}IP}_{n,\ell ,t}\), Definition 2.9 / A.7

Given \(v_1, \ldots , v_n \in \{ 0,1\} ^{\ell }\) and \(0 \le t \le \ell \), \(\mathsf{Min\text{-}IP}_{n,\ell ,t}\) asks to determine whether there exists a pair \(i \ne j\) with \(\langle v_i, v_j \rangle \le t\).

Definition 29 Bichromatic Min-IP

Given two sets \(A, B\) of vectors in \(\{ 0,1\} ^{\ell }\), bichromatic \(\mathsf{Min\text{-}IP}_{n,\ell }\) (resp. its \(\gamma \)-approximate and decision versions) asks to find \(i,j\) achieving (resp. \(\gamma \)-approximating, deciding) the minimal \(\langle a_i, b_j \rangle \) over \(a_i \in A\), \(b_j \in B\).

Definition 30 Maximum Inner Product, \(\mathsf{Max\text{-}IP}_{n,\ell }\), Definition A.9

Given \(v_1, \ldots , v_n \in \{ 0,1\} ^{\ell }\), \(\mathsf{Max\text{-}IP}_{n,\ell }\) asks to find a pair \(i \ne j\) such that \(\langle v_i, v_j \rangle \) is maximal.

Definition 31 \(\gamma \)-Max-IP, Definition A.10

Given \(v_1, \ldots , v_n \in \{ 0,1\} ^{\ell }\), \(\gamma \text{-}\mathsf{Max\text{-}IP}_{n,\ell }\) asks to find \(i \ne j\) such that \(\langle v_i, v_j \rangle \) is a \(\gamma \)-approximation of the maximal inner product.

Definition 32 Max-IP decision version, \(\mathsf{Max\text{-}IP}_{n,\ell ,t}\), Definition A.11

Given \(v_1, \ldots , v_n \in \{ 0,1\} ^{\ell }\) and \(0 \le t \le \ell \), \(\mathsf{Max\text{-}IP}_{n,\ell ,t}\) asks to determine whether there exist \(i \ne j\) with \(\langle v_i, v_j \rangle \ge t\).

Definition 33 Bichromatic Max-IP

Given two sets \(A, B\) of vectors in \(\{ 0,1\} ^{\ell }\), bichromatic \(\mathsf{Max\text{-}IP}_{n,\ell }\) (resp. its \(\gamma \)-approximate and decision versions) asks to find \(i,j\) achieving (resp. \(\gamma \)-approximating, deciding) the maximal \(\langle a_i, b_j \rangle \).