CMP.11:11 - SoTA-Echoing

How can a performance limit cover procedures not yet invented? Adopt the decision-tree construction in Morin’s comparison-sorting analysis, in :4.2–4.3 and :5.2. It overcomes the limit of timing or analyzing only the current algorithm by counting distinctions every comparison procedure must make. Direct performance analysis remains the cheaper sufficient method when the question concerns only that implementation. A new access primitive, key promise or output requirement reopens the universal comparison claim.

For randomized access, adopt the explicit separation of deterministic, zero-error, bounded-error and expected-cost models in Blais’s Randomized Complexity, query-complexity treatment, for :4.1 and :4.4. The coupled proof in :5.1 supplies its own bound rather than transferring a deterministic adversary unchanged. A direct coupling is lighter than a general minimax argument when it settles the limit; an input-distribution or stronger information method is useful when the simple pair does not. Changed promises, error or cost quantifiers reopen that selection.

The same course’s communication-complexity treatment, following Rao and Yehudayoff’s 2020 account, supplies the transcript and public-randomness distinction adapted in :5.3. A full string is the simple zero-error choice; random parity accepts bounded error to reduce communication while retaining local computation and shared randomness. A changed requirement for zero error, private randomness or adaptive adversarial inputs changes the comparison. This bounded choice does not claim that communication, query and physical limits are interchangeable.