## Appendix B Gap Amplification via Randomized Graph Product  
In this section, we provide a full proof of the gap amplification step for biclique problems, thereby proving Theorem 1. The argument provided below is almost the same as the randomized graph product-based analysis of [PERSON] (Appendix D [20]), which is in turn based on the analysis of [PERSON] and [PERSON] [29], except that we modify the construction slightly so that the reduction time is polynomial. (Using [PERSON]'s result directly would result in the construction time being quasi-polynomial.) Specifically, we will prove the following statement, which immediately implies Theorem 1. Lemma A1 (): _Assuming SSEH and NP \(\
eq\) BPP, for every \(\varepsilon>0\), no polynomial time algorithm can, given a bipartite graph \(G^{\prime}=(L^{\prime},R^{\prime},E^{\prime})\) with \(|L^{\prime}|=|R^{\prime}|=N\), distinguish between the following two cases:_  
* (Completeness)__\(G^{\prime}\) _contains_ \(K_{N^{1-\varepsilon},N^{1-\varepsilon}}\) _as a subgraph._
* (Soundness)__\(G^{\prime}\) _does not contain_ \(K_{N^{r},N^{\varepsilon}}\) _as a subgraph._  
Proof. : Let \(\varepsilon>0\) be any constant. Assume without loss of generality that \(\varepsilon<1\). Consider any bipartite graph \(G=(L,R,E)\) with \(|L|=|R|=n\). Let \(\delta=2^{-4/\varepsilon},k=\log n\) and \(N=(1/\delta)^{k}\). We construct a graph \(G^{\prime}=(L^{\prime},R^{\prime},E^{\prime})\) where \(|L^{\prime}|=|R^{\prime}|=N\) as follows. For \(i\in[N]\), pick random elements \(U^{i}\sim L^{k}\) and \(V^{i}\sim R^{k}\), and add them to \(L^{\prime}\) and \(R^{\prime}\) respectively. Finally, for every \(U\in L^{\prime}\) and \(V\in R^{\prime}\), there is an edge between \(U\) and \(V\) in \(G^{\prime}\) if and only if there is an edge in the original graph \(G\) between \(U_{j_{1}}\) and \(V_{j_{2}}\) for every \(j_{1},j_{2}\in[k]\). **Completeness. ** Suppose that the original graph \(G\) contains \(K_{(1/2-\delta)n,(1/2-\delta)n}\) as a subgraph. Let one such subgraph be \((S,T)\) where \(S\subseteq L\) and \(T\subseteq R\). Observe that \((L^{\prime}\cap S^{k},R^{\prime}\cap T^{k})\) induces a biclique in \(G^{\prime}\). For each \(i\in[N]\), note that \(U_{i}\in S^{k}\) with probability \((1/2-\delta)^{k}\geqslant(1/4)^{k}=N^{-\epsilon/2}\) independent of each other. As a result, from Chernoff bound, \(|L^{\prime}\cap S^{k}|\geqslant N^{1-\epsilon}\) with high probability. Similarly, we also have \(|R^{\prime}\cap T^{k}|\geqslant N^{1-\epsilon}\) with high probability. Thus, \(G^{\prime}\) contains \(K_{N^{1-\epsilon},N^{1-\epsilon}}\) as a subgraph with high probability. **Soundness. ** Suppose that \(G\) does not contain \(K_{\delta n,\delta n}\) as a subgraph. We will show that, with high probability, \(G^{\prime}\) does not contain \(K_{N^{\epsilon},N^{\epsilon}}\) as a subgraph. To do so, we will first prove the following proposition. **Proposition A1**. : _For any set \(A\), let \(\mathcal{P}(A)\) denote the power set of \(A\). Moreover, let \(\mathcal{F}:\mathcal{P}(L^{k}\cup R^{k})\rightarrow\mathcal{P}(L\cup R)\) be the \"flattening\" operation defined by \(\mathcal{F}(A)\triangleq\cup_{U\in A}\{U_{i}\mid i\in[k]\}\). Then, with high probability, we have \(|\mathcal{F}(S^{\prime})|\geqslant\delta n\) for every subset \(S^{\prime}\subseteq L^{\prime}\) of size \(N^{\epsilon}\) and \(|\mathcal{F}(T^{\prime})|\geqslant\delta n\) for every subset \(T^{\prime}\subseteq R^{\prime}\) of size \(N^{\epsilon}\)._  
Proof of Proposition A1. : Let us consider the probability that there exists a set \(S^{\prime}\subseteq L^{\prime}\) of size \(N^{\epsilon}\) such that \(|\mathcal{F}(S^{\prime})|<\delta n\). This can be bounded as follows.