What is the meaning of O( polylog(n) )? In particular, how is polylog(n) defined?

Question

Abuse of notation or not, polylog(n) does mean "some polynomial in log(n)", just as "poly(n)" can mean "some polynomial in n". So O(polylog(n)) means "O((log n)^k) for some k". (See Wikipedia: Polylogarithmic, or, to see it in context, Prof. Scott Aaronson's blog: My Favorite Growth Rates.)

The point is that just as we often don't care about constant factors, it is often convenient to ignore powers of logarithms. Sometimes the "log factors" are ignored entirely and you might see "Õ(f(n))" — O with a tilde above it — which means "O(f(n) polylog(f(n)))", i.e., "O(f(n) (log f(n))^k) for some k".

The way it is used in this paper seems to be describing something as:

O(log^p n)