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]. [ .pdf ] |
| [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. |
This file has been generated by bibtex2html 1.81.