# The Inapproximability of \(k\)-DominatingSet for Parameterized AC\({}^{0}\) Circuits +
## 3 Introducing Gap to the \(k\)-SetCover Problem  
Theorem 1 and Theorem 2 show that the para-\(\mathsf{AC^{0}}\) circuits cannot approximate the \(k\)-DomSet problem with ratio \(f(k)\) for any computable function \(f\). To achieve this, we need to introduce gaps for \(k\)-DomSet instances. In this section, we present the lemmas which allow us to introduce gaps to the \(k\)-SetCover problem, using _gap-gadgets_ as presented in [PERSON]'s work [18]. Lemma 1 gives an upper bound for \(\mathsf{CAN}(k,n,2)\). The next two lemmas also follow the idea from [PERSON]'s work [18]. Lemma 2 allows us to construct gap gadgets with \(h\leq\frac{\log n}{\log\log n}\) and \(k\log\log n\leq\log n\). In Lemma 3, we present the construction which introduces gaps to set cover instances. **Definition 1**. : _A \((k,n,m,\ell,h)\)-Gap-Gadget is a bipartite graph \(T=(A,B,E)\) satisfying the following conditions._  
1. _[label=(G0)]_
2. \(A\) _is partitioned into_ \((A_{1},\ldots,A_{m})\) _where_ \(|A_{i}|=\ell\) _for every_ \(i\in[m]\)_._
3. \(B\) _is partitioned into_ \((B_{1},\ldots,B_{k})\) _where_ \(|B_{j}|=n\) _for every_ \(j\in[k]\)_._
4. _For each_ \(b_{1}\in B_{1},\ldots,b_{k}\in B_{k}\)_, there exists_ \(a_{1}\in A_{1},\ldots,a_{m}\in A_{m}\) _such that_ \(a_{i}\) _is adjacent to_ \(b_{j}\) _for_ \(i\in[m],j\in[k]\)_._
5. _For any_ \(X\subseteq B\) _and_ \(a_{1}\in A_{1},\ldots,a_{m}\in A_{m}\)_, if_ \(a_{i}\) _has_ \(k+1\) _neighbors in_ \(X\) _for_ \(i\in[m]\)_, then_ \(|X|>h\)_._  
**Lemma 1**. : \(\mathsf{CAN}(k,n,2)\leq k2^{k}\log n\) _for \(n\geq 5\)._  
Proof. : We let \(M=2^{k}\binom{n}{k}(1-\frac{1}{2^{k}})^{k2^{k}\log n}\). [PERSON] and [PERSON] showed that if \(2^{k}\binom{n}{k}(1-\frac{1}{2^{k}})^{r}<1\), \(\mathsf{CAN}(k,n,2)\leq r\)[32]. Thus, we only need to show that \(M<1\). Since \(2^{x}\log\left(\frac{2^{x}}{2^{x}-1}\right)>\frac{1}{\ln 2}\) and \(n>5\), we have  
\[\log M <k+k\log n+k2^{k}\log n\log(1-\frac{1}{2^{k}})\] \[<k+k\log n-\frac{1}{\ln 2}k\log n\qquad\qquad\qquad\] \[<0\]  
This implies \(M<1\). **Lemma 2**. : _There is a constant-depth circuit family \((\mathsf{C}_{k,n,h})_{k,n,h\in\mathbb{N}}\) which, for sufficiently large \(n\) and \(k,h\in\mathbb{N}\) with \(h\leq\frac{\log n}{\log\log n}\) and \(k\log\log n\leq\log n\), given \(S=S_{1}\cup\cdots\cup S_{k}\) with \(|S_{i}|=n\) for \(i\in[k]\), outputs a \((k,n,n\log h,h^{k},h)\)-Gap-Gadget \(T=(A,B,E)\) with \(|A|=h^{k}n\log h\), \(B=S\). Furthermore, \(\mathsf{C}_{k,n,h}\) has size at most \(kh^{k}n^{2}\log h\) and could output whether **a** and \(b\) are adjacent using \(O(1)\) gates, for every \(\textbf{a}\in A,b\in B\)._  
Proof. : Let \(m=n\log h\). Note that \(\log((h\log h)2^{h\log h}\log m)\leq(h+2)\log h+\log\log n\), that is, \((h\log h)2^{h\log h}\log m\leq n\leq n\log h\); by Lemma 1, we know that there exists a covering array \(\mathsf{CA}(n\log h;k,n,2)\), denoted by \(\mathcal{S}\). We partition every row of \(\mathcal{S}\) into \(n=\frac{m}{\log h}\) blocks so that each block has length \(\log h\), interpreted as an integer in \([h]\). From the \(m\times n\) numbers of \(\mathcal{S}\), we could obtain an \(m\times n\) matrix \(M\) by setting \(M_{r,c}\) to be the \(c\)-th integer of the \(r\)-th row. **Claim**. : _For any \(C\subseteq[n]\) with \(|C|\leq h\), there exists \(r\in[m]\) such that \(|\{M_{r,c}\ \mid\ c\in C\}|=|C|\)._  
This claim says that for any \(C=\{i_{1},\ldots,i_{j}\}\subseteq[n]\) for \(j\leq h\), there is a row \(r\) such that the \(i_{1}\)-th,..., \(i_{j}\)-th numbers of \(r\) are distinct. This is because we could choose the corresponding bits \(C^{\prime}=\cup_{c\in C}[(c-1)\log h+1,c\log h]\) (since for each \(c\in[n]\), the \(c\)-th number of a row is from the \(\big{(}(c-1)\log h+1\big{)}\)-th bit to the \((c\log n)\)-th bit) of the row, with \(|C^{\prime}|\leq h\log h\); by the property of a \(\mathsf{CA}(n\log h;k,n,2)\) covering array, there must be a row \(r\) such that for each \(i_{j^{\prime}}\in C\), \(M_{r,i_{j^{\prime}}}=j^{\prime}\). Now we construct a bipartite graph \(T=(A,B,E)\) as follows.