@inproceedings{2b791a421e474cd3a396b233fbeaae1e,
title = "Quasilinear time complexity theory",
abstract = "This paper furthers the study of quasi-linear time complexity initiated by Schnorr and Gurevich and Shelah [GS89]. We show that the fundamental properties of the polynomial-time hierarchy carry over to the quasilineartime hierarchy. Whereas all previously known versions of the Valiant-Vazirani reduction from NP to parity run in quadratic time, we give a new 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 quasi-linear time, then all of NP is contained in quasi-polynomial time. Other connections to work by Stearns and Hunt [SH86, SH90, HS90] on “power indices” of NP languages are made.",
author = "Naik, \{Ashish V.\} and Regan, \{Kenneth W.\} and D. Sivakumar",
note = "Publisher Copyright: {\textcopyright} 1994, Springer Verlag. All rights reserved.; Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science (STACS'94) ; Conference date: 24-02-1994 Through 26-02-1994",
year = "1994",
doi = "10.1007/3-540-57785-8\_134",
language = "English",
isbn = "9783540577850",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "97--108",
editor = "Patrice Enjalbert and Mayr, \{Ernst W.\} and Wagner, \{Klaus W.\}",
booktitle = "STACS 1994 - 11th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings",
address = "Germany",
}