Randomization Is Necessary for Learning from Symmetric Equivalence Queries

We resolve the deterministic-derandomization question of Braverman, Livni, Mansour, Moran, and Nissim for symmetric equivalence-query adversaries: no deterministic learner can match the dimension-only guarantees available to randomized learners. Under the protocol in which the target may be reselected from the current version space, symmetric two-point generators force deterministic complexity as large as linear in the number of concepts even when the Littlestone dimension is one, whereas randomized learning uses fewer than three expected queries in our examples. For independently resampled distributions over total orders, we determine the extremal deterministic complexity on the singleton class: it is $\Theta(\sqrt n)$. A uniform mixture of cyclic rotations has the exact value $1+\sum_{k=0}^{n-2}\prod_{r=1}^{k}(1-r/n)\sim\sqrt{\pi n/2}$, while a row lower-envelope inequality for the linear-order polytope, combined with a blocking-point learner, gives the matching universal $O(\sqrt n)$ upper bound. This statement permits proper class-internal queries that need not remain version-consistent. The same order-induced terminology hides a sharp distinction: for one fixed, known total order, a lexicographic projection of the standard optimal algorithm gives a version-consistent proper learner using at most $\mathrm{Ldim}(\mathcal{H})+1$ queries, and complete classes attain this bound. With a fixed target, arbitrary symmetric generators instead have a tight worst-case $\Theta(\log n)$ hierarchy on singleton classes, while every finite class admits a generator-dependent $2\log_2|\mathcal{H}|+O(1)$ deterministic upper bound. Randomized learning remains $O(\mathrm{Ldim})$ throughout.