standard sequential algorithm with polylog runtime?

At the Wikipedia article on time complexity, only a PRAM example is given for polylogarithmic time.

Let $T(n)$ denote the largest number of steps used by a machine to reach a final state on any input with size $n$ bits.


Is there a program for a standard sequential model of computation (e.g. a Turing machine or a sequential random-access machine), solving some natural problem, so that $T(n) \in \Theta((\log n)^k)$ for some fixed $k>1$?

Where each operation is $ O\left(\log^kn\right)$ amortized/expected; I don't know if necessarily $\Theta\left(\log^kn\right)$:

• Dynamic graph connectivity algorithms

• Poly-Logarithmic Deterministic Fully-Dynamic Algorithms

for Connectivity, Minimum Spanning Tree, 2-Edge,
and Biconnectivity (PDF)

• Dynamic graph connectivity in polylogarithmic worst case time (PDF, slides)

• Fully Dynamic 2-Edge Connectivity Algorithm in

Polylogarithmic Time per Operation (PDF)

• Lists of connectivity problems

-
Maintaining Dynamic Sequences under Equality Tests
in Polylogarithmic Time (PDF)

-
Distances and point-sets:

• Maintaining the miminal distance of a point set in polylogarithmic time (PDF, $O\left(\log^2n\right)$, Smid)

• New techniques for some dynamic closest-point and farthest-point problems ($O\left(\log^D n\right)$ Supowit)

• New Techniques For Exact And Approximate Dynamic Closest-Point Problems (PDF, Kapoor, Smid, $O\left(\log^D n \log \log n\right)$, though cites others with just $O(polylog)$)

• TOPP 63: Dynamic Planar Nearest Neighbors, lists 3 papers with data structures that have operations that run in $O\left(log^k n\right)$ time

• Point location algorithms,

• Monotone subdivisions, without fractional cascading, query-time is $O\left(\log^2 n\right)$

• Best known algorithms for point-location in higher-dimensions ($\gt 2$) have a trade-off; $O\left(\log n\right)$ query-time has large memory requirements that make them unscaleable. Reducing the memory requirements (for example to $O\left(n\log n\right)$ results in query-times of $O\left(\log^k n\right)$

• Efficient Partition Trees (PDF, Matousek, $O\left(\log^2 n\right)$ insertion time)

• An Implicit Data Structure For The Dictionary Problem That Runs In Polylog Time (Munro, $O\left(\log^2n\right)$)

There are also many algorithms with polylogarithmic factors; $\tilde {O}(\cdot)$ is notation that is used when hiding polylogarithmic factors. So $O\left(n\log^k n \right)\in\tilde {O}(n)$.

StackExchange Computer Science Q#16622, answer score: 6