Algorithmic Barriers to Detecting and Repairing Structural Overspecification in Adaptive Data-Structure Selection
arXiv:2603.24597v1 Announce Type: new Abstract: We study algorithmic barriers to detecting and repairing a systematic form of structural overspecification in adaptive data-structure selection. An input instance induces an implied workload signature, such as ordering, sparsity, dynamism, locality, or substring structure, and candidate implementations may be preferred because they match that full signature even when the measured workload evidence supports only a strict subset of it. Under a model in which pairwise evaluators favor implementations that realize the implied […]