Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance

Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani +1

How many adjacency matrix queries (also known as pair queries) are required to estimate the size of a maximum matching in an $n$-vertex graph $G$? We study this fundamental questio…