On the complexity of approximating the VC dimension. (English) Zbl 1059.68049
Summary: We study the complexity of approximating the VC dimension of a collection of sets, when the sets are encoded succinctly by a small circuit. We show that this problem is: \(\Sigma_3^p\)-hard to approximate to within a factor \(2-\varepsilon\) for all \(\varepsilon >0\), approximable in \(\mathcal{AM}\) to within a factor 2, and \(\mathcal{AM}\)-hard to approximate to within a factor \(N^{1-\varepsilon}\) for all \(\varepsilon>0\). To obtain the \(\Sigma_3^p\)-hardness result we solve a randomness extraction problem using list-decodable binary codes; for the positive result we utilize the Sauer-Shelah(-Perles) Lemma. We prove analogous results for the \(q\)-ary VC dimension, where the approximation threshold is \(q\).
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
complexity of approximationReferences:
| [1] | Alon, N., On the density of sets of vectors, Discrete Math., 46, 199-202 (1983) · Zbl 0514.05003 |
| [2] | Babai, L.; Moran, S., Arthur-Merlin gamesa randomized proof system, and a hierarachy of complexity classes, J. Comput. System Sci., 36, 254-276 (1988) · Zbl 0652.03029 |
| [3] | Bennett, C.; Brassard, G.; Robert, J., Privacy amplification by public discussion, SIAM J. Comput., 17, 2, 210-229 (1988) · Zbl 0644.94010 |
| [4] | B. Chor, J. Friedman, O. Goldreich, J. Hastad, S. Rudich, R. Smolensky, The bit extraction problem or \(t\); B. Chor, J. Friedman, O. Goldreich, J. Hastad, S. Rudich, R. Smolensky, The bit extraction problem or \(t\) |
| [5] | V. Guruswami, P. Indyk, Expander-based constructions of efficiently decodable codes, in: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS), Las Vegas, NV, 2001, pp. 658-667.; V. Guruswami, P. Indyk, Expander-based constructions of efficiently decodable codes, in: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS), Las Vegas, NV, 2001, pp. 658-667. |
| [6] | V. Guruswami, M. Sudan, List decoding algorithms for certain concatenated codes, in: Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC), Portland, OR, 2000.; V. Guruswami, M. Sudan, List decoding algorithms for certain concatenated codes, in: Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC), Portland, OR, 2000. · Zbl 1296.94170 |
| [7] | J. Kahn, G. Kalai, N. Linial, The influence of variables on Boolean functions, in: Proceedings of the 29th Annual Symposium on Foundations of Computer Science (FOCS), White Plains, NY, 1988, pp. 68-80.; J. Kahn, G. Kalai, N. Linial, The influence of variables on Boolean functions, in: Proceedings of the 29th Annual Symposium on Foundations of Computer Science (FOCS), White Plains, NY, 1988, pp. 68-80. |
| [8] | Karpovsky, M. G.; Milman, V., Coordinate density of sets of vectors, Discrete Math., 24, 177-184 (1978) · Zbl 0401.05015 |
| [9] | K.-I. Ko, C.-L. Lin, Non-approximability in the polynomial-time hierarchy, Technical Report TR-94-2, Department of Computer Science, State University of New York at Stony Brook, 1994.; K.-I. Ko, C.-L. Lin, Non-approximability in the polynomial-time hierarchy, Technical Report TR-94-2, Department of Computer Science, State University of New York at Stony Brook, 1994. |
| [10] | Ko, K.-I.; Lin, C.-L., On the complexity of min-max optimization problems and their approximation, (Du, D.-Z.; Pardalos, P. M., Minimax and Applications (1995), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 219-239 · Zbl 0847.90117 |
| [11] | N. Linial, Y. Mansour, R.L. Rivest, Results on learnability and the Vapnik-Červonenkis dimension, in: Proceedings of FOCS, White Plains, NY, 1988, pp. 120-129.; N. Linial, Y. Mansour, R.L. Rivest, Results on learnability and the Vapnik-Červonenkis dimension, in: Proceedings of FOCS, White Plains, NY, 1988, pp. 120-129. |
| [12] | Nisan, N.; Ta-Shma, A., Extracting randomnessa survey and new constructions, J. Comput. System Sci., 58, 1, 148-173 (1999) · Zbl 0943.68190 |
| [13] | Papadimitriou, C. H.; Yannakakis, M., On limited nondeterminism and the complexity of the V-C dimension, J. Comput. System Sci., 53, 2, 161-170 (1996) · Zbl 0859.68031 |
| [14] | Sauer, N., On the density of families of sets, J. Combin. Theory, A, 13, 145-147 (1972) · Zbl 0248.05005 |
| [15] | Schaefer, M., Deciding the Vapnik-Červonenkis dimension is \(Σ_3^p\)-complete, J. Comput. System Sci., 58, 1, 177-182 (1999) · Zbl 0946.68118 |
| [16] | R. Shaltiel, C. Umans, Simple extractors for all min-entropies and a new pseudo-random generator, in: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS), Las Vegas, NV, 2001, pp. 648-657.; R. Shaltiel, C. Umans, Simple extractors for all min-entropies and a new pseudo-random generator, in: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS), Las Vegas, NV, 2001, pp. 648-657. |
| [17] | Shelah, S., A combinatorial problemstability and order for models and theories in infinitary languages, Pacific J. Math., 41, 247-261 (1972) · Zbl 0239.02024 |
| [18] | Sipser, M., Expanders, randomness, or time versus space, J. Comput. System Sci., 36, 3, 379-383 (1988) · Zbl 0652.68050 |
| [19] | A. Ta-Shma, C. Umans, and D. Zuckerman, Loss-less condensers, unbalanced expanders, and extractors, in: Proceedings of the 33rd ACM Symposium on Theory of computing (STOC), Hersonissos, Crete, Greece, 2001, pp. 143-152.; A. Ta-Shma, C. Umans, and D. Zuckerman, Loss-less condensers, unbalanced expanders, and extractors, in: Proceedings of the 33rd ACM Symposium on Theory of computing (STOC), Hersonissos, Crete, Greece, 2001, pp. 143-152. · Zbl 1323.68263 |
| [20] | A. Ta-Shma, D. Zuckerman, S. Safra, Extractors from Reed-Muller codes, in: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS), Las Vegas, NV, 2001, pp. 638-647.; A. Ta-Shma, D. Zuckerman, S. Safra, Extractors from Reed-Muller codes, in: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS), Las Vegas, NV, 2001, pp. 638-647. · Zbl 1094.68036 |
| [21] | C. Umans, Hardness of approximating \(Σ_2^p\); C. Umans, Hardness of approximating \(Σ_2^p\) |
| [22] | Vazirani, U., Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources, Combinatorica, 7, 4, 375-392 (1987) · Zbl 0643.94002 |
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.
