在流模型下的Max-Cut问题中，算法接收到未知图$ G=(V,E) $的边序列，其目标是近似图中最大割的大小。Kapralov和Krachun改进了Kapralov、Khanna和Sudan的早期结果，证明了对于所有$\varepsilon>0$，任何内存为$o(n)$的单次通过流算法都无法实现$(1/2+\varepsilon)$-近似。他们的结果适用于单次通过流，即仅允许算法查看一次数据流的情况，并且开放问题是多次通过访问是否可能有所帮助。Assadi和N给出的最佳现有结果排除了常数次通过且空间为$n^{1-\delta}$的任意好的近似算法，其中$\delta>0$。我们改进了这一现有结果，表明任何非平凡的Max-Cut近似算法都需要多项式次数的通过或多项式大小的空间。具体来说，我们证明了对于所有$\varepsilon>0$，$k$次通过流的$(1/2+\varepsilon)$-近似算法需要$\Omega_{\varepsilon}\left(n^{1/3}/k\right)$的空间。该结果还导致了对Maximum Directed Cut问题类似的下界，展示了[Saxena, Singer, Sudan, Velusamy, SODA 2025]算法的接近最优性。我们的下界是通过展示Kapralov和Krachun引入的分布隐含隐藏划分（DIHP）问题的通信复杂度下界得出的。尽管直接应用差异方法失败，我们识别了一个称为“全局性”的协议属性，并证明（1）任何DIHP协议都可以转换为全局协议，（2）全局协议的差异必须较小。第二个步骤是论证中更技术性的部分，在这里我们使用了全局超合同不等式。

In the Max-Cut problem in the streaming model, an algorithm is given the edges of an unknown graph $G = (V,E)$ in some fixed order, and its goal is to approximate the size of the largest cut in $G$. Improving upon an earlier result of Kapralov, Khanna and Sudan, it was shown by Kapralov and Krachun that for all $\varepsilon>0$, no $o(n)$ memory streaming algorithm can achieve a $(1/2+\varepsilon)$-approximation for Max-Cut. Their result holds for single-pass streams, i.e.~the setting in which the algorithm only views the stream once, and it was open whether multi-pass access may help. The state-of-the-art result along these lines, due to Assadi and N, rules out arbitrarily good approximation algorithms with constantly many passes and $n^{1-\delta}$ space for any $\delta>0$. We improve upon this state-of-the-art result, showing that any non-trivial approximation algorithm for Max-Cut requires either polynomially many passes or polynomially large space. More specifically, we show that for all $\varepsilon>0$, a $k$-pass streaming $(1/2+\varepsilon)$-approximation algorithm for Max-Cut requires $\Omega_{\varepsilon}\left(n^{1/3}/k\right)$ space. This result leads to a similar lower bound for the Maximum Directed Cut problem, showing the near optimality of the algorithm of [Saxena, Singer, Sudan, Velusamy, SODA 2025]. Our lower bounds proceed by showing a communication complexity lower bound for the Distributional Implicit Hidden Partition (DIHP) Problem, introduced by Kapralov and Krachun. While a naive application of the discrepancy method fails, we identify a property of protocols called ``globalness'', and show that (1) any protocol for DIHP can be turned into a global protocol, (2) the discrepancy of a global protocol must be small. The second step is the more technically involved step in the argument, and therein we use global hypercontractive inequalities.