Christian Konrad

A semi-streaming algorithm in dynamic graph streams processes any n -vertex graph by making one or multiple passes over a stream of insertions and deletions to edges of the graph and using O ( n · polylog( n )) space. Semi-streaming algorithms for dynamic streams were first obtained in the seminal work of Ahn, Guha, and McGregor in 2012, alongside the introduction of the graph sketching technique, which remains the de facto way of designing algorithms in this model and a highly popular technique for designing graph algorithms in general. We settle the pass complexity of approximating maximum matchings in dynamic streams via semi-streaming algorithms by improving the state-of-the-art in both upper and lower bounds: • We present a randomized sketching based semi-streaming algorithm for O (1)-approximation of maximum matching in dynamic streams using O (log log n ) passes. The approximation ratio of this algorithm can be improved to (1 + ε) for any fixed ε > 0 even on weighted graphs using standard techniques. This exponentially improves upon several O (log n ) pass algorithms developed for this problem since the introduction of the dynamic graph streaming model. • We prove that any semi-streaming algorithm (not only sketching based) for O (1)-approximation of maximum matching in dynamic streams requires Ω (log log n ) passes. This presents the first multi-pass lower bound for this problem, which is already also optimal, settling a longstanding open question in this area.

Submesoscale flows are energetic motions on scales of several kilometers that may lead to substantial vertical motions. Here we present satellite and ship radar as well as underway conductivity‐temperature‐depth and Acoustic Doppler Current Profiler observations of a cyclonic submesoscale filament in the marginal ice zone of Fram Strait. The filament created a 500‐m thin and 50‐km long sea ice streak and extends to >250‐m depth with a negative/positive density anomaly within/below the halocline. The frontal jets of 0.5 m/s are in turbulent thermal wind balance while the ageostrophic secondary circulation in places appears to subduct Atlantic Water at >50 m/day. Our study reveals the submesoscale dynamics related to sea ice shapes that can be sensed remotely and shows how submesoscale dynamics contribute to shaping the marginal ice zone. It also demonstrates the co‐occurrence and mixing of water masses over short horizontal scales, which has implications for ocean and sea ice models and understanding of patch formation of planktonic organisms.