## 1 Introduction
### Maximum Edge Biclique and Maximum Balanced Biclique
In this work, we prove strong inapproximability results for both problems, assuming SSEH:  
Theorem 1: _Assuming the Small Set Expansion Hypothesis, there is no polynomial time algorithm that approximates MEB or MBB to within \(n^{1-\varepsilon}\) factor of the optimum for every \(\varepsilon>0\), unless NP \(\subseteq\) BPP._  
We note that the only part of the reduction that is randomized is the gap amplification via randomized graph product [29; 30]. If one is willing to assume only that NP \(\
eq\) P (and SSEH), our reduction still implies that both are hard to approximate to within any constant factor. Only [PERSON] et al. 's result [22] and our result achieve the inapproximability ratio of \(n^{1-\varepsilon}\) for every \(\varepsilon>0\); all other results achieve at most \(n^{\varepsilon}\) ratio for some \(\varepsilon>0\). Moreover, only [PERSON] et al. 's reduction and ours are candidate NP-hardness reductions, whereas each of the other reductions either uses superpolynomial time [19; 20; 21; 23] or relies on an average-case assumption [18]. It is also worth noting here that, while both [PERSON] et al. 's result and our result are based on assumptions which can be viewed as stronger variants of UGC, the two assumptions are incomparable and, to the best of our knowledge, [PERSON] et al. 's technique does not apply to SSEH. A discussion on the similarities and differences between the two assumptions can be found in Appendix C.  
Along the way, we prove inapproximability of the following hypergraph bisection problem, which may be of independent interest: given a hypergraph \(H=(V_{H},E_{H})\) find a bisection \((T_{0},T_{1})\) of \(V_{H}\) such that the number of uncut hyperedges is maximized. (\((T_{0},T_{1})\) is a bisection of \(V_{H}\) if \(|T_{0}|=|T_{1}|=|V_{H}|/2\), \(T_{0}\cap T_{1}=\emptyset\) and \(V_{H}=T_{0}\cup T_{1}\).) We refer to this problem as _Max UnCut Hypergraph Bisection_ (MUCHB). Roughly speaking, we show that, assuming SSEH, it is hard to distinguish a hypergraph whose optimal bisection cuts only \(\varepsilon\) fraction of hyperedges from one in which every bisection cuts all but \(\varepsilon\) fraction of hyperedges:  
Lemma 1: _Assuming the Small Set Expansion Hypothesis, for every \(\varepsilon>0\), it is NP-hard to, given a hypergraph \(H=(V_{H},E_{H})\), distinguish between the following two cases:_  
* (Completeness) _There is a bisection_ \((T_{0},T_{1})\) _of_ \(V_{H}\) _s.t._ \(|E_{H}(T_{0})|,|E_{H}(T_{1})|\geqslant(1/2-\varepsilon)|E_{H}|\)_._
* (Soundness) _For every set_ \(T\subseteq V_{H}\) _of size at most_ \(|V_{H}|/2\)_,_ \(|E_{H}(T)|\leqslant\varepsilon|E_{H}|\)_._  
_Here \(E_{H}(T)\triangleq\{e\in E_{H}\mid e\subseteq T\}\) denotes the set of hyperedges that lie completely inside of the set \(T\subseteq V_{H}\)._  
Our result above is similar to [PERSON]'s quasi-random PCP [20]. Specifically, [PERSON]'s quasi-random PCP can be viewed as a hardness for MUCHB in the setting where the hypergraph is \(d\)-uniform; roughly speaking, [PERSON]'s result states that it is hard (if 3 SAT \(\
otin\bigcap_{\delta>0}\) BPTIME(\(2^{nd}\))) to distinguish between a \(d\)-uniform hypergraph where \(1/2^{d-2}\) fraction of hyperedges are uncut in the optimal bisection from one where roughly \(1/2^{d-1}\) fraction of hyperedges are uncut in any bisection. Note that the latter is the fraction of uncut hyperedges in random \(d\)-uniform hypergraphs and hence the name \"quasi-random\". In this sense, [PERSON]'s result provides better soundness at the expense of worse completeness compared to Theorem 1.