# The Inapproximability of \(k\)-DominatingSet for Parameterized AC\({}^{0}\) Circuits +
## 4 Inapproximability of \(k\)-DominatingSet
### The Difficulty of Proving \(\mathsf{AC}^{0}\)-EtH  
Though \(\mathsf{AC}^{0}\)-ETH seems much weaker than ETH, we find that it is still very hard to settle by showing Theorem 5, i.e., \(\mathsf{AC}^{0}\)-ETH implies \(\mathsf{NP}\
ot\subseteq\mathsf{NC}^{1}\).  
Lemma 7: _For every \(L\in\mathsf{NC}^{1}\), i.e., there exists \(c\in\mathbb{N}\) such that \(L\) could be computed by a family of circuits \((\mathsf{C}_{n})_{n\in\mathbb{N}}\) such that \(\mathsf{C}_{n}\) has size at most \(n^{c}\) and depth at most \(c\log n\), there exists \(d\in\mathbb{N}\) such that there is a family of circuits \((\mathsf{C}^{\prime}_{n})_{n\in\mathbb{N}}\) which satisfies_  
* \(s\in L\) _if and only if_ \(C^{\prime}_{|s|}\) _outputs_ \(1\)_;_
* \(\mathsf{C}^{\prime}_{n}\) _has depth_ \(d\) _and size at most_ \(n^{3c/2}(2^{n^{2c/d}+1}+1)\)_._  
Proof.: We show that for every \(n\in\mathbb{N}\), \(\mathsf{C}_{n}\) could be simulated by a circuit \(\mathsf{C}_{n}{}^{\prime}\) that has depth \(d\) and size \(n^{3c/2}(2^{n^{2c/d}+1}+1)\). Suppose \(\mathsf{C}_{n}\) has size \(n^{c}\) and depth \(c\log n\) (otherwise, we could add dummy gates to \(\mathsf{C}_{n}\)). For every gate \(\sigma\) of depth \(\frac{c\log n}{2}d\), let \(f_{\sigma}\) be the Boolean function computed by \(\sigma\). Note that \(f_{\sigma}\) has at most \(n^{2c/d}\) input bits, denoted by \(b_{1},\ldots,b_{n^{2c/d}}\) since \(\mathsf{C}_{n}\) is of fan-in \(2\). Now we could replace \(\sigma\) using brute force by  
\[\bigvee_{f_{\sigma}(\ell)=1,\ell\in\{0,1\}^{n^{2c/d}}}\bigwedge_{i\in[n^{2c/d }]}\beta_{i}\]  
where \(\beta_{i}=b_{i}\) if \(\ell[i]=1\) and \(\beta_{i}=\
eg b_{i}\) if \(\ell[i]=0\). That is, \(\sigma\) could be simulated by a \(2\)-depth circuit which has size at most \(2^{n^{2c/d}+1}+1\).  
Assume for every \(l\in[d/2-1]\), every gate \(\sigma\) of depth \(\frac{l\cdot 2c\log n}{d}\) could be replaced by a \(2l\)-depth circuit \(\mathsf{C}^{(\sigma)}\) which has size \(n^{\frac{(l-1)\cdot 3c}{d}}(2^{n^{2c/d}+1}+1)\). Now we could simulate each gate \(\gamma\) of depth \(\frac{(l+1)\cdot 2c\log n}{d}\), whose output is determined by the gates \(\sigma_{1},\ldots,\sigma_{n^{2c/d}}\) from the \(\frac{l\cdot 2c\log n}{d}\)-th layer, in the similar way. That is, \(\sigma\) is replaced by  
\[\bigvee_{f_{\sigma}(\ell)=1,\ell\in\{0,1\}^{n^{2c/d}}}\bigwedge_{i\in[n^{2c/d }]}\mathsf{C}^{(i)}\]  
where \(\mathsf{C}^{(i)}=\mathsf{C}^{(\sigma_{i})}\) if \(\ell[i]=1\) and \(\mathsf{C}^{(i)}=\
eg\mathsf{C}^{(\sigma_{i})}\) if \(\ell[i]=0\). Now, \(\mathsf{C}^{(\gamma)}\) has depth \(2(l+1)\) and size at most \((2^{n^{2c/d}+1}+1)+n^{2c/d}\cdot n^{\frac{(l-1)\cdot 3c}{d}}(2^{n^{2c/d}+1}+1)\leq n^{ \frac{13c}{d}}(2^{n^{2c/d}+1}+1)\).  
Thus, the output gate of \(\mathsf{C}_{n}\) could be simulated by a depth \(d\) circuit whose size is at most \(n^{3c/2}(2^{n^{2c/d}+1}+1)\).  
Theorem 5: \(\mathsf{AC}^{0}\)_-ETH implies \(\mathsf{NP}\
ot\subseteq\mathsf{NC}^{1}\)._  
Proof.: We show that \(\mathsf{AC}^{0}\)-ETH implies \(3\)-CNF-SAT \(\
ot\subseteq\mathsf{NC}^{1}\). If there exists \(c\in\mathbb{N}\) such that \(3\)-CNF-SAT could be computed by a family of circuits \((\mathsf{C}_{n})_{n\in\mathbb{N}}\) satisfying \(\mathsf{C}_{n}\) has size at most \(n^{c}\) and depth at most \(c\log n\). By Lemma 7, 3-CNF-SAT could be computed by \(5c\)-depth, size \(n^{3c/2}(2^{n^{2/5}+1}+1)=O(2^{\sqrt{n}})\) circuits for sufficiently large \(n\), which contradicts \(\mathsf{AC^{0}}\)-ETH.