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.
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.