We study two-pass streaming algorithms for Maximum Bipartite Matching (MBM).
All known two-pass streaming algorithms for MBM operate in a similar fashion:
They compute a maximal matching in the first pass and find 3-augmenting paths
in the second in order to augment the matching found in the first pass. Our aim
is to explore the limitations of this approach and to determine whether current
techniques can be used to further improve the state-of-the-art algorithms. We
give the following results:
We show that every two-pass streaming algorithm that solely computes a
maximal matching in the first pass and outputs a $(2/3+\epsilon)$-approximation
requires $n^{1+\Omega(\frac{1}{\log \log n})}$ space, for every $\epsilon > 0$,
where $n$ is the number of vertices of the input graph. This result is obtained
by extending the Ruzsa-Szemer\'{e}di graph construction of [GKK, SODA'12] so as
to ensure that the resulting graph has a close to perfect matching, the key
property needed in our construction. This result may be of independent
interest.
Furthermore, we combine the two main techniques, i.e., subsampling followed
by the Greedy matching algorithm [Konrad, MFCS'18] which gives a $2-\sqrt{2}
\approx 0.5857$-approximation, and the computation of \emph{degree-bounded
semi-matchings} [EHM, ICDMW'16][KT, APPROX'17] which gives a $\frac{1}{2} +
\frac{1}{12} \approx 0.5833$-approximation, and obtain a meta-algorithm that
yields Konrad's and Esfandiari et al.'s algorithms as special cases. This
unifies two strands of research. By optimizing parameters, we discover that
Konrad's algorithm is optimal for the implied class of algorithms and, perhaps
surprisingly, that there is a second optimal algorithm. We show that the
analysis of our meta-algorithm is best possible. Our results imply that further
improvements, if possible, require new techniques.

该研究研究了二遍流算法在最大二分匹配上的应用，提出了结合子抽样和贪心匹配算法以及度有界半匹配算法的元算法，证明了近似算法的下限，并且发现了最优算法，同时也强调了需求使用新技术以进一步改进。

关于最大二分匹配的两遍流算法

On Two-Pass Streaming Algorithms for Maximum Bipartite Matching

We prove that any two-pass graph streaming algorithm for the $s$-$t$
reachability problem in $n$-vertex directed graphs requires near-quadratic
space of $n^{2-o(1)}$ bits. As a corollary, we also obtain near-quadratic space
lower bounds for several other fundamental problems including maximum bipartite
matching and (approximate) shortest path in undirected graphs.
Our results collectively imply that a wide range of graph problems admit
essentially no non-trivial streaming algorithm even when two passes over the
input is allowed. Prior to our work, such impossibility results were only known
for single-pass streaming algorithms, and the best two-pass lower bounds only
ruled out $o(n^{7/6})$ space algorithms, leaving open a large gap between
(trivial) upper bounds and lower bounds.

研究表明，任何针对 $n$- 顶点有向图中 $s$-$t$ 可达性问题的二遍流图算法都需要近似二次的 $n^ {2-o (1)}$ 比特空间，这个相当于空间的下界也适用于其他基本问题，例如最大二分匹配和在无向图中（近似）最短路径。

两趟图数据流算法的近二次下界

Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms

Graph neural networks (GNNs) have found application for learning in the space
of algorithms. However, the algorithms chosen by existing research (sorting,
Breadth-First search, shortest path finding, etc.) usually align perfectly with
a standard GNN architecture. This report describes how neural execution is
applied to a complex algorithm, such as finding maximum bipartite matching by
reducing it to a flow problem and using Ford-Fulkerson to find the maximum
flow. This is achieved via neural execution based only on features generated
from a single GNN. The evaluation shows strongly generalising results with the
network achieving optimal matching almost 100% of the time.

本文介绍了如何利用单个图神经网络的特征，通过神经执行将复杂算法（如最大二分匹配）转化为流量问题，并使用 Ford-Fulkerson 算法实现最大流问题的求解，该方法取得了 100% 的理想匹配效果。

神经双分图匹配

Neural Bipartite Matching

Inspired by the Elitzur-Vaidman bomb testing problem [arXiv:hep-th/9305002],
we introduce a new query complexity model, which we call bomb query complexity
$B(f)$. We investigate its relationship with the usual quantum query complexity
$Q(f)$, and show that $B(f)=\Theta(Q(f)^2)$.
This result gives a new method to upper bound the quantum query complexity:
we give a method of finding bomb query algorithms from classical algorithms,
which then provide nonconstructive upper bounds on $Q(f)=\Theta(\sqrt{B(f)})$.
We subsequently were able to give explicit quantum algorithms matching our
upper bound method. We apply this method on the single-source shortest paths
problem on unweighted graphs, obtaining an algorithm with $O(n^{1.5})$ quantum
query complexity, improving the best known algorithm of $O(n^{1.5}\sqrt{\log
n})$ [arXiv:quant-ph/0606127]. Applying this method to the maximum bipartite
matching problem gives an $O(n^{1.75})$ algorithm, improving the best known
trivial $O(n^2)$ upper bound.

本文提出了基于炸弹测试问题的一种新的查询复杂度模型：炸弹查询复杂度，并研究了它与常规量子查询复杂度的关系，并表明其与最短路径问题和最大二分匹配问题的应用。