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$?
standard sequential algorithm with polylog runtime?
algorithms;time complexity
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 algorithmsPoly-Logarithmic Deterministic Fully-Dynamic Algorithmsfor 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 inPolylogarithmic Time per Operation (PDF)Lists of connectivity problemsMaintaining Dynamic Sequences under Equality Testsin 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)$ timePoint 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)$.