On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy
by Ishay Haviv, Oded Regev, and Amnon Ta-Shma
Theory of Computing, Volume 3(3), pp. 45-60, 2007
Bibliography with links to cited articles
[1] N. Alon and M. Capalbo: Smaller explicit superconcentrators. Internet Math., 1(2):151–163, 2004. [InternetMath:1(2):151–163].
[2] S. Arora and C. Lund: Hardness of approximation. In Dorit S. Hochbaum, editor, Approximation algorithms for NP-hard problems. PWS, Boston, 1996.
[3] O. Gabber and Z. Galil: Explicit constructions of linear-sized superconcentrators. Journal of Computer and System Sciences, 22(3):407–420, June 1981. [JCSS:10.1016/0022-0000(81)90040-4].
[4] V. Guruswami, D. Micciancio, and O. Regev: The complexity of the covering radius problem on lattices and codes. Computational Complexity, 14(2):90–121, 2005. Preliminary version in CCC’04. [doi:10.1007/s00037-005-0193-y].
[5] I. Haviv and O. Regev: Hardness of the covering radius problem on lattices. In Proc. of 21st Ann. Conf. on Computational Complexity (CCC’06), pp. 145–158. IEEE Computer Society Press, 2006. [CCC:10.1109/CCC.2006.23].
[6] K.-I. Ko and C.-L. Lin: Non-approximability in the polynomial-time hierarchy. Technical Report 94-2, Dept. of Computer Science, SUNY at Stony Brook, 1994.
[7] K.-I. Ko and C.-L. Lin: On the longest circuit in an alterable digraph. J. Global Optimization, 7(3):279–295, 1995. [Springer:k74448w88p1483ww].
[8] A. Lubotzky, R. Phillips, and P. Sarnak: Ramanujan graphs. Combinatorica, 8(3):261–277, 1988. [Springer:k285687344657q53].
[9] G. A. Margulis: Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii, 24(1):51–60, 1988.
[10] C. H. Papadimitriou and M. Yannakakis: Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43(3):425–440, 1991. [JCSS:10.1016/0022-0000(91)90023-X].
[11] M. Schaefer and C. Umans: Completeness in the polynomial-time hierarchy: A compendium. SIGACT News, 33(3):32–49, September 2002. Guest column in Complexity Theory Column. [SIGACT:10.1145/582475.582484].
[12] M. Schaefer and C. Umans: Completeness in the polynomial-time hierarchy: Part II. SIGACT News, 33(4):22–36, December 2002. Guest column in Complexity Theory Column. [SIGACT:10.1145/601819.601829].
[13] C.A. Tovey: A simplified NP-complete satisfiability problem. Discrete Applied Mathematics, 8(1):85–89, 1984. [Elsevier:10.1016/0166-218X(84)90081-7].
[14] V.V. Vazirani: Approximation algorithms. Springer-Verlag, Berlin, 2001.