๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On ordinal VC-dimension and some notions of complexity

โœ Scribed by Eric Martin; Arun Sharma; Frank Stephan

Book ID
108281233
Publisher
Elsevier Science
Year
2006
Tongue
English
Weight
282 KB
Volume
364
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

On the complexity of approximating the V
On the complexity of approximating the VC dimension
โœ Elchanan Mossel; Christopher Umans ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 181 KB

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 appr

On the complexity of some geometric prob
On the complexity of some geometric problems in unbounded dimension
โœ Nimrod Megiddo ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 429 KB

This paper examines the complexity of several geometric problems due to unbounded dimension. The problems considered are: (i) minimum cover of points by unit cubes, (ii) minimum cover of points by unit ball% and (iii) minimum number of lines to hit a set of balls. Each of these problems is proven no

On the effective dimension and dynamic c
On the effective dimension and dynamic complexity of earthquake faults
โœ Marian Anghel ๐Ÿ“‚ Article ๐Ÿ“… 2004 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 929 KB

We measure the effective dimensionality of a driven, dissipative fault model as its dynamics explore a wide parameter range from a crack like model to a dislocation model. The dynamics of each fault model are probed by recording (a) the first and second order moments of the stresses and slips define