This paper furthers the study of quasilinear-time complexity initiated
by Schnorr and Gurevich and Shelah. We show that the fundamental prop
erties of the polynomial-time hierarchy carry over to the quasilinear-
time hierarchy. Whereas all previously known versions of the Valiant-V
azirani reduction from NP to parity run in quadratic time, we give a n
ew construction using error-correcting codes that runs in quasilinear
time. We show, however, that the important equivalence between search
problems and decision problems in polynomial time is unlikely to carry
over: if search reduces to decision for SAT in quasilinear time, then
all of NP is contained in quasipolynomial time. Other connections are
made to work by Steams and Hunt on ''power indices'' of NP languages,
and to work on bounded-query Turing reductions and helping by robust
oracle machines.