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

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

• Multiplication has only recently (since Pentium III) been in $AC^0$. Can we include solutions which use multiplication? – A T Jun 9 '14 at 4:50
• I don't think that's correct. First, I don't think multiplication is in $AC^0$. Second, I don't think particular machines, like the Pentium III you mention, have anything to do with the question of whether multiplication is in $AC^0$. Finally, as demonstrated in the question, I obviously am aware of several multiplication-based algorithms for this problem, so adding more in a new "answer" does not in any way improve things. – jbapple Jun 9 '14 at 4:57
• Found where I read about this; it was about Pentium 4 not III; and didn't implement multiplication instead worked around it with a new instruction from that processor: M. Thorup, ‘On AC0 Implementations of Fusion Trees and Atomic Heaps’, in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, USA, 2003, pp. 699–707. – A T Jun 9 '14 at 9:32

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.