𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the complexity of approximating the VC dimension

✍ Scribed by Elchanan Mossel; Christopher Umans

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
181 KB
Volume
65
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

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:

3 -hard to approximate to within a factor 2 Γ€ e for all e > 0; * approximable in AM to within a factor 2; and * AM-hard to approximate to within a factor N 1Γ€e for all e > 0:

To obtain the S p 3 -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:

πŸ“œ SIMILAR VOLUMES

The VC-Dimension of Sperner Systems
The VC-Dimension of Sperner Systems
✍ G. Greco πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 119 KB

A family F of subsets of a finite set X shatters a set D X, if the intersections of the members of F with D coincide with the power set of D. The maximum size of a set shattered by F is the VC-dimension (or density) of the system. P. Frankl (1983, J. Combin. Theory Ser. A 34, 41 45) investigates the

On the complexity of approximating mappi
On the complexity of approximating mappings using feedforward networks
✍ Pascal Koiran πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 359 KB

I4~, study the approximation o.f continuous mappings and dichotomies by one-hidden-layer networks from a computational point of view Our approach is based on a new approximation method specially designed for constructing "small networks. We give upper bounds on the size o.f these networks.

The Space Complexity of Approximating th
The Space Complexity of Approximating the Frequency Moments
✍ Noga Alon; Yossi Matias; Mario Szegedy πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 172 KB

The frequency moments of a sequence containing m i elements of type i, 1 i n, are the numbers F k = n i=1 m k i . We consider the space complexity of randomized algorithms that approximate the numbers F k , when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it

On Limited Nondeterminism and the Comple
On Limited Nondeterminism and the Complexity of the V-C Dimension
✍ Christos H. Papadimitriou; Mihalis Yannakakis πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 439 KB

We characterize precisely the complexity of several natural computational problems in NP, which have been proposed but not categorized satisfactorily in the literature: Computing the Vapnik Chervonenkis dimension of a 0 1 matrix; finding the minimum dominating set of a tournament; satisfying a Boole

Complexity of approximating the oriented
Complexity of approximating the oriented diameter of chordal graphs
✍ Fedor V. Fomin; MartΓ­n Matamala; Ivan Rapaport πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 135 KB

## Abstract The oriented diameter of a bridgeless connected undirected (__bcu__) graph __G__ is the smallest diameter among all the diameters of strongly connected orientations of __G__. We study algorithmic aspects of determining the oriented diameter of a chordal graph. We (a) construct a linear‐