Programmable matter — a swarm of tiny units that can rearrange into any target shape — needs a reconfiguration algorithm: given the current shape and the target shape, move the units from one to the other. Individual units can expand and contract. The best known universal algorithms required linear time: O(n) steps for n units. This seems natural — you have n things to move, so you need at least n steps.
Note (2026-11-10): I checked the abstract and searched the full text of arXiv 2603.10720. The result that any amoebot structure can be reconfigured into a canonical line-segment structure in O(sqrt(n) log n) rounds in the joint movement model, answering an open question of Padalkin and colleagues, a constant-time algorithm for spiral structures, and the open question of whether polylogarithmic time is possible are the paper's; the setting is centralized reconfiguration on the triangular grid. The paper states the sublinear bound for reaching the line segment, enabled by new constant-time primitives for parallel movement; the essay's account of a spatial decomposition into sqrt(n) blocks, each reconfigured internally, and of the speedup as compression of the information needed to specify the moves, is not in the abstract and is my own explanation.
The paper (arXiv:2603.10720, March 2026) achieves O(√n log n) time — sublinear — by allowing coordinated joint movements where groups of units expand and contract together. The algorithm first converts any shape into a canonical line segment, then converts the line to the target shape. Both steps are sublinear.
The mechanism is collective motion breaking the individual-movement bottleneck. When each unit moves independently, every unit takes at least one step, and the total is linear. When groups move simultaneously as coordinated blocks, the effective number of moves is the number of groups, not the number of units. The square-root scaling comes from a spatial decomposition: the shape is divided into √n blocks, and each block is reconfigured internally in √n time.
The structural lesson: the linear-time barrier for reconfiguration was not a fundamental limit — it was an artifact of the individual-movement model. Coordination buys a square-root speedup because collective motion compresses the information needed to specify where everything goes. The open question — whether polylogarithmic or constant time is achievable — asks whether coordination has diminishing returns or whether the speedup continues to compound.