Introduction
Given a boolean function f f f , how compactly can we “encode” f f f as a CNF formula (see Definition 1 )? A partial answer was provided first by the Cook–Levin theorem [12 , 42 ] , which implies that if f f f can be computed nondeterministically in n n n steps, then it can be encoded as a CNF instance of size n O ( 1 ) n^{O(1)} n O ( 1 ) . Since then, more compact encodings of size O ~ ( n ) \widetilde{O}(n) O ( n ) have been devised and extended to different models of computation [56 , 51 , 13 , 55 ] . These optimized Cook–Levin theorems have several complexity-theoretic applications, including showing that CNF-SAT is complete for nondeterministic quasilinear time [56 , 23 ] and proving time-space tradeoffs for CNF-SAT [21 ] . The problem of compactly encoding boolean functions has also acquired tremendous practical utility with the advent of SAT solvers, where efficient encodings are often make-or-break for whether a problem can be solved in practice [58 , 37 HS24, 54 , 28 ] ; empirically, smaller encodings tend to perform better in practice [Bjӧ09, ANORC13].1
Consequently, the SAT community has studied encodings for a variety of concrete functions, including both classical NP-complete problems (e.g., Hamiltonian cycle [69 , 70 ] , graph coloring [17 ] , k k k -clique [31 , 60 ] , and many others [10 ] ) as well as elementary constraints such as parity [16 ] or at-most-k k k [59 , 41 , 36 ] , which serve as building blocks of larger encodings. However, despite the theoretical and practical importance of CNF encodings, this model of computation has yet to receive a systematic theoretical treatment that focuses on large classes of boolean functions rather than particular instances, which is in stark contrast to other models of computation like boolean circuits [32 ] . In this paper, we prove fundamental results about the complexity of boolean functions in this model and show how this complexity metric relates to complexities in other nonuniform models. We hope to convince the reader that the theory of CNF encodings is much deeper than has previously been appreciated. In particular, we show that the optimized Cook–Levin results mentioned above are not the end of the story.
A CNF encoding of a boolean function f f f is a CNF formula with nondeterministic variables that computes f f f . Formally:
Definition 1 (Encoding). Given a boolean function f : { 0 , 1 } n → { 0 , 1 } f : \{0,1\}^{n} \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } , we say that a triple ( φ , X , Y ) (\varphi, X, Y) ( φ , X , Y ) is an encoding of f f f if: (i) X : = ( x 1 , … , x n ) X := (x_1, \ldots, x_n) X := ( x 1 , … , x n ) is a sequence of propositional variables, and Y Y Y is a set of propositional variables disjoint from X X X ; (ii) φ \varphi φ is a CNF formula over variables X ⊔ Y X \sqcup Y X ⊔ Y ; and (iii) for every assignment τ : X → { 0 , 1 } \tau: X \to\{0,1\} τ : X → { 0 , 1 } ,
f ( τ ( x 1 ) , … , τ ( x n ) ) = 1 ⟺ ∃ θ : Y → { 0 , 1 } , ( τ ∪ θ ) ⊨ φ . f\bigl(\tau(x_1),\ldots,\tau(x_n)\bigr)=1 \Longleftrightarrow\exists\theta:Y\to\{0,1\},\;(\tau\cup\theta)\models\varphi. f ( τ ( x 1 ) , … , τ ( x n ) ) = 1 ⟺ ∃ θ : Y → { 0 , 1 } , ( τ ∪ θ ) ⊨ φ .
The variables in X X X are called input variables, and those in Y Y Y are called auxiliary variables.
:::
Thus, CNF encodings constitute a nondeterministic, nonuniform model of computation. We say that the CNF encoding complexity of a boolean function f f f , denoted enc ( f ) \operatorname{enc}(f) enc ( f ) , is the minimum number of clauses in a CNF encoding of f f f . In Section 1.3, we elaborate on why we choose to focus on the clause count instead of, say, the total number of literals in a CNF encoding.
One of the few theoretical results known about encoding complexity is due to Tseitin [65 ] : if the (nondeterministic) circuit complexity of f f f is n n n , then enc ( f ) = O ( n ) \operatorname{enc}(f)=O(n) enc ( f ) = O ( n ) . Each of our main results implies that the converse of Tseitin’s theorem fails strongly: there are boolean functions for which $\operatorname{enc}(f) is much smaller than its (nondeterministic) circuit complexity. In § 6 , we characterize enc ( f ) \operatorname{enc}(f) enc ( f ) exactly in terms of nondeterministic conjunctive circuit complexity: whenever enc ( f ) ≥ 2 \operatorname{enc}(f) \ge2 enc ( f ) ≥ 2 , it equals the minimum number of wires entering ∧ \land ∧ -gates in a nondeterministic De Morgan circuit computing f f f . Thus, all of our results also have circuit complexity analogues.
Our results
Our first result relates encoding complexity to the time complexity of nondeterministic RAM machines with advice. Robson [55 ] showed the following variant of the Cook–Levin theorem: if f : { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^{n} \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } can be computed by a nondeterministic RAM machine in time t ≥ n t \ge n t ≥ n , then enc ( f ) = O ( t lg t ) \operatorname{enc}(f)=O(t\lg t) enc ( f ) = O ( t lg t ) , and such an encoding can be constructed in polynomial time (strictly speaking, if the machine has program size p p p , Robson yields O ( ( t + p ) lg ( t + p ) ) O((t+p)\lg(t+p)) O (( t + p ) lg ( t + p )) ). However, there is a precise sense in which Robson’s result does not capture the full power of CNF encodings; nondeterministic RAM is a uniform model of computation, whereas CNF encodings constitute a nonuniform model. Thus, it is natural to instead translate nondeterministic RAM machines with advice (a model we call ANRAM) to CNF encodings. A naïve extension of Robson’s result would state that if f f f can be computed by an ANRAM machine in time t t t with m m m bits of advice, then enc ( f ) = O ~ ( t + m ) \operatorname{enc}(f)=\widetilde{O}(t+m) enc ( f ) = O ( t + m ) .2 We show the following quantitative improvement:
Theorem 2. Let f : { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^{n} \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } , and suppose that f f f can be evaluated in time t ≥ n t \ge n t ≥ n with m m m bits of advice by an ANRAM machine that accesses at most b b b bits of the advice for each input. Then, enc ( f ) = O ~ ( t + m b ) \operatorname{enc}(f)=\widetilde{O}(t+\sqrt{mb}) enc ( f ) = O ( t + mb ) . Furthermore, such an encoding can be constructed deterministically in time polynomial in n + t + m n+t+m n + t + m given the advice string.
We find Theorem 2 remarkable. It provides a tight bound on the number of clauses (up to polylogarithmic factors) for a wide variety of functions (technically speaking, even for a 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) fraction of all boolean functions), and yields encodings with fewer clauses for a variety of classical NP-complete problems (we discuss some in Section 1.2). In contrast, applying Robson’s result yields quadratically worse bounds for almost all functions. Indeed, suppose one takes f : { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^{n} \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } to be an arbitrary boolean function. Then, letting the advice string A A A be the string of length 2 n 2^{n} 2 n encoding f f f ’s truth table, we can compute f f f by reading the input x ⃗ \vec{x} x and consulting A [ x ⃗ ] = f ( x ⃗ ) A[\vec{x}]=f(\vec{x}) A [ x ] = f ( x ) ; this way t = O ( n ) t=O(n) t = O ( n ) , m = 2 n m=2^{n} m = 2 n , and b = 1 b=1 b = 1 , which yields enc ( f ) = O ~ ( 2 n ) \operatorname{enc}(f)=\widetilde{O}(\sqrt{2^{n}}) enc ( f ) = O ( 2 n ) . In contrast, an application of Robson’s theorem would yield the trivial bound enc ( f ) = O ~ ( 2 n ) \operatorname{enc}(f)=\widetilde{O}(2^{n}) enc ( f ) = O ( 2 n ) .3
In fact, a simple lower bound shows that Theorem 2 is not too far from optimal, meaning roughly that for every boolean function f f f , there is some ANRAM machine for which applying Theorem 2 yields an encoding of size at most enc ( f ) 3 / 2 \operatorname{enc}(f)^{3/2} enc ( f ) 3/2 .
Proposition 3. Let f : { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^{n} \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } be a boolean function with enc ( f ) = Ω ( n ) \operatorname{enc}(f)=\Omega(n) enc ( f ) = Ω ( n ) , let ( M f ⋆ , A f ⋆ ) (M_f^\star,A_f^\star) ( M f ⋆ , A f ⋆ ) be an ANRAM machine that computes f f f and minimizes t + m b t+\sqrt{mb} t + mb over all possible (machine, advice) pairs, and let t ⋆ , m ⋆ , b ⋆ t^\star,m^\star,b^\star t ⋆ , m ⋆ , b ⋆ be the corresponding optimal parameters. Then,
enc ( f ) = Ω ~ ( ( t ⋆ + m ⋆ b ⋆ ) 2 / 3 ) . \operatorname{enc}(f)=\widetilde{\Omega}\left(\left(t^\star+\sqrt{m^\star b^\star}\right)^{2/3}\right). enc ( f ) = Ω ( ( t ⋆ + m ⋆ b ⋆ ) 2/3 ) .
Proof. Let F F F be a formula that encodes f f f with enc ( f ) \operatorname{enc}(f) enc ( f ) clauses, and Y Y Y be its set of auxiliary variables. We can further assume that ∣ Y ∣ ≤ enc ( f ) \lvert Y\rvert\le\operatorname{enc}(f) ∣ Y ∣ ≤ enc ( f ) ; we prove that this assumption is without loss of generality in Proposition 30 . Then, consider the ANRAM machine receiving F F F as advice, and upon receiving an input x ⃗ \vec{x} x , proceed as follows. First, guess an assignment θ \theta θ for each of the auxiliary variables in time O ( ∣ Y ∣ ) = O ( enc ( f ) ) O(\lvert Y\rvert)=O(\operatorname{enc}(f)) O (∣ Y ∣) = O ( enc ( f )) . Next, for each clause in F F F , nondeterministically guess which of its at most n + enc ( f ) n+\operatorname{enc}(f) n + enc ( f ) literals satisfies it; guessing this index takes time O ( lg ( enc ( f ) ) ) O(\lg(\operatorname{enc}(f))) O ( lg ( enc ( f ))) . Then, check that the polarity of that literal matches its value on the input, or on θ \theta θ if it corresponds to an auxiliary variable, which can be done in time O ( lg ( enc ( f ) ) ) O(\lg(\operatorname{enc}(f))) O ( lg ( enc ( f ))) , and accept if and only if all such checks succeed. Thus, the total time is t = O ( enc ( f ) lg ( enc ( f ) ) ) t=O(\operatorname{enc}(f)\lg(\operatorname{enc}(f))) t = O ( enc ( f ) lg ( enc ( f ))) , the advice length is m = O ~ ( enc ( f ) 2 ) m=\widetilde{O}(\operatorname{enc}(f)^2) m = O ( enc ( f ) 2 ) and the number of bits read is b = O ~ ( enc ( f ) ) b=\widetilde{O}(\operatorname{enc}(f)) b = O ( enc ( f )) . We thus have
t + m b = O ~ ( enc ( f ) ) + O ~ ( enc ( f ) 2 ) ⋅ O ~ ( enc ( f ) ) = O ~ ( enc ( f ) 3 / 2 ) . t+\sqrt{mb}=\widetilde{O}(\operatorname{enc}(f))+\sqrt{\widetilde{O}(\operatorname{enc}(f)^2)\cdot\widetilde{O}(\operatorname{enc}(f))}=\widetilde{O}(\operatorname{enc}(f)^{3/2}). t + mb = O ( enc ( f )) + O ( enc ( f ) 2 ) ⋅ O ( enc ( f )) = O ( enc ( f ) 3/2 ) .
Since t + m b ≥ t ⋆ + m ⋆ b ⋆ t+\sqrt{mb}\ge t^\star+\sqrt{m^\star b^\star} t + mb ≥ t ⋆ + m ⋆ b ⋆ by definition, we obtain O ~ ( enc ( f ) 3 / 2 ) ≥ t ⋆ + m ⋆ b ⋆ \widetilde{O}(\operatorname{enc}(f)^{3/2})\ge t^\star+\sqrt{m^\star b^\star} O ( enc ( f ) 3/2 ) ≥ t ⋆ + m ⋆ b ⋆ from which the result follows.
More generally, Theorem 2 has a natural interpretation in terms of data structures. Suppose we have an algorithm to compute f f f that has access to a data structure D f D_f D f which uses m m m bits of memory, and upon receiving an input x ⃗ \vec{x} x , nondeterministically computes f ( x ⃗ ) f(\vec{x}) f ( x ) in time t t t by querying at most b b b bits of D f D_f D f . Then, Theorem 2 says that f f f must have a small CNF encoding, regardless of how long it takes to build D f D_f D f . As a more interesting application, consider the functions I S G : { 0 , 1 } n → { 0 , 1 } \mathrm{IS}_G:\{0,1\}^n\to\{0,1\} IS G : { 0 , 1 } n → { 0 , 1 } , each parametrized by some graph G G G on n n n vertices v 1 , … , v n v_1,\ldots,v_n v 1 , … , v n , defined by
I S G ( x 1 , … , x n ) = 1 ⟺ { v i ∣ x i = 1 } is an independent set of G . \mathrm{IS}_G(x_1,\ldots,x_n)=1\Longleftrightarrow\{v_i\mid x_i=1\}\text{ is an independent set of }G. IS G ( x 1 , … , x n ) = 1 ⟺ { v i ∣ x i = 1 } is an independent set of G .
Larsen and Williams [44 Thm. 3.2] showed that there is a randomized data structure using O ( n 2 ) O(n^2) O ( n 2 ) bits of space that computes this function in time n 2 2 Ω ( lg n ) \frac{n^2}{2^{\Omega(\sqrt{\lg n})}} 2 Ω ( l g n ) n 2 . We show that this data structure can be derandomized, and therefore Theorem 2 implies that enc ( I S G ) = n 2 2 Ω ( lg n ) \operatorname{enc}(\mathrm{IS}_G)=\frac{n^2}{2^{\Omega(\sqrt{\lg n})}} enc ( IS G ) = 2 Ω ( l g n ) n 2 . It is not hard to see that this implies that every 2-CNF function has a CNF encoding of size n 2 2 Ω ( lg n ) \frac{n^2}{2^{\Omega(\sqrt{\lg n})}} 2 Ω ( l g n ) n 2 . More generally, we show the following:
Theorem 4. If f : { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^n\to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } is a k k k -CNF function for some k ≥ 2 k\ge2 k ≥ 2 , then enc ( f ) = n k 2 Ω k ( lg n ) \operatorname{enc}(f)=\frac{n^k}{2^{\Omega_k(\sqrt{\lg n})}} enc ( f ) = 2 Ω k ( l g n ) n k .
The class of k k k -CNF functions (i.e., representable by CNF formulas where each clause has width exactly k k k ) is not only theoretically interesting [5 ] but is also of great practical importance in SAT solving, particularly for k = 2 k=2 k = 2 . This is because the encodings for many NP-complete graph problems (e.g., vertex cover, k k k -coloring, k k k -clique, etc.) are dominated by a 2-CNF component [60 ] . Theorem 4 implies that, for a fixed graph, all of these problems have CNF encodings with n 2 2 Ω k ( lg n ) \frac{n^2}{2^{\Omega_k(\sqrt{\lg n})}} 2 Ω k ( l g n ) n 2 clauses. Previously, the best known bound was O ( n 2 / lg n ) O(n^2/\lg n) O ( n 2 / lg n ) [60 , 53 ] , and more generally, hypergraph decompositions give encodings for k k k -CNF functions with O k ( n k / lg n ) O_k(n^k/\lg n) O k ( n k / lg n ) clauses [11 , 38 ] . Interestingly, a counting argument shows that if we restrict ourselves to encodings that are themselves k k k -CNF (or even bounded width), then some k k k -CNF functions require Ω k ( n k / lg n ) \Omega_k(n^k/\lg n) Ω k ( n k / lg n ) clauses. Thus, Theorem 4 rather surprisingly implies that clauses of unbounded width are helpful for encoding k k k -CNF functions.
Larsen and Williams’ data structure requires superpolynomial preprocessing time, so we do not know how to construct the encoding given by Theorem 4 in polynomial time. However, we do have a weaker bound, albeit still improving on the Θ k ( n k / lg n ) \Theta_k(n^k / \lg n) Θ k ( n k / lg n ) bound for bounded-width encodings, for which we have a polynomial-time construction:
Theorem 5. If f : { 0 , 1 } n → { 0 , 1 } f : \{0,1\}^n \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } is a k k k -CNF function for some fixed k ≥ 2 k \ge2 k ≥ 2 , then one can construct in deterministic polynomial time a CNF encoding of f f f with O k ( n k ( lg lg n ) 3 lg 2 n ) O_k\left(\frac{n^k(\lg\lg n)^3}{\lg^2 n}\right) O k ( l g 2 n n k ( l g l g n ) 3 ) clauses.
The best lower bound we have for the encoding complexity of k k k -CNF functions is Ω k ( n k / 2 ) \Omega_k(n^{k/2}) Ω k ( n k /2 ) clauses obtained via a counting argument (Proposition 35 ). Thus, there is a wide gap between our upper and lower bounds for this problem, and narrowing this gap is an interesting open problem.
En route to proving Theorem 2, we prove a result about encoding arbitrary boolean functions that are sparsely supported. We later sharpen this bound to the following, which may be of independent interest:
Theorem 6. For all 1 ≤ M ≤ 2 n − 1 1 \le M \le2^{n-1} 1 ≤ M ≤ 2 n − 1 , we have
enc ( n , M ) : = max { enc ( f ) : f : { 0 , 1 } n → { 0 , 1 } , ∣ f − 1 ( 1 ) ∣ = M } = Θ ( n + M ( n − lg M ) ) . \operatorname{enc}(n,M) := \max\left\{\operatorname{enc}(f) : f : \{0,1\}^n \to\{0,1\},\ |f^{-1}(1)| = M\right\} = \Theta\left(n+\sqrt{M(n-\lg M)}\right). enc ( n , M ) := max { enc ( f ) : f : { 0 , 1 } n → { 0 , 1 } , ∣ f − 1 ( 1 ) ∣ = M } = Θ ( n + M ( n − lg M ) ) .
As a direct corollary, we get an upper bound on arbitrary functions. Let f : { 0 , 1 } n → { 0 , 1 } f : \{0,1\}^n \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } , and consider the function g f : { 0 , 1 } n + 1 → { 0 , 1 } g_f : \{0,1\}^{n+1} \to\{0,1\} g f : { 0 , 1 } n + 1 → { 0 , 1 } defined by g f ( x ⃗ , y ) = f ( x ⃗ ) ∧ y g_f(\vec{x},y) = f(\vec{x}) \wedge y g f ( x , y ) = f ( x ) ∧ y , for which applying Theorem 6 gives enc ( g f ) = O ( 2 n ) \operatorname{enc}(g_f) = O(\sqrt{2^n}) enc ( g f ) = O ( 2 n ) . It is then easy to see that any encoding for g f g_f g f is also an encoding for f f f taking y y y as an auxiliary variable. Thus, enc ( f ) = O ( 2 n ) \operatorname{enc}(f) = O(\sqrt{2^n}) enc ( f ) = O ( 2 n ) , and this bound is optimal; this is a slight strengthening of the O ~ ( 2 n ) \widetilde{O}(\sqrt{2^n}) O ( 2 n ) bound we obtained from Theorem 2 above. Similar bounds are known for depth-3 unbounded fan-in circuits from [Dan96] and nondeterministic branching programs [47 ] (see § 1.4 ). In contrast, applying the Tseitin transformation to an optimal (fan-in-2) circuit for f f f [43 ] only gives enc ( f ) = O ( 2 n / n ) \operatorname{enc}(f) = O(2^n/n) enc ( f ) = O ( 2 n / n ) . In this sense, encodings, whose clauses can be arbitrarily wide, are more directly comparable to circuits with unbounded fan-in gates or nondeterministic branching programs.
Further applications of thm:robson-advice
To demonstrate how generally applicable Theorem 2 is, we derive a few corollaries for problems of interest to the SAT community.
Corollary 7. Let G G G be a graph with V ( G ) = [ n ] V(G) = [n] V ( G ) = [ n ] , and let H C G \mathrm{HC}_G HC G be the boolean function that receives vertices v 1 , … , v n ∈ [ n ] v_1,\ldots,v_n \in[n] v 1 , … , v n ∈ [ n ] , each written in binary using ⌈ lg n ⌉ \lceil\lg n\rceil ⌈ lg n ⌉ input variables, and outputs 1 if and only if v 1 , … , v n v_1,\ldots,v_n v 1 , … , v n are distinct and { v i , v i + 1 } ∈ E ( G ) \{v_i,v_{i+1}\} \in E(G) { v i , v i + 1 } ∈ E ( G ) for every i ∈ [ n ] i \in[n] i ∈ [ n ] , where v n + 1 : = v 1 v_{n+1} := v_1 v n + 1 := v 1 . Then, enc ( H C G ) = O ~ ( n ∣ E ( G ) ∣ ) \operatorname{enc}(\mathrm{HC}_G) = \widetilde{O}(\sqrt{n|E(G)|}) enc ( HC G ) = O ( n ∣ E ( G ) ∣ ) .
Proof. We may assume that ∣ E ( G ) ∣ ≥ n |E(G)| \ge n ∣ E ( G ) ∣ ≥ n , as otherwise H C G \mathrm{HC}_G HC G is constantly 0. Let the advice be a list A A A of the edges of G G G , each stored as a pair of integers written in binary, so m = O ( ∣ E ( G ) ∣ lg n ) m = O(|E(G)|\lg n) m = O ( ∣ E ( G ) ∣ lg n ) . An ANRAM machine can check that v 1 , … , v n v_1,\ldots,v_n v 1 , … , v n are distinct by scanning over the vertices and maintaining an array of which have been seen so far; then, for each i ∈ [ n ] i \in[n] i ∈ [ n ] , it can guess an index p p p and verify that A [ p ] = { v i , v i + 1 } A[p] = \{v_i,v_{i+1}\} A [ p ] = { v i , v i + 1 } by querying O ( lg n ) O(\lg n) O ( lg n ) bits of advice. Hence, t = O ~ ( n ) t = \widetilde{O}(n) t = O ( n ) and b = O ( n lg n ) b = O(n\lg n) b = O ( n lg n ) , and Theorem 2 gives enc ( H C G ) = O ~ ( n ∣ E ( G ) ∣ ) \operatorname{enc}(\mathrm{HC}_G) = \widetilde{O}(\sqrt{n|E(G)|}) enc ( HC G ) = O ( n ∣ E ( G ) ∣ ) .
In contrast, the most compact CNF encodings from Zhou [69 ] for Hamiltonian cycle use Θ ( ∣ E ( G ) ∣ lg n ) \Theta(|E(G)|\lg n) Θ ( ∣ E ( G ) ∣ lg n ) clauses. We note however that Zhou uses a different representation for the input variables: instead of a binary representation with Θ ( n lg n ) \Theta(n\lg n) Θ ( n lg n ) variables, he uses a one-hot representation with Θ ( ∣ E ∣ ) \Theta(|E|) Θ ( ∣ E ∣ ) variables. Nevertheless, our encoding provides a reduction of the Hamiltonian cycle problem to SAT with fewer clauses.
Corollary 8. Let G G G be a graph with V ( G ) = [ n ] V(G)=[n] V ( G ) = [ n ] and let k ≥ 2 k \ge2 k ≥ 2 . Let CLIQUE G , k \operatorname{CLIQUE}_{G,k} CLIQUE G , k be the boolean function that receives vertices v 1 , … , v k ∈ [ n ] v_1,\ldots,v_k \in[n] v 1 , … , v k ∈ [ n ] in binary and outputs 1 if and only if { v i , v j } ∈ E ( G ) \{v_i,v_j\} \in E(G) { v i , v j } ∈ E ( G ) for all i ≠ j i \ne j i = j . Then, enc ( CLIQUE G , k ) = O ~ ( k ∣ E ( G ) ∣ lg n ) \operatorname{enc}(\operatorname{CLIQUE}_{G,k})=\tilde{O}(k\sqrt{|E(G)|}\lg n) enc ( CLIQUE G , k ) = O ~ ( k ∣ E ( G ) ∣ lg n ) .
Proof. We may assume that ∣ E ( G ) ∣ ≥ ( k 2 ) |E(G)| \ge\binom{k}{2} ∣ E ( G ) ∣ ≥ ( 2 k ) , as otherwise CLIQUE G , k \operatorname{CLIQUE}_{G,k} CLIQUE G , k is constantly 0. With the same advice A A A as in Corollary 7, an ANRAM machine can guess, for each pair i ≠ j i \ne j i = j , an index p p p and verify that A [ p ] = { v i , v j } A[p]=\{v_i,v_j\} A [ p ] = { v i , v j } . Hence, t = O ( k 2 lg n ) t=O(k^2\lg n) t = O ( k 2 lg n ) and b = O ( k 2 lg n ) b=O(k^2\lg n) b = O ( k 2 lg n ) , and Theorem 2 gives enc ( CLIQUE G , k ) = O ~ ( k ∣ E ( G ) ∣ lg n ) \operatorname{enc}(\operatorname{CLIQUE}_{G,k})=\tilde{O}(k\sqrt{|E(G)|}\lg n) enc ( CLIQUE G , k ) = O ~ ( k ∣ E ( G ) ∣ lg n ) .
For comparison, a direct encoding of k k k -clique uses Ω ( ∣ E ( G ) ∣ ) \Omega(|E(G)|) Ω ( ∣ E ( G ) ∣ ) clauses, and Subercaseaux [60 ] showed one can obtain O ( n 2 / lg n ) O(n^2/\lg n) O ( n 2 / lg n ) clauses. Corollary 8 is better than these bounds whenever k k k is much smaller than ∣ E ( G ) ∣ \sqrt{|E(G)|} ∣ E ( G ) ∣ .
Our third corollary shows that randomly chosen k k k -CNF functions have much smaller encodings than the worst-case bound of Theorem 4, leveraging the celebrated result of Balogh, Dong, Lidický, Mani, and Zhao [5 ] who showed that almost all k k k -CNF functions are unate , i.e., antitone after negating some of the input variables.
Corollary 9. For every fixed k ≥ 2 k \ge2 k ≥ 2 , a uniformly random k k k -CNF function f : { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^n \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } satisfies enc ( f ) = O ~ ( n k / 2 ) \operatorname{enc}(f)=\tilde{O}(n^{k/2}) enc ( f ) = O ~ ( n k /2 ) with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) .
Proof. By [5 Theorem 1.1] , the number of k k k -CNF functions on n n n variables is ( 1 + o ( 1 ) ) 2 ( n k ) + n (1+o(1))2^{\binom{n}{k}+n} ( 1 + o ( 1 )) 2 ( k n ) + n . Thus, it suffices to show that there are ( 1 − o ( 1 ) ) 2 ( n k ) + n (1-o(1))2^{\binom{n}{k}+n} ( 1 − o ( 1 )) 2 ( k n ) + n k k k -CNF functions f f f that satisfy the desired bound. Indeed, consider the set H \mathcal{H} H of functions of the form ⋀ i = 1 m ⋁ j ∈ S i x j ‾ \bigwedge_{i=1}^{m}\bigvee_{j\in S_i}\overline{x_j} ⋀ i = 1 m ⋁ j ∈ S i x j for sets S 1 , … , S m ∈ ( [ n ] k ) S_1,\ldots,S_m\in\binom{[n]}{k} S 1 , … , S m ∈ ( k [ n ] ) , and note that ∣ H ∣ = 2 ( n k ) |\mathcal{H}|=2^{\binom{n}{k}} ∣ H ∣ = 2 ( k n ) . It is a standard fact that with high probability a uniformly random function from H \mathcal{H} H does not accept any input with more than s : = ⌈ 3 lg n ⌉ s:=\lceil3\lg n\rceil s := ⌈ 3 lg n ⌉ ones. Indeed, the expected number of satisfying inputs to a uniformly random function from H \mathcal{H} H with Hamming weight s s s is
( n s ) 2 − ( s k ) ≤ n s 2 − ( s 2 ) ≤ 2 s lg n − s ( s − 1 ) / 2 ≤ 2 − s = o ( 1 ) . \binom{n}{s}2^{-\binom{s}{k}} \le n^s2^{-\binom{s}{2}} \le2^{s\lg n-s(s-1)/2} \le2^{-s}=o(1). ( s n ) 2 − ( k s ) ≤ n s 2 − ( 2 s ) ≤ 2 s l g n − s ( s − 1 ) /2 ≤ 2 − s = o ( 1 ) .
Therefore, there is a subset H ′ ⊆ H \mathcal{H}'\subseteq\mathcal{H} H ′ ⊆ H of size ( 1 − o ( 1 ) ) 2 ( n k ) (1-o(1))2^{\binom{n}{k}} ( 1 − o ( 1 )) 2 ( k n ) for which no satisfying assignment has more than s s s ones. Moreover, the subset H ′ ′ ⊆ H ′ \mathcal{H}''\subseteq\mathcal{H}' H ′′ ⊆ H ′ of functions for which all n n n variables appear in their corresponding formulas satisfies ∣ H ′ ′ ∣ = ( 1 − o ( 1 ) ) ∣ H ′ ∣ |\mathcal{H}''|=(1-o(1))|\mathcal{H}'| ∣ H ′′ ∣ = ( 1 − o ( 1 )) ∣ H ′ ∣ . Now, note that relabeling any subset of the variables of a function by their negations never changes its encoding complexity, and thus, for each function in H ′ ′ \mathcal{H}'' H ′′ there are 2 n 2^n 2 n distinct k k k -CNF functions with the same encoding complexity, and these 2 n ∣ H ′ ′ ∣ 2^n|\mathcal{H}''| 2 n ∣ H ′′ ∣ functions are all distinct. Therefore, it remains to see that enc ( f ) = O ~ ( n k / 2 ) \operatorname{enc}(f)=\tilde{O}(n^{k/2}) enc ( f ) = O ~ ( n k /2 ) for every f ∈ H ′ ′ f\in\mathcal{H}'' f ∈ H ′′ .
We show this by Theorem 2. Let the advice be the characteristic vector of the collection S 1 , … , S m S_1,\ldots,S_m S 1 , … , S m over all ( n k ) \binom{n}{k} ( k n ) size-k k k subsets, so m = ( n k ) m=\binom{n}{k} m = ( k n ) . An ANRAM machine can deterministically scan the input and reject if it contains more than s s s ones; otherwise, it lists the at most s s s variables set to 1 and queries one advice bit for each of the at most ( s k ) \binom{s}{k} ( k s ) sets of k k k of them, accepting if and only if none of these sets has a 1 in the advice string. Hence, t = O ~ ( n ) t=\tilde{O}(n) t = O ~ ( n ) and b = O ( lg k n ) b=O(\lg^k n) b = O ( lg k n ) , and Theorem 2 gives enc ( f ) = O ~ ( n + n k lg k n ) = O ~ ( n k / 2 ) \operatorname{enc}(f)=\tilde{O}(n+\sqrt{n^k\lg^k n})=\tilde{O}(n^{k/2}) enc ( f ) = O ~ ( n + n k lg k n ) = O ~ ( n k /2 ) .
We show in Proposition 35 that, conversely, a random k k k -CNF function satisfies enc ( f ) = Ω k ( n k / 2 ) \operatorname{enc}(f)=\Omega_k(n^{k/2}) enc ( f ) = Ω k ( n k /2 ) with high probability, so Corollary 9 is tight up to polylogarithmic factors. Curiously, the situation for worst-case k k k -CNF functions is much more complicated: there, the best bounds we know are the same Ω k ( n k / 2 ) \Omega_k(n^{k/2}) Ω k ( n k /2 ) lower bound and the n k 2 Ω k ( lg n ) \frac{n^k}{2^{\Omega_k(\sqrt{\lg n})}} 2 Ω k ( l g n ) n k upper bound of Theorem 4. Closing this gap remains an interesting open problem, and is related to the gap between the worst-case results of Larsen and Williams [44 ] for answering independent set queries in graphs, and the average case, which is much easier.
Why study clause minimization?
The choice of CNF encoding is known to have a dramatic impact on the performance of modern SAT solvers, allowing, for instance, the solution of long-standing problems in discrete mathematics [HS24, SH23]. A major challenge, however, is to understand what properties of encodings are best correlated with empirical runtimes [6 , 24 ] . In 2009, Björk published interviews with several experts on practical CNF encodings, and the consensus was that clause width (which impacts the total number of literals in an encoding) was not an important factor, but the total number of clauses was more relevant.4 The encodings we present in this paper reduce the number of clauses by increasing the width, which can often be a favorable trade-off. We recently showed that CNF encodings for cardinality constraints (i.e., ∑ i x i ≤ k \sum_i x_i \le k ∑ i x i ≤ k ) with fewer but wider clauses can outperform classical encodings in some settings [36 ] .
Furthermore, measuring complexity by the number of clauses has connections to other theoretically interesting models of computation. For example, we show in § 6 that enc ( f ) \operatorname{enc}(f) enc ( f ) is equal to the minimum number of ∧ \wedge ∧ -wires (when enc ( f ) ≥ 2 \operatorname{enc}(f) \ge2 enc ( f ) ≥ 2 ), which is within a factor of two of the minimum number of fan-in-two ∧ \wedge ∧ -gates in a nondeterministic De Morgan circuit computing f f f . It is therefore no coincidence that our recent work on CNF encodings of cardinality constraints has yielded insights that have led to improved circuit complexity bounds [36 ] . Similarly, encoding complexity is related to the minimum number of constraints in integer linear programs (ILPs), since each clause ⋁ i ℓ i \bigvee_i \ell_i ⋁ i ℓ i can be written as ∑ i ℓ i ≥ 1 \sum_i \ell_i \ge1 ∑ i ℓ i ≥ 1 . Thus, our encodings directly translate to 0/1-ILP formulations with few constraints, using auxiliary variables (cf. extension complexity [68 FMP⁺12] ).
Related work
The key ingredients for Theorems 4 and 5 are data structures for computing independent-set queries, which is a well-studied problem in fine-grained complexity. Williams [67 ] showed that there is a data structure for this task with deterministic polynomial preprocessing and O ( n 2 / lg 2 n ) O(n^2/\lg^2 n) O ( n 2 / lg 2 n ) query time on a pointer machine; Billeloch, Vassilevska, and Williams [8 ] extended this work to support queries on sparse graphs. Bansal and Williams [9 ] gave faster batched queries using graph decompositions based on weak regularity. These query-time bounds do not directly give the same clause bounds in our setting, because the memory needed to represent lookup tables must also be encoded. As mentioned above, Theorem 4 is a consequence of derandomizing a data structure of Larsen and Williams [44 ] for computing independent set queries (see Theorem 15). Our proof of Theorem 5 can be seen as yet another data structure for independent set queries, albeit implemented directly as a CNF encoding.
Our results are closely related to the extension complexity of polytopes that have a prescribed intersection with the boolean hypercube, as studied by Hrubeš and Talebanfard [30 ] . They obtain an O ( 2 n ) O(\sqrt{2^n}) O ( 2 n ) extension complexity for polytopes intersecting an arbitrary A ⊆ { 0 , 1 } n A \subseteq\{0,1\}^n A ⊆ { 0 , 1 } n , which is similar to a special case of our Theorem 6, although in their case the lower bound is not known to be tight (see below for other bounds of this order in related models). Furthermore, the edge polytope of graphs, which is tightly related to the boolean function I S G \mathrm{IS}_G IS G , was studied by Fiorini, Kaibel, Pashkovich, and Theis [FKPT13] using biclique partitions, one of the components of our proof of Theorem 5. More generally, the problem of compactly encoding I S G \mathrm{IS}_G IS G fits into a broader landscape of graph complexity measures [33 , 32 ] . Interestingly, most of these prior results also rely on biclique partitions, which by themselves cannot yield encodings of size o ( n 2 / lg n ) o(n^2/\lg n) o ( n 2 / lg n ) ; more specifically related to our work, Subercaseaux [60 ] observed that biclique partitions give enc ( I S G ) = O ( n 2 / lg n ) \operatorname{enc}(\mathrm{IS}_G)=O(n^2/\lg n) enc ( IS G ) = O ( n 2 / lg n ) , and recently a refined analysis using rectifier networks from Przybocki, Subercaseaux, and Heule [53 ] showed enc ( I S G ) ≤ ( 1 4 + o ( 1 ) ) n 2 / lg n \operatorname{enc}(\mathrm{IS}_G)\leq(\frac{1}{4}+o(1))n^2/\lg n enc ( IS G ) ≤ ( 4 1 + o ( 1 )) n 2 / lg n , and that this cannot be improved via rectifier-network encodings.
The dense case of Theorem 6, namely that every boolean function on n n n inputs has enc ( f ) = Θ ( 2 n ) \operatorname{enc}(f)=\Theta(\sqrt{2^n}) enc ( f ) = Θ ( 2 n ) in the worst case, has classical circuit complexity analogues: worst-case bounds of order 2 n \sqrt{2^n} 2 n are well known in models of computation where gates have unbounded fan-in or some operations come for free, and in several of them the exact constant is known; see [32 Sec. 1.4.4] for an overview. For instance, every boolean function on n n n inputs can be computed by a depth-3 unbounded fan-in circuit with ( 2 + o ( 1 ) ) 2 n (2+o(1))\sqrt{2^n} ( 2 + o ( 1 )) 2 n gates, and this is tight [Dan96, Ser19].5 Nechiporuk [47 ] proved that nondeterministic branching programs with ( 2 + o ( 1 ) ) 2 n (2+o(1))\sqrt{2^n} ( 2 + o ( 1 )) 2 n edges suffice for all n n n -bit functions.6
Recently, Sheng and Xiao have shown a surprising role of CNF encodings in the theory of kernelization, using them as ingredients to exhibit the first polynomial-sized kernel for planar directed feedback vertex set [62 ] , as well as a near-linear element kernel for d d d -hitting set [61 ] .
Technical Overview
Nondeterministic RAM with advice
In § 3 , we prove Theorem 2, which states that if f : { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^n\to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } can be evaluated in time t t t with m m m bits of advice by an ANRAM machine that accesses at most b b b bits of the advice for each input, then enc ( f ) = O ~ ( t + m b ) \operatorname{enc}(f)=\widetilde{O}(t+\sqrt{mb}) enc ( f ) = O ( t + mb ) . Our starting point is the case without advice proven by Robson [55 ] , which states that enc ( f ) = O ~ ( t ) \operatorname{enc}(f)=\widetilde{O}(t) enc ( f ) = O ( t ) when m = 0 m=0 m = 0 . Thus, the central challenge is how to encode the advice queries using only O ~ ( m b ) \widetilde{O}(\sqrt{mb}) O ( mb ) clauses. Since the advice string can be thought of as a function h : { 0 , 1 } lg m → { 0 , 1 } h:\{0,1\}^{\lg m}\to\{0,1\} h : { 0 , 1 } l g m → { 0 , 1 } , and such functions can be encoded with O ( 2 lg m ) = O ( m ) O(\sqrt{2^{\lg m}})=O(\sqrt{m}) O ( 2 l g m ) = O ( m ) clauses according to Theorem 6, a naïve approach would use a total of O ( b m ) O(b\sqrt{m}) O ( b m ) clauses to query b b b bits. We improve upon this in Lemma 11, which provides a “mass-production theorem” (cf. [66 , 39 ] ) that roughly states we can encode b b b queries to a function only paying a b \sqrt{b} b multiplicative factor. More precisely, for any boolean function g : { 0 , 1 } k → { 0 , 1 } g:\{0,1\}^k\to\{0,1\} g : { 0 , 1 } k → { 0 , 1 } , let g ∧ b : { 0 , 1 } k b → { 0 , 1 } g^{\wedge b}:\{0,1\}^{kb}\to\{0,1\} g ∧ b : { 0 , 1 } k b → { 0 , 1 } be the function defined by g ∧ b ( x ⃗ 1 , … , x ⃗ b ) : = ⋀ i = 1 b g ( x ⃗ i ) g^{\wedge b}(\vec{x}_1,\ldots,\vec{x}_b) := \bigwedge_{i=1}^{b} g(\vec{x}_i) g ∧ b ( x 1 , … , x b ) := ⋀ i = 1 b g ( x i ) , where each x ⃗ i \vec{x}_i x i has length k k k . Then, our lemma says that enc ( g ∧ b ) = O ~ ( b 2 k ) \operatorname{enc}(g^{\wedge b}) = \widetilde{O}(\sqrt{b2^k}) enc ( g ∧ b ) = O ( b 2 k ) .
We think of the truth table of g g g as an array A A A of size 2 k 2^k 2 k , indexed in binary by x ⃗ ∈ { 0 , 1 } k \vec{x} \in\{0,1\}^k x ∈ { 0 , 1 } k . Then, the key idea to prove Lemma 11 is that if we were promised that the inputs x ⃗ 1 , … , x ⃗ b \vec{x}_1,\ldots,\vec{x}_b x 1 , … , x b on which we want to query the array A A A were such that each x ⃗ i \vec{x}_i x i is in the i i i th 2 k / b 2^k/b 2 k / b -sized chunk of A A A (see Figure 1 ), then each x ⃗ i \vec{x}_i x i could be described with only lg ( 2 k / b ) \lg(2^k/b) lg ( 2 k / b ) bits representing its position within the corresponding chunk, and thus the boolean function defined by whether those k − lg ( b ) k-\lg(b) k − lg ( b ) bits indicate a 1 in A A A can be encoded with O ( 2 k / b ) O(\sqrt{2^k/b}) O ( 2 k / b ) clauses according to Theorem 6; taking the conjunction of these b b b encodings would give enc ( g ∧ b ) = b ⋅ O ( 2 k / b ) = O ( b 2 k ) \operatorname{enc}(g^{\wedge b}) = b \cdot O(\sqrt{2^k/b}) = O(\sqrt{b2^k}) enc ( g ∧ b ) = b ⋅ O ( 2 k / b ) = O ( b 2 k ) .
Figure 1. The truth table of g g g , partitioned into b b b chunks of 2 k / b 2^k/b 2 k / b entries each.
Naturally, we do not have this promise in general, but we can roughly simulate it by “hashing” each input x ⃗ i \vec{x}_i x i into O ( b ) O(b) O ( b ) slots in such a way that the average number of possible inputs that are hashed into a slot is O ~ ( 2 k / b ) \widetilde{O}(2^k/b) O ( 2 k / b ) . This hashing takes place within the encoding itself, using an explicit expander from Teutsch [64 ] . As opposed to the simplified promise described above, where each input’s address is indexed only by the lg ( 2 k / b ) \lg(2^k/b) lg ( 2 k / b ) variables associated to its chunk, the inputs that are mapped into a given slot may have addresses anywhere in A A A . Nevertheless, we can still apply Theorem 6, because each slot’s function is sparse , accepting only O ~ ( 2 k / b ) \widetilde{O}(2^k/b) O ( 2 k / b ) addresses on average (recall that for a function with M M M satisfying inputs, the bound of Theorem 6 scales roughly with M \sqrt{M} M rather than 2 n \sqrt{2^n} 2 n ).7
We find it notable that sparsity enters the argument at all. The function g g g we are querying is arbitrary and potentially dense, and both the naïve approach and the promise version above use only the special case enc ( f ) = O ( 2 n ) \operatorname{enc}(f) = O(\sqrt{2^n}) enc ( f ) = O ( 2 n ) for arbitrary f f f . The hashing step is what creates sparsity : each of the b b b queries may land anywhere in the dense table of 2 k 2^k 2 k entries, but hashing routes it to one of O ( b ) O(b) O ( b ) slots, each responsible for only an O ~ ( 1 / b ) \widetilde{O}(1/b) O ( 1/ b ) fraction of the addresses on average. The dependence of Theorem 6 on the support size, in the regime M = o ( 2 n ) M = o(2^n) M = o ( 2 n ) , is exactly what lets us exploit this.
k-CNF boolean functions
We start with a reduction, presented in § 4.4 , that shows how upper bounds for encoding the independent-set function I S G \mathrm{IS}_G IS G translate into upper bounds for general k k k -CNF functions. More precisely, if every n n n -vertex graph G G G satisfies enc ( I S G ) ≤ f ( n ) \operatorname{enc}(\mathrm{IS}_G) \le f(n) enc ( IS G ) ≤ f ( n ) for some function f f f , then any k k k -CNF function can be encoded with O k ( n k − 2 f ( n ) ) O_k(n^{k-2}f(n)) O k ( n k − 2 f ( n )) clauses.
Thus, to prove Theorem 4, it suffices to prove that enc ( I S G ) = n 2 2 Ω ( lg n ) \operatorname{enc}(\mathrm{IS}_G) = \frac{n^2}{2^{\Omega(\sqrt{\lg n})}} enc ( IS G ) = 2 Ω ( l g n ) n 2 for all n n n -vertex graphs G G G . We do this by applying our Theorem 2 to a derandomized version of the algorithm of Larsen and Williams [44 ] for answering independent set queries. In order to derandomize their algorithm, we use a derandomization for the orthogonal vectors problem due to Chan and Williams [14 ] .
The proof of Theorem 5 explicitly constructs an encoding for I S G \mathrm{IS}_G IS G without using Theorem 2, which makes it much more technically sophisticated. The reason for this is that we do not know how to save more than a lg 2 n \lg^2 n lg 2 n factor within deterministic polynomial time, and since Theorem 2 loses polylogarithmic factors, its direct application could not beat the n k / lg n n^k / \lg n n k / lg n simple known upper bound. This proof, instead, is based on an efficient regularity-like graph decomposition (Lemma 27 ), whose building blocks can be encoded compactly: bipartite graphs without large empty squares (i.e., their bipartite complement does not have large bicliques), and a single sparse subgraph. The sparse part can be encoded directly by known results on biclique partitions, while the bipartite graphs without large empty squares are handled by a dedicated encoding which uses hashing (via explicit expanders) in a similar way to Theorem 2. Computing this decomposition in deterministic polynomial time is technically challenging, and relies on an efficient algorithm for identifying sparse squares in a graph (Lemma 25 ) which is based on derandomizing a random walk via explicit expanders in the same spirit as the derandomization of graph products from Alon, Feige, Wigderson, and Zuckerman [1 ] .
Finally, in § 4.8 , we prove our lower bounds for k k k -CNF functions using information-theoretic arguments, which are the only technique we have for proving superlinear lower bounds on encodings. For encodings of bounded width, a direct counting argument gives the Ω k ( n k / lg n ) \Omega_k(n^k / \lg n) Ω k ( n k / lg n ) lower bound mentioned above. Without a width bound, we need to bound the number of minimal encodings with at most q q q clauses, which in turn requires a bound on the number of auxiliary variables that can appear in such an encoding. We prove in Proposition 30 that a minimal encoding has fewer auxiliary variables than clauses. Intuitively, if we have more auxiliary variables than clauses in an encoding, then clauses become “too easy” to satisfy. To formalize this idea, we show using Hall’s marriage theorem that if there are at least as many auxiliary variables as clauses, then there is a partial assignment α \alpha α to the auxiliary variables that satisfies every clause containing a variable in the domain of α \alpha α . Such an α \alpha α is called an autarky [46 ] , and it is a straightforward argument to show that an encoding with an autarky cannot be minimal. This yields Lemma 34 , which states that at most 3 ( n + q ) q + 1 3^{(n+q)q}+1 3 ( n + q ) q + 1 functions on n n n inputs have encodings with at most q q q clauses; this lemma gives the Ω k ( n k / 2 ) \Omega_k(n^{k/2}) Ω k ( n k /2 ) bound of Proposition 35 , as well as the lower bounds for sparsely supported functions described next.
Sparsely supported functions
In § 5 , we prove Theorem 6, which states that the worst-case encoding complexity of a function f : { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^n \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } with exactly M M M satisfying inputs is enc ( n , M ) = Θ ( n + M ( n − lg M ) ) \operatorname{enc}(n,M)=\Theta(n+\sqrt{M(n-\lg M)}) enc ( n , M ) = Θ ( n + M ( n − lg M ) ) for 1 ≤ M ≤ 2 n − 1 1 \le M \le2^{n-1} 1 ≤ M ≤ 2 n − 1 . Our upper-bound construction translates a succinct static dictionary [7 , 49 Pătr08, HLY⁺25] directly into an encoding. This further illustrates the principle behind Theorem 2 of translating data structures into encodings; perhaps remarkably, here an asymptotically space-optimal data structure yields an asymptotically optimal encoding.
Conceptually, the dictionary reduces the sparse case to the dense case: it compresses f − 1 ( 1 ) f^{-1}(1) f − 1 ( 1 ) into a table σ f \sigma_f σ f of S = O ( M ( n − lg M ) ) S=O(M(n-\lg M)) S = O ( M ( n − lg M )) bits, from which f f f is evaluated with O ( 1 ) O(1) O ( 1 ) lookups and word operations. Here, each of the O ( 1 ) O(1) O ( 1 ) word operations can be encoded directly via the Tseitin transformation (without even invoking Robson’s theorem [55 ] ), so the main difficulty lies in the lookups. It is tempting to handle each lookup by viewing σ f \sigma_f σ f as an arbitrary function on lg S \lg S lg S variables and applying a construction for arbitrary functions with O ( S ) O(\sqrt{S}) O ( S ) clauses, such as Proposition 36 or Nechiporuk’s nondeterministic branching programs [47 ] . However, each lookup retrieves an entire word of w = Θ ( n ) w = \Theta(n) w = Θ ( n ) bits, and fetching it one bit at a time costs O ( w S ) O(w\sqrt{S}) O ( w S ) clauses, a factor of Θ ( n ) \Theta(n) Θ ( n ) too many.
We overcome this with Lemma 38 , which may be of independent interest: an entire block of w w w bits of a table of size S S S can be fetched with O ( S + w ) O(\sqrt{S} + w) O ( S + w ) clauses. Since even a single bit of a worst-case table requires Ω ( S ) \Omega(\sqrt{S}) Ω ( S ) clauses (Proposition 36 ), the remaining bits come essentially for free when w ≤ S w \le\sqrt{S} w ≤ S . Checking each memory read with this lemma then gives the upper bound of Theorem 6.
In turn, we derive Lemma 38 from Lemma 13 , a slightly weaker version of Theorem 6 with O ( n + n M ) O(n + \sqrt{nM}) O ( n + n M ) clauses that we prove directly in § 3.3 . Its proof arranges the M M M satisfying inputs in an R × C R \times C R × C table and guesses an entry, with the column written in binary and the row chosen by one-hot variables. Rather than checking each row separately, which would cost n n n clauses per row, for each column, each value of each input bit x i x_i x i implies the disjunction of the rows whose entry agrees with it. Thus we pay only for the C C C columns and n n n coordinates, giving O ( R + n C ) = O ( n + n M ) O(R + nC) = O(n + \sqrt{nM}) O ( R + n C ) = O ( n + n M ) clauses for C = Θ ( M / n ) C = \Theta(\sqrt{M/n}) C = Θ ( M / n ) . Lemma 38 is then a direct application of Lemma 13 to the function that accepts an address j j j and a word z ⃗ \vec{z} z if and only if z ⃗ \vec{z} z is stored at address j j j ; this function has Θ ( w ) \Theta(w) Θ ( w ) variables and S / w S/w S / w satisfying inputs, giving O ( w + w ⋅ S / w ) = O ( S + w ) O(w + \sqrt{w \cdot S/w}) = O(\sqrt{S} + w) O ( w + w ⋅ S / w ) = O ( S + w ) clauses. In other words, the dictionary turns the sparse problem into a dense one, and Lemma 38 turns it back into a sparse one, loosely echoing how hashing creates sparsity in the proof of Lemma 11.
Encoding Nonuniform Computation
In this section, we prove Theorem 2:
Theorem 2. Let f : { 0 , 1 } n → { 0 , 1 } f : \{0,1\}^{n} \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } , and suppose that f f f can be evaluated in time t ≥ n t \ge n t ≥ n with m m m bits of advice by an ANRAM machine that accesses at most b b b bits of the advice for each input. Then, enc ( f ) = O ~ ( t + m b ) \operatorname{enc}(f) = \widetilde{O}(t + \sqrt{mb}) enc ( f ) = O ( t + mb ) . Furthermore, such an encoding can be constructed deterministically in time polynomial in n + t + m n + t + m n + t + m given the advice string.
Our proof relies on several ingredients, including a modification to Robson’s theorem [55 ] . Robson proved that given a nondeterministic RAM machine M \mathcal{M} M and an input x ⃗ \vec{x} x such that M ( x ⃗ ) \mathcal{M}(\vec{x}) M ( x ) runs in time t t t , one can construct in deterministic polynomial time a CNF formula φ M , x ⃗ \varphi_{\mathcal{M},\vec{x}} φ M , x of size O ( t lg t ) O(t \lg t) O ( t lg t ) such that SAT ( φ M , x ⃗ ) \operatorname{SAT}(\varphi_{\mathcal{M},\vec{x}}) SAT ( φ M , x ) if and only if M ( x ⃗ ) \mathcal{M}(\vec{x}) M ( x ) accepts. However, by inspecting the proof it is easy to see that his construction is “uniform” over the inputs, meaning that a very slight modification yields a formula φ M \varphi_{\mathcal{M}} φ M , with x ⃗ \vec{x} x as the input variables (and with auxiliary variables), and such that M ( x ⃗ ) \mathcal{M}(\vec{x}) M ( x ) accepts if and only if SAT ( φ M ( x ⃗ ) ) \operatorname{SAT}(\varphi_{\mathcal{M}}(\vec{x})) SAT ( φ M ( x )) . Thus, we have the following:
Theorem 10 (Robson’s theorem [55 ] ). Let f : { 0 , 1 } n → { 0 , 1 } f : \{0,1\}^{n} \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } , and suppose that f f f can be evaluated in time t t t by a nondeterministic RAM machine. Then, enc ( f ) = O ( t lg t ) \operatorname{enc}(f) = O(t \lg t) enc ( f ) = O ( t lg t ) . Furthermore, such an encoding can be constructed deterministically in time polynomial in n + t n + t n + t .
Nondeterministic RAM with advice (ANRAM)
Our nondeterministic-RAM-with-advice model closely follows that of the nondeterministic RAM used by [55 ] . In Robson’s model, a machine is specified by a sequence of instructions ( i 1 , … , i T ) (i_1,\ldots,i_T) ( i 1 , … , i T ) , which are to be executed sequentially by default, but include the possibility of jumping to other instructions, as for example i 7 : = J U M P 3 i_7 := \mathrm{JUMP}\ 3 i 7 := JUMP 3 , which would make the machine go back to execute i 3 i_3 i 3 . For the sake of our asymptotic results, we follow Robson in assuming that the number of instructions is upper-bounded by a fixed constant; this assumption is without loss of generality, because we can use a universal machine and encode the instructions as part of the advice. The input is given on a read-only tape, which is read sequentially (i.e., no random access). There are infinitely many registers r 0 , r 1 , r 2 , … r_0,r_1,r_2,\ldots r 0 , r 1 , r 2 , … , with r 0 r_0 r 0 representing a special accumulator register where operations take place. The machine has instructions for loading data into the accumulator, storing the contents of the accumulator, adding and subtracting to the accumulator, unconditional jumping, conditional jumping, nondeterministic jumping, and halting. As with Robson, we use the logarithmic cost criterion , where the cost of an operation is proportional to the lengths of its operands measured in bits.
The above model of computation constitutes nondeterministic RAM. For ANRAM, we allow the machine to make random-access queries to a read-only advice memory containing an advice string A A A , which does not depend on the input. In principle, such a machine could query the advice string at any point throughout a computation. It will be convenient, however, to assume all advice queries are made at the very beginning. Thanks to nondeterminism, this assumption can be made without loss of generality, since such a machine can nondeterministically guess, at the beginning of a computation, which advice queries will be made during the remaining computation. After making these queries, the machine operates as a nondeterministic RAM machine without advice , which uses the prefetched advice queries instead of directly querying the advice memory. If the machine ever needs the i i i th bit of advice, and it is not available in the registers corresponding to prefetched advice queries, then it simply rejects. Formally, we stipulate that an ANRAM machine operates as follows after receiving an input x ⃗ \vec{x} x :
First, the machine nondeterministically guesses the indices i 1 , i 2 , … , i b i_1,i_2,\ldots,i_b i 1 , i 2 , … , i b of A A A that will be queried during the computation on x ⃗ \vec{x} x . The machine then fetches those bits of advice, storing the results as a list of ordered pairs ( ( i 1 , A [ i 1 ] ) , … , ( i b , A [ i b ] ) ) ((i_1,A[i_1]),\ldots,(i_b,A[i_b])) (( i 1 , A [ i 1 ]) , … , ( i b , A [ i b ])) .
Then, the machine passes x ⃗ \vec{x} x together with the advice queries ( ( i 1 , A [ i 1 ] ) , … , ( i b , A [ i b ] ) ) ((i_1,A[i_1]),\ldots,(i_b,A[i_b])) (( i 1 , A [ i 1 ]) , … , ( i b , A [ i b ])) to a nondeterministic RAM machine without advice.
Proof of the advice-to-CNF theorem
To prove Theorem 2, we will use auxiliary variables that serve to nondeterministically guess the advice string, and then use Theorem 10 in a black-box fashion. The main technical difficulty, however, is that we cannot afford to guess the entire advice string, but only the b b b bits that will be accessed during the computation, and thus we will need to encode into CNF a “check-advice” subroutine that ensures that the b b b bits guessed, which can vary depending on the input, are compatible with the global advice string A A A . It turns out that the subroutine we need for checking advice is a particular case of a more general problem: obtaining compact encodings for “multiple queries” to a boolean function. The following lemma, in the spirit of “mass production theorems” [66 , 39 ] , shows that querying a boolean function b b b times on arbitrary inputs can be encoded with substantially fewer clauses than b b b independent encodings.
Lemma 11. Let f : { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^n\to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } , and let b ∈ [ 2 n ] b\in[2^n] b ∈ [ 2 n ] . Let f ∧ b : { 0 , 1 } b n → { 0 , 1 } f^{\wedge b}:\{0,1\}^{bn}\to\{0,1\} f ∧ b : { 0 , 1 } bn → { 0 , 1 } be such that for every x ⃗ 1 , … , x ⃗ b ∈ { 0 , 1 } n \vec{x}_1,\ldots,\vec{x}_b\in\{0,1\}^n x 1 , … , x b ∈ { 0 , 1 } n we have
f ∧ b ( x ⃗ 1 , … , x ⃗ b ) = ⋀ i ∈ [ b ] f ( x ⃗ i ) . f^{\wedge b}(\vec{x}_1,\ldots,\vec{x}_b)=\bigwedge_{i\in[b]}f(\vec{x}_i). f ∧ b ( x 1 , … , x b ) = i ∈ [ b ] ⋀ f ( x i ) . Then, enc ( f ∧ b ) = O ~ ( 2 n b ) \operatorname{enc}(f^{\wedge b})=\widetilde{O}(\sqrt{2^n b}) enc ( f ∧ b ) = O ( 2 n b ) . Furthermore, such an encoding can be obtained deterministically in time polynomial in 2 n 2^n 2 n and b b b .
Before proving Lemma 11, we show how it yields Theorem 2.
Proof of Theorem 2. Let f : { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^{n}\to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } be a boolean function, and suppose that A \mathcal{A} A is an ANRAM machine that evaluates f f f in time t t t with an advice string A A A consisting of m m m bits such that at most b b b bits of A A A are queried for each input. The cases m = 0 m=0 m = 0 or b = 0 b=0 b = 0 follow directly from Theorem 10 , so assume 1 ≤ b ≤ m 1\le b\le m 1 ≤ b ≤ m . Pad m m m to a power of two, increasing it by a factor of at most two. Also, if fewer than b b b bits are read, it is always possible to read additional bits without changing the computation. Thus, we assume exactly b b b bits of advice are read per input.
We construct our encoding of f f f as follows. Introduce i ⃗ 1 , … , i ⃗ b \vec{i}_{1},\ldots,\vec{i}_{b} i 1 , … , i b , where each i ⃗ j \vec{i}_{j} i j is a sequence of lg m \lg m lg m auxiliary variables that represent addresses of A A A . Furthermore, we have auxiliary variables a 1 , … , a b a_{1},\ldots,a_{b} a 1 , … , a b , representing the values of the fetched bits of advice; intuitively, we want to enforce that A [ i ⃗ j ] = a j A[\vec{i}_{j}]=a_{j} A [ i j ] = a j . Let h : { 0 , 1 } lg m + 1 → { 0 , 1 } h:\{0,1\}^{\lg m+1}\to\{0,1\} h : { 0 , 1 } l g m + 1 → { 0 , 1 } be the boolean function that takes the binary expansion of a number j ∈ [ 0 , m − 1 ] j\in[0,m-1] j ∈ [ 0 , m − 1 ] and a value v v v , and returns whether A [ j ] = v A[j]=v A [ j ] = v . Then, by invoking Lemma 11 with h h h , there is an encoding
( ψ , ( i ⃗ 1 , a 1 , … , i ⃗ b , a b ) , Y ) (\psi,(\vec{i}_{1},a_{1},\ldots,\vec{i}_{b},a_{b}),\mathcal{Y}) ( ψ , ( i 1 , a 1 , … , i b , a b ) , Y )
with O ~ ( m b ) \widetilde{O}(\sqrt{mb}) O ( mb ) clauses such that ψ \psi ψ is satisfiable for an assignment τ \tau τ to its input variables if and only if
∀ j ∈ [ b ] , A [ τ ( i ⃗ j ) ] = τ ( a j ) . \forall j\in[b],\quad A[\tau(\vec{i}_{j})]=\tau(a_{j}). ∀ j ∈ [ b ] , A [ τ ( i j )] = τ ( a j ) .
According to our definition of an ANRAM machine, A \mathcal{A} A invokes a nondeterministic RAM machine (without advice) B \mathcal{B} B on an input of length n ′ : = n + b ⋅ ( lg ( m ) + 1 ) n':=n+b\cdot(\lg(m)+1) n ′ := n + b ⋅ ( lg ( m ) + 1 ) . Let g : { 0 , 1 } n ′ → { 0 , 1 } g:\{0,1\}^{n'}\to\{0,1\} g : { 0 , 1 } n ′ → { 0 , 1 } be the boolean function computed by B \mathcal{B} B . By Theorem 10 , there is an encoding φ B \varphi_{\mathcal{B}} φ B of g g g with the n ′ n' n ′ input variables x ⃗ , i ⃗ 1 , a 1 , … , i ⃗ b , a b \vec{x},\vec{i}_{1},a_{1},\ldots,\vec{i}_{b},a_{b} x , i 1 , a 1 , … , i b , a b and using O ~ ( t + n ′ ) = O ~ ( t + b lg m ) \widetilde{O}(t+n')=\widetilde{O}(t+b\lg m) O ( t + n ′ ) = O ( t + b lg m ) clauses. Then, our encoding for f f f is simply ψ ∧ φ B \psi\wedge\varphi_{\mathcal{B}} ψ ∧ φ B , which has O ~ ( t + m b ) \widetilde{O}(t+\sqrt{mb}) O ( t + mb ) clauses. The correctness follows from the correctness of its components. Indeed, if f ( x ⃗ ) = 1 f(\vec{x})=1 f ( x ) = 1 , then there is some assignment τ \tau τ to i ⃗ 1 , … , i ⃗ b , a 1 , … , a b \vec{i}_{1},\ldots,\vec{i}_{b},a_{1},\ldots,a_{b} i 1 , … , i b , a 1 , … , a b representing the advice queries performed by A \mathcal{A} A and fed to B \mathcal{B} B , and then φ B \varphi_{\mathcal{B}} φ B is satisfiable for this assignment since B \mathcal{B} B accepts on input ( x ⃗ , τ ( i ⃗ 1 ) , τ ( a 1 ) , … , τ ( i ⃗ b ) , τ ( a b ) ) (\vec{x},\tau(\vec{i}_{1}),\tau(a_{1}),\ldots,\tau(\vec{i}_{b}),\tau(a_{b})) ( x , τ ( i 1 ) , τ ( a 1 ) , … , τ ( i b ) , τ ( a b )) . Conversely, if τ \tau τ is a satisfying assignment to ψ ∧ φ B \psi\wedge\varphi_{\mathcal{B}} ψ ∧ φ B , then by Theorem 10 , B \mathcal{B} B accepts on ( x ⃗ , τ ( i ⃗ 1 ) , τ ( a 1 ) , … , τ ( i ⃗ b ) , τ ( a b ) ) (\vec{x},\tau(\vec{i}_{1}),\tau(a_{1}),\ldots,\tau(\vec{i}_{b}),\tau(a_{b})) ( x , τ ( i 1 ) , τ ( a 1 ) , … , τ ( i b ) , τ ( a b )) . By Lemma 11, A [ τ ( i ⃗ j ) ] = τ ( a j ) A[\tau(\vec{i}_{j})]=\tau(a_{j}) A [ τ ( i j )] = τ ( a j ) , so B \mathcal{B} B accepts on ( x ⃗ , τ ( i ⃗ 1 ) , A [ τ ( i ⃗ 1 ) ] , … , τ ( i ⃗ b ) , A [ τ ( i ⃗ b ) ] ) (\vec{x},\tau(\vec{i}_{1}),A[\tau(\vec{i}_{1})],\ldots,\tau(\vec{i}_{b}),A[\tau(\vec{i}_{b})]) ( x , τ ( i 1 ) , A [ τ ( i 1 )] , … , τ ( i b ) , A [ τ ( i b )]) . Therefore, A \mathcal{A} A accepts on x ⃗ \vec{x} x and we conclude f ( x ⃗ ) = 1 f(\vec{x})=1 f ( x ) = 1 .
Finally, note that the deterministic polynomial-time construction follows directly from the deterministic polynomial-time constructions of Lemma 11 and Theorem 10 .
Encoding sparse functions
To check the advice queries, we need compact encodings of functions with few satisfying inputs. Our construction uses a compact encoding for the function AtMostOne ( x 1 , … , x n ) \operatorname{AtMostOne}(x_{1},\ldots,x_{n}) AtMostOne ( x 1 , … , x n ) , which evaluates to 1 1 1 if and only if at most one of the variables x 1 , … , x n x_{1},\ldots,x_{n} x 1 , … , x n is 1 1 1 . The following is the best known upper bound on enc ( AtMostOne ( x 1 , … , x n ) ) \operatorname{enc}(\operatorname{AtMostOne}(x_{1},\ldots,x_{n})) enc ( AtMostOne ( x 1 , … , x n )) :
Proposition 12 ([36 ] ). We have enc ( AtMostOne ( x 1 , … , x n ) ) ≤ 2 n + 2 2 n + O ~ ( n 4 ) \operatorname{enc}(\operatorname{AtMostOne}(x_{1},\ldots,x_{n}))\le2n+2\sqrt{2n}+\widetilde{O}(\sqrt[4]{n}) enc ( AtMostOne ( x 1 , … , x n )) ≤ 2 n + 2 2 n + O ( 4 n ) .
The following lemma bounds the encoding complexity of sparsely supported functions.
Lemma 13. Let f : { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^{n}\to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } , and let M : = ∣ f − 1 ( 1 ) ∣ ≥ 1 M:=|f^{-1}(1)|\ge1 M := ∣ f − 1 ( 1 ) ∣ ≥ 1 . Then,
enc ( f ) = O ( n + n M ) . \operatorname{enc}(f)=O\left(n+\sqrt{nM}\right). enc ( f ) = O ( n + n M ) .
Given the list of elements of f − 1 ( 1 ) f^{-1}(1) f − 1 ( 1 ) , an encoding attaining this bound can be constructed deterministically in time polynomial in n M nM n M .
Proof. Arrange the elements of f − 1 ( 1 ) f^{-1}(1) f − 1 ( 1 ) in an R × C R \times C R × C table T T T , where C C C is a power of two to be specified later and R : = ⌈ M / C ⌉ R := \lceil M/C \rceil R := ⌈ M / C ⌉ . Pad the table by repeating any element of f − 1 ( 1 ) f^{-1}(1) f − 1 ( 1 ) . For r ∈ [ 0 , R − 1 ] r \in[0,R-1] r ∈ [ 0 , R − 1 ] and v ∈ [ 0 , C − 1 ] v \in[0,C-1] v ∈ [ 0 , C − 1 ] , write T [ r , v ] ∈ { 0 , 1 } n T[r,v] \in\{0,1\}^{n} T [ r , v ] ∈ { 0 , 1 } n for the entry in row r r r and column v v v , and T [ r , v ] i T[r,v]_i T [ r , v ] i for its i i i th coordinate. Introduce a vector c ⃗ \vec{c} c of lg C \lg C lg C auxiliary variables to select a column, and auxiliary variables y 0 , … , y R − 1 y_0,\ldots,y_{R-1} y 0 , … , y R − 1 to select a row. Enforce exactly one true row variable using an encoding of AtMostOne ( y 0 , … , y R − 1 ) \operatorname{AtMostOne}(y_0,\ldots,y_{R-1}) AtMostOne ( y 0 , … , y R − 1 ) and the clause ⋁ r = 0 R − 1 y r \bigvee_{r=0}^{R-1} y_r ⋁ r = 0 R − 1 y r . This requires O ( R ) O(R) O ( R ) clauses by Proposition 12 . We note that the encoding from Proposition 12 can be constructed in deterministic polynomial time.
For each column v ∈ [ 0 , C − 1 ] v \in[0,C-1] v ∈ [ 0 , C − 1 ] , let D v ( c ⃗ ) D_v(\vec{c}) D v ( c ) be the clause asserting that c ⃗ \vec{c} c is not the binary representation of v v v . For every v v v and every coordinate i ∈ [ n ] i \in[n] i ∈ [ n ] , add the two clauses
D v ( c ⃗ ) ∨ x i ‾ ∨ ⋁ r T [ r , v ] i = 1 y r D_v(\vec{c}) \lor\overline{x_i} \lor\bigvee_{\substack{r\\T[r,v]_i=1}} y_r D v ( c ) ∨ x i ∨ r T [ r , v ] i = 1 ⋁ y r
D v ( c ⃗ ) ∨ x i ∨ ⋁ r T [ r , v ] i = 0 y r D_v(\vec{c}) \lor x_i \lor\bigvee_{\substack{r\\T[r,v]_i=0}} y_r D v ( c ) ∨ x i ∨ r T [ r , v ] i = 0 ⋁ y r
Fix a satisfying assignment, write x ⃗ \vec{x} x for its values on the input variables, let v ∈ [ 0 , C − 1 ] v \in[0,C-1] v ∈ [ 0 , C − 1 ] be the number represented by c ⃗ \vec{c} c , and let r r r be the unique index with y r = 1 y_r=1 y r = 1 . Then D v ( c ⃗ ) D_v(\vec{c}) D v ( c ) is false, so for every i i i , the two clauses for v v v and i i i force x i = T [ r , v ] i x_i = T[r,v]_i x i = T [ r , v ] i ; that is, x ⃗ = T [ r , v ] ∈ f − 1 ( 1 ) \vec{x} = T[r,v] \in f^{-1}(1) x = T [ r , v ] ∈ f − 1 ( 1 ) . Conversely, suppose x ⃗ ∈ f − 1 ( 1 ) \vec{x} \in f^{-1}(1) x ∈ f − 1 ( 1 ) . Since every element of f − 1 ( 1 ) f^{-1}(1) f − 1 ( 1 ) appears in the table, we have x ⃗ = T [ r , v ] \vec{x} = T[r,v] x = T [ r , v ] for some r ∈ [ 0 , R − 1 ] r \in[0,R-1] r ∈ [ 0 , R − 1 ] and v ∈ [ 0 , C − 1 ] v \in[0,C-1] v ∈ [ 0 , C − 1 ] . Set c ⃗ \vec{c} c to the binary representation of v v v , set y r = 1 y_r = 1 y r = 1 and every other row variable to 0 0 0 , and extend this assignment to the auxiliary variables of the encoding of AtMostOne ( y 0 , … , y R − 1 ) \operatorname{AtMostOne}(y_0,\ldots,y_{R-1}) AtMostOne ( y 0 , … , y R − 1 ) . If T [ r , v ] i = 1 T[r,v]_i = 1 T [ r , v ] i = 1 , the first clause for v v v and i i i contains y r y_r y r , which is true, and the second contains x i x_i x i , which is true since x i = T [ r , v ] i x_i = T[r,v]_i x i = T [ r , v ] i ; the case T [ r , v ] i = 0 T[r,v]_i = 0 T [ r , v ] i = 0 is symmetric. The clauses for every other column v ′ v' v ′ are satisfied by D v ′ ( c ⃗ ) D_{v'}(\vec{c}) D v ′ ( c ) . Thus, the encoding is satisfiable when x ⃗ ∈ f − 1 ( 1 ) \vec{x} \in f^{-1}(1) x ∈ f − 1 ( 1 ) . This completes the proof that the encoding is correct.
The number of clauses is O ( R + n C ) O(R+nC) O ( R + n C ) . If M ≥ n M \ge n M ≥ n , choose a power of two C = Θ ( M / n ) C = \Theta(\sqrt{M/n}) C = Θ ( M / n ) ; if M < n M < n M < n , choose C = 1 C = 1 C = 1 . In both cases the bound is O ( n + n M ) O(n+\sqrt{nM}) O ( n + n M ) . All table entries and clauses can be written in time polynomial in n M nM n M .
In Theorem 6, proven in § 5 , we sharpen this result to O ( n + M ( n − lg M ) ) O(n+\sqrt{M(n-\lg M)}) O ( n + M ( n − lg M ) ) clauses for 1 ≤ M ≤ 2 n − 1 1 \le M \le2^{n-1} 1 ≤ M ≤ 2 n − 1 , and prove that this is optimal in the worst case up to constant factors.
Proof of the multi-query lemma
For the proof of Lemma 11, we need to encode a kind of hash table, so in order to keep the encoding constructible in deterministic polynomial time, we will make use of explicit expanders. Intuitively, we represent a hash table by a bipartite incidence graph: left vertices are universe elements and right vertices are slots , and a form of Hall’s condition [25 ] satisfied by the considered expander will guarantee that any sufficiently small set of universe elements can be matched into distinct slots. Concretely, we will use the following lemma.
Lemma 14 (Teutsch’s expander lemma [64 Section 4] ). For every integer k ≥ 0 k \ge0 k ≥ 0 and finite universe L L L with ∣ L ∣ ≥ 2 k |L| \ge2^k ∣ L ∣ ≥ 2 k , there is a bipartite graph ( L , R , E ) (L,R,E) ( L , R , E ) with ∣ R ∣ < 2 k + 3 |R| < 2^{k+3} ∣ R ∣ < 2 k + 3 , left degree bounded by a fixed polynomial
in lg ∣ L ∣ \lg|L| lg ∣ L ∣ , and ∣ N ( S ) ∣ ≥ ∣ S ∣ |N(S)| \ge|S| ∣ N ( S ) ∣ ≥ ∣ S ∣ for every S ⊆ L S \subseteq L S ⊆ L of size at most 2 k 2^k 2 k . For each left vertex, its i i i th neighbor can be computed deterministically in time polynomial in lg ∣ L ∣ \lg|L| lg ∣ L ∣ and lg d \lg d lg d , where d d d is the maximum left degree.
Proof of Lemma 11. Let k : = ⌈ lg b ⌉ k := \lceil\lg b \rceil k := ⌈ lg b ⌉ and q : = 2 k + 3 q := 2^{k+3} q := 2 k + 3 . Apply Lemma 14 to L : = { 0 , 1 } n L := \{0,1\}^n L := { 0 , 1 } n with this k k k , and pad the right vertex set with isolated vertices until it is [ q ] [q] [ q ] . Write the resulting graph as G = ( L , [ q ] , E ) G = (L,[q],E) G = ( L , [ q ] , E ) . For r ∈ [ q ] r \in[q] r ∈ [ q ] , define g r : { 0 , 1 } n → { 0 , 1 } g_r : \{0,1\}^n \to\{0,1\} g r : { 0 , 1 } n → { 0 , 1 } by
g r ( y ⃗ ) : = f ( y ⃗ ) ∧ [ ( y ⃗ , r ) ∈ E ] . g_r(\vec{y}) := f(\vec{y}) \land[(\vec{y},r) \in E]. g r ( y ) := f ( y ) ∧ [( y , r ) ∈ E ] .
Since ∣ g r − 1 ( 1 ) ∣ ≤ deg ( r ) |g_r^{-1}(1)| \le\deg(r) ∣ g r − 1 ( 1 ) ∣ ≤ deg ( r ) , Lemma 13 gives a formula φ r \varphi_r φ r encoding g r g_r g r with O ( n + n deg ( r ) ) O(n+\sqrt{n\deg(r)}) O ( n + n deg ( r ) ) clauses. If g r − 1 ( 1 ) = ∅ g_r^{-1}(1)=\varnothing g r − 1 ( 1 ) = ∅ , take φ r \varphi_r φ r to consist of the empty clause.
Introduce vectors of auxiliary variables y ⃗ 1 , … , y ⃗ q \vec{y}_1,\ldots,\vec{y}_q y 1 , … , y q each of length n n n , and individual auxiliary variables a 1 , … , a q a_1,\ldots,a_q a 1 , … , a q , representing the contents of the slots and whether they are occupied or not, respectively. Let h h h be the boolean function defined by
h ( x ⃗ 1 , … , x ⃗ b , y ⃗ 1 , a 1 , … , y ⃗ q , a q ) : = ⋀ i ∈ [ b ] ⋁ r ∈ [ q ] ( a r ∧ [ x ⃗ i = y ⃗ r ] ) . h(\vec{x}_1,\ldots,\vec{x}_b,\vec{y}_1,a_1,\ldots,\vec{y}_q,a_q) := \bigwedge_{i\in[b]} \bigvee_{r\in[q]} (a_r \land[\vec{x}_i=\vec{y}_r]). h ( x 1 , … , x b , y 1 , a 1 , … , y q , a q ) := i ∈ [ b ] ⋀ r ∈ [ q ] ⋁ ( a r ∧ [ x i = y r ]) .
The fact that enc ( h ) = O ~ ( n b ) \operatorname{enc}(h)=\widetilde{O}(nb) enc ( h ) = O ( nb ) follows directly from Robson’s result since an NRAM can evaluate h h h in time O ~ ( n b ) \widetilde{O}(nb) O ( nb ) : for each i ∈ [ b ] i\in[b] i ∈ [ b ] guess an index r i ∈ [ q ] r_i\in[q] r i ∈ [ q ] , and check that both a r i = 1 a_{r_i}=1 a r i = 1 and x ⃗ i = y ⃗ r i \vec{x}_i=\vec{y}_{r_i} x i = y r i . Thus, by Theorem 10 , h h h has an encoding ψ \psi ψ with O ~ ( n b ) \widetilde{O}(nb) O ( nb ) clauses.
Our encoding of f ∧ b f^{\wedge b} f ∧ b is now given by
Φ : = ψ ∧ ⋀ r ∈ [ q ] ⋀ C ∈ φ r ( a r ‾ ∨ C ) , \Phi:= \psi\land\bigwedge_{r\in[q]} \bigwedge_{C\in\varphi_r} (\overline{a_r} \lor C), Φ := ψ ∧ r ∈ [ q ] ⋀ C ∈ φ r ⋀ ( a r ∨ C ) ,
and we assume that the sets of auxiliary variables internal to ψ \psi ψ and each of the φ r \varphi_r φ r are pairwise disjoint.
To prove correctness, suppose first that an assignment τ \tau τ satisfies f ( τ ( x ⃗ i ) ) = 1 f(\tau(\vec{x}_i))=1 f ( τ ( x i )) = 1 for every i ∈ [ b ] i\in[b] i ∈ [ b ] . Then, by Hall’s theorem [25 ] , the set S : = { τ ( x ⃗ i ) ∣ i ∈ [ b ] } S:=\{\tau(\vec{x}_i)\mid i\in[b]\} S := { τ ( x i ) ∣ i ∈ [ b ]} , which has size at most b ≤ 2 k b\le2^k b ≤ 2 k , admits a matching M M M in G G G saturating S S S (i.e., an injective mapping M : S → [ q ] M:S\to[q] M : S → [ q ] with ( s , M ( s ) ) ∈ E (s,M(s))\in E ( s , M ( s )) ∈ E for every s ∈ S s\in S s ∈ S ). Extend τ \tau τ by an assignment θ \theta θ such that θ ( a r ) = 1 \theta(a_r)=1 θ ( a r ) = 1 if and only if r r r is in the image of M M M , and θ ( y ⃗ r ) : = τ ( x ⃗ i ) \theta(\vec{y}_r):=\tau(\vec{x}_i) θ ( y r ) := τ ( x i ) for every i ∈ [ b ] i\in[b] i ∈ [ b ] such that M ( τ ( x ⃗ i ) ) = r M(\tau(\vec{x}_i))=r M ( τ ( x i )) = r . Then h h h evaluates to 1 1 1 under θ \theta θ , and every occupied slot r r r (i.e., θ ( a r ) = 1 \theta(a_r)=1 θ ( a r ) = 1 ) satisfies g r ( θ ( y ⃗ r ) ) = 1 g_r(\theta(\vec{y}_r))=1 g r ( θ ( y r )) = 1 . Thus, the auxiliary variables of ψ \psi ψ and the φ r \varphi_r φ r can be chosen to satisfy Φ \Phi Φ . Conversely, any satisfying assignment θ \theta θ to Φ \Phi Φ gives, for each i ∈ [ b ] i\in[b] i ∈ [ b ] , a slot r r r with θ ( a r ) = 1 \theta(a_r)=1 θ ( a r ) = 1 and θ ( x ⃗ i ) = θ ( y ⃗ r ) \theta(\vec{x}_i)=\theta(\vec{y}_r) θ ( x i ) = θ ( y r ) . The clauses ( a r ‾ ∨ C ) (\overline{a_r}\lor C) ( a r ∨ C ) for C ∈ φ r C\in\varphi_r C ∈ φ r force θ \theta θ to satisfy φ r \varphi_r φ r , which in turn implies g r ( θ ( y ⃗ r ) ) = 1 g_r(\theta(\vec{y}_r))=1 g r ( θ ( y r )) = 1 , and hence f ( θ ( x ⃗ i ) ) = 1 f(\theta(\vec{x}_i))=1 f ( θ ( x i )) = 1 .
Let us now bound the number of clauses. First,
∣ Φ ∣ = ∣ ψ ∣ + ∑ r ∈ [ q ] ∣ φ r ∣ = O ~ ( n b ) + ∑ r O ( n + n deg ( r ) ) . |\Phi|=|\psi|+\sum_{r\in[q]}|\varphi_r|=\widetilde{O}(nb)+\sum_r O\left(n+\sqrt{n\deg(r)}\right). ∣Φ∣ = ∣ ψ ∣ + r ∈ [ q ] ∑ ∣ φ r ∣ = O ( nb ) + r ∑ O ( n + n deg ( r ) ) .
Then, by the Cauchy–Schwarz inequality, and letting d : = max ℓ ∈ L deg ( ℓ ) d:=\max_{\ell\in L}\deg(\ell) d := max ℓ ∈ L deg ( ℓ ) ,
∑ r ∈ [ q ] n deg ( r ) ≤ n q ∑ r ∈ [ q ] deg ( r ) ≤ n q 2 n d . \sum_{r\in[q]}\sqrt{n\deg(r)}\le\sqrt{nq\sum_{r\in[q]}\deg(r)}\le\sqrt{nq2^n d}. r ∈ [ q ] ∑ n deg ( r ) ≤ n q r ∈ [ q ] ∑ deg ( r ) ≤ n q 2 n d .
Therefore, the total number of clauses is
O ~ ( n b ) + O ( n q + n q 2 n d ) = O ~ ( 2 n b ) , \widetilde{O}(nb) + O(nq + \sqrt{nq2^{n}d}) = \widetilde{O}(\sqrt{2^{n}b}), O ( nb ) + O ( n q + n q 2 n d ) = O ( 2 n b ) ,
since q = O ( b ) q = O(b) q = O ( b ) , b ≤ 2 n b \le2^n b ≤ 2 n , and d = poly ( n ) d = \operatorname{poly}(n) d = poly ( n ) . Finally, we can explicitly construct G G G in time polynomial in 2 n 2^n 2 n by Lemma 14 , and then enumerate the satisfying assignments of every g r g_r g r within the same time bound. Thus, each φ r \varphi_r φ r can be computed in deterministic time poly ( 2 n ) \operatorname{poly}(2^n) poly ( 2 n ) by Lemma 13 , and ψ \psi ψ can be computed deterministically in time poly ( 2 n ) \operatorname{poly}(2^n) poly ( 2 n ) by Theorem 10 . Thus, Φ \Phi Φ can be computed deterministically in time poly ( 2 n ) \operatorname{poly}(2^n) poly ( 2 n ) .
Encoding k k k -CNF Functions
In this section, we prove Theorems 4 and 5. Both theorems reduce to compactly encoding I S G \mathrm{IS}_G IS G , where G G G is a bipartite graph. We prove Theorem 4 by showing that there is a deterministic data structure for computing I S G \mathrm{IS}_G IS G that uses O ( n 2 ) O(n^2) O ( n 2 ) bits of memory whose query time is n 2 / 2 Ω ( lg n ) n^2/2^{\Omega(\sqrt{\lg n})} n 2 / 2 Ω ( l g n ) . This is a derandomization of a data structure of Larsen and Williams [44 ] , which we give in § 4.1 . Together with Theorem 2, this proves Theorem 4. For Theorem 5, we encode sparse graphs using biclique partitions in § 4.5 , and bipartite graphs with small bipartite independence number using hash tables in Section 4.4. In § 4.7 , we decompose an arbitrary bipartite graph into pieces to which one of these two encodings applies. We conclude with counting lower bounds in § 4.8 .
Derandomizing the Larsen–Williams data structure
We adapt the strategy of Larsen and Williams [44 ] , replacing its randomized orthogonal-vector subroutine from Abboud, Williams, and Yu [4 ] by the deterministic algorithm of Chan and Williams [14 ] . Following Larsen and Williams, we formulate our goal as preprocessing a boolean matrix A A A to compute queries of the form u T A v u^T A v u T A v over the boolean semiring, since this is equivalent to querying I S G \mathrm{IS}_G IS G for a bipartite graph G G G .
Theorem 15. For every boolean matrix A ∈ { 0 , 1 } n × n A \in\{0,1\}^{n \times n} A ∈ { 0 , 1 } n × n , there is a data structure using O ( n 2 ) O(n^2) O ( n 2 ) bits of memory for which, given u , v ∈ { 0 , 1 } n u,v \in\{0,1\}^n u , v ∈ { 0 , 1 } n , one can deterministically compute u T A v u^T A v u T A v over the boolean semiring in time n 2 / 2 Ω ( lg n ) n^2/2^{\Omega(\sqrt{\lg n})} n 2 / 2 Ω ( l g n ) .
For U , V ⊆ [ n ] U,V \subseteq[n] U , V ⊆ [ n ] , we use notation A { U × V } : = { ( i , j ) ∈ U × V : A ( i , j ) = 1 } A\{U \times V\} := \{(i,j) \in U \times V : A(i,j) = 1\} A { U × V } := {( i , j ) ∈ U × V : A ( i , j ) = 1 } . If U U U and V V V are the supports of u u u and v v v , then u T A v = 1 u^T A v = 1 u T A v = 1 if and only if A { U × V } ≠ ∅ A\{U \times V\} \ne\varnothing A { U × V } = ∅ .
Preprocessing
Call a rectangle U × V U \times V U × V empty if A { U × V } = ∅ A\{U \times V\} = \varnothing A { U × V } = ∅ . Given a list L L L of rectangles, let
C ( L ) : = [ n 2 ] ∖ ⋃ ( U , V ) ∈ L ( U × V ) . C(L) := [n^2] \setminus\bigcup_{(U,V)\in L}(U \times V). C ( L ) := [ n 2 ] ∖ ( U , V ) ∈ L ⋃ ( U × V ) .
Lemma 16. For every R ≥ 1 R \ge1 R ≥ 1 , there is a list L L L of at most R R R empty rectangles such that every empty rectangle U × V U \times V U × V satisfies
∣ ( U × V ) ∩ C ( L ) ∣ < n 2 / R . |(U \times V) \cap C(L)| < n^2/R. ∣ ( U × V ) ∩ C ( L ) ∣ < n 2 / R .
Proof. Start with L = ∅ L = \emptyset L = ∅ . While some empty rectangle has at least n 2 / R n^2/R n 2 / R entries in C ( L ) C(L) C ( L ) , add it to L L L . Each addition removes at least n 2 / R n^2/R n 2 / R entries from C ( L ) C(L) C ( L ) , so there are at most R R R additions. □ \square □
Choose constants ε , α > 0 \varepsilon, \alpha> 0 ε , α > 0 with 3 α < ε 3\alpha< \varepsilon 3 α < ε as in Lemma 17 below, and set R : = 2 ε lg n R := 2^{\varepsilon\sqrt{\lg n}} R := 2 ε l g n . Construct L L L as above, and enumerate it as ( U 1 , V 1 ) , … , ( U ∣ L ∣ , V ∣ L ∣ ) (U_1,V_1),\ldots,(U_{|L|},V_{|L|}) ( U 1 , V 1 ) , … , ( U ∣ L ∣ , V ∣ L ∣ ) . Store A A A as a bit matrix, and for every row i i i and column j j j , store vectors a i , b j ∈ { 0 , 1 } ∣ L ∣ a_i,b_j \in\{0,1\}^{|L|} a i , b j ∈ { 0 , 1 } ∣ L ∣ such that for every r ∈ [ ∣ L ∣ ] r \in[|L|] r ∈ [ ∣ L ∣ ] ,
a i , r : = { 1 if i ∈ U r , 0 otherwise, b j , r : = { 1 if j ∈ V r , 0 otherwise. a_{i,r}:=
\begin{cases}
1 & \text{if } i \in U_r,\\
0 & \text{otherwise,}
\end{cases}
\qquad
b_{j,r}:=
\begin{cases}
1 & \text{if } j \in V_r,\\
0 & \text{otherwise.}
\end{cases} a i , r := { 1 0 if i ∈ U r , otherwise, b j , r := { 1 0 if j ∈ V r , otherwise.
Note that these vectors satisfy
( i , j ) ∈ C ( L ) ⟺ ⟨ a i , b j ⟩ = 0. (1) (i,j) \in C(L) \iff\langle a_i,b_j\rangle= 0. \tag*{(1)} ( i , j ) ∈ C ( L ) ⟺ ⟨ a i , b j ⟩ = 0. (1)
Furthermore, the total space used is O ( n 2 ) O(n^2) O ( n 2 ) bits.
Answering queries
For a query ( U , V ) (U,V) ( U , V ) , let W : = ( U × V ) ∩ C ( L ) W := (U \times V) \cap C(L) W := ( U × V ) ∩ C ( L ) . Since the rectangles of L L L are empty, every 1-entry of A A A lies in C ( L ) C(L) C ( L ) . Thus, A { U × V } ⊆ W A\{U \times V\} \subseteq W A { U × V } ⊆ W , so our goal is to compute whether W W W contains a 1. We proceed as follows.
Compute ∣ W ∣ |W| ∣ W ∣ as described below. If ∣ W ∣ ≥ n 2 / R |W| \ge n^2/R ∣ W ∣ ≥ n 2 / R , return 1.
Otherwise, determine as described below whether A ( i , j ) = 1 A(i,j) = 1 A ( i , j ) = 1 for some ( i , j ) ∈ W (i,j) \in W ( i , j ) ∈ W , and return the result.
If U × V U \times V U × V is empty, then ∣ W ∣ < n 2 / R |W| < n^2/R ∣ W ∣ < n 2 / R by Lemma 16, so a return in step 1 is correct. Step 2 is correct because A { U × V } ⊆ W A\{U \times V\} \subseteq W A { U × V } ⊆ W . Moreover, whenever step 2 is executed, we have ∣ W ∣ < n 2 / R |W| < n^2/R ∣ W ∣ < n 2 / R . It remains to show that both steps of the algorithm can be computed in time n 2 / 2 Ω ( lg n ) n^2/2^{\Omega(\sqrt{\lg n})} n 2 / 2 Ω ( l g n ) .
Counting the uncovered entries
By (1), W W W consists of the pairs ( i , j ) ∈ U × V (i,j) \in U \times V ( i , j ) ∈ U × V with ⟨ a i , b j ⟩ = 0 \langle a_i,b_j\rangle= 0 ⟨ a i , b j ⟩ = 0 . Thus, both steps of the query algorithm amount to an orthogonal-vectors problem on the vectors a i a_i a i for i ∈ U i \in U i ∈ U and b j b_j b j for j ∈ V j \in V j ∈ V , which we solve with the deterministic algorithm of Chan and Williams [14 ] ; Larsen and Williams [44 ] used essentially the same subroutine, with the randomized algorithm of Abboud, Williams, and Yu [4 ] instead. Rather than only the total number of orthogonal pairs, we need the number of orthogonal pairs between every pair of blocks of partitions of U U U and V V V .
Lemma 17. There are constants ε , α > 0 \varepsilon,\alpha> 0 ε , α > 0 with 3 α < ε 3\alpha< \varepsilon 3 α < ε for which the following holds. Let β : = ⌊ 2 α lg n ⌋ \beta:= \left\lfloor2^{\alpha\sqrt{\lg n}}\right\rfloor β := ⌊ 2 α l g n ⌋ . Let x 1 , … , x n x_1,\ldots,x_n x 1 , … , x n and y 1 , … , y n y_1,\ldots,y_n y 1 , … , y n be boolean vectors of dimension at most 2 ε lg n 2^{\varepsilon\sqrt{\lg n}} 2 ε l g n , and let I 1 , … , I p I_1,\ldots,I_p I 1 , … , I p and J 1 , … , J q J_1,\ldots,J_q J 1 , … , J q be subsets of [ n ] [n] [ n ] , each of size at most β \beta β , with p , q ≤ ⌈ n / β ⌉ p,q \le\lceil n/\beta\rceil p , q ≤ ⌈ n / β ⌉ . Then all counts
Z h , ℓ : = ∣ { ( i , j ) ∈ I h × J ℓ : ⟨ x i , y j ⟩ = 0 } ∣ Z_{h,\ell} := \left|\{(i,j) \in I_h \times J_\ell: \langle x_i,y_j\rangle= 0\}\right| Z h , ℓ := ∣ {( i , j ) ∈ I h × J ℓ : ⟨ x i , y j ⟩ = 0 } ∣ can be computed deterministically in time O ~ ( n 2 / 2 α lg n ) \widetilde{O}(n^2/2^{\alpha\sqrt{\lg n}}) O ( n 2 / 2 α l g n ) .
Proof. This is a minor modification of the algorithm of Chan and Williams [14 Theorem 1.3] for counting orthogonal pairs. Given N N N vectors of dimension c lg N c\lg N c lg N , where c ≤ 2 δ lg N c \le2^{\delta\sqrt{\lg N}} c ≤ 2 δ l g N for a sufficiently small constant δ > 0 \delta> 0 δ > 0 , they deterministically count the orthogonal pairs of distinct vectors. To do so, they partition the vectors into blocks of at most s : = N 1 / ( k lg c ) s := N^{1/(k\lg c)} s := N 1/ ( k l g c ) vectors each, for a sufficiently large constant k k k , and construct a polynomial whose value on the vectors of two blocks determines the number of orthogonal pairs between them. They evaluate this polynomial on all pairs of blocks at once with a single rectangular matrix multiplication, and add up the resulting counts. We change this in two ways. First, the vectors come from two collections: one factor of the matrix multiplication is built from the blocks I h I_h I h of the vectors x i x_i x i , and the other from the blocks J ℓ J_\ell J ℓ of the vectors y j y_j y j . Second, we output the count for every pair of blocks instead of their sum. For sufficiently small ε \varepsilon ε and α : = ε / 4 \alpha:= \varepsilon/4 α := ε /4 , our vectors have dimension in their range and our blocks have at most s s s elements, so the same analysis computes all counts Z h , ℓ Z_{h,\ell} Z h , ℓ in time O ~ ( n 2 / β 2 ) \widetilde{O}(n^2/\beta^2) O ( n 2 / β 2 ) .
Lemma 18. Both steps of the query algorithm can be carried out deterministically in time n 2 / 2 Ω ( lg n ) n^2/2^{\Omega(\sqrt{\lg n})} n 2 / 2 Ω ( l g n ) .
Proof. Partition U U U into p : = ⌈ ∣ U ∣ / β ⌉ p := \lceil|U|/\beta\rceil p := ⌈ ∣ U ∣/ β ⌉ sets I 1 , … , I p I_1,\ldots,I_p I 1 , … , I p and V V V into q : = ⌈ ∣ V ∣ / β ⌉ q := \lceil|V|/\beta\rceil q := ⌈ ∣ V ∣/ β ⌉ sets J 1 , … , J q J_1,\ldots,J_q J 1 , … , J q , each of size at most β = ⌊ 2 α lg n ⌋ \beta= \lfloor2^{\alpha\sqrt{\lg n}}\rfloor β = ⌊ 2 α l g n ⌋ . Apply Lemma 17 with x i : = a i x_i := a_i x i := a i and y j : = b j y_j := b_j y j := b j ; this is possible because these vectors have dimension ∣ L ∣ ≤ R = 2 ε lg n |L| \le R = 2^{\varepsilon\sqrt{\lg n}} ∣ L ∣ ≤ R = 2 ε l g n . By (1), its count Z h , ℓ Z_{h,\ell} Z h , ℓ is exactly ∣ W ∩ ( I h × J ℓ ) ∣ |W \cap(I_h \times J_\ell)| ∣ W ∩ ( I h × J ℓ ) ∣ , so ∣ W ∣ = ∑ h , ℓ Z h , ℓ |W| = \sum_{h,\ell} Z_{h,\ell} ∣ W ∣ = ∑ h , ℓ Z h , ℓ . This gives step 1 in time O ~ ( n 2 / 2 α lg n ) \widetilde{O}(n^2/2^{\alpha\sqrt{\lg n}}) O ( n 2 / 2 α l g n ) .
For step 2, check all entries of every block pair I h × J ℓ I_h \times J_\ell I h × J ℓ with positive count, and return 1 precisely when some entry satisfies A ( i , j ) = 1 A(i,j) = 1 A ( i , j ) = 1 . The block products are pairwise disjoint, so at most ∣ W ∣ |W| ∣ W ∣ of them have positive count. Since step 2 is executed only if ∣ W ∣ < n 2 / R |W| < n^2/R ∣ W ∣ < n 2 / R , the number of entries checked is at most
∣ W ∣ β 2 < n 2 2 ( ε − 2 α ) lg n ≤ n 2 2 α lg n . |W|\beta^2 < \frac{n^2}{2^{(\varepsilon-2\alpha)\sqrt{\lg n}}} \le\frac{n^2}{2^{\alpha\sqrt{\lg n}}}. ∣ W ∣ β 2 < 2 ( ε − 2 α ) l g n n 2 ≤ 2 α l g n n 2 .
Proof of Theorem 15 . The preprocessing uses O ( n 2 ) O(n^2) O ( n 2 ) bits and is deterministic. The query algorithm is correct by § 4.2 , and it runs in time n 2 / 2 Ω ( lg n ) n^2/2^{\Omega(\sqrt{\lg n})} n 2 / 2 Ω ( l g n ) by Lemma 18 .
Encoding arbitrary k k k -CNF functions
We first reduce 2-CNF functions to independent-set constraints of bipartite graphs.
Lemma 19. Let φ \varphi φ be a 2-CNF formula on n ≥ 1 n \ge1 n ≥ 1 variables. One can construct in polynomial time a bipartite graph G G G with 2 n 2n 2 n vertices on each side with the following property: given an encoding of I S G \mathrm{IS}_G IS G with T T T clauses, one can construct in polynomial time an encoding of the function defined by φ \varphi φ with at most T + 4 n T + 4n T + 4 n clauses.
Proof. If φ \varphi φ contains the empty clause, then it defines the constant-0 function, and the empty clause is an encoding of it; in this case, G G G can be arbitrary. Otherwise, let φ ′ \varphi' φ ′ be the 2-CNF formula obtained from φ \varphi φ by replacing every positive literal x i x_i x i by y i ‾ \overline{y_i} y i , where y i y_i y i is a fresh variable. Then, φ ′ \varphi' φ ′ is an antitone 2-CNF formula on the 2 n 2n 2 n variables x 1 , … , x n , y 1 , … , y n x_1,\ldots,x_n,y_1,\ldots,y_n x 1 , … , x n , y 1 , … , y n , meaning that all of its literals are negative. Thus, each clause of φ ′ \varphi' φ ′ is either a unit clause or a clause a ‾ ∨ b ‾ \overline{a} \vee\overline{b} a ∨ b with a ≠ b a \ne b a = b . Let U U U be the set of unit clauses of φ ′ \varphi' φ ′ , so ∣ U ∣ ≤ 2 n |U| \le2n ∣ U ∣ ≤ 2 n , and let F F F be the graph on these 2 n 2n 2 n variables with an edge { a , b } \{a,b\} { a , b } for each clause a ‾ ∨ b ‾ \overline{a} \vee\overline{b} a ∨ b of φ ′ \varphi' φ ′ . Then, φ ′ \varphi' φ ′ is equivalent to I S F ∧ ⋀ c ∈ U c \mathrm{IS}_F \wedge\bigwedge_{c\in U} c IS F ∧ ⋀ c ∈ U c .
Since F F F need not be bipartite, let G G G be the bipartite graph with a left vertex a L a^L a L and a right vertex a R a^R a R for each vertex a a a of F F F , and with the edges { a L , b R } \{a^L,b^R\} { a L , b R } and { b L , a R } \{b^L,a^R\} { b L , a R } for each edge { a , b } \{a,b\} { a , b } of F F F . A set X X X of vertices is independent in F F F if and only if { a L ∣ a ∈ X } ∪ { a R ∣ a ∈ X } \{a^L \mid a \in X\} \cup\{a^R \mid a \in X\} { a L ∣ a ∈ X } ∪ { a R ∣ a ∈ X } is independent in G G G . Thus, given an encoding of I S G \mathrm{IS}_{G} IS G with T T T clauses, substituting the variable a a a for both input variables a L a^{L} a L and a R a^{R} a R gives an encoding ψ ′ \psi' ψ ′ of I S F \mathrm{IS}_{F} IS F with T T T clauses. Finally,
ψ : = ψ ′ ∧ ⋀ C ∈ U C ∧ ⋀ i ∈ [ n ] ( x i ∨ y i ) ∧ ⋀ i ∈ [ n ] ( x i ‾ ∨ y i ‾ ) , \psi:= \psi' \land\bigwedge_{C\in\mathcal{U}} C \land\bigwedge_{i\in[n]}(x_i \lor y_i) \land\bigwedge_{i\in[n]}(\overline{x_i} \lor\overline{y_i}), ψ := ψ ′ ∧ C ∈ U ⋀ C ∧ i ∈ [ n ] ⋀ ( x i ∨ y i ) ∧ i ∈ [ n ] ⋀ ( x i ∨ y i ) ,
with y 1 , … , y n y_1,\ldots,y_n y 1 , … , y n regarded as auxiliary variables, is an encoding of φ \varphi φ with at most T + 4 n T+4n T + 4 n clauses. Indeed, the last two conjunctions force y i = x i ‾ y_i=\overline{x_i} y i = x i for every i i i , and under this substitution, φ ′ \varphi' φ ′ is equivalent to φ \varphi φ . All of these steps take polynomial time.
Next, we lift encodings of k k k -CNF functions to ( k + 1 ) (k+1) ( k + 1 ) -CNF functions. This costs a factor of 2 n 2n 2 n in the number of clauses, and hence preserves any improvement factor over n k n^k n k .
Lemma 20. Let k ≥ 2 k\ge2 k ≥ 2 . Suppose that every k k k -CNF function on n ≥ 1 n\ge1 n ≥ 1 variables has an encoding with at most f ( n ) f(n) f ( n ) clauses for some f : N → N f:\mathbb{N}\to\mathbb{N} f : N → N . Then, every ( k + 1 ) (k+1) ( k + 1 ) -CNF function on n n n variables has an encoding with at most 2 n ⋅ f ( n ) 2n\cdot f(n) 2 n ⋅ f ( n ) clauses. Moreover, this lifting is constructive: if encodings of k k k -CNF functions with at most f ( n ) f(n) f ( n ) clauses can be computed from k k k -CNF formulas in polynomial time, then encodings of ( k + 1 ) (k+1) ( k + 1 ) -CNF functions with at most 2 n ⋅ f ( n ) 2n\cdot f(n) 2 n ⋅ f ( n ) clauses can be computed from ( k + 1 ) (k+1) ( k + 1 ) -CNF formulas in polynomial time.
Proof. Let φ \varphi φ be a ( k + 1 ) (k+1) ( k + 1 ) -CNF formula on the variables x 1 , … , x n x_1,\ldots,x_n x 1 , … , x n . If φ \varphi φ contains the empty clause, then it defines the constant-0 0 0 function, and the empty clause is an encoding of it. This encoding has at most 2 n ⋅ f ( n ) 2n\cdot f(n) 2 n ⋅ f ( n ) clauses, since f ( n ) ≥ 1 f(n)\ge1 f ( n ) ≥ 1 .
Otherwise, given a literal ℓ \ell ℓ , let φ ℓ : = { C ∣ ( ℓ ∨ C ) ∈ φ } \varphi_{\ell}:=\{C\mid(\ell\lor C)\in\varphi\} φ ℓ := { C ∣ ( ℓ ∨ C ) ∈ φ } , which is a k k k -CNF formula on x 1 , … , x n x_1,\ldots,x_n x 1 , … , x n . Every clause of φ \varphi φ is nonempty, so it has the form ℓ ∨ C \ell\lor C ℓ ∨ C for some literal ℓ \ell ℓ , and then C ∈ φ ℓ C\in\varphi_{\ell} C ∈ φ ℓ . Conversely, ℓ ∨ C \ell\lor C ℓ ∨ C is a clause of φ \varphi φ for every C ∈ φ ℓ C\in\varphi_{\ell} C ∈ φ ℓ . Thus,
φ = ⋀ i ∈ [ n ] ( x i ∨ φ x i ) ∧ ⋀ i ∈ [ n ] ( x i ‾ ∨ φ x i ‾ ) , \varphi=\bigwedge_{i\in[n]}(x_i\lor\varphi_{x_i})\land\bigwedge_{i\in[n]}(\overline{x_i}\lor\varphi_{\overline{x_i}}), φ = i ∈ [ n ] ⋀ ( x i ∨ φ x i ) ∧ i ∈ [ n ] ⋀ ( x i ∨ φ x i ) ,
where ℓ ∨ φ ℓ \ell\lor\varphi_{\ell} ℓ ∨ φ ℓ denotes the CNF formula ⋀ C ∈ φ ℓ ( ℓ ∨ C ) \bigwedge_{C\in\varphi_{\ell}}(\ell\lor C) ⋀ C ∈ φ ℓ ( ℓ ∨ C ) . By hypothesis, the function defined by each φ ℓ \varphi_{\ell} φ ℓ has an encoding ψ ℓ \psi_{\ell} ψ ℓ with at most f ( n ) f(n) f ( n ) clauses, and we choose these encodings with pairwise disjoint auxiliary variables. Let
ψ : = ⋀ i ∈ [ n ] ( x i ∨ ψ x i ) ∧ ⋀ i ∈ [ n ] ( x i ‾ ∨ ψ x i ‾ ) . \psi:=\bigwedge_{i\in[n]}(x_i\lor\psi_{x_i})\land\bigwedge_{i\in[n]}(\overline{x_i}\lor\psi_{\overline{x_i}}). ψ := i ∈ [ n ] ⋀ ( x i ∨ ψ x i ) ∧ i ∈ [ n ] ⋀ ( x i ∨ ψ x i ) .
Then, ψ \psi ψ has at most 2 n ⋅ f ( n ) 2n\cdot f(n) 2 n ⋅ f ( n ) clauses. It is not hard to see that ψ \psi ψ is an encoding of the function defined by φ \varphi φ . Furthermore, if the encodings ψ ℓ \psi_{\ell} ψ ℓ can be computed in polynomial time, then so can ψ \psi ψ .
We can now prove Theorem 4.
Theorem 4. If f : { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^{n}\to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } is a k k k -CNF function for some k ≥ 2 k\ge2 k ≥ 2 , then enc ( f ) = n k 2 Ω k ( lg n ) \operatorname{enc}(f)=\dfrac{n^{k}}{2^{\Omega_k(\sqrt{\lg n})}} enc ( f ) = 2 Ω k ( l g n ) n k .
Proof. First, let G G G be a bipartite graph with s s s vertices on each side, and let A ∈ { 0 , 1 } s × s A\in\{0,1\}^{s\times s} A ∈ { 0 , 1 } s × s be its biadjacency matrix. Writing u , v ∈ { 0 , 1 } s u,v\in\{0,1\}^{s} u , v ∈ { 0 , 1 } s for the sets of vertices on the two sides, we have
I S G ( u , v ) = 1 ⟺ u T A v = 0. \mathrm{IS}_{G}(u,v)=1\Longleftrightarrow u^{T}Av=0. IS G ( u , v ) = 1 ⟺ u T A v = 0.
Theorem 15 therefore evaluates I S G \mathrm{IS}_{G} IS G from m = O ( s 2 ) m=O(s^2) m = O ( s 2 ) advice bits in time
t = s 2 2 Ω ( lg s ) . (2) t=\frac{s^2}{2^{\Omega(\sqrt{\lg s})}}. \tag*{(2)} t = 2 Ω ( l g s ) s 2 . (2)
At most t t t distinct advice bits are read. Applying Theorem 2 with b ≤ t b \le t b ≤ t gives
enc ( I S G ) = O ~ ( t + m t ) = s 2 2 Ω ( lg s ) . \operatorname{enc}(\mathrm{IS}_{G}) = \widetilde{O}(t+\sqrt{mt}) = \frac{s^{2}}{2^{\Omega(\sqrt{\lg s})}}. enc ( IS G ) = O ( t + m t ) = 2 Ω ( l g s ) s 2 .
Now let f f f be a 2-CNF function on n n n variables. Lemma 19 reduces f f f to I S G \mathrm{IS}_{G} IS G for a bipartite graph with s = 2 n s=2n s = 2 n vertices on each side, at the cost of at most 4 n 4n 4 n additional clauses, which gives the claimed bound for k = 2 k=2 k = 2 . The bound for each fixed k ≥ 3 k \ge3 k ≥ 3 now follows from Lemma 20 .
Encoding sparse graphs
We first state Feder and Motwani’s result about biclique partitions [19 ] , which is essentially a restatement of a result of Nechiporuk [48 ] . Given a graph G G G , a biclique partition is a set { B 1 , … , B k } \{B_{1},\ldots,B_{k}\} { B 1 , … , B k } , where each B i B_{i} B i is a complete bipartite subgraph of G G G , and E ( G ) = ⋃ i = 1 k E ( B i ) E(G)=\bigcup_{i=1}^{k}E(B_{i}) E ( G ) = ⋃ i = 1 k E ( B i ) . The weight of such a partition is ∑ i = 1 k ∣ V ( B i ) ∣ \sum_{i=1}^{k}|V(B_{i})| ∑ i = 1 k ∣ V ( B i ) ∣ . The edge density of a graph with n n n vertices and m m m edges is m / ( n 2 ) m/\binom{n}{2} m / ( 2 n ) .
Lemma 21. (Feder and Motwani [19 ] ). Let G = ( V , E ) G=(V,E) G = ( V , E ) be a graph with n ≥ 2 n\ge2 n ≥ 2 vertices and edge density γ > 0 \gamma>0 γ > 0 . Then, G G G has a biclique partition of weight O ( γ n 2 lg ( 2 / γ ) lg n ) O\left(\frac{\gamma n^{2}\lg(2/\gamma)}{\lg n}\right) O ( l g n γ n 2 l g ( 2/ γ ) ) . Moreover, such a biclique partition can be constructed deterministically in time polynomial in n n n .
Using this result, we can efficiently encode the independent set constraint for sparse graphs.
Lemma 22. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a graph with n ≥ 2 n\ge2 n ≥ 2 vertices and edge density at most γ \gamma γ , where 0 < γ ≤ 1 / 2 0<\gamma\le1/2 0 < γ ≤ 1/2 . Then, enc ( I S G ) = O ( γ n 2 lg ( γ − 1 ) lg n ) \operatorname{enc}(\mathrm{IS}_{G})=O\left(\frac{\gamma n^{2}\lg(\gamma^{-1})}{\lg n}\right) enc ( IS G ) = O ( l g n γ n 2 l g ( γ − 1 ) ) . Moreover, such an encoding can be constructed deterministically in time polynomial in n n n .
Proof. Let γ ′ \gamma' γ ′ be the edge density of G G G . If γ ′ = 0 \gamma'=0 γ ′ = 0 , then the empty formula is an encoding. Otherwise, by Lemma 21 , G G G has a biclique partition B = { B 1 , … , B k } \mathcal{B}=\{B_{1},\ldots,B_{k}\} B = { B 1 , … , B k } of weight O ( γ ′ n 2 lg ( 2 / γ ′ ) lg n ) O\left(\frac{\gamma'n^{2}\lg(2/\gamma')}{\lg n}\right) O ( l g n γ ′ n 2 l g ( 2/ γ ′ ) ) , which can be constructed in polynomial time. Since the function x ↦ x lg ( 2 / x ) x\mapsto x\lg(2/x) x ↦ x lg ( 2/ x ) is increasing on ( 0 , 1 / 2 ] (0,1/2] ( 0 , 1/2 ] and lg ( 2 / γ ) ≤ 2 lg ( γ − 1 ) \lg(2/\gamma)\le2\lg(\gamma^{-1}) lg ( 2/ γ ) ≤ 2 lg ( γ − 1 ) , this weight is O ( γ n 2 lg ( γ − 1 ) lg n ) O\left(\frac{\gamma n^{2}\lg(\gamma^{-1})}{\lg n}\right) O ( l g n γ n 2 l g ( γ − 1 ) ) . We construct an encoding as follows. For each biclique B i = ( X i , Y i ) B_{i}=(X_{i},Y_{i}) B i = ( X i , Y i ) , introduce an auxiliary variable z i z_{i} z i . Then, for each such biclique, include the following clauses in the encoding:
⋀ x ∈ X i ( x ‾ ∨ z i ) ∧ ⋀ y ∈ Y i ( z i ‾ ∨ y ‾ ) . \bigwedge_{x\in X_{i}}(\overline{x}\lor z_{i})\land\bigwedge_{y\in Y_{i}}(\overline{z_{i}}\lor\overline{y}). x ∈ X i ⋀ ( x ∨ z i ) ∧ y ∈ Y i ⋀ ( z i ∨ y ) .
The total number of clauses in the encoding is
∑ i ∈ [ k ] ( ∣ X i ∣ + ∣ Y i ∣ ) = O ( γ n 2 lg ( γ − 1 ) lg n ) . \sum_{i\in[k]}(|X_{i}|+|Y_{i}|)=O\left(\frac{\gamma n^{2}\lg(\gamma^{-1})}{\lg n}\right). i ∈ [ k ] ∑ ( ∣ X i ∣ + ∣ Y i ∣ ) = O ( lg n γ n 2 lg ( γ − 1 ) ) .
Now, we prove that the encoding is correct. Let X ⊆ V X\subseteq V X ⊆ V be an independent set. For each i ∈ [ k ] i\in[k] i ∈ [ k ] , set z i z_{i} z i to true if and only if X ∩ X i ≠ ∅ X\cap X_{i}\ne\varnothing X ∩ X i = ∅ . Then, every clause of the form x ‾ ∨ z i \overline{x}\lor z_{i} x ∨ z i is satisfied. Also, if z i z_{i} z i is true, then X ∩ Y i = ∅ X\cap Y_{i}=\varnothing X ∩ Y i = ∅ , since X X X is independent and every vertex of X i X_{i} X i is adjacent to every vertex of Y i Y_{i} Y i . Thus, every clause of the form z i ‾ ∨ y ‾ \overline{z_{i}}\lor\overline{y} z i ∨ y is satisfied. Therefore, the encoding is satisfiable.
On the other hand, suppose that X ⊆ V X\subseteq V X ⊆ V is not independent. Let x 1 , x 2 ∈ X x_{1},x_{2}\in X x 1 , x 2 ∈ X be such that { x 1 , x 2 } ∈ E \{x_{1},x_{2}\}\in E { x 1 , x 2 } ∈ E . Then, { x 1 , x 2 } \{x_{1},x_{2}\} { x 1 , x 2 } is covered by some biclique B i B_{i} B i . Thus, our encoding either contains the pair of clauses x 1 ‾ ∨ z i \overline{x_{1}}\lor z_{i} x 1 ∨ z i and z i ‾ ∨ x 2 ‾ \overline{z_{i}}\lor\overline{x_{2}} z i ∨ x 2 or the pair of clauses x 2 ‾ ∨ z i \overline{x_{2}}\lor z_{i} x 2 ∨ z i and z i ‾ ∨ x 1 ‾ \overline{z_{i}}\lor\overline{x_{1}} z i ∨ x 1 . In either case, the clauses imply the falsified clause x 1 ‾ ∨ x 2 ‾ \overline{x_{1}}\lor\overline{x_{2}} x 1 ∨ x 2 . Therefore, the encoding is unsatisfiable.
Encoding bipartite graphs with small α b \alpha_{\mathrm{b}} α b
Given a bipartite graph G = ( V 1 ⊔ V 2 , E ) G = (V_1 \sqcup V_2, E) G = ( V 1 ⊔ V 2 , E ) , its bipartite independence number , denoted α b ( G ) \alpha_{\mathrm{b}}(G) α b ( G ) , is the largest k k k such that G G G has an independent set S S S with ∣ S ∩ V 1 ∣ = ∣ S ∩ V 2 ∣ = k |S \cap V_1| = |S \cap V_2| = k ∣ S ∩ V 1 ∣ = ∣ S ∩ V 2 ∣ = k .
Hash table lemma
Our encoding of the independent set constraint for graphs with small α b \alpha_{\mathrm{b}} α b , Lemma 24 , requires a hash table construction. As in § 3 , we formalize the hash table as a bipartite graph, whose left side represents the universe of elements that can be hashed and whose right side represents the slots of the table, and we use Teutsch’s explicit expander (Lemma 14 ). For our application, we need a uniform bound on the degree of vertices on the right side. We achieve this from Lemma 14 by splitting vertices on the right side whose degree is too high.
Lemma 23. There is a function n ↦ d n n \mapsto d_n n ↦ d n with 1 ≤ d n = ( lg n ) O ( 1 ) 1 \le d_n = (\lg n)^{O(1)} 1 ≤ d n = ( lg n ) O ( 1 ) such that the following holds. Let L L L be a set of size n ≥ 1 n \ge1 n ≥ 1 , and let r r r be an integer with 1 ≤ r ≤ n 1 \le r \le n 1 ≤ r ≤ n . Then, there is a bipartite graph ( L ⊔ R , E ) (L \sqcup R, E) ( L ⊔ R , E ) such that (i) ∣ R ∣ ≤ 17 r |R| \le17r ∣ R ∣ ≤ 17 r , (ii) for every S ⊆ L S \subseteq L S ⊆ L with ∣ S ∣ ≤ r |S| \le r ∣ S ∣ ≤ r , there is a matching that saturates S S S , and (iii) every vertex of L L L has degree at most d n d_n d n , and every vertex of R R R has degree at most ⌈ n d n / r ⌉ \lceil nd_n/r\rceil ⌈ n d n / r ⌉ . Moreover, this graph can be constructed deterministically in time polynomial in n n n .
Proof. Let k = ⌈ lg r ⌉ k = \lceil\lg r\rceil k = ⌈ lg r ⌉ , so that r ≤ 2 k < 2 r r \le2^k < 2r r ≤ 2 k < 2 r . If 2 k > n 2^k > n 2 k > n , then we give each element of L L L its own slot: let R R R be a copy of L L L and match each element to its copy. Then, ∣ R ∣ = n < 2 k < 2 r |R| = n < 2^k < 2r ∣ R ∣ = n < 2 k < 2 r , and all degrees are 1, so the lemma holds.
Otherwise, n ≥ 2 k n \ge2^k n ≥ 2 k . By Lemma 14 , there is a bipartite graph ( L ⊔ R ′ , E ′ ) (L \sqcup R', E') ( L ⊔ R ′ , E ′ ) with ∣ R ′ ∣ < 2 k + 3 < 16 r |R'| < 2^{k+3} < 16r ∣ R ′ ∣ < 2 k + 3 < 16 r such that every S ⊆ L S \subseteq L S ⊆ L with ∣ S ∣ ≤ 2 k |S| \le2^k ∣ S ∣ ≤ 2 k satisfies ∣ N ( S ) ∣ ≥ ∣ S ∣ |N(S)| \ge|S| ∣ N ( S ) ∣ ≥ ∣ S ∣ , and every vertex of L L L has degree bounded by a fixed polynomial in lg n \lg n lg n . Let d n d_n d n be the maximum of 1 and this bound. By Hall’s theorem [25 ] , every S ⊆ L S \subseteq L S ⊆ L with ∣ S ∣ ≤ r ≤ 2 k |S| \le r \le2^k ∣ S ∣ ≤ r ≤ 2 k has a matching that saturates S S S . Furthermore, ∣ E ′ ∣ ≤ n d n |E'| \le nd_n ∣ E ′ ∣ ≤ n d n .
Let Δ : = ⌈ n d n / r ⌉ \Delta:= \lceil nd_n/r\rceil Δ := ⌈ n d n / r ⌉ . We construct ( L ⊔ R , E ) (L \sqcup R, E) ( L ⊔ R , E ) from ( L ⊔ R ′ , E ′ ) (L \sqcup R', E') ( L ⊔ R ′ , E ′ ) by doing the following operation on each v ∈ R ′ v \in R' v ∈ R ′ : split v v v into ⌈ d ( v ) / Δ ⌉ \lceil d(v)/\Delta\rceil ⌈ d ( v ) /Δ ⌉ vertices v 1 , … , v ⌈ d ( v ) / Δ ⌉ v_1,\ldots,v_{\lceil d(v)/\Delta\rceil} v 1 , … , v ⌈ d ( v ) /Δ ⌉ such that d ( v i ) ≤ Δ d(v_i) \le\Delta d ( v i ) ≤ Δ for each i i i and the sets N ( v i ) N(v_i) N ( v i ) partition N ( v ) N(v) N ( v ) . We have
∣ R ∣ = ∑ v ∈ R ′ ⌈ d ( v ) Δ ⌉ ≤ ∣ R ′ ∣ + 1 Δ ∑ v ∈ R ′ d ( v ) ≤ ∣ R ′ ∣ + ∣ E ′ ∣ Δ < 16 r + r = 17 r . |R| = \sum_{v\in R'} \left\lceil\frac{d(v)}{\Delta}\right\rceil\le|R'| + \frac{1}{\Delta}\sum_{v\in R'}d(v) \le|R'| + \frac{|E'|}{\Delta} < 16r+r=17r. ∣ R ∣ = v ∈ R ′ ∑ ⌈ Δ d ( v ) ⌉ ≤ ∣ R ′ ∣ + Δ 1 v ∈ R ′ ∑ d ( v ) ≤ ∣ R ′ ∣ + Δ ∣ E ′ ∣ < 16 r + r = 17 r .
Every vertex of L L L retains its degree, and every vertex of R R R has degree at most Δ \Delta Δ by construction. Furthermore, a matching that saturates S S S in ( L ⊔ R ′ , E ′ ) (L \sqcup R', E') ( L ⊔ R ′ , E ′ ) lifts to a matching that saturates S S S in ( L ⊔ R , E ) (L \sqcup R, E) ( L ⊔ R , E ) , by replacing the right endpoint of each matching edge with the copy containing that edge; distinct right endpoints have distinct copies. Finally, by Lemma 14 , all ∣ E ′ ∣ ≤ n d n |E'| \le nd_n ∣ E ′ ∣ ≤ n d n edges can be computed in time polynomial in n n n , and the splitting takes polynomial time. □ \square □
The small α b \alpha_{\mathrm{b}} α b encoding
The explicit hash table of Lemma 23 has polylogarithmic left degree, so we state the encoding only in the range α ≥ n / lg n \alpha\ge n/\lg n α ≥ n / lg n , which suffices for our application.
Lemma 24. Let G = ( V 1 ⊔ V 2 , E ) G = (V_1 \sqcup V_2, E) G = ( V 1 ⊔ V 2 , E ) be a bipartite graph with n n n vertices, and let α \alpha α be an integer with n / lg n ≤ α ≤ n / 2 n/\lg n \le\alpha\le n/2 n / lg n ≤ α ≤ n /2 and α b ( G ) ≤ α \alpha_{\mathrm{b}}(G) \le\alpha α b ( G ) ≤ α . Then, enc ( I S G ) = O ( n lg lg n lg n ) \operatorname{enc}(\mathrm{IS}_G) = O\left(\frac{n\lg\lg n}{\lg n}\right) enc ( IS G ) = O ( l g n n l g l g n ) . Moreover, given G G G and α \alpha α , such an encoding can be constructed deterministically in time polynomial in n n n .
Proof. For n n n smaller than a sufficiently large absolute constant, we use one clause per edge, so assume that n n n is sufficiently large. By Lemma 23 with L = V 1 ⊔ V 2 L = V_1 \sqcup V_2 L = V 1 ⊔ V 2 and r = α r = \alpha r = α , there is a bipartite graph H = ( L ⊔ R , E ′ ) H = (L \sqcup R, E') H = ( L ⊔ R , E ′ ) such that (i) ∣ R ∣ ≤ 17 α |R| \le17\alpha ∣ R ∣ ≤ 17 α , (ii) for every S ⊆ V 1 ⊔ V 2 S \subseteq V_1 \sqcup V_2 S ⊆ V 1 ⊔ V 2 with ∣ S ∣ ≤ α |S| \le\alpha ∣ S ∣ ≤ α , there is a matching that saturates S S S , and (iii) every i ∈ V 1 ⊔ V 2 i \in V_1 \sqcup V_2 i ∈ V 1 ⊔ V 2 has degree at most d n d_n d n , and every j ∈ R j \in R j ∈ R has degree at most ⌈ n d n / α ⌉ ≤ d n lg n + 1 \lceil nd_n/\alpha\rceil\le d_n \lg n + 1 ⌈ n d n / α ⌉ ≤ d n lg n + 1 . Extend H H H by adding a vertex 0 0 0 to L L L (we assume that 0 ∉ V 1 ⊔ V 2 0 \notin V_1 \sqcup V_2 0 ∈ / V 1 ⊔ V 2 ) such that N H ( 0 ) = R N_H(0) = R N H ( 0 ) = R . Let d : = ⌈ d n lg n ⌉ + 2 d := \lceil d_n \lg n\rceil+ 2 d := ⌈ d n lg n ⌉ + 2 , so that ∣ N H ( j ) ∣ ≤ d |N_H(j)| \le d ∣ N H ( j ) ∣ ≤ d for every j ∈ R j \in R j ∈ R . Let t = ⌈ log d n 3 ⌉ t = \left\lceil\log_d \sqrt[3]{n}\right\rceil t = ⌈ log d 3 n ⌉ . Since d = ( lg n ) O ( 1 ) d = (\lg n)^{O(1)} d = ( lg n ) O ( 1 ) and n n n is sufficiently large, we have t ≥ 1 t \ge1 t ≥ 1 . Partition R R R into parts S 1 , … , S K S_1,\ldots,S_K S 1 , … , S K , where K : = ⌈ ∣ R ∣ / t ⌉ K := \lceil|R|/t\rceil K := ⌈ ∣ R ∣/ t ⌉ , each of size at most t t t . For each k ∈ [ K ] k \in[K] k ∈ [ K ] , let A k = ∏ j ∈ S k N H ( j ) A_k = \prod_{j\in S_k} N_H(j) A k = ∏ j ∈ S k N H ( j ) . Given a ⃗ ∈ A k \vec a \in A_k a ∈ A k and j ∈ S k j \in S_k j ∈ S k , we write a ⃗ ( j ) \vec a(j) a ( j ) to denote the element of N H ( j ) N_H(j) N H ( j ) occupying the j j j -component of a ⃗ \vec a a , and we write a ⃗ ∩ N G ( i ) = ∅ \vec a \cap N_G(i) = \varnothing a ∩ N G ( i ) = ∅ if a ⃗ ( j ) ∉ N G ( i ) \vec a(j) \notin N_G(i) a ( j ) ∈ / N G ( i ) for every j ∈ S k j \in S_k j ∈ S k .
We introduce the following auxiliary variables: b b b , h i , j h_{i,j} h i , j for all i ∈ V 1 ⊔ V 2 ⊔ { 0 } i \in V_1 \sqcup V_2 \sqcup\{0\} i ∈ V 1 ⊔ V 2 ⊔ { 0 } and j ∈ N H ( i ) j \in N_H(i) j ∈ N H ( i ) , and z k , a ⃗ z_{k,\vec a} z k , a for all k ∈ [ K ] k \in[K] k ∈ [ K ] and a ⃗ ∈ A k \vec a \in A_k a ∈ A k . Then, our encoding is as follows:
⋀ i ∈ V 1 ( x i ‾ ∨ b ‾ ∨ ⋁ j ∈ N H ( i ) h i , j ) ∧ ⋀ i ∈ V 2 ( x i ‾ ∨ b ∨ ⋁ j ∈ N H ( i ) h i , j ) (3) \bigwedge_{i\in V_1}\left(\overline{x_i}\vee\overline b\vee\bigvee_{j\in N_H(i)}h_{i,j}\right)\wedge\bigwedge_{i\in V_2}\left(\overline{x_i}\vee b\vee\bigvee_{j\in N_H(i)}h_{i,j}\right) \tag*{(3)} i ∈ V 1 ⋀ x i ∨ b ∨ j ∈ N H ( i ) ⋁ h i , j ∧ i ∈ V 2 ⋀ x i ∨ b ∨ j ∈ N H ( i ) ⋁ h i , j (3)
⋀ k ∈ [ K ] AtMostOne ( { z k , a ⃗ ∣ a ⃗ ∈ A k } ) (4) \bigwedge_{k\in[K]}\operatorname{AtMostOne}\left(\{z_{k,\vec a}\mid\vec a\in A_k\}\right) \tag*{(4)} k ∈ [ K ] ⋀ AtMostOne ( { z k , a ∣ a ∈ A k } ) (4)
⋀ k ∈ [ K ] ⋀ j ∈ S k ⋀ i ∈ N H ( j ) ( h i , j ‾ ∨ ⋁ a ⃗ ∈ A k a ⃗ ( j ) = i z k , a ⃗ ) (5) \bigwedge_{k\in[K]}\bigwedge_{j\in S_k}\bigwedge_{i\in N_H(j)}\left(\overline{h_{i,j}}\vee\bigvee_{\substack{\vec a\in A_k\\\vec a(j)=i}}z_{k,\vec a}\right) \tag*{(5)} k ∈ [ K ] ⋀ j ∈ S k ⋀ i ∈ N H ( j ) ⋀ h i , j ∨ a ∈ A k a ( j ) = i ⋁ z k , a (5)
⋀ i ∈ V 1 ⊔ V 2 ⋀ k ∈ [ K ] ( x i ‾ ∨ ⋁ a ⃗ ∈ A k a ⃗ ∩ N G ( i ) = ∅ z k , a ⃗ ) . (6) \bigwedge_{i\in V_1\sqcup V_2}\bigwedge_{k\in[K]}\left(\overline{x_i}\vee\bigvee_{\substack{\vec a\in A_k\\\vec a\cap N_G(i)=\varnothing}}z_{k,\vec a}\right). \tag*{(6)} i ∈ V 1 ⊔ V 2 ⋀ k ∈ [ K ] ⋀ x i ∨ a ∈ A k a ∩ N G ( i ) = ∅ ⋁ z k , a . (6)
First, we justify the correctness of the encoding. Given an assignment to the input variables, let X X X be the set of vertices of G G G corresponding to true input variables, so { x i ∣ i ∈ X } \{x_i\mid i\in X\} { x i ∣ i ∈ X } is the set of true input variables. Suppose first that X X X is an independent set in G G G . We either have ∣ X ∩ V 1 ∣ ≤ α b ( G ) ≤ α |X\cap V_1|\le\alpha_b(G)\le\alpha ∣ X ∩ V 1 ∣ ≤ α b ( G ) ≤ α or ∣ X ∩ V 2 ∣ ≤ α |X\cap V_2|\le\alpha ∣ X ∩ V 2 ∣ ≤ α , since otherwise X X X contains an independent set with α b ( G ) + 1 \alpha_b(G)+1 α b ( G ) + 1 vertices on each side. If the former case holds, then set b b b to true; otherwise, set b b b to false. From now on, we assume that ∣ X ∩ V 1 ∣ ≤ α |X\cap V_1|\le\alpha ∣ X ∩ V 1 ∣ ≤ α , since the other case is symmetric. There is a matching in H H H that saturates X ∩ V 1 X\cap V_1 X ∩ V 1 . Given i ∈ X ∩ V 1 i\in X\cap V_1 i ∈ X ∩ V 1 , let h ( i ) ∈ N H ( i ) h(i)\in N_H(i) h ( i ) ∈ N H ( i ) be the vertex paired with i i i according to the matching. For each i ∈ V 1 ⊔ V 2 i\in V_1\sqcup V_2 i ∈ V 1 ⊔ V 2 and j ∈ N H ( i ) j\in N_H(i) j ∈ N H ( i ) , set h i , j h_{i,j} h i , j to true if and only if i ∈ X ∩ V 1 i\in X\cap V_1 i ∈ X ∩ V 1 and h ( i ) = j h(i)=j h ( i ) = j . For each j ∈ R j\in R j ∈ R , set h 0 , j h_{0,j} h 0 , j to true if and only if there is no i ∈ X ∩ V 1 i\in X\cap V_1 i ∈ X ∩ V 1 with h ( i ) = j h(i)=j h ( i ) = j . Then, for each j ∈ R j\in R j ∈ R , there is exactly one i ∈ N H ( j ) i\in N_H(j) i ∈ N H ( j ) such that h i , j h_{i,j} h i , j is true; call it i j i_j i j . For each k ∈ [ K ] k\in[K] k ∈ [ K ] , let a ⃗ k ∈ A k \vec a_k\in A_k a k ∈ A k be the tuple with a ⃗ k ( j ) = i j \vec a_k(j)=i_j a k ( j ) = i j for each j ∈ S k j\in S_k j ∈ S k , and set z k , a ⃗ z_{k,\vec a} z k , a to true if and only if a ⃗ = a ⃗ k \vec a=\vec a_k a = a k . We claim that with this assignment to the auxiliary variables, each clause is satisfied:
If x i x_i x i is true and i ∈ V 1 i\in V_1 i ∈ V 1 , then h i , h ( i ) h_{i,h(i)} h i , h ( i ) is true. Since we are assuming that b b b is true, the clauses on line (1) are satisfied.
The clauses on line (2) are satisfied, because for each k ∈ [ K ] k\in[K] k ∈ [ K ] , we set z k , a ⃗ z_{k,\vec a} z k , a to true for exactly one a ⃗ ∈ A k \vec a\in A_k a ∈ A k .
The clauses on line (3) are satisfied, because if h i , j h_{i,j} h i , j is true for some j ∈ S k j\in S_k j ∈ S k , then i = i j = a ⃗ k ( j ) i=i_j=\vec a_k(j) i = i j = a k ( j ) , and z k , a ⃗ k z_{k,\vec a_k} z k , a k is true.
Suppose x i x_i x i is true, and let k ∈ [ K ] k \in[K] k ∈ [ K ] . Then, z k , a ⃗ k z_{k,\vec{a}_k} z k , a k is true, and a ⃗ k ( j ) ∈ ( X ∩ V 1 ) ⊔ { 0 } \vec{a}_k(j) \in(X \cap V_1) \sqcup\{0\} a k ( j ) ∈ ( X ∩ V 1 ) ⊔ { 0 } for all j ∈ S k j \in S_k j ∈ S k . Since X X X is an independent set and i ∈ X i \in X i ∈ X , we have a ⃗ k ∩ N G ( i ) = ∅ \vec{a}_k \cap N_G(i) = \varnothing a k ∩ N G ( i ) = ∅ . Thus, the clauses on line (4) are satisfied.
Suppose next that X X X is not an independent set in G G G . Then, there is some i 1 ∈ X ∩ V 1 i_1 \in X \cap V_1 i 1 ∈ X ∩ V 1 and i 2 ∈ X ∩ V 2 i_2 \in X \cap V_2 i 2 ∈ X ∩ V 2 such that { i 1 , i 2 } ∈ E \{i_1,i_2\} \in E { i 1 , i 2 } ∈ E . Then, by the clauses in line (1), we have h i , j h_{i,j} h i , j true for some i ∈ { i 1 , i 2 } i \in\{i_1,i_2\} i ∈ { i 1 , i 2 } and j ∈ R j \in R j ∈ R . Without loss of generality, h i 1 , j h_{i_1,j} h i 1 , j is true. Let k ∈ [ K ] k \in[K] k ∈ [ K ] be such that j ∈ S k j \in S_k j ∈ S k . Then, by the clauses in line (3), z k , a ⃗ z_{k,\vec{a}} z k , a is true for some a ⃗ ∈ A k \vec{a} \in A_k a ∈ A k with a ⃗ ( j ) = i 1 \vec{a}(j) = i_1 a ( j ) = i 1 . Also, by the clauses in line (4), z k , a ⃗ ′ z_{k,\vec{a}'} z k , a ′ is true for some a ⃗ ′ ∈ A k \vec{a}' \in A_k a ′ ∈ A k with a ⃗ ′ ∩ N G ( i 2 ) = ∅ \vec{a}' \cap N_G(i_2) = \varnothing a ′ ∩ N G ( i 2 ) = ∅ . Since i 1 ∈ N G ( i 2 ) i_1 \in N_G(i_2) i 1 ∈ N G ( i 2 ) , we have a ⃗ ≠ a ⃗ ′ \vec{a} \ne\vec{a}' a = a ′ , contradicting the clauses in line (2). This completes the proof that the encoding is correct.
Now, we count the number of clauses in the encoding. Since t ≥ 1 t \ge1 t ≥ 1 , we have t ≥ 1 2 log d n 3 = lg n 6 lg d t \ge\frac{1}{2}\log_d \sqrt[3]{n} = \frac{\lg n}{6\lg d} t ≥ 2 1 log d 3 n = 6 l g d l g n , and lg d = O ( lg lg n ) \lg d = O(\lg\lg n) lg d = O ( lg lg n ) . Recall also that α ≥ n / lg n \alpha\ge n/\lg n α ≥ n / lg n . We count the number of clauses as follows:
∣ A k ∣ ≤ d t ≤ n 3 , |A_k| \le d^t \le\sqrt[3]{n}, ∣ A k ∣ ≤ d t ≤ 3 n ,
so by Proposition 12 , the number of clauses on line (2) is
K ⋅ O ( n 3 ) = O ( α n 3 ) = O ( n α lg lg n lg n ) , K \cdot O\left(\sqrt[3]{n}\right) = O\left(\alpha\sqrt[3]{n}\right) = O\left(\frac{n\alpha\lg\lg n}{\lg n}\right), K ⋅ O ( 3 n ) = O ( α 3 n ) = O ( lg n n α lg lg n ) ,
since K ≤ ∣ R ∣ ≤ 17 α K \le|R| \le17\alpha K ≤ ∣ R ∣ ≤ 17 α .
There is one clause on line (3) for each edge of H H H , so there are at most n d n + ∣ R ∣ ≤ n d n + 17 α = O ( n α lg lg n lg n ) nd_n + |R| \le nd_n + 17\alpha= O\left(\frac{n\alpha\lg\lg n}{\lg n}\right) n d n + ∣ R ∣ ≤ n d n + 17 α = O ( l g n n α l g l g n ) clauses on line (3), since d n = ( lg n ) O ( 1 ) d_n = (\lg n)^{O(1)} d n = ( lg n ) O ( 1 ) and α ≥ n / lg n \alpha\ge n/\lg n α ≥ n / lg n .
n K ≤ n ( 17 α t + 1 ) = O ( n α lg d lg n + n ) = O ( n α lg lg n lg n ) . nK \le n\left(\frac{17\alpha}{t}+1\right) = O\left(\frac{n\alpha\lg d}{\lg n}+n\right) = O\left(\frac{n\alpha\lg\lg n}{\lg n}\right). n K ≤ n ( t 17 α + 1 ) = O ( lg n n α lg d + n ) = O ( lg n n α lg lg n ) .
Thus, the total number of clauses is O ( n α lg lg n lg n ) O\left(\frac{n\alpha\lg\lg n}{\lg n}\right) O ( l g n n α l g l g n ) , as desired. Finally, H H H can be constructed in polynomial time by Lemma 23 , and since ∣ A k ∣ ≤ n 3 |A_k| \le\sqrt[3]{n} ∣ A k ∣ ≤ 3 n for each k k k , all clauses can be written in polynomial time.
Encoding arbitrary bipartite graphs
At this point of the argument, we decompose an arbitrary bipartite graph into components to which Lemmas 22 and 24 apply, by recursively splitting its biadjacency matrix into squares. Given a bipartite graph G = ( A ⊔ B , E ) G = (A \sqcup B,E) G = ( A ⊔ B , E ) , we identify each edge { a , b } \{a,b\} { a , b } with a ∈ A a \in A a ∈ A and b ∈ B b \in B b ∈ B with the pair ( a , b ) ∈ A × B (a,b) \in A \times B ( a , b ) ∈ A × B . Given U ⊆ A U \subseteq A U ⊆ A and W ⊆ B W \subseteq B W ⊆ B , we call U × W U \times W U × W a rectangle with sides U U U and W W W , and a square if ∣ U ∣ = ∣ W ∣ |U| = |W| ∣ U ∣ = ∣ W ∣ ; we write e ( U , W ) : = ∣ E ∩ ( U × W ) ∣ e(U,W) := |E \cap(U \times W)| e ( U , W ) := ∣ E ∩ ( U × W ) ∣ and G [ U , W ] : = ( U ⊔ W , E ∩ ( U × W ) ) G[U,W] := (U \sqcup W,E \cap(U \times W)) G [ U , W ] := ( U ⊔ W , E ∩ ( U × W )) . The density of U × W U \times W U × W is
d ( U , W ) : = e ( U , W ) ∣ U ∣ ⋅ ∣ W ∣ , d(U,W) := \frac{e(U,W)}{|U| \cdot|W|}, d ( U , W ) := ∣ U ∣ ⋅ ∣ W ∣ e ( U , W ) ,
and U × W U \times W U × W is empty if e ( U , W ) = 0 e(U,W) = 0 e ( U , W ) = 0 . Thus, α b ( G [ U , W ] ) \alpha_b(G[U,W]) α b ( G [ U , W ]) is the largest k k k such that U × W U \times W U × W contains an empty k × k k \times k k × k square.
Deciding whether a bipartite graph has a large empty square is NP-complete [22 ] . Instead, we use the following search, which finds a sparse square whenever a large empty square exists. We state it for binary matrices, which should be interpreted as biadjacency matrices, whose rows and columns are indexed by the two sides of a bipartite graph, so that a rectangle of the matrix is a rectangle U × W U \times W U × W , and its density is d ( U , W ) d(U, W) d ( U , W ) .
Lemma 25 (Deterministic sparse-square search). Given an s × s s \times s s × s binary matrix, rational numbers 0 < α ≤ 1 0 < \alpha\le1 0 < α ≤ 1 and 0 < δ < 1 / 4 0 < \delta< 1/4 0 < δ < 1/4 , and an integer u u u such that 1 ≤ u ≤ α s / 2 1 \le u \le\alpha s/2 1 ≤ u ≤ α s /2 , with the property that the matrix contains an empty square I × J I \times J I × J with ∣ I ∣ = ∣ J ∣ ≥ α s |I| = |J| \ge\alpha s ∣ I ∣ = ∣ J ∣ ≥ α s , there is a deterministic algorithm that finds a u × u u \times u u × u square of density at most 4 δ 4\delta 4 δ in time
s O ( 1 ) exp ( O ( δ − 1 lg 2 1 α δ ) ) . s^{O(1)}\exp\left(O\left(\delta^{-1}\lg^2\frac{1}{\alpha\delta}\right)\right). s O ( 1 ) exp ( O ( δ − 1 lg 2 α δ 1 ) ) .
Our proof uses the following bounds of Alon, Feige, Wigderson, and Zuckerman on the probability that a random walk stays inside a set; we state the special case in which all eigenvalues are nonnegative.
Lemma 26 (Alon–Feige–Wigderson–Zuckerman [1 Proposition 2] ). Let P P P be the transition matrix of the random walk on a regular multigraph on s s s vertices, and suppose that P P P is positive semidefinite and every eigenvector of P P P orthogonal to the all-ones vector 1 \mathbf{1} 1 has eigenvalue at most λ \lambda λ . Let T T T be a set of μ ⋅ s \mu\cdot s μ ⋅ s vertices, and let w 0 , … , w L w_0,\ldots,w_L w 0 , … , w L be a random walk with transition matrix P P P and a uniformly random starting vertex. Then,
Pr [ w 0 , … , w L ∈ T ] ≤ μ ( μ + λ ) L , \Pr[w_0,\ldots,w_L \in T] \le\mu(\mu+\lambda)^L, Pr [ w 0 , … , w L ∈ T ] ≤ μ ( μ + λ ) L , and if L L L is even, then also
Pr [ w 0 , … , w L ∈ T ] ≥ μ L + 1 . \Pr[w_0,\ldots,w_L \in T] \ge\mu^{L+1}. Pr [ w 0 , … , w L ∈ T ] ≥ μ L + 1 .
Proof of Lemma 25. We prove the claim assuming s = m 2 s = m^2 s = m 2 is a perfect square, since otherwise the same argument can be made by padding the matrix with 1s until its dimension is the next perfect square.8 The proof proceeds conceptually by considering a random walk over possible squares, and showing that it succeeds in finding a sparse square, without taking too many steps, with positive probability. The deterministic algorithm is based on enumerating all short random walks of a suitable explicit expander.
We label the s s s rows of the input matrix M M M by Z m 2 \mathbb{Z}_m^2 Z m 2 , and use them as the vertex set of an 8-regular expander multigraph on s s s vertices, constructed as per Margulis–Gabber–Galil [26 Construction 8.1] , meaning that each vertex ( x , y ) ∈ Z m 2 (x,y) \in\mathbb{Z}_m^2 ( x , y ) ∈ Z m 2 has an edge to the following vertices:
( x ± 2 y , y ) , ( x ± ( 2 y + 1 ) , y ) , (x \pm2y,y),\quad(x \pm(2y+1),y), ( x ± 2 y , y ) , ( x ± ( 2 y + 1 ) , y ) ,
( x , y ± 2 x ) , ( x , y ± ( 2 x + 1 ) ) , (x,y \pm2x),\quad(x,y \pm(2x+1)), ( x , y ± 2 x ) , ( x , y ± ( 2 x + 1 )) ,
where all arithmetic is modulo m m m . Let A A A be the adjacency matrix of this graph, and Q 0 : = A / 8 Q_0 := A/8 Q 0 := A /8 its transition matrix. By [26 Theorem 8.2] , the constant vector 1 ∈ R s \mathbf{1} \in\mathbb{R}^s 1 ∈ R s is an eigenvector of Q 0 Q_0 Q 0 with eigenvalue 1, and every eigenvector in the set 1 ⊥ : = { v ∈ R s ∣ ⟨ v , 1 ⟩ = 0 } \mathbf{1}^{\perp} := \{v \in\mathbb{R}^s \mid\langle v,\mathbf{1}\rangle= 0\} 1 ⊥ := { v ∈ R s ∣ ⟨ v , 1 ⟩ = 0 } has an eigenvalue with absolute value at most 5 2 / 8 < 0.89 5\sqrt{2}/8 < 0.89 5 2 /8 < 0.89 .
We then consider the lazy random walk of transition matrix
Q : = Id s + Q 0 2 . Q := \frac{\operatorname{Id}_s + Q_0}{2}. Q := 2 Id s + Q 0 .
meaning that it stays at its current row with probability 1/2 and otherwise takes a step according to Q 0 Q_0 Q 0 . Note that Q Q Q is symmetric, and since each eigenvalue θ \theta θ of Q 0 Q_0 Q 0 corresponds to an eigenvalue ( 1 + θ ) / 2 ≥ 0 (1+\theta)/2 \ge0 ( 1 + θ ) /2 ≥ 0 of Q Q Q , we have that Q Q Q is positive semidefinite, and its eigenvalues on 1 ⊥ 1^\perp 1 ⊥ are at most
1 + 5 2 / 8 2 < 19 20 . \frac{1+5\sqrt{2}/8}{2}<\frac{19}{20}. 2 1 + 5 2 /8 < 20 19 .
Note that taking a step according to Q Q Q can be seen as choosing uniformly from 16 possibilities (8 directions and 8 choices representing staying at the given row).
Instead of considering Q Q Q directly, we use a power of Q Q Q in order to further reduce the magnitude of the eigenvalues. Let b : = ⌈ lg ( 2 / ( α δ ) ) ⌉ b:=\lceil\lg(2/(\alpha\delta))\rceil b := ⌈ lg ( 2/ ( α δ ))⌉ , and h : = 20 b h:=20b h := 20 b . We consider P : = Q h P:=Q^h P := Q h , which corresponds to taking h h h steps according to Q Q Q . Therefore, each step according to P P P can be seen as choosing uniformly from 16 h 16^h 1 6 h possibilities. The eigenvalues of P P P on 1 ⊥ 1^\perp 1 ⊥ lie in [ 0 , λ ] [0,\lambda] [ 0 , λ ] , where
λ ≤ ( 19 / 20 ) 20 b ≤ e − b ≤ 2 − b ≤ α δ / 2. \lambda\le(19/20)^{20b}\le e^{-b}\le2^{-b}\le\alpha\delta/2. λ ≤ ( 19/20 ) 20 b ≤ e − b ≤ 2 − b ≤ α δ /2.
Let L : = 2 ⌈ b / δ ⌉ L:=2\lceil b/\delta\rceil L := 2 ⌈ b / δ ⌉ be the length of the walks we consider. The algorithm enumerates all walks W : = ( w 0 , w 1 , … , w L ) W:=(w_0,w_1,\ldots,w_L) W := ( w 0 , w 1 , … , w L ) with transition matrix P P P , over all starting rows and all step choices. The number of such walks is at most
s ⋅ ( 16 h ) L = s exp ( O ( b 2 δ ) ) = s ⋅ exp ( O ( δ − 1 lg 2 1 α δ ) ) . s\cdot(16^h)^L=s\exp\left(O\left(\frac{b^2}{\delta}\right)\right)=s\cdot\exp\left(O\left(\delta^{-1}\lg^2\frac{1}{\alpha\delta}\right)\right). s ⋅ ( 1 6 h ) L = s exp ( O ( δ b 2 ) ) = s ⋅ exp ( O ( δ − 1 lg 2 α δ 1 ) ) .
For each walk W W W , we attempt to get a sparse square in the original matrix M M M as follows:
Let C ⊆ [ s ] C\subseteq[s] C ⊆ [ s ] be the columns of M M M whose entries are zero in every row visited by W W W .
Let R ⊆ [ s ] R\subseteq[s] R ⊆ [ s ] be the set of rows r r r such that M M M has at most 4 δ ∣ C ∣ 4\delta|C| 4 δ ∣ C ∣ ones on row r r r in the columns C C C .
If ∣ R ∣ < u |R|<u ∣ R ∣ < u or ∣ C ∣ < u |C|<u ∣ C ∣ < u , continue to the next walk.
Otherwise, choose any u u u rows R ′ ⊆ R R'\subseteq R R ′ ⊆ R and the u u u columns C ′ ⊆ C C'\subseteq C C ′ ⊆ C with the fewest ones in those rows, and return R ′ × C ′ R'\times C' R ′ × C ′ .
Writing e ( X , Y ) e(X,Y) e ( X , Y ) for the number of ones in M [ X × Y ] M[X\times Y] M [ X × Y ] , the choice of C ′ C' C ′ gives
e ( R ′ , C ′ ) ≤ u ∣ C ∣ e ( R ′ , C ) ≤ 4 δ u 2 . e(R',C')\le\frac{u}{|C|}e(R',C)\le4\delta u^2. e ( R ′ , C ′ ) ≤ ∣ C ∣ u e ( R ′ , C ) ≤ 4 δ u 2 .
Thus every returned square has the required density. If no walk succeeds, the algorithm reports failure. Note immediately that each of the four steps above takes time polynomial in s s s , and thus the final runtime is upper bounded by the number of walks times a polynomial in s s s , satisfying the desired bound.
We now prove that some walk succeeds whenever the promised empty square I × J I\times J I × J exists. Put β : = ∣ I ∣ / s ≥ α \beta:=|I|/s\ge\alpha β := ∣ I ∣/ s ≥ α , and consider a random walk w 0 , … , w L w_0,\ldots,w_L w 0 , … , w L with transition matrix P P P and a uniformly chosen starting row. Let E \mathcal{E} E be the event that all L + 1 L+1 L + 1 visited rows lie in I I I . Since L L L is even, Lemma 26 applied to T : = I T:=I T := I gives
Pr [ E ] ≥ β L + 1 . \Pr[\mathcal{E}]\ge\beta^{L+1}. Pr [ E ] ≥ β L + 1 .
Call a column bad if it has at least δ ∣ I ∣ \delta|I| δ ∣ I ∣ ones in the rows of I I I . For a bad column j j j , let S ⊆ I S\subseteq I S ⊆ I be the rows where its entry is zero. Then ∣ S ∣ / s ≤ ( 1 − δ ) β |S|/s\le(1-\delta)\beta ∣ S ∣/ s ≤ ( 1 − δ ) β . Conditional on E \mathcal{E} E , the column belongs to $C. precisely when the walk stays entirely in S S S . By Lemma 26 applied to T : = S T := S T := S , we have
Pr [ w 0 , … , w L ∈ S ] ≤ ∣ S ∣ s ( ∣ S ∣ s + λ ) L ≤ β ( ( 1 − δ ) β + λ ) L . \Pr[w_0,\ldots,w_L \in S] \le\frac{|S|}{s}\left(\frac{|S|}{s}+\lambda\right)^L \le\beta\left((1-\delta)\beta+\lambda\right)^L. Pr [ w 0 , … , w L ∈ S ] ≤ s ∣ S ∣ ( s ∣ S ∣ + λ ) L ≤ β ( ( 1 − δ ) β + λ ) L .
Dividing by the lower bound on Pr [ E ] \Pr[\mathcal{E}] Pr [ E ] and using λ / β ≤ δ / 2 \lambda/\beta\le\delta/2 λ / β ≤ δ /2 , we obtain
Pr [ j ∈ C ∣ E ] ≤ ( 1 − δ + λ / β ) L ≤ e − δ L / 2 ≤ e − b ≤ α δ . \Pr[j \in C \mid\mathcal{E}] \le(1-\delta+\lambda/\beta)^L \le e^{-\delta L/2} \le e^{-b} \le\alpha\delta. Pr [ j ∈ C ∣ E ] ≤ ( 1 − δ + λ / β ) L ≤ e − δ L /2 ≤ e − b ≤ α δ .
There are at most s s s bad columns, so, conditional on E \mathcal{E} E , the expected number of bad columns in C C C is at most α δ s \alpha\delta s α δ s . Hence some walk entirely inside I I I leaves at most that many bad columns in C C C . For this walk, J ⊆ C J \subseteq C J ⊆ C because I × J I \times J I × J is empty, so ∣ C ∣ ≥ α s |C| \ge\alpha s ∣ C ∣ ≥ α s . Each column that is not bad contributes fewer than δ ∣ I ∣ \delta|I| δ ∣ I ∣ ones in the rows of I I I , and each bad column contributes at most ∣ I ∣ |I| ∣ I ∣ . Therefore,
e ( I , C ) ≤ δ ∣ I ∣ ∣ C ∣ + α δ s ∣ I ∣ ≤ 2 δ ∣ I ∣ ∣ C ∣ . e(I,C) \le\delta|I||C|+\alpha\delta s|I| \le2\delta|I||C|. e ( I , C ) ≤ δ ∣ I ∣∣ C ∣ + α δ s ∣ I ∣ ≤ 2 δ ∣ I ∣∣ C ∣.
The average number of ones in C C C over the rows of I I I is thus at most 2 δ ∣ C ∣ 2\delta|C| 2 δ ∣ C ∣ . At least half those rows have at most 4 δ ∣ C ∣ 4\delta|C| 4 δ ∣ C ∣ ones, so ∣ R ∣ ≥ ∣ I ∣ / 2 ≥ u |R| \ge|I|/2 \ge u ∣ R ∣ ≥ ∣ I ∣/2 ≥ u . We also have ∣ C ∣ ≥ α s ≥ 2 u |C| \ge\alpha s \ge2u ∣ C ∣ ≥ α s ≥ 2 u , and the algorithm succeeds.
We now state the graph decomposition. It can be seen as a kind of regularity lemma [63 ] : every square of the decomposition is pseudorandom in the sense that it contains no large empty square, and all remaining edges form a sparse graph.
Lemma 27 (Sparse–pseudorandom decomposition). Let G = ( A ⊔ B , E ) G=(A \sqcup B,E) G = ( A ⊔ B , E ) be a bipartite graph with ∣ A ∣ = ∣ B ∣ = N |A|=|B|=N ∣ A ∣ = ∣ B ∣ = N . Then, there is an integer q = Θ ( lg N ( lg lg N ) 2 ) q=\Theta\left(\frac{\lg N}{(\lg\lg N)^2}\right) q = Θ ( ( l g l g N ) 2 l g N ) such that A × B A\times B A × B can be partitioned into squares U 1 × W 1 , … , U p × W p U_1\times W_1,\ldots,U_p\times W_p U 1 × W 1 , … , U p × W p and a set S ⊆ A × B S\subseteq A\times B S ⊆ A × B such that:
(i) every square has side length m i : = ∣ U i ∣ = ∣ W i ∣ ≥ N m_i:=|U_i|=|W_i|\ge\sqrt{N} m i := ∣ U i ∣ = ∣ W i ∣ ≥ N ;
(ii) for every i ∈ [ p ] i\in[p] i ∈ [ p ] , we have α b ( G [ U i , W i ] ) < 2 ⌊ m i / q ⌋ \alpha_b(G[U_i,W_i])<2\lfloor m_i/q\rfloor α b ( G [ U i , W i ]) < 2 ⌊ m i / q ⌋ ;
(iii) ∣ E ∩ S ∣ = O ( N 2 / q ) |E\cap S|=O(N^2/q) ∣ E ∩ S ∣ = O ( N 2 / q ) .
Moreover, q q q and such a partition can be computed deterministically in time polynomial in N N N .
Proof. If N N N is smaller than a sufficiently large absolute constant, we take q : = 1 q:=1 q := 1 , p : = 0 p:=0 p := 0 , and S : = A × B S:=A\times B S := A × B . Otherwise, put
t : = ⌊ lg N ⌋ , ℓ : = ⌈ lg t ⌉ , q : = ⌊ t 64 ℓ 2 ⌋ , t:=\lfloor\lg N\rfloor,\qquad\ell:=\lceil\lg t\rceil,\qquad q:=\left\lfloor\frac{t}{64\ell^2}\right\rfloor, t := ⌊ lg N ⌋ , ℓ := ⌈ lg t ⌉ , q := ⌊ 64 ℓ 2 t ⌋ ,
so that q = Θ ( lg N ( lg lg N ) 2 ) q=\Theta\left(\frac{\lg N}{(\lg\lg N)^2}\right) q = Θ ( ( l g l g N ) 2 l g N ) , and assume that N N N is large enough that q ≥ 12 q\ge12 q ≥ 12 , N ≥ 2 q \sqrt{N}\ge2q N ≥ 2 q , and ℓ ≥ 6 \ell\ge6 ℓ ≥ 6 . We describe a recursive procedure SPLIT ( U , W ) \operatorname{SPLIT}(U,W) SPLIT ( U , W ) , which takes a square U × W U\times W U × W with U ⊆ A U\subseteq A U ⊆ A , W ⊆ B W\subseteq B W ⊆ B , and ∣ U ∣ = ∣ W ∣ = m |U|=|W|=m ∣ U ∣ = ∣ W ∣ = m , and partitions it into squares of the form required by (i) and (ii) and cells that are added to S S S :
(a) If m < N m<\sqrt{N} m < N , add U × W U\times W U × W to S S S . We call U × W U\times W U × W a small square .
(b) Otherwise, let u : = ⌊ m / q ⌋ u:=\lfloor m/q\rfloor u := ⌊ m / q ⌋ , and write m = q u + r m=qu+r m = q u + r with 0 ≤ r < q 0\le r<q 0 ≤ r < q . Since m ≥ 2 q m\ge2q m ≥ 2 q , we have u ≥ m / ( 2 q ) ≥ 1 u\ge m/(2q)\ge1 u ≥ m / ( 2 q ) ≥ 1 . Apply Lemma 25 to the biadjacency matrix of G [ U , W ] G[U,W] G [ U , W ] with α : = 2 u / m \alpha:=2u/m α := 2 u / m , δ : = 1 / q \delta:=1/q δ := 1/ q , and target side length u u u ; its hypotheses hold since α ≤ 2 / q ≤ 1 \alpha\le2/q\le1 α ≤ 2/ q ≤ 1 , δ < 1 / 4 \delta<1/4 δ < 1/4 , and u = α m / 2 u=\alpha m/2 u = α m /2 .
(b1) If the search reports failure, then U × W U \times W U × W contains no empty square of side length at least α m = 2 u \alpha m = 2u α m = 2 u , so α b ( G [ U , W ] ) < 2 u \alpha_b(G[U,W]) < 2u α b ( G [ U , W ]) < 2 u . Output U × W U \times W U × W as one of the squares U i × W i U_i \times W_i U i × W i .
(b2) Otherwise, the search returns U ′ ⊆ U U' \subseteq U U ′ ⊆ U and W ′ ⊆ W W' \subseteq W W ′ ⊆ W with ∣ U ′ ∣ = ∣ W ′ ∣ = u |U'| = |W'| = u ∣ U ′ ∣ = ∣ W ′ ∣ = u and e ( U ′ , W ′ ) ≤ 4 u 2 / q e(U',W') \le4u^2/q e ( U ′ , W ′ ) ≤ 4 u 2 / q . Add U ′ × W ′ U' \times W' U ′ × W ′ to S S S ; we call it a sparse square . Since m − u = ( q − 1 ) u + r m-u = (q-1)u+r m − u = ( q − 1 ) u + r , we can partition U ∖ U ′ U \setminus U' U ∖ U ′ into sets U 1 ′ , … , U q − 1 ′ U'_1,\ldots,U'_{q-1} U 1 ′ , … , U q − 1 ′ of size u u u and a set U 0 ′ U'_0 U 0 ′ of size r r r , and similarly partition W ∖ W ′ W \setminus W' W ∖ W ′ into sets W 1 ′ , … , W q − 1 ′ W'_1,\ldots,W'_{q-1} W 1 ′ , … , W q − 1 ′ of size u u u and a set W 0 ′ W'_0 W 0 ′ of size r r r . Add U ′ × W 0 ′ U' \times W'_0 U ′ × W 0 ′ and U 0 ′ × W ′ U'_0 \times W' U 0 ′ × W ′ to S S S ; we call them slivers . Finally, call SPLIT ( U ∖ U ′ , W ∖ W ′ ) \operatorname{SPLIT}(U \setminus U', W \setminus W') SPLIT ( U ∖ U ′ , W ∖ W ′ ) , and call SPLIT ( U j ′ , W j ′ ) \operatorname{SPLIT}(U'_j,W'_j) SPLIT ( U j ′ , W j ′ ) for every j ∈ [ q − 1 ] j \in[q-1] j ∈ [ q − 1 ] . We call SPLIT ( U ∖ U ′ , W ∖ W ′ ) \operatorname{SPLIT}(U \setminus U', W \setminus W') SPLIT ( U ∖ U ′ , W ∖ W ′ ) the large child of this call, and the large-child branch of a call is the sequence of calls obtained by repeatedly passing to the large child.
In case (b2), the sparse square, the two slivers, and the squares of the recursive calls partition U × W U \times W U × W . Thus, SPLIT ( A , B ) \operatorname{SPLIT}(A,B) SPLIT ( A , B ) produces a partition of A × B A \times B A × B into squares U i × W i U_i \times W_i U i × W i and a set S S S , which consists of sparse squares, slivers, and small squares. Properties (i) and (ii) hold by construction, since squares are only output in case (b1). It remains to prove (iii) and to bound the running time.
We first bound the running time. Every recursive call is on a square of side length m − u m-u m − u or u u u , both of which are positive and smaller than m m m , so the recursion terminates. The calls that do not recurse are on pairwise disjoint nonempty squares, so there are at most N 2 N^2 N 2 of them, and every call that recurses makes at least two recursive calls, so there are at most 2 N 2 2N^2 2 N 2 calls in total. In each call, δ − 1 = q \delta^{-1}=q δ − 1 = q and α δ = 2 u / ( m q ) ≥ 1 / q 2 \alpha\delta= 2u/(mq) \ge1/q^2 α δ = 2 u / ( m q ) ≥ 1/ q 2 , so by Lemma 25 the search takes time
m O ( 1 ) exp ( O ( q ln 2 q ) ) = N O ( 1 ) , m^{O(1)}\exp\left(O\left(q\ln^2 q\right)\right)=N^{O(1)}, m O ( 1 ) exp ( O ( q ln 2 q ) ) = N O ( 1 ) ,
since ln q ≤ ln t ≤ ℓ \ln q \le\ln t \le\ell ln q ≤ ln t ≤ ℓ and therefore q ln 2 q ≤ t / 64 ≤ lg N q\ln^2 q \le t/64 \le\lg N q ln 2 q ≤ t /64 ≤ lg N . Thus, the decomposition can be computed in time polynomial in N N N .
Now, we prove (iii) by bounding the number of edges in the sparse squares, slivers, and small squares:
Every sparse square U ′ × W ′ U' \times W' U ′ × W ′ has e ( U ′ , W ′ ) ≤ 4 u 2 / q = 4 q ∣ U ′ ∣ ∣ W ′ ∣ e(U',W') \le4u^2/q = \frac{4}{q}|U'||W'| e ( U ′ , W ′ ) ≤ 4 u 2 / q = q 4 ∣ U ′ ∣∣ W ′ ∣ . Since the sparse squares are pairwise disjoint, they contain at most 4 N 2 / q 4N^2/q 4 N 2 / q edges in total.
Consider a call in case (b2) on a square of side length m m m . Its two slivers have 2 u r < 2 q u ≤ 2 m 2ur < 2qu \le2m 2 u r < 2 q u ≤ 2 m cells, and its sparse square has u 2 ≥ m 2 / ( 4 q 2 ) u^2 \ge m^2/(4q^2) u 2 ≥ m 2 / ( 4 q 2 ) cells. Hence, the slivers have at most
2 m ≤ 8 q 2 u 2 m ≤ 8 q 2 u 2 N 2m \le\frac{8q^2u^2}{m} \le\frac{8q^2u^2}{\sqrt{N}} 2 m ≤ m 8 q 2 u 2 ≤ N 8 q 2 u 2
cells. Since the sparse squares are pairwise disjoint, summing over all calls in case (b2) shows that the slivers have at most 8 q 2 N 2 / N = 8 q 2 N 3 / 2 = O ( N 2 / q ) 8q^2N^2/\sqrt{N}=8q^2N^{3/2}=O(N^2/q) 8 q 2 N 2 / N = 8 q 2 N 3/2 = O ( N 2 / q ) cells in total, since q = O ( lg N ) q=O(\lg N) q = O ( lg N ) .
To bound the small squares, group consecutive calls along the large-child branch. A group starts with side length m ≥ 2 N m \ge2\sqrt{N} m ≥ 2 N and follows this branch until its side length is at most m / 2 m/2 m /2 or a search reports failure. Its children are the calls on squares of side length u u u produced along the branch and the final large-child call, if one exists. Stop grouping at squares of side length below 2 N 2\sqrt{N} 2 N . Every original small square lies within one of these squares.
For every call in a group, its side length a a a satisfies m / 2 < a ≤ m m/2 < a \le m m /2 < a ≤ m and a ≥ N ≥ 2 q a \ge\sqrt{N} \ge2q a ≥ N ≥ 2 q , so u = ⌊ a / q ⌋ ≥ m / ( 4 q ) u=\lfloor a/q\rfloor\ge m/(4q) u = ⌊ a / q ⌋ ≥ m / ( 4 q ) . If the group reaches side length at most m / 2 m/2 m /2 , its sparse squares satisfy ∑ u ≥ m / 2 \sum u \ge m/2 ∑ u ≥ m /2 , hence ∑ u 2 ≥ m 2 / ( 8 q ) \sum u^2 \ge m^2/(8q) ∑ u 2 ≥ m 2 / ( 8 q ) . Otherwise, the search failure outputs a square of area at least m 2 / 4 m^2/4 m 2 /4 . Thus, the children have total area at most ρ m 2 \rho m^2 ρ m 2 , where ρ : = 1 − 1 / ( 8 q ) \rho:= 1 - 1/(8q) ρ := 1 − 1/ ( 8 q ) . Every child has side length at least m / ( 4 q ) m/(4q) m / ( 4 q ) ; the final large child has side length at least m / 2 − m / q m/2 - m/q m /2 − m / q .
Put d : = ⌊ log 4 q ( N / 2 ) ⌋ d := \left\lfloor\log_{4q}(\sqrt{N}/2) \right\rfloor d := ⌊ log 4 q ( N /2 ) ⌋ . At depth j j j of the grouped recursion, every square has side length at least N / ( 4 q ) j N/(4q)^j N / ( 4 q ) j , so no square of side length below 2 N 2\sqrt{N} 2 N occurs at depth at most d d d . All small squares therefore lie within the squares at depth d d d , whose total area is at most N 2 ρ d N^2\rho^d N 2 ρ d . Since ln ( 4 q ) ≤ ln 4 + ( ln 2 ) ℓ ≤ ℓ \ln(4q) \le\ln4 + (\ln2)\ell\le\ell ln ( 4 q ) ≤ ln 4 + ( ln 2 ) ℓ ≤ ℓ , we have
d 8 q ≥ ln N 16 q ln ( 4 q ) − 1 4 q ≥ 4 ( ln 2 ) ℓ − 1 4 q ≥ 2 ℓ . \frac{d}{8q} \ge\frac{\ln N}{16q\ln(4q)} - \frac{1}{4q} \ge4(\ln2)\ell- \frac{1}{4q} \ge2\ell. 8 q d ≥ 16 q ln ( 4 q ) ln N − 4 q 1 ≥ 4 ( ln 2 ) ℓ − 4 q 1 ≥ 2 ℓ .
Therefore, the small squares have at most N 2 ρ d ≤ N 2 e − 2 ℓ ≤ N 2 / t ≤ N 2 / q N^2\rho^d \le N^2e^{-2\ell} \le N^2/t \le N^2/q N 2 ρ d ≤ N 2 e − 2 ℓ ≤ N 2 / t ≤ N 2 / q cells in total.
Therefore, ∣ E ∩ S ∣ ≤ 4 N 2 / q + 8 q 2 N 3 / 2 + N 2 / q = O ( N 2 / q ) |E \cap S| \le4N^2/q + 8q^2N^{3/2} + N^2/q = O(N^2/q) ∣ E ∩ S ∣ ≤ 4 N 2 / q + 8 q 2 N 3/2 + N 2 / q = O ( N 2 / q ) .
We can now prove our upper bound on encoding the independent set constraint for arbitrary bipartite graphs.
Lemma 28. Let G = ( A ⊔ B , E ) G = (A \sqcup B, E) G = ( A ⊔ B , E ) be a bipartite graph with ∣ A ∣ = ∣ B ∣ = N |A| = |B| = N ∣ A ∣ = ∣ B ∣ = N . Then, enc ( I S G ) = O ( N 2 ( lg lg N ) 3 lg 2 N ) \operatorname{enc}(\mathrm{IS}_G) = O\left(\frac{N^2(\lg\lg N)^3}{\lg^2 N}\right) enc ( IS G ) = O ( l g 2 N N 2 ( l g l g N ) 3 ) . Moreover, such an encoding can be constructed deterministically in time polynomial in N N N .
Proof. For N N N smaller than a sufficiently large absolute constant, we use one clause per edge, so assume that N N N is sufficiently large.
Apply Lemma 27 to get a partition of A × B A \times B A × B into squares U 1 × W 1 , … , U p × W p U_1 \times W_1,\ldots,U_p \times W_p U 1 × W 1 , … , U p × W p and a set S S S of the stated form. We decompose G G G into subgraphs whose edge sets partition E E E :
For each i ∈ [ p ] i \in[p] i ∈ [ p ] , let G i : = G [ U i , W i ] G_i := G[U_i,W_i] G i := G [ U i , W i ] be the subgraph consisting of the edges in the square U i × W i U_i \times W_i U i × W i .
Let G 0 : = ( A ⊔ B , E ∩ S ) G_0 := (A \sqcup B, E \cap S) G 0 := ( A ⊔ B , E ∩ S ) be the subgraph consisting of the edges in S S S , that is, the edges in sparse squares, slivers, and small squares.
A set of vertices is independent in G G G if and only if it is independent in G 0 G_0 G 0 and its intersection with U i ⊔ W i U_i \sqcup W_i U i ⊔ W i is independent in G i G_i G i for every i ∈ [ p ] i \in[p] i ∈ [ p ] . Thus, the conjunction of encodings of I S G 0 \mathrm{IS}_{G_0} IS G 0 and I S G 1 , … , I S G p \mathrm{IS}_{G_1},\ldots,\mathrm{IS}_{G_p} IS G 1 , … , IS G p , with pairwise disjoint auxiliary variables, is an encoding of I S G \mathrm{IS}_G IS G . We now show that these encodings use O ( N 2 ( lg lg N ) 3 lg 2 N ) O\left(\frac{N^2(\lg\lg N)^3}{\lg^2 N}\right) O ( l g 2 N N 2 ( l g l g N ) 3 ) clauses in total.
For each i ∈ [ p ] i \in[p] i ∈ [ p ] , the graph G i G_i G i is bipartite with 2 m i 2m_i 2 m i vertices, where m i ≥ N m_i \ge\sqrt{N} m i ≥ N . Let u i : = ⌊ m i / q ⌋ u_i := \lfloor m_i/q \rfloor u i := ⌊ m i / q ⌋ and α i : = 2 u i \alpha_i := 2u_i α i := 2 u i , so α b ( G i ) < α i \alpha_b(G_i) < \alpha_i α b ( G i ) < α i by Lemma 27 . We check the remaining hypotheses of Lemma 24 with n : = 2 m i n := 2m_i n := 2 m i and α : = α i \alpha:= \alpha_i α := α i . Since N N N is sufficiently large and q = Θ ( lg N ( lg lg N ) 2 ) q = \Theta\left(\frac{\lg N}{(\lg\lg N)^2}\right) q = Θ ( ( l g l g N ) 2 l g N ) , we have 2 ≤ q ≤ lg N 64 2 \le q \le\frac{\lg N}{64} 2 ≤ q ≤ 64 l g N and m i ≥ N ≥ 2 q m_i \ge\sqrt{N} \ge2q m i ≥ N ≥ 2 q . Thus, α i ≥ m i / q \alpha_i \ge m_i/q α i ≥ m i / q , and since q ≤ lg N 64 ≤ lg ( 2 m i ) 32 q \le\frac{\lg N}{64} \le\frac{\lg(2m_i)}{32} q ≤ 64 l g N ≤ 32 l g ( 2 m i ) , this gives α i ≥ lg ( 2 m i ) 2 m i \alpha_i \ge\frac{\lg(2m_i)}{2m_i} α i ≥ 2 m i l g ( 2 m i ) . Furthermore, α i ≤ 2 m i / q ≤ m i \alpha_i \le2m_i/q \le m_i α i ≤ 2 m i / q ≤ m i . Thus, by Lemma 24 , I S G i \mathrm{IS}_{G_i} IS G i can be encoded using
O ( m i u i lg lg m i lg m i ) = O ( m i 2 lg lg N q lg N ) O\left(\frac{m_i u_i \lg\lg m_i}{\lg m_i}\right) = O\left(\frac{m_i^2 \lg\lg N}{q\lg N}\right) O ( lg m i m i u i lg lg m i ) = O ( q lg N m i 2 lg lg N )
clauses, since u i ≤ m i / q u_i \le m_i/q u i ≤ m i / q and lg m i ≥ 1 2 lg N \lg m_i \ge\frac{1}{2}\lg N lg m i ≥ 2 1 lg N . Since the squares are pairwise disjoint, ∑ i ∈ [ p ] m i 2 ≤ N 2 \sum_{i \in[p]}m_i^2 \le N^2 ∑ i ∈ [ p ] m i 2 ≤ N 2 , so the total number of clauses over all i ∈ [ p ] i \in[p] i ∈ [ p ] is O ( N 2 lg lg N q lg N ) = O ( N 2 ( lg lg N ) 3 lg 2 N ) O\left(\frac{N^2\lg\lg N}{q\lg N}\right) = O\left(\frac{N^2(\lg\lg N)^3}{\lg^2 N}\right) O ( q l g N N 2 l g l g N ) = O ( l g 2 N N 2 ( l g l g N ) 3 ) , since q = Θ ( lg N ( lg lg N ) 2 ) q = \Theta\left(\frac{\lg N}{(\lg\lg N)^2}\right) q = Θ ( ( l g l g N ) 2 l g N ) . By Lemma 27 , the graph G 0 G_0 G 0 has 2 N 2N 2 N vertices and at most C N 2 / q CN^2/q C N 2 / q edges for some absolute constant C C C , so its edge density is at most
C N 2 q ( 2 N 2 ) ≤ C q = : γ . \frac{CN^2}{q\binom{2N}{2}} \le\frac{C}{q} =: \gamma. q ( 2 2 N ) C N 2 ≤ q C =: γ .
Since N N N is sufficiently large, we may assume that 0 < γ ≤ 1 / 2 0 < \gamma\le1/2 0 < γ ≤ 1/2 . Therefore, by Lemma 22 , we can encode I S G 0 \mathrm{IS}_{G_0} IS G 0 using
O ( γ N 2 lg ( γ − 1 ) lg N ) = O ( N 2 lg q q lg N ) = O ( N 2 ( lg lg N ) 3 lg 2 N ) O\left(\frac{\gamma N^2\lg(\gamma^{-1})}{\lg N}\right) = O\left(\frac{N^2\lg q}{q\lg N}\right) = O\left(\frac{N^2(\lg\lg N)^3}{\lg^2 N}\right) O ( lg N γ N 2 lg ( γ − 1 ) ) = O ( q lg N N 2 lg q ) = O ( lg 2 N N 2 ( lg lg N ) 3 )
clauses, again since q = Θ ( lg N ( lg lg N ) 2 ) q = \Theta\left(\frac{\lg N}{(\lg\lg N)^2}\right) q = Θ ( ( l g l g N ) 2 l g N ) .
Finally, the decomposition can be computed in polynomial time by Lemma 27 , there are at most N 2 N^2 N 2 squares, and each encoding can be constructed in polynomial time by Lemmas 22 and 24 .
Theorem 5. If f : { 0 , 1 } n → { 0 , 1 } f : \{0,1\}^n \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } is a k k k -CNF function for some fixed k ≥ 2 k \ge2 k ≥ 2 , then one can construct in deterministic polynomial time a CNF encoding of f f f with O k ( n k ( lg lg n ) 3 lg 2 n ) O_k\left(\frac{n^k(\lg\lg n)^3}{\lg^2 n}\right) O k ( l g 2 n n k ( l g l g n ) 3 ) clauses.
Proof. For k = 2 k = 2 k = 2 , apply Lemma 19 and encode I S G \mathrm{IS}_G IS G by Lemma 28 with N = 2 n N = 2n N = 2 n . For k ≥ 3 k \ge3 k ≥ 3 , applying Lemma 20 k − 2 k - 2 k − 2 times gives O k ( n k ( lg lg n ) 3 / lg 2 n ) O_k(n^k(\lg\lg n)^3/\lg^2 n) O k ( n k ( lg lg n ) 3 / lg 2 n ) clauses. Since each application is constructive, for fixed k k k the encoding can be computed in polynomial time.
Counting lower bounds
A k k k -CNF function has a width-k k k encoding with O k ( n k / lg n ) O_k(n^k/\lg n) O k ( n k / lg n ) clauses [11 , 38 ] . The following counting argument shows that unbounded clause width is necessary to improve this bound, as in Theorems 4 and 5.
Proposition 29. For every fixed k ≥ 2 k \ge2 k ≥ 2 and w ≥ k w \ge k w ≥ k , there are k k k -CNF functions on n n n inputs whose width-w w w encodings require Ω k , w ( n k / lg n ) \Omega_{k,w}(n^k/\lg n) Ω k , w ( n k / lg n ) clauses.
Proof. For each collection H ⊆ ( [ n ] k ) \mathcal{H} \subseteq\binom{[n]}{k} H ⊆ ( k [ n ] ) , consider the antitone k k k -CNF
f H ( x ⃗ ) = ⋀ S ∈ H ⋁ i ∈ S x i ‾ . f_{\mathcal{H}}(\vec{x}) = \bigwedge_{S\in\mathcal{H}}\bigvee_{i\in S}\overline{x_i}. f H ( x ) = S ∈ H ⋀ i ∈ S ⋁ x i . On an assignment selecting exactly the elements of S ∈ ( [ n ] k ) S \in\binom{[n]}{k} S ∈ ( k [ n ] ) , this function is false exactly when S ∈ H S \in\mathcal{H} S ∈ H . Hence, these collections give 2 ( n k ) 2^{\binom{n}{k}} 2 ( k n ) distinct functions.
Let q q q be the minimum integer such that these functions all have width-w w w encodings with at most q q q clauses. Since w ≥ k w \ge k w ≥ k , their original CNFs give q ≤ ( n k ) q \le\binom{n}{k} q ≤ ( k n ) . An encoding with at most q q q clauses of width at most w w w uses at most w q wq w q occurring auxiliary variables. The number of possible clauses over n + w q n+wq n + w q variables is O w ( ( n + q ) w ) O_w((n+q)^w) O w (( n + q ) w ) , so comparing the number of functions with the number of encodings gives
2 ( n k ) ≤ 2 O w ( q lg ( n + q ) ) = 2 O k , w ( q lg n ) . 2^{\binom{n}{k}} \le2^{O_w(q\lg(n+q))} = 2^{O_{k,w}(q\lg n)}. 2 ( k n ) ≤ 2 O w ( q l g ( n + q )) = 2 O k , w ( q l g n ) . Thus q = Ω k , w ( n k / lg n ) q = \Omega_{k,w}(n^k/\lg n) q = Ω k , w ( n k / lg n ) .
To run the same counting argument without a width bound, we need another way to bound the number of auxiliary variables. The following proposition shows that a minimal encoding has fewer auxiliary variables than clauses.
Proposition 30. Every boolean function f f f with enc ( f ) ≥ 1 \operatorname{enc}(f) \ge1 enc ( f ) ≥ 1 has an encoding ( φ , X , Y ) (\varphi, X, Y) ( φ , X , Y ) such that ∣ φ ∣ = enc ( f ) |\varphi| = \operatorname{enc}(f) ∣ φ ∣ = enc ( f ) and ∣ Y ∣ < enc ( f ) |Y| < \operatorname{enc}(f) ∣ Y ∣ < enc ( f ) .
Its proof relies on a graph-theoretic fact, similar in spirit to the matching argument of Aharoni and Linial for minimal unsatisfiable formulas [2 ] .
Lemma 31. Let G : = ( U ⊔ V , E ) G := (U \sqcup V, E) G := ( U ⊔ V , E ) be a bipartite graph with ∣ V ∣ ≥ ∣ U ∣ > 0 |V| \ge|U| > 0 ∣ V ∣ ≥ ∣ U ∣ > 0 and such that all vertices in V V V have degree at least 1. Then, there is a nonempty subset S ⊆ V S \subseteq V S ⊆ V for which G G G contains a perfect matching between S S S and N G ( S ) N_G(S) N G ( S ) .
Proof. The proof is by induction on ∣ V ∣ |V| ∣ V ∣ . If ∣ V ∣ = 1 |V| = 1 ∣ V ∣ = 1 the only option is ∣ U ∣ = 1 |U| = 1 ∣ U ∣ = 1 and E = { { u , v } } E = \{\{u,v\}\} E = {{ u , v }} for u ∈ U u \in U u ∈ U and v ∈ V v \in V v ∈ V , so the statement holds trivially. Now, for the inductive case, let us say a matching M M M is V V V -saturating if every vertex v ∈ V v \in V v ∈ V belongs to some edge in M M M . Note that a V V V -saturating matching is a perfect matching between V V V and N G ( V ) = U N_G(V) = U N G ( V ) = U . Thus, if a V V V -saturating matching exists we take S : = V S := V S := V and complete the proof. On the other hand, if no such V V V -saturating matching exists, then by Hall’s condition [25 ] , there exists a nonempty subset W ⊆ V W \subseteq V W ⊆ V such that ∣ N G ( W ) ∣ < ∣ W ∣ |N_G(W)| < |W| ∣ N G ( W ) ∣ < ∣ W ∣ . We have ∣ W ∣ ≥ 2 |W| \ge2 ∣ W ∣ ≥ 2 , because otherwise ∣ N G ( W ) ∣ = 0 |N_G(W)| = 0 ∣ N G ( W ) ∣ = 0 , contradicting our assumption that V V V has no isolated vertices. Let W ′ = W ∖ { w } W' = W \setminus\{w\} W ′ = W ∖ { w } for an arbitrary w ∈ W w \in W w ∈ W . Then, W ′ W' W ′ is nonempty and 0 < ∣ N G ( W ′ ) ∣ ≤ ∣ W ′ ∣ 0 < |N_G(W')| \le|W'| 0 < ∣ N G ( W ′ ) ∣ ≤ ∣ W ′ ∣ . Therefore, the induced bipartite graph G ′ : = G [ N G ( W ′ ) , W ′ ] G' := G[N_G(W'), W'] G ′ := G [ N G ( W ′ ) , W ′ ] satisfies the inductive hypothesis, so there is a nonempty subset S ⊆ W ′ S \subseteq W' S ⊆ W ′ for which G ′ G' G ′ contains a perfect matching between S S S and N G ′ ( S ) N_{G'}(S) N G ′ ( S ) . Since N G ′ ( S ) = N G ( S ) N_{G'}(S) = N_G(S) N G ′ ( S ) = N G ( S ) , the set S ⊆ V S \subseteq V S ⊆ V satisfies the conclusion of the lemma. □
Now, to prove Proposition 30 , we need an elementary definition and a lemma.
Definition 32 (Autarky [46 ] ). Given a CNF formula φ \varphi φ over a set of variables X X X , an autarky is a partial assignment α : X → { 0 , 1 } \alpha: X \to\{0,1\} α : X → { 0 , 1 } such that for any clause C ∈ φ C \in\varphi C ∈ φ containing a variable in the domain of α \alpha α , we have α ⊨ C \alpha\models C α ⊨ C .
Lemma 33 ([46 ] , cf. [34 ] , Thm. 4). Let φ \varphi φ be a CNF formula and α \alpha α an autarky for φ \varphi φ . Then, SAT ( φ ) ⟺ SAT ( φ ↾ α ) \operatorname{SAT}(\varphi) \Longleftrightarrow\operatorname{SAT}(\varphi\restriction_\alpha) SAT ( φ ) ⟺ SAT ( φ ↾ α ) .9 {}^{9} 9
We are now ready to prove Proposition 30 .
Proof of Proposition 30 . Let ( φ , X , Y ) (\varphi, X, Y) ( φ , X , Y ) be an encoding for f f f with ∣ φ ∣ = enc ( f ) ≥ 1 |\varphi| = \operatorname{enc}(f) \ge1 ∣ φ ∣ = enc ( f ) ≥ 1 . Let Y ′ ⊆ Y Y' \subseteq Y Y ′ ⊆ Y be the subset of auxiliary variables that appear in φ \varphi φ (with any polarity). Naturally, ( φ , X , Y ′ ) (\varphi, X, Y') ( φ , X , Y ′ ) is also an encoding for f f f . Assume, expecting a contradiction, that ∣ Y ′ ∣ ≥ enc ( f ) |Y'| \ge\operatorname{enc}(f) ∣ Y ′ ∣ ≥ enc ( f ) . Then, construct a bipartite graph G φ : = ( φ ⊔ Y ′ , E ) G_\varphi:= (\varphi\sqcup Y', E) G φ := ( φ ⊔ Y ′ , E ) where there is an edge between an auxiliary variable y ∈ Y ′ y \in Y' y ∈ Y ′ and a clause C ∈ φ C \in\varphi C ∈ φ if and only if y ∈ C y \in C y ∈ C or y ‾ ∈ C \overline{y} \in C y ∈ C . Now, observe that G φ G_\varphi G φ satisfies the conditions of Lemma 31 , so there exists a nonempty set Y ∗ ⊆ Y ′ Y^* \subseteq Y' Y ∗ ⊆ Y ′ and a set φ ∗ : = N G φ ( Y ∗ ) \varphi^* := N_{G_\varphi}(Y^*) φ ∗ := N G φ ( Y ∗ ) such that there is a perfect matching M M M between Y ∗ Y^* Y ∗ and φ ∗ \varphi^* φ ∗ . Let α : Y ∗ → { 0 , 1 } \alpha: Y^* \to\{0,1\} α : Y ∗ → { 0 , 1 } be the assignment defined by
α ( y ) = { 1 if y ∈ M ( y ) 0 if y ‾ ∈ M ( y ) , \alpha(y) =
\begin{cases}
1 & \text{if } y \in M(y) \\
0 & \text{if } \overline{y} \in M(y),
\end{cases} α ( y ) = { 1 0 if y ∈ M ( y ) if y ∈ M ( y ) ,
and observe that α \alpha α is an autarky for φ \varphi φ . Let τ : X → { 0 , 1 } \tau: X \to\{0,1\} τ : X → { 0 , 1 } be an arbitrary assignment to the input variables. Note that α \alpha α and τ \tau τ have disjoint domains, so α \alpha α is still an autarky for φ ↾ τ \varphi\restriction\tau φ ↾ τ , and by Lemma 33 , we have SAT ( φ ↾ τ ) ⟺ SAT ( ( φ ↾ τ ) ↾ α ) \operatorname{SAT}(\varphi\restriction\tau) \Longleftrightarrow\operatorname{SAT}((\varphi\restriction\tau)\restriction\alpha) SAT ( φ ↾ τ ) ⟺ SAT (( φ ↾ τ ) ↾ α ) . Since ( φ ↾ τ ) ↾ α = ( φ ↾ α ) ↾ τ (\varphi\restriction\tau)\restriction\alpha= (\varphi\restriction\alpha)\restriction\tau ( φ ↾ τ ) ↾ α = ( φ ↾ α ) ↾ τ , it follows that ( φ ↾ α , X , Y ∖ Y ∗ ) (\varphi\restriction\alpha, X, Y\setminus Y^*) ( φ ↾ α , X , Y ∖ Y ∗ ) is an encoding of f f f , and since ∣ φ ↾ α ∣ = ∣ φ ∣ − ∣ φ ∗ ∣ < ∣ φ ∣ |\varphi\restriction\alpha| = |\varphi|-|\varphi^*| < |\varphi| ∣ φ ↾ α ∣ = ∣ φ ∣ − ∣ φ ∗ ∣ < ∣ φ ∣ , we conclude that ∣ φ ↾ α ∣ < enc ( f ) |\varphi\restriction\alpha| < \operatorname{enc}(f) ∣ φ ↾ α ∣ < enc ( f ) , a contradiction.
We now state the following counting lemma, which we use to prove all of our lower bounds for enc \operatorname{enc} enc .
Lemma 34. For all integers n ≥ 1 n \ge1 n ≥ 1 and q ≥ 1 q \ge1 q ≥ 1 , at most 3 ( n + q ) q + 1 3^{(n+q)q}+1 3 ( n + q ) q + 1 functions f : { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^n \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } satisfy enc ( f ) ≤ q \operatorname{enc}(f) \le q enc ( f ) ≤ q .
Proof. The constant-1 function is the only f f f with enc ( f ) = 0 \operatorname{enc}(f)=0 enc ( f ) = 0 . If 1 ≤ enc ( f ) ≤ q 1 \le\operatorname{enc}(f) \le q 1 ≤ enc ( f ) ≤ q , then by Proposition 30 , f f f has an encoding with enc ( f ) \operatorname{enc}(f) enc ( f ) clauses and fewer than q q q auxiliary variables. This encoding has no tautological clauses, since deleting one would give a smaller encoding. Rename its auxiliary variables from a fixed set of q q q names, and pad it to exactly q q q clauses by repeating a clause. The result is a sequence of q q q non-tautological clauses over n + q n+q n + q fixed variables, and it determines f f f . Each such clause is determined by deciding, for each variable, whether it appears positively, appears negatively, or is absent, so there are at most 3 n + q 3^{n+q} 3 n + q of them. Hence at most 3 ( n + q ) q 3^{(n+q)q} 3 ( n + q ) q functions satisfy 1 ≤ enc ( f ) ≤ q 1 \le\operatorname{enc}(f) \le q 1 ≤ enc ( f ) ≤ q .
Without a width bound, the counting argument, now based on Lemma 34 , gives a much weaker lower bound.
Proposition 35. For every fixed k ≥ 2 k \ge2 k ≥ 2 , there are k k k -CNF functions on n n n inputs with enc ( f ) = Ω k ( n k / 2 ) \operatorname{enc}(f)=\Omega_k(n^{k/2}) enc ( f ) = Ω k ( n k /2 ) .
Proof. For n ≥ k n \ge k n ≥ k , let q : = max H enc ( f H ) ≥ 1 q := \max_H \operatorname{enc}(f_H) \ge1 q := max H enc ( f H ) ≥ 1 , where the f H f_H f H are the 2 ( n k ) 2^{\binom{n}{k}} 2 ( k n ) functions from the proof of Proposition 29 . By Lemma 34 , 2 ( n k ) ≤ 3 ( n + q ) q + 1 2^{\binom{n}{k}} \le3^{(n+q)q}+1 2 ( k n ) ≤ 3 ( n + q ) q + 1 , hence
q ≥ n 2 4 + log 3 ( 2 ( n k ) − 1 ) − n 2 = Ω k ( n k / 2 ) . q \ge\sqrt{\frac{n^2}{4}+\log_3\left(2^{\binom{n}{k}}-1\right)}-\frac{n}{2}=\Omega_k(n^{k/2}). q ≥ 4 n 2 + log 3 ( 2 ( k n ) − 1 ) − 2 n = Ω k ( n k /2 ) .
Together with Corollary 9 , Proposition 35 shows that almost all k k k -CNF functions satisfy enc ( f ) = Θ ~ ( n k / 2 ) \operatorname{enc}(f)=\widetilde{\Theta}(n^{k/2}) enc ( f ) = Θ ( n k /2 ) .10 Thus, any better worst-case lower bound must come from functions that are far from random. Even for independent-set constraints (k = 2 k=2 k = 2 ), a large gap remains: Proposition 35 gives only Ω ( n ) \Omega(n) Ω ( n ) , while the best upper bound we prove is n 2 / 2 Ω ( lg n ) n^2/2^{\Omega(\sqrt{\lg n})} n 2 / 2 Ω ( l g n ) (Theorem 4). Closing this gap is a fascinating open problem. We expect the upper bound to be closer to the truth, but we currently lack a technique for proving superlinear lower bounds for enc ( I S G ) \operatorname{enc}(\mathrm{IS}_{G}) enc ( IS G ) .
Arbitrary and Sparsely Supported Functions
In this section, we prove Theorem 6, which we restate for convenience.
Theorem 6. For all 1 ≤ M ≤ 2 n − 1 1 \le M \le2^{n-1} 1 ≤ M ≤ 2 n − 1 , we have
enc ( n , M ) : = max { enc ( f ) : f : { 0 , 1 } n → { 0 , 1 } , ∣ f − 1 ( 1 ) ∣ = M } = Θ ( n + M ( n − lg M ) ) . \operatorname{enc}(n,M):=\max\left\{\operatorname{enc}(f): f:\{0,1\}^n\to\{0,1\},\ |f^{-1}(1)|=M\right\}=\Theta\left(n+\sqrt{M(n-\lg M)}\right). enc ( n , M ) := max { enc ( f ) : f : { 0 , 1 } n → { 0 , 1 } , ∣ f − 1 ( 1 ) ∣ = M } = Θ ( n + M ( n − lg M ) ) .
We give some extra consideration to the case of densely supported functions, establishing the following explicit constant bounds:
Proposition 36. Let enc ( n ) \operatorname{enc}(n) enc ( n ) be the maximum of enc ( f ) \operatorname{enc}(f) enc ( f ) over all functions f : { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^n \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } , and let c : = 1 / lg 3 ≈ 0.794 c := 1/\sqrt{\lg3} \approx0.794 c := 1/ lg 3 ≈ 0.794 . Then, we have ( c − o ( 1 ) ) 2 n ≤ enc ( n ) ≤ ( 2 2 + o ( 1 ) ) 2 n (c-o(1))\sqrt{2^n} \le\operatorname{enc}(n) \le(2\sqrt{2}+o(1))\sqrt{2^n} ( c − o ( 1 )) 2 n ≤ enc ( n ) ≤ ( 2 2 + o ( 1 )) 2 n .
Establishing an exact constant for the upper and lower bounds in this model remains an open question. We expect that the upper bound is tight.
Bounds of the same order, often with exact constants, are classical in related models of computation such as depth-3 A C 0 \mathrm{AC}^0 AC 0 circuits, circuits with free gates, and nondeterministic branching programs (see § 1.4 ); in particular, Nechiporuk’s construction for nondeterministic branching programs [47 ] translates directly into an encoding with ( 4 + o ( 1 ) ) 2 n (4+o(1))\sqrt{2^n} ( 4 + o ( 1 )) 2 n clauses, which the upper bound of Proposition 36 improves.
Upper bound for sparse functions
We now bootstrap Lemma 13 to prove the upper bound in Theorem 6. Our construction is based on a succinct static dictionary, which stores a function f : { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^n \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } with ∣ f − 1 ( 1 ) ∣ = M |f^{-1}(1)|=M ∣ f − 1 ( 1 ) ∣ = M using close to the information-theoretic minimum of lg ( 2 n M ) \lg\binom{2^n}{M} lg ( M 2 n ) bits and evaluates f f f in O ( 1 ) O(1) O ( 1 ) time on a word RAM. Such dictionaries go back to Brodnik and Munro [7 ] ; Pagh [49 ] and Pătraşcu [Păt08] subsequently reduced the number of extra bits. The following is the best known such dictionary, which we restate in a slightly weakened form convenient for our purposes.11
Theorem 37 (Hu, Liang, Yu, Zhang, and Zhou [27 ] ). Let f : { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^n \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } with ∣ f − 1 ( 1 ) ∣ = M |f^{-1}(1)|=M ∣ f − 1 ( 1 ) ∣ = M , where 2 n / 2 < M ≤ 2 n − 1 2^{n/2}<M\le2^{n-1} 2 n /2 < M ≤ 2 n − 1 . There is a string σ f \sigma_f σ f of
lg ( 2 n M ) + o ( M ) \lg\binom{2^n}{M}+o(M) lg ( M 2 n ) + o ( M ) bits such that a word RAM with word size Θ ( n ) \Theta(n) Θ ( n ) whose memory holds σ f \sigma_f σ f computes f ( x ⃗ ) f(\vec{x}) f ( x ) from x ⃗ \vec{x} x in worst-case O ( 1 ) O(1) O ( 1 ) time.
Our encoding will be based on unrolling the lookup operations; since the lookup time is O ( 1 ) O(1) O ( 1 ) , the size of our encoding will be dominated by the cost of encoding the query algorithm’s memory accesses (assuming M M M is large). The key step is the following lemma, which may be of independent interest. If we identify a function with the binary string encoding its truth table, then the lemma shows that an entire contiguous block of bits can be fetched at essentially the same cost as fetching a single bit, even when the block is as long as the square root of the memory size. Here, we only need blocks consisting of a single word of the RAM, i.e., Θ ( n ) \Theta(n) Θ ( n ) bits.
Lemma 38. Let f : { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^n \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } , and let w = 2 k w=2^k w = 2 k with 0 ≤ k ≤ n 0\le k\le n 0 ≤ k ≤ n . For j ∈ [ 0 , 2 n − k − 1 ] j\in[0,2^{n-k}-1] j ∈ [ 0 , 2 n − k − 1 ] , the j j j th block of f f f is the string ( f ( j w ) , f ( j w + 1 ) , … , f ( j w + w − 1 ) ) ∈ { 0 , 1 } w (f(jw),f(jw+1),\ldots,f(jw+w-1))\in\{0,1\}^w ( f ( j w ) , f ( j w + 1 ) , … , f ( j w + w − 1 )) ∈ { 0 , 1 } w , where each argument of f f f is identified with its n n n -bit binary representation. Define g w : { 0 , 1 } n − k × { 0 , 1 } w → { 0 , 1 } g_w:\{0,1\}^{n-k}\times\{0,1\}^w\to\{0,1\} g w : { 0 , 1 } n − k × { 0 , 1 } w → { 0 , 1 } by letting g w ( j , z ⃗ ) = 1 g_w(j,\vec{z})=1 g w ( j , z ) = 1 if and only if z ⃗ \vec{z} z is the j j j th block of f f f . Then,
enc ( g w ) = O ( 2 n + w ) . \operatorname{enc}(g_w)=O\left(\sqrt{2^n}+w\right). enc ( g w ) = O ( 2 n + w ) .
Proof. First suppose that w ≥ n w \ge n w ≥ n . Then g w g_w g w has n − k + w ≤ 2 w n-k+w \le2w n − k + w ≤ 2 w inputs. For each block index j j j , exactly one z ⃗ \vec{z} z satisfies g w ( j , z ⃗ ) = 1 g_w(j,\vec{z})=1 g w ( j , z ) = 1 , so ∣ g w − 1 ( 1 ) ∣ = 2 n − k \lvert g_w^{-1}(1)\rvert=2^{n-k} ∣ g w − 1 ( 1 )∣ = 2 n − k . By Lemma 13 ,
enc ( g w ) = O ( w + w ⋅ 2 n − k ) = O ( 2 n + w ) . \operatorname{enc}(g_w)=O\left(w+\sqrt{w\cdot2^{n-k}}\right)=O\left(\sqrt{2^n}+w\right). enc ( g w ) = O ( w + w ⋅ 2 n − k ) = O ( 2 n + w ) .
If w < n w<n w < n , let w ′ w' w ′ be the power of two with n ≤ w ′ < 2 n n\le w'<2n n ≤ w ′ < 2 n . Then enc ( g w ) ≤ enc ( g w ′ ) + O ( w ′ ) = O ( 2 n + w ) \operatorname{enc}(g_w)\le\operatorname{enc}(g_{w'})+O(w')=O\left(\sqrt{2^n}+w\right) enc ( g w ) ≤ enc ( g w ′ ) + O ( w ′ ) = O ( 2 n + w ) .
We are now ready to prove the upper bound in Theorem 6.
Lemma 39. For all integers n ≥ 1 n\ge1 n ≥ 1 and 1 ≤ M ≤ 2 n − 1 1\le M\le2^{n-1} 1 ≤ M ≤ 2 n − 1 , we have enc ( n , M ) = O ( n + M ( n − lg M ) ) \operatorname{enc}(n,M)=O\left(n+\sqrt{M(n-\lg M)}\right) enc ( n , M ) = O ( n + M ( n − lg M ) ) .
Proof. Let f : { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^n\to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } with ∣ f − 1 ( 1 ) ∣ = M \lvert f^{-1}(1)\rvert=M ∣ f − 1 ( 1 )∣ = M , where 1 ≤ M ≤ 2 n − 1 1\le M\le2^{n-1} 1 ≤ M ≤ 2 n − 1 . If M ≤ 2 n / 2 M\le2^{n/2} M ≤ 2 n /2 , then n − lg M ≥ n / 2 n-\lg M\ge n/2 n − lg M ≥ n /2 , so Lemma 13 already gives O ( n + n M ) = O ( n + M ( n − lg M ) ) O(n+\sqrt{nM})=O\left(n+\sqrt{M(n-\lg M)}\right) O ( n + n M ) = O ( n + M ( n − lg M ) ) clauses. Hence, we may assume M > 2 n / 2 M>2^{n/2} M > 2 n /2 . Since 2 n ≤ ( 2 n M ) ≤ ( e 2 n / M ) M 2^n\le\binom{2^n}{M}\le(e2^n/M)^M 2 n ≤ ( M 2 n ) ≤ ( e 2 n / M ) M and n − lg M ≥ 1 n-\lg M\ge1 n − lg M ≥ 1 , the string σ f \sigma_f σ f from Theorem 37 has S = O ( M ( n − lg M ) ) S=O(M(n-\lg M)) S = O ( M ( n − lg M )) bits, and note that S ≥ n S\ge n S ≥ n . Let the word size be a power of two w = 2 k = Θ ( n ) = O ( S ) w=2^k=\Theta(n)=O(S) w = 2 k = Θ ( n ) = O ( S ) , and let f ′ : { 0 , 1 } n ′ → { 0 , 1 } f':\{0,1\}^{n'}\to\{0,1\} f ′ : { 0 , 1 } n ′ → { 0 , 1 } be the function whose truth table is σ f \sigma_f σ f padded with zeros to a length 2 n ′ = O ( S ) 2^{n'}=O(S) 2 n ′ = O ( S ) that is at least w w w . Then the words of memory are exactly the blocks of f ′ f' f ′ .
The query algorithm runs a fixed program for O ( 1 ) O(1) O ( 1 ) steps, so we can unroll it into a straight-line program with O ( 1 ) O(1) O ( 1 ) memory reads and O ( 1 ) O(1) O ( 1 ) word operations: at each step, perform every instruction of the program and keep the result of the one selected by the program counter. Truncating each read address to its n ′ − k n'-k n ′ − k low-order bits keeps every read in range without affecting the actual computation. We introduce auxiliary variables for the register contents after each step, and take the conjunction of the encodings of the individual steps:
each memory read is checked by the encoding of g w g_w g w for f ′ f' f ′ from Lemma 38 , with O ( 2 n ′ + w ) = O ( M ( n − lg M ) + n ) O(\sqrt{2^{n'}}+w)=O\left(\sqrt{M(n-\lg M)}+n\right) O ( 2 n ′ + w ) = O ( M ( n − lg M ) + n ) clauses;
each word operation, including multiplication and division, is computed by a circuit with O ( n 2 ) O(n^2) O ( n 2 ) gates, whose Tseitin encoding has O ( n 2 ) O(n^2) O ( n 2 ) clauses.
Finally, a unit clause requires the output to be 1. Each step’s encoding admits only the correct output for given inputs, so the resulting formula encodes f f f with
O ( M ( n − lg M ) + n 2 ) O\left(\sqrt{M(n-\lg M)+n^2}\right) O ( M ( n − lg M ) + n 2 )
clauses. Since M > 2 n / 2 M>2^{n/2} M > 2 n /2 , we have M ( n − lg M ) ≥ 2 n / 4 \sqrt{M(n-\lg M)}\ge2^{n/4} M ( n − lg M ) ≥ 2 n /4 , which asymptotically absorbs the n 2 n^2 n 2 term.
Lower bounds
We now prove the lower bounds in Theorem 6 and Proposition 36 . Both are proved via an information-theoretic argument, using the counting bound of Lemma 34 .
Lemma 40. For all integers n ≥ 1 n\ge1 n ≥ 1 and 1 ≤ M ≤ 2 n − 1 1\le M\le2^{n-1} 1 ≤ M ≤ 2 n − 1 , we have
enc ( n , M ) ≥ max { n , 1 2 M ( n − lg M ) } = Ω ( n + M ( n − lg M ) ) . \operatorname{enc}(n,M)\ge\max\left\{n,\frac{1}{2}\sqrt{M(n-\lg M)}\right\}=\Omega\left(n+\sqrt{M(n-\lg M)}\right). enc ( n , M ) ≥ max { n , 2 1 M ( n − lg M ) } = Ω ( n + M ( n − lg M ) ) .
Proof. Choose a support of size M M M containing 0 n 0^n 0 n but none of the n n n unit vectors. This is possible because 2 n − n ≥ 2 n − 1 2^n-n \ge2^{n-1} 2 n − n ≥ 2 n − 1 for every n ≥ 1 n \ge1 n ≥ 1 . Fix an accepting auxiliary assignment of any encoding at 0 n 0^n 0 n . Flipping the i i i th input to obtain a unit vector must falsify some clause under the same auxiliary assignment. Such a clause had x i ‾ \overline{x_i} x i as its only true literal at the original full assignment. One clause cannot have this property for two distinct input bits, so at least n n n clauses are necessary. Consequently enc ( n , M ) ≥ n \operatorname{enc}(n,M) \ge n enc ( n , M ) ≥ n .
Set q : = enc ( n , M ) ≥ n ≥ 1 q := \operatorname{enc}(n,M) \ge n \ge1 q := enc ( n , M ) ≥ n ≥ 1 . By Lemma 34 and ( 2 n M ) ≥ ( 2 n / M ) M \binom{2^n}{M} \ge(2^n/M)^M ( M 2 n ) ≥ ( 2 n / M ) M ,
2 M ( n − lg M ) ≤ ( 2 n M ) ≤ 3 ( n + q ) q + 1 ≤ 4 ( n + q ) q ≤ 2 4 q 2 . 2^{M(n-\lg M)} \le\binom{2^n}{M} \le3^{(n+q)q}+1 \le4^{(n+q)q} \le2^{4q^2}. 2 M ( n − l g M ) ≤ ( M 2 n ) ≤ 3 ( n + q ) q + 1 ≤ 4 ( n + q ) q ≤ 2 4 q 2 .
Here we used 3 r + 1 ≤ 4 r 3^r+1 \le4^r 3 r + 1 ≤ 4 r for positive integers r r r . Taking logarithms gives q ≥ 1 2 M ( n − lg M ) q \ge\frac{1}{2}\sqrt{M(n-\lg M)} q ≥ 2 1 M ( n − lg M ) .
Lemma 41. With c : = 1 / lg 3 c := 1/\sqrt{\lg3} c := 1/ lg 3 , we have enc ( n ) ≥ ( c − o ( 1 ) ) 2 n \operatorname{enc}(n) \ge(c-o(1))\sqrt{2^n} enc ( n ) ≥ ( c − o ( 1 )) 2 n .
Proof. Let q : = enc ( n ) q := \operatorname{enc}(n) q := enc ( n ) . Every boolean function on n n n inputs has an encoding with at most q q q clauses, so Lemma 34 gives 2 2 n ≤ 3 ( n + q ) q + 1 2^{2^n} \le3^{(n+q)q}+1 2 2 n ≤ 3 ( n + q ) q + 1 . Solving for q q q , we obtain
q ≥ n 2 4 + log 3 ( 2 2 n − 1 ) − n 2 = c 2 n − n 2 + o ( 1 ) = ( c − o ( 1 ) ) 2 n . q \ge\sqrt{\frac{n^2}{4}+\log_3(2^{2^n}-1)}-\frac{n}{2}
= c\sqrt{2^n}-\frac{n}{2}+o(1)
= (c-o(1))\sqrt{2^n}. q ≥ 4 n 2 + log 3 ( 2 2 n − 1 ) − 2 n = c 2 n − 2 n + o ( 1 ) = ( c − o ( 1 )) 2 n .
Upper bound for arbitrary functions
We now give a constructive upper bound on enc ( n ) \operatorname{enc}(n) enc ( n ) , which is relatively similar to the construction of Dančík for depth-3 A C 0 \mathrm{AC}^0 AC 0 circuits [Dan96].
Lemma 42. Every f : { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^n \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } satisfies enc ( f ) ≤ ( 2 2 + o ( 1 ) ) 2 n \operatorname{enc}(f) \le(2\sqrt{2}+o(1))\sqrt{2^n} enc ( f ) ≤ ( 2 2 + o ( 1 )) 2 n . In particular, enc ( n ) ≤ ( 2 2 + o ( 1 ) ) 2 n \operatorname{enc}(n) \le(2\sqrt{2}+o(1))\sqrt{2^n} enc ( n ) ≤ ( 2 2 + o ( 1 )) 2 n .
Proof. Let f : { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^n \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } be arbitrary, and let x 1 , … , x n x_1,\ldots,x_n x 1 , … , x n be input variables. First, introduce auxiliary variables a 1 , … , a ⌊ n / 2 ⌋ a_1,\ldots,a_{\lfloor n/2\rfloor} a 1 , … , a ⌊ n /2 ⌋ and b 1 , … , b ⌈ ( n + 1 ) / 2 ⌉ b_1,\ldots,b_{\lceil(n+1)/2\rceil} b 1 , … , b ⌈( n + 1 ) /2 ⌉ . Given an assignment
τ : { x 1 , … , x n , a 1 , … , a ⌊ n / 2 ⌋ , b 1 , … , b ⌈ ( n + 1 ) / 2 ⌉ } → { 0 , 1 } , \tau:\{x_1,\ldots,x_n,a_1,\ldots,a_{\lfloor n/2\rfloor},b_1,\ldots,b_{\lceil(n+1)/2\rceil}\}\to\{0,1\}, τ : { x 1 , … , x n , a 1 , … , a ⌊ n /2 ⌋ , b 1 , … , b ⌈( n + 1 ) /2 ⌉ } → { 0 , 1 } ,
we can naturally define X τ X_\tau X τ , A τ A_\tau A τ , and B τ B_\tau B τ to be the integers whose binary representations are given by the x x x -, a a a -, and b b b -variables respectively. Let K : = ⌈ 2 ( n + 1 ) / 2 ⌉ K:=\left\lceil2^{(n+1)/2}\right\rceil K := ⌈ 2 ( n + 1 ) /2 ⌉ . Then, we want to encode that any satisfying assignment τ \tau τ will satisfy
X τ = A τ ⋅ K + B τ and B τ < K , X_\tau=A_\tau\cdot K+B_\tau\qquad\text{and}\qquad B_\tau<K, X τ = A τ ⋅ K + B τ and B τ < K ,
which can be done by applying the Tseitin transformation to circuits for addition and multiplication, which results in poly ( n ) \operatorname{poly}(n) poly ( n ) clauses.
Let A : = [ 0 , ⌊ ( 2 n − 1 ) / K ⌋ ] \mathcal{A}:=[0,\lfloor(2^n-1)/K\rfloor] A := [ 0 , ⌊( 2 n − 1 ) / K ⌋] . Every X τ < 2 n X_\tau<2^n X τ < 2 n satisfies A τ = ⌊ X τ / K ⌋ ∈ A A_\tau=\lfloor X_\tau/K\rfloor\in\mathcal{A} A τ = ⌊ X τ / K ⌋ ∈ A . Moreover, K ≥ 2 ⌈ n / 2 ⌉ K\ge2^{\lceil n/2\rceil} K ≥ 2 ⌈ n /2 ⌉ , so every element of A \mathcal{A} A is less than 2 ⌊ n / 2 ⌋ 2^{\lfloor n/2\rfloor} 2 ⌊ n /2 ⌋ ; hence distinct elements of A \mathcal{A} A have distinct ⌊ n / 2 ⌋ \lfloor n/2\rfloor ⌊ n /2 ⌋ -bit binary representations. Next, for each A ∈ A A\in\mathcal{A} A ∈ A , introduce an auxiliary variable y A y_A y A . Let A [ i ] A[i] A [ i ] be the i i i th bit of A A A 's binary representation. Then, add the following clauses:
∀ i ∈ [ ⌊ n / 2 ⌋ ] , ( a i ‾ ∨ ⋁ A ∈ A A [ i ] = 1 y A ) ∧ ( a i ∨ ⋁ A ∈ A A [ i ] = 0 y A ) (7) \forall i \in[\lfloor n/2 \rfloor],\quad\left(\overline{a_i} \lor\bigvee_{\substack{A\in\mathcal{A}\\ A[i]=1}} y_A\right) \land\left(a_i \lor\bigvee_{\substack{A\in\mathcal{A}\\ A[i]=0}} y_A\right) \tag*{(7)} ∀ i ∈ [⌊ n /2 ⌋] , a i ∨ A ∈ A A [ i ] = 1 ⋁ y A ∧ a i ∨ A ∈ A A [ i ] = 0 ⋁ y A (7)
AtMostOne ( { y A ∣ A ∈ A } ) . (8) \operatorname{AtMostOne}\left(\{y_A \mid A \in\mathcal{A}\}\right). \tag*{(8)} AtMostOne ( { y A ∣ A ∈ A } ) . (8)
Intuitively, (2) states that each a i a_i a i variable implies a disjunction of the A A A -variables compatible with it, and then (3) enforces that only one A A A -variable is assigned to 1.
Now, for each B ∈ [ 0 , K − 1 ] B \in[0,K-1] B ∈ [ 0 , K − 1 ] , let S B : = { A ∈ A ∣ A ⋅ K + B < 2 n and f ( A ⋅ K + B ) = 1 } S_B := \{A \in\mathcal{A} \mid A \cdot K+B<2^n \text{ and } f(A\cdot K+B)=1\} S B := { A ∈ A ∣ A ⋅ K + B < 2 n and f ( A ⋅ K + B ) = 1 } , where by f ( A ⋅ K + B ) f(A\cdot K+B) f ( A ⋅ K + B ) we mean the value of f f f applied to the n n n -bit binary representation of A ⋅ K + B A\cdot K+B A ⋅ K + B . Intuitively, S B S_B S B is the set of values of A ∈ A A \in\mathcal{A} A ∈ A that are “compatible” with B B B . Moreover, for each B ∈ [ 0 , K − 1 ] B \in[0,K-1] B ∈ [ 0 , K − 1 ] , let
L B : = { b i ∣ B [ i ] = 1 } ∪ { b i ‾ ∣ B [ i ] = 0 } , L_B := \{b_i \mid B[i]=1\} \cup\{\overline{b_i} \mid B[i]=0\}, L B := { b i ∣ B [ i ] = 1 } ∪ { b i ∣ B [ i ] = 0 } ,
where B [ i ] B[i] B [ i ] is the i i i th bit of B B B ’s binary representation. The encoding is then completed by adding clauses
∀ B ∈ [ 0 , K − 1 ] , ( ⋁ A ∈ S B y A ∨ ⋁ ℓ ∈ L B ℓ ‾ ) . (9) \forall B \in[0,K-1],\quad\left(\bigvee_{A\in S_B} y_A \lor\bigvee_{\ell\in L_B} \overline{\ell}\right). \tag*{(9)} ∀ B ∈ [ 0 , K − 1 ] , ( A ∈ S B ⋁ y A ∨ ℓ ∈ L B ⋁ ℓ ) . (9)
First, let us analyze the number of clauses. The constraints enforcing that
X τ = A τ ⋅ K + B τ and B τ < K , X_\tau=A_\tau\cdot K+B_\tau\qquad\text{and}\qquad B_\tau<K, X τ = A τ ⋅ K + B τ and B τ < K ,
for all τ \tau τ use only poly ( n ) = o ( 2 n ) \operatorname{poly}(n)=o(\sqrt{2^n}) poly ( n ) = o ( 2 n ) clauses. Constraint (2) uses at most n n n clauses, and by Proposition 12 , the constraint in (3) can be encoded with ( 2 + o ( 1 ) ) ∣ A ∣ = ( 2 + o ( 1 ) ) 2 n / 2 (2+o(1))|\mathcal{A}|=(\sqrt{2}+o(1))2^{n/2} ( 2 + o ( 1 )) ∣ A ∣ = ( 2 + o ( 1 )) 2 n /2 clauses, since ∣ A ∣ ≤ 2 n / K + 1 |\mathcal{A}|\le2^n/K+1 ∣ A ∣ ≤ 2 n / K + 1 and K > 2 ( n + 1 ) / 2 − 1 K>2^{(n+1)/2}-1 K > 2 ( n + 1 ) /2 − 1 give ∣ A ∣ = ( 1 + o ( 1 ) ) 2 ( n − 1 ) / 2 |\mathcal{A}|=(1+o(1))2^{(n-1)/2} ∣ A ∣ = ( 1 + o ( 1 )) 2 ( n − 1 ) /2 . Finally, (4) includes K = ⌈ 2 ( n + 1 ) / 2 ⌉ ≤ 2 ⋅ 2 n / 2 K=\lceil2^{(n+1)/2}\rceil\le\sqrt{2}\cdot2^{n/2} K = ⌈ 2 ( n + 1 ) /2 ⌉ ≤ 2 ⋅ 2 n /2 clauses. Thus, the total number of clauses is ( 2 2 + o ( 1 ) ) 2 n (2\sqrt{2}+o(1))\sqrt{2^n} ( 2 2 + o ( 1 )) 2 n .
Now, to prove correctness, let τ : { x 1 , … , x n } → { 0 , 1 } \tau:\{x_1,\ldots,x_n\}\to\{0,1\} τ : { x 1 , … , x n } → { 0 , 1 } be an arbitrary assignment, and let X τ X_\tau X τ be the integer whose binary representation is given by the x x x -variables. Let A τ A_\tau A τ and B τ B_\tau B τ be the unique nonnegative integers such that
X τ = A τ ⋅ K + B τ and B τ < K . X_\tau=A_\tau\cdot K+B_\tau\qquad\text{and}\qquad B_\tau<K. X τ = A τ ⋅ K + B τ and B τ < K .
First, assume that f ( τ ( x 1 ) , … , τ ( x n ) ) = 1 f(\tau(x_1),\ldots,\tau(x_n))=1 f ( τ ( x 1 ) , … , τ ( x n )) = 1 . Let Y : = { y A ∣ A ∈ A } \mathcal{Y}:=\{y_A\mid A\in\mathcal{A}\} Y := { y A ∣ A ∈ A } , and consider the assignment θ : Y → { 0 , 1 } \theta:\mathcal{Y}\to\{0,1\} θ : Y → { 0 , 1 } defined by
θ ( y ) = { 1 if y = y A τ 0 otherwise. \theta(y)=
\begin{cases}
1 & \text{if } y=y_{A_\tau}\\
0 & \text{otherwise.}
\end{cases} θ ( y ) = { 1 0 if y = y A τ otherwise.
Now, by correctness of the encoding for AtMostOne, the assignment θ \theta θ can be extended into an assignment θ ′ \theta' θ ′ that assigns the auxiliary variables internal to (3) satisfying said constraint. Then, extend θ ′ \theta' θ ′ into an assignment θ ′ ′ \theta'' θ ′′ that assigns the a a a - and b b b -variables so that they are the binary representations of A τ A_\tau A τ and B τ B_\tau B τ respectively. Note that at this point the full assignment τ ∪ θ ′ ′ \tau\cup\theta'' τ ∪ θ ′′ satisfies (2) and (3). Then, for each B ∈ [ 0 , K − 1 ] ∖ { B τ } B\in[0,K-1]\setminus\{B_\tau\} B ∈ [ 0 , K − 1 ] ∖ { B τ } some literal in L B L_B L B must be false, which satisfies (4), and since A τ ∈ S B τ A_\tau\in S_{B_\tau} A τ ∈ S B τ , (4) is also satisfied for B = B τ B=B_\tau B = B τ .
Conversely, assume f ( τ ( x 1 ) , … , τ ( x n ) ) = 0 f(\tau(x_1),\ldots,\tau(x_n))=0 f ( τ ( x 1 ) , … , τ ( x n )) = 0 , and assume for a contradiction that some assignment θ \theta θ of the auxiliary variables is such that τ ∪ θ \tau\cup\theta τ ∪ θ satisfies all clauses. Then, the assignment to the a a a - and b b b -variables must be such that they are the binary representations of A τ A_\tau A τ and B τ B_\tau B τ respectively. Also, by correctness of the encoding of AtMostOne we have that θ ( y A ) = 1 \theta(y_A) = 1 θ ( y A ) = 1 for at most one A ∈ A A \in\mathcal{A} A ∈ A . Then, since τ ∪ θ \tau\cup\theta τ ∪ θ satisfies (2) for i = 1 i = 1 i = 1 (any i i i works), then by the resolution rule we have that at least one y A y_A y A variable must be true. Thus, exactly one variable in Y \mathcal{Y} Y is assigned to 1 by θ \theta θ , and we claim that it must be y A τ y_{A_\tau} y A τ . Indeed, if it were y A y_A y A for some A ≠ A τ A \ne A_\tau A = A τ , and i i i is an index such that A [ i ] ≠ A τ [ i ] A[i] \ne A_\tau[i] A [ i ] = A τ [ i ] (which exists because A , A τ ∈ A A, A_\tau\in\mathcal{A} A , A τ ∈ A ), then (2) would not be satisfied for said i i i , giving us the desired contradiction. Now, if the only true variable in Y \mathcal{Y} Y is y A τ y_{A_\tau} y A τ , then constraint (4) is not satisfied for B = B τ B = B_\tau B = B τ , since by assumption A τ ∉ S B τ A_\tau\notin S_{B_\tau} A τ ∈ / S B τ , which yields the desired contradiction.
A Characterization of Encoding Complexity
A De Morgan circuit is a circuit over the basis { ∧ , ∨ , ¬ } \{\land, \lor, \neg\} { ∧ , ∨ , ¬ } such that ¬ \neg ¬ is only applied to input variables. We allow constants 0 and 1, and we allow both ∧ \land ∧ -gates and ∨ \lor ∨ -gates to have unbounded fan-in. In other words, a De Morgan circuit on the input variables x 1 , … , x n x_1, \ldots, x_n x 1 , … , x n is a monotone circuit over the basis { ∧ , ∨ } \{\land, \lor\} { ∧ , ∨ } on the input literals x 1 , … , x n , x 1 ‾ , … , x n ‾ x_1, \ldots, x_n, \overline{x_1}, \ldots, \overline{x_n} x 1 , … , x n , x 1 , … , x n . If a De Morgan circuit C C C on the input variables x 1 , … , x n , y 1 , … , y m x_1, \ldots, x_n, y_1, \ldots, y_m x 1 , … , x n , y 1 , … , y m computes a function g : { 0 , 1 } n + m → { 0 , 1 } g : \{0,1\}^{n+m} \to\{0,1\} g : { 0 , 1 } n + m → { 0 , 1 } such that
∀ x ⃗ ∈ { 0 , 1 } n , f ( x ⃗ ) = 1 ⟺ ∃ y ⃗ ∈ { 0 , 1 } m . g ( x ⃗ , y ⃗ ) = 1 , \forall\vec{x} \in\{0,1\}^{n}, \quad f(\vec{x}) = 1 \Longleftrightarrow\exists\vec{y} \in\{0,1\}^{m}.\ g(\vec{x},\vec{y}) = 1, ∀ x ∈ { 0 , 1 } n , f ( x ) = 1 ⟺ ∃ y ∈ { 0 , 1 } m . g ( x , y ) = 1 ,
then we say that C C C is a nondeterministic De Morgan circuit computing f f f . Our metric for these circuits, which we will show coincides with CNF encoding complexity, is the number of wires entering its ∧ \land ∧ -gates:
Definition 43. Given a boolean function f : { 0 , 1 } n → { 0 , 1 } f : \{0,1\}^{n} \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } , let nondet-wires ∧ ( f ) \operatorname{nondet\text{-}wires}_{\land}(f) nondet - wires ∧ ( f ) be the minimum, over all nondeterministic De Morgan circuits computing f f f , of the total fan-in of their ∧ \land ∧ -gates.
We prove in Proposition 44 that this measure coincides exactly with encoding complexity, except for functions with enc ( f ) = 1 \operatorname{enc}(f) = 1 enc ( f ) = 1 , which are computed by a single ∨ \lor ∨ -gate and hence need no ∧ \land ∧ -gates.
Proposition 44. For every boolean function f f f ,
nondet-wires ∧ ( f ) = { enc ( f ) if enc ( f ) ≥ 2 , 0 if enc ( f ) ≤ 1. \operatorname{nondet\text{-}wires}_{\land}(f) =
\begin{cases}
\operatorname{enc}(f) & \text{if } \operatorname{enc}(f) \ge2, \\
0 & \text{if } \operatorname{enc}(f) \le1.
\end{cases} nondet - wires ∧ ( f ) = { enc ( f ) 0 if enc ( f ) ≥ 2 , if enc ( f ) ≤ 1.
Proof. Write W : = nondet-wires ∧ ( f ) W := \operatorname{nondet\text{-}wires}_{\land}(f) W := nondet - wires ∧ ( f ) . First, we show that W ≤ enc ( f ) W \le\operatorname{enc}(f) W ≤ enc ( f ) if enc ( f ) ≥ 2 \operatorname{enc}(f) \ge2 enc ( f ) ≥ 2 , and W = 0 W = 0 W = 0 if enc ( f ) ≤ 1 \operatorname{enc}(f) \le1 enc ( f ) ≤ 1 . Take an encoding of f f f with c = enc ( f ) c = \operatorname{enc}(f) c = enc ( f ) clauses, and regard its auxiliary variables as nondeterministic inputs. If c ≥ 2 c \ge2 c ≥ 2 , regard each clause as an ∨ \lor ∨ -gate and combine them with a single ∧ \land ∧ -gate of fan-in c c c . If c = 1 c = 1 c = 1 , the single clause, regarded as an ∨ \lor ∨ -gate, is the whole circuit. If c = 0 c = 0 c = 0 , then f f f is constantly 1, and the constant 1 is the whole circuit.
It remains to show that every nondeterministic De Morgan circuit C C C computing f f f whose ∧ \land ∧ -gates have total fan-in w w w satisfies enc ( f ) ≤ max { 1 , w } \operatorname{enc}(f) \le\max\{1,w\} enc ( f ) ≤ max { 1 , w } . If f f f is constantly 1, then enc ( f ) = 0 \operatorname{enc}(f) = 0 enc ( f ) = 0 , so assume otherwise. Remove all gates that do not reach the output; this does not increase w w w . Write o o o for the output gate of C C C . For every gate or input u u u of C C C , define its disjunct set D ( u ) D(u) D ( u ) as follows: if u u u is a literal, a constant, or an ∧ \land ∧ -gate, then D ( u ) : = { u } D(u) := \{u\} D ( u ) := { u } ; if u u u is an ∨ \lor ∨ -gate, then D ( u ) D(u) D ( u ) is the union of the disjunct sets of its inputs. Thus, every ∨ \lor ∨ -gate computes the disjunction of its disjunct set. For a disjunct set S S S not containing 1, let cl ( S ) \operatorname{cl}(S) cl ( S ) be the clause obtained from S S S by replacing every ∧ \land ∧ -gate h h h by a variable z h z_h z h , keeping every literal, and deleting 0 if it is present. Since f f f is not constantly 1, the disjunct set D ( o ) D(o) D ( o ) does not contain 1.
If C C C has no ∧ \wedge ∧ -gates, then D ( o ) D(o) D ( o ) consists of literals and possibly 0, and C C C outputs 1 exactly when cl ( D ( o ) ) \operatorname{cl}(D(o)) cl ( D ( o )) is true. Hence the single clause cl ( D ( o ) ) \operatorname{cl}(D(o)) cl ( D ( o )) , with the nondeterministic inputs of C C C as auxiliary variables, is an encoding of f f f , and enc ( f ) ≤ 1 \operatorname{enc}(f) \le1 enc ( f ) ≤ 1 .
Otherwise, fix an ∧ \wedge ∧ -gate g ∗ g^* g ∗ such that every path from g ∗ g^* g ∗ to o o o passes through no other ∧ \wedge ∧ -gates. Then, g ∗ ∈ D ( o ) g^* \in D(o) g ∗ ∈ D ( o ) , and g ∗ g^* g ∗ does not lie in any disjunct set of an input of an ∧ \wedge ∧ -gate. Let B : = cl ( D ( o ) ∖ { g ∗ } ) B := \operatorname{cl}(D(o) \setminus\{g^*\}) B := cl ( D ( o ) ∖ { g ∗ }) , and introduce a fresh auxiliary variable z g z_g z g for every ∧ \wedge ∧ -gate g ≠ g ∗ g \ne g^* g = g ∗ . Our encoding consists of the clauses
z g ‾ ∨ cl ( D ( v ) ) for every ∧ -gate g ≠ g ∗ and every input v of g with 1 ∉ D ( v ) , B ∨ cl ( D ( v ) ) for every input v of g ∗ with 1 ∉ D ( v ) . \begin{aligned}
\overline{z_g} \lor\operatorname{cl}(D(v)) &\qquad\text{for every }\wedge\text{-gate }g \ne g^*\text{ and every input }v\text{ of }g\text{ with }1 \notin D(v),\\
B \lor\operatorname{cl}(D(v)) &\qquad\text{for every input }v\text{ of }g^*\text{ with }1 \notin D(v).
\end{aligned} z g ∨ cl ( D ( v )) B ∨ cl ( D ( v )) for every ∧ -gate g = g ∗ and every input v of g with 1 ∈ / D ( v ) , for every input v of g ∗ with 1 ∈ / D ( v ) .
and its auxiliary variables are the nondeterministic inputs of C C C and the variables z g z_g z g for every ∧ \wedge ∧ -gate g ≠ g ∗ g \ne g^* g = g ∗ . There is at most one clause per wire entering an ∧ \wedge ∧ -gate, so the encoding has at most w w w clauses.
Now we show that the encoding is correct. First, suppose x ⃗ \vec{x} x is such that f ( x ⃗ ) = 1 f(\vec{x}) = 1 f ( x ) = 1 , and fix nondeterministic inputs for which C C C outputs 1, and set each z g z_g z g to the value of g g g . If an ∧ \wedge ∧ -gate evaluates to 1, then so does each of its inputs v v v , so some element of D ( v ) D(v) D ( v ) is true, and this element makes cl ( D ( v ) ) \operatorname{cl}(D(v)) cl ( D ( v )) true. This satisfies the clauses of every ∧ \wedge ∧ -gate g ≠ g ∗ g \ne g^* g = g ∗ , and also the clauses of g ∗ g^* g ∗ if g ∗ g^* g ∗ evaluates to 1. Otherwise, since o o o evaluates to 1, some element of D ( o ) ∖ { g ∗ } D(o) \setminus\{g^*\} D ( o ) ∖ { g ∗ } is true, which makes B B B true. Thus, every clause is satisfied.
Conversely, suppose the encoding is satisfiable for an input x ⃗ \vec{x} x , and fix a satisfying assignment to the auxiliary variables. We show that C C C evaluates to 1 on input x ⃗ \vec{x} x when the nondeterministic inputs are set according to the satisfying assignment; this implies that f ( x ⃗ ) = 1 f(\vec{x}) = 1 f ( x ) = 1 .
We first prove the following claim: for every ∧ \wedge ∧ -gate g ≠ g ∗ g \ne g^* g = g ∗ , if z g = 1 z_g = 1 z g = 1 , then g g g evaluates to 1. We proceed by induction along a topological order of C C C . Let g ≠ g ∗ g \ne g^* g = g ∗ be an ∧ \wedge ∧ -gate with z g = 1 z_g = 1 z g = 1 , and assume the claim for all ∧ \wedge ∧ -gates that precede g g g . Let v v v be an input of g g g ; we show that v v v evaluates to 1. If 1 ∈ D ( v ) 1 \in D(v) 1 ∈ D ( v ) , this holds because v v v computes the disjunction of D ( v ) D(v) D ( v ) . Otherwise, the encoding contains the clause z g ‾ ∨ cl ( D ( v ) ) \overline{z_g} \lor\operatorname{cl}(D(v)) z g ∨ cl ( D ( v )) , and since z g = 1 z_g = 1 z g = 1 , some literal of cl ( D ( v ) ) \operatorname{cl}(D(v)) cl ( D ( v )) is true. Either this literal is an element of D ( v ) D(v) D ( v ) , or it is z h z_h z h for an ∧ \wedge ∧ -gate h ∈ D ( v ) h \in D(v) h ∈ D ( v ) . In the latter case, h h h precedes g g g and h ≠ g ∗ h \ne g^* h = g ∗ , so h h h evaluates to 1 by the induction hypothesis. Thus, some element of D ( v ) D(v) D ( v ) evaluates to 1, and therefore so does v v v . Since every input of g g g evaluates to 1, so does g g g , which proves the claim.
Consequently, if cl ( S ) \operatorname{cl}(S) cl ( S ) is true, where S S S is a set of literals, ∧ \wedge ∧ -gates other than g ∗ g^* g ∗ , and possibly 0, then some element of S S S evaluates to 1. We use this to show that o o o evaluates to 1, distinguishing two cases. If B B B is true, then some element of D ( o ) ∖ { g ∗ } D(o) \setminus\{g^*\} D ( o ) ∖ { g ∗ } evaluates to 1, so o o o evaluates to 1. If B B B is false, then for every input v v v of g ∗ g^* g ∗ with 1 ∉ D ( v ) 1 \notin D(v) 1 ∈ / D ( v ) , the clause B ∨ cl ( D ( v ) ) B \lor\operatorname{cl}(D(v)) B ∨ cl ( D ( v )) forces cl ( D ( v ) ) \operatorname{cl}(D(v)) cl ( D ( v )) to be true. Since g ∗ ∉ D ( v ) g^* \notin D(v) g ∗ ∈ / D ( v ) , some element of D ( v ) D(v) D ( v ) evaluates to 1, and hence so does v v v ; inputs v v v with 1 ∈ D ( v ) 1 \in D(v) 1 ∈ D ( v ) evaluate to 1 trivially. Thus, every input of g ∗ g^* g ∗ evaluates to 1, so g ∗ g^* g ∗ evaluates to 1. Since g ∗ ∈ D ( o ) g^* \in D(o) g ∗ ∈ D ( o ) , o o o evaluates to 1. In both cases, C C C outputs 1. Therefore, the encoding is correct. □ \square □
Acknowledgments
We thank Ryan O’Donnell for helpful conversations about the presentation of our results. Krapivin was supported in part by NSF grant 2504471, NSF CAREER award 2542165, a Jane Street Research Grant, the Jeanne B. and Richard F. Berdik ARCS Pittsburgh Endowed Scholar Award, the David and Lucile Packard Foundation (Award #202071730), and gifts from Nikolai Mushegian and Microsoft. Przybocki and Subercaseaux were supported by the DARPA expMath program through the DARPA CMO contract number HR0011262E028 and by the National Science Foundation (NSF) under grant DMS2434625. Przybocki was additionally supported by the NSF Graduate Research Fellowship Program under Grant Nos. DGE-2140739 and DGE-2631988.
AI Methodology
We used ChatGPT 6 Astra in order to make quantitative improvements on some of our results. Concretely, we provided Astra with a human-written proof of a version of Theorem 5 that used Szemerédi’s regularity lemma and yielded O k ( n k ⋅ lg ( lg ∗ n ) lg ( n ) 5 lg ∗ ( n ) ) O_k\left(\frac{n^k\cdot\lg(\lg^* n)}{\lg(n)5^{\lg^*(n)}}\right) O k ( l g ( n ) 5 l g ∗ ( n ) n k ⋅ l g ( l g ∗ n ) ) clauses for arbitrary k k k -CNF. Astra provided Lemma 25 and Lemma 27 in order to yield the improved bound presented in the paper. Similarly, we presented it with a weaker version of Theorem 6, which gave an upper bound of O ( M ⋅ ( n − lg M + 1 ) ) O\left(\sqrt{M}\cdot(n-\lg M+1)\right) O ( M ⋅ ( n − lg M + 1 ) ) , and Astra improved this by leveraging a succinct static dictionary. In both cases, the original writing produced by the model was poor, and some of its arguments were overcomplicated, so we simplified and rewrote each of them. We also used Claude Opus 5.5 for help with writing and reorganizing some proofs.