On the hardness of approximating label-cover. (English) Zbl 1178.68676
Summary: The Label-Cover problem, defined by S. Arora, L. Babai, J. Stern and Z. Sweedyk [Proceedings of 34th IEEE Symposium on Foundations of Computer Science, 724–733 (1993)], serves as a starting point for numerous hardness of approximation reductions. It is one of six ‘canonical’ approximation problems in the survey of S. Arora and C. Lund [Hardness of Approximations, in: Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, Chapter 10 (1996)]. In this paper we present a direct combinatorial reduction from low error-probability PCP to Label-Cover showing it NP-hard to approximate to within 2\((\log n)^{1 - o(1)}\). This improves upon the best previous hardness of approximation results known for this problem.We also consider the Minimum-monotone-satisfying-assignment Full-size image problem of finding a satisfying assignment to a monotone formula with the least number of 1’s, introduced by M. Alekhnovich, S. Buss, S. Moran and T. Pitassi [J. Symb. Log. 66, No.1, 171–191 (2001; Zbl 0977.03032)]. We define a hierarchy of approximation problems obtained by restricting the number of alternations of the monotone formula. This hierarchy turns out to be equivalent to an AND/OR scheduling hierarchy suggested by M. H. Goldwasser and R. Motwani [Lect. Notes Comput. Sci. 1272, 307–320 (1997)]. We show some hardness results for certain levels in this hierarchy, and place Label-Cover between levels 3 and 4. This partially answers an open problem from M. H. Goldwasser, R. Motwani regarding the precise complexity of each level in the hierarchy, and the place of Label-Cover in it.
MSC:
| 68W25 | Approximation algorithms |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
Citations:
Zbl 0977.03032References:
| [1] | M. Alekhnovich, S. Buss, S. Moran, T. Pitassi, Minimum propositional proof length is NP-hard to linearly approximate, manuscript, 1998; M. Alekhnovich, S. Buss, S. Moran, T. Pitassi, Minimum propositional proof length is NP-hard to linearly approximate, manuscript, 1998 · Zbl 0911.03028 |
| [2] | Arora, S.; Babai, L.; Stern, J.; Sweedyk, Z., The hardness of approximate optima in lattices, codes and linear equations, (Proceedings of 34th IEEE Symposium on Foundations of Computer Science (1993)), 724-733 |
| [3] | Bellare, M.; Goldwasser, S.; Lund, C.; Russell, A., Efficient multi-prover interactive proofs with applications to approximation problems, (Proceedings of 25th ACM Symposium on Theory of Computing (1993)), 113-131 |
| [4] | Dinur, I.; Fischer, E.; Kindler, G.; Raz, R.; Safra, S., PCP characterizations of NP: Towards a polynomially-small error-probability, (Proceedings of 31st ACM Symposium on Theory of Computing (1999)), 29-40 · Zbl 1346.68096 |
| [5] | Feige, U.; Lovász, L., Two-prover one-round proof systems: Their power and their problems, (Proceedings of 24th ACM Symposium on Theory of Computing (1992)), 733-741 |
| [6] | Goldwasser, M. H.; Motwani, R., Intractability of assembly sequencing: Unit disks in the plane, (Proceedings of the Workshop on Algorithms and Data Structures. Proceedings of the Workshop on Algorithms and Data Structures, Lecture Notes in Comput. Sci., vol. 1272 (1997), Springer-Verlag: Springer-Verlag Berlin), 307-320 · Zbl 1497.68528 |
| [7] | Johnson, D. S., Approximation algorithms for combinatorial problems, J. Comput. System Sci., 9, 256-278 (1974) · Zbl 0296.65036 |
| [8] | Lapidot, D.; Shamir, A., Fully parallelized multi prover protocols for NEXPTIME, (Proceedings of 32nd IEEE Symposium on Foundations of Computer Science (1991)), 13-18 |
| [9] | Lovász, L., On the ratio of optimal integral and fractional covers, Discrete Math., 13, 383-390 (1975) · Zbl 0323.05127 |
| [10] | Lund, C.; Yannakakis, M., On the hardness of approximating minimization problems, J. ACM, 41, 5, 960-981 (1994) · Zbl 0814.68064 |
| [11] | Raz, R., A parallel repetition theorem, SIAM J. Comput., 27, 3, 763-803 (1998) · Zbl 0911.68082 |
| [12] | Raz, R.; Safra, S., A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, (Proceedings of 29th ACM Symposium on Theory of Computing (1997)), 475-484 · Zbl 0963.68175 |
| [13] | Umans, C., Hardness of approximating \(Σ^p_2\) minimization problems, (40th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’99) (1999)), 465-474 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
