Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds

The study investigates the trade-off between round complexity (the number of sequential batches of queries) and query complexity (the total number of PAIR queries) when learning an unknown partition of $n$ elements. While it is well-established that $O(n|P|)$ queries are necessary and sufficient to learn a partition, the most efficient algorithms for this are highly sequential. This paper explores how randomization can reduce the number of rounds required to achieve near-optimal query complexity.

The authors utilize random sampling to construct 'nets'—small subsets of elements that hit all sufficiently large parts of the hidden partition. By performing pairwise queries on these samples, the algorithm identifies representatives for the parts. In subsequent rounds, these representatives are used to classify the remaining elements. The authors also develop adversarial lower-bound arguments to prove that the number of rounds cannot be reduced further without significantly increasing the query count, establishing tight bounds for both known and unknown numbers of parts.

• Known Number of Parts ($k$): The authors provide a 3-round randomized algorithm using $O(nk \log n)$ queries. They prove that 2 rounds are insufficient, requiring $\Omega(n^{4/3}k^{2/3})$ queries, matching the deterministic lower bound.
• Unknown Number of Parts: The authors provide a 4-round randomized algorithm using $O(n|P| \log^2 n)$ queries. They prove that 3 rounds are insufficient to achieve near-optimal query complexity.
• Deterministic Comparison: The paper highlights an exponential gap between randomized and deterministic round complexity. While deterministic algorithms require $\Theta(\log n / \log \log n)$ rounds when the number of parts is unknown, randomized algorithms achieve this in a constant 4 rounds.