## 1 Introduction
### Maximum Edge Biclique and Maximum Balanced Biclique  
Our first result is an adaptation of RST technique to prove inapproximability of Maximum Edge Biclique (MEB) and Maximum Balanced Biclique (MBB). For both problems, the input is a bipartite graph. The goal for the former is to find a complete bipartite subgraph that contains as many edges as possible whereas, for the latter, the goal is to find a balanced complete bipartite subgraph that contains as many vertices as possible. Both problems are NP-hard. MBB was stated (without proof) to be NP-hard in [PERSON] and [PERSON]'s seminal book (p. 196 [12]); several proofs of this exist such as one provided in [13]. For MEB, it was proved to be NP-hard more recently by [PERSON] [14]. Unfortunately, much less is known when it comes to approximability of both problems. Similar to Maximum Clique, folklore algorithms give \(O(n/\operatorname{polylog}n)\) approximation ratio for both MBB and MEB, and no better algorithm is known. However, not even NP-hardness of approximation of some constant ratio is known for the problems. This is in stark contrast to Maximum Clique for which strong inapproximability results are known [4; 15; 16; 17]. Fortunately, the situation is not completely hopeless as the problems are known to be hard to approximate under stronger complexity assumptions. [PERSON] [18] showed that, assuming that random 3 SAT formulae cannot be refuted in polynomial time, both problems cannot be approximated to within \(n^{\varepsilon}\) of the optimum in polynomial time for some \(\varepsilon>0\). (While [PERSON] only stated this for MBB, the reduction clearly works for MEB too.) Later, [PERSON] and [PERSON] [19] proved \(2^{(\log n)^{\varepsilon}}\) ratio inapproximability for both problems for some \(\varepsilon>0\), assuming that \(3\text{SAT}\
otin\text{DTIME}(2^{n^{3/4+\delta}})\) for some \(\delta>0\). Moreover, [PERSON] [20] showed, assuming \(3\text{SAT}\
otin\text{BPTIME}(2^{n^{\varepsilon}})\) for some \(\delta>0\), that no polynomial time algorithm achieves \(n^{\varepsilon}\)-approximation for MBB for some \(\varepsilon>0\). [PERSON] et al. [21] subsequently built on [PERSON]'s result and showed a similar hardness for MEB. Recently, [PERSON] et al. [22] proved that both problems are hard to approximate to within \(n^{1-\varepsilon}\) factor for every \(\varepsilon>0\), assuming a certain strengthened version of UGC and \(\text{NP}\
eq\text{BPP}\). (In [22], the inapproximability ratio is only claimed to be \(n^{\varepsilon}\) for _some_\(\varepsilon>0\). However, it is not hard to see that their result in fact implies \(n^{1-\varepsilon}\) factor hardness of approximation as well.) In addition, while not stated explicitly, the author's recent reduction for Densest \(k\)-Subgraph [23] yields \(n^{1/\operatorname{polylog}n}\) ratio inapproximability for both problems under the Exponential Time Hypothesis [24] (\(3\text{SAT}\
otin\text{DTIME}(2^{(n)})\)) and this ratio can be improved to \(n^{f(n)}\) for any \(f\in o(1)\) under the stronger Gap Exponential Time Hypothesis [25; 26] (no \(2^{o(n)}\) time algorithm can distinguish a fully satisfiable 3 SAT formula from one which is only \((1-\varepsilon)\)-satisfiable for some \(\varepsilon>0\)); these ratios are better than those in [19] but worse than those in [20; 21; 22]. Finally, it is worth noting that, assuming the Planted Clique Hypothesis [27; 28] (no polynomial time algorithm can distinguish between a random graph \(\mathcal{G}(n,1/2)\) and one with a planted clique of size \(\Omega(\sqrt{n})\)), it follows (by partitioning the vertex set into two equal sets and delete all the edges within each partition) that Maximum Balanced Biclique cannot be approximated to within \(\tilde{O}(\sqrt{n})\) ratio in polynomial time. Interestingly, this does not give any hardness for Maximum Edge Biclique, since the planted clique has only \(O(n)\) edges, which less than that in a trivial biclique consisting of any vertex and all of its neighbors.