Maintaining order in a list in $AC^0$ in $O(1)$ time The order maintenance problem (or "maintaining order in a list") is to support the operations:


singleton: creates a list with one item, returns a pointer to it
insertAfter: given a pointer to an item, inserts a new item after it, returning a pointer to the new item
delete: given a pointer to an item, removes it from its list
minPointer: given two pointers to items in the same list, returns the one closer to the front of the list


I am aware of three solutions to this problem that perform all operations in $O(1)$ amortized time. They all use multiplication.


Athanasios K. Tsakalidis: Maintaining order in a generalized linked list
Dietz, P., D. Sleator, Two algorithms for maintaining order in a list
Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, and Jack Zito, “Two Simplified Algorithms for Maintaining Order in a List”


Can order be maintained in a list in $O(1)$ amortized time without using any arithmetic operations not in $AC^0$?
Yes!

Use a two-level structure as discussed at the end of Section 2 of the Dietz and Sleator paper. For the top structure, use a scapegoat tree. By using a balance factor that can be implemented in $AC^0$ (like $2$), we get the result.

See also exercise 8.12 from open data structures and Roura's "A new method for balancing binary search trees".