standard sequential algorithm with polylog runtime?

Question

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$?

Answer 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)$.