Tight Non-Adaptive Query-Approximation Tradeoffs for Maximum Matching Size EstimationResearch Paper
Maximum matching is a benchmark problem for algorithms with limited access to their input. In the adjacency-list query model an algorithm cannot read the graph; it may only ask for the degree of a vertex or for the -th entry of its adjacency list. Outputting the edges of a constant-factor approximate matching in this model needs queries…