# The Inapproximability of \(k\)-DominatingSet for Parameterized AC\({}^{0}\) Circuits +
## 4 Inapproximability of \(k\)-DominatingSet
### The Inapproximability of \(k\)-DominatingSet Assuming \(\mathsf{AC^{0}}\)-ETH  
Next we show the \(f(k)\)-inapproximability of the set cover problem for constant-depth circuits of size \(n^{o(k)}\) for any computable function \(f\), assuming \(\mathsf{AC^{0}}\)-ETH. To achieve this, we use Lemma 6 to reduce 3-CNF-SAT formulas to set cover instances with gaps. **Lemma 6**. : _There is a circuit family \((\mathsf{C}_{n,k})_{n,k\in\mathbb{N}}\) which for every \(k\in\mathbb{N}\), given a \(3\)-CNF-SAT instance \(\varphi\) with \(n\) variables where \(n\) is much larger than \(k\), outputs \(N\leq 2^{\frac{11n}{2k}}\) and a set cover instance \(I=(S,U,E)\) satisfying_* \(|S|+|U|\leq N\)_;_
* _If_ \(\varphi\) _is satisfiable, then the set cover number of_ \(I\) _is at most_ \(k\)_;_
* _If_ \(\varphi\) _is not satisfiable, then the set cover number of_ \(I\) _is greater than_ \(\left(\frac{\log N}{3\log\log N}\right)^{1/k}\) _;_ _Furthermore,_ \(\mathsf{C}_{n,k}\) _has constant depth and size at most_ \(2^{\frac{11n}{2k}}\)_._  
Proof. : Firstly, we construct a set cover instance \(I^{\prime}=(S^{\prime},U^{\prime},E^{\prime})\) whose set cover number is \(k\) if and only if \(\varphi\) is satisfiable, as follows. Partition \(n\) variables into \(k\) parts and each part has \(n/k\) variables. We let \(S^{\prime}=S_{1}\cup\cdots\cup S_{k}\) and for \(i\in[k]\), each \(S_{i}\) be the set of all the assignments of the variables from the \(i\)-th part. Thus, \(|S_{i}|=2^{n/k}\) for each \(i\in[k]\). Let \(U^{\prime}:=\{C\mid C\in\varphi\}\cup\{x_{i}\mid i\in[k]\}\) be the clauses of \(\varphi\) and vertices \(x_{1},\ldots,x_{k}\). We define \(E^{\prime}:=\cup_{i\in[k]}\left(\{\{s,C\}\mid s\text{ satisfies }C\text{ for }s\in S_{i},C\in U^{\prime}\}\cup\{\{s,x_{i}\}\mid s\in S_{i}\}\right)\) the edges connecting each \(s\in S_{i}\) with \(x_{i}\) and every \(C\in U^{\prime}\) such that \(s\) satisfies \(C\), for each \(i\in[k]\). It is clear that if \(\varphi\) is satisfied by assignment \(\sigma\), then we know that there are \(s_{1}\in S_{1},\ldots,s_{k}\in S_{k}\) such that we can combine \(s_{1},\ldots,s_{k}\) to get the \(\sigma\), satisfying \(\varphi\). Now suppose \(s_{1}\in S_{1},\ldots,s_{k}\in S_{k}\) can cover \(U^{\prime}\). Note that the set cover number of \(I^{\prime}\) cannot be less than \(k\) because of the existence of \(x_{1},\ldots,x_{k}\). Since the different sets \(S_{1},...,S_{k}\) of variables are pairwise disjoint, we could simply combine the assignments \(s_{1},\ldots,s_{k}\), which together satisfy all the clauses, to have the assignment satisfying \(\varphi\). We have \(I^{\prime}\) with \(|S^{\prime}|=k2^{n/k}\) and \(|U^{\prime}|\leq(^{n}_{3})+k\leq 2n^{3}\) and let \(m=2^{n/k}\). By Lemma 2, there is a constant-depth circuit which can compute a \((k,m,m\log h,h^{k},h)\)-Gap-Gadget \(T\) with \(h=\sqrt[k]{\frac{\log m}{\log\log m}}\geq\left(\frac{\log N}{3\log\log N} \right)^{1/k}\) which has size \(O(k^{2}m^{2}h^{2k+1})=O(k^{2}m^{2}\log^{3}m)\). By Lemma 3, there is a constant-depth circuit \(\mathsf{C}\) that can construct a set cover instance \(I=(S,U,E)\) which, given \(I^{\prime}\) and \(T\) such that  
* If \(\varphi\) is satisfiable, then the set cover number of \(I\) is at most \(k\);
* If \(\varphi\) is unsatisfiable, then the set cover number of \(I\) is greater than \(h\);
* \(S=S^{\prime}\), \(|U|=m\log h|U^{\prime}|^{h^{k}}\leq\frac{1}{k}m(\log\log m-\log\log\log m)(2n ^{3})^{\frac{\log m}{\log\log m}}\leq m\cdot\log\log m\cdot(2^{\frac{\log m} {\log\log n}}+n^{\frac{3n}{k(\log n-\log k)}})\leq m\cdot\log\log m\cdot(2^{ \frac{\log m}{\log\log n}}+n^{\frac{3n}{k}})=m^{4+o(1)}\). Thus, \(|S|+|U|=km+m^{4+o(1)}\leq 2^{\frac{11n}{2k}}=N\). Furthermore, \(\mathsf{C}\) has size at most \((h^{k}+1)(km\cdot m^{4+o(1)})=O(m^{5+o(1)})=2^{\frac{11n}{2k}}\).