Maintaining order in a list in $AC^0$ in $O(1)$ time

Question

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 09 '14 at 04: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 09 '14 at 04: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 09 '14 at 09:32

score 6 · Accepted Answer · answered Apr 13 '13 at 22:34

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

Maintaining order in a list in $AC^0$ in $O(1)$ time

1 Answers1