  We study the robust communication complexity of maximum matching. Edges of an
arbitrary $n$-vertex graph $G$ are randomly partitioned between Alice and Bob
independently and uniformly. Alice has to send a single message to Bob such
that Bob can find an (approximate) maximum matching of the whole graph $G$. We
specifically study the best approximation ratio achievable via protocols where
Alice communicates only $\widetilde{O}(n)$ bits to Bob.
  There has been a growing interest on the robust communication model due to
its connections to the random-order streaming model. An algorithm of Assadi and
Behnezhad [ICALP'21] implies a $(2/3+\epsilon_0 \sim .667)$-approximation for a
small constant $0 < \epsilon_0 < 10^{-18}$, which remains the best-known
approximation for general graphs. For bipartite graphs, Assadi and Behnezhad
[Random'21] improved the approximation to .716 albeit with a computationally
inefficient (i.e., exponential time) protocol.
  In this paper, we study a natural and efficient protocol implied by a
random-order streaming algorithm of Bernstein [ICALP'20] which is based on
edge-degree constrained subgraphs (EDCS) [Bernstein and Stein; ICALP'15]. The
result of Bernstein immediately implies that this protocol achieves an (almost)
$(2/3 \sim .666)$-approximation in the robust communication model. We present a
new analysis, proving that it achieves a much better (almost) $(5/6 \sim
.833)$-approximation. This significantly improves previous approximations both
for general and bipartite graphs. We also prove that our analysis of
Bernstein's protocol is tight.
