Name
Abstract | ||
|---|---|---|
We provide upper bounds for the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers whose membership tests are programs described by bounded-depth arithmetic networks. Our upper bounds are of the kind O(k2d2), where dis the depth of the network (representing the parallel running time) and kis the number of parameters needed to codify the concept. This bound becomes O(k2d) when membership tests are described by Boolean-arithmetic circuits. As a consequence we conclude that families of concepts classes having parallel polynomial time algorithms expressing their membership tests have polynomial VC dimension. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-75225-7_12 | ALT |
Keywords | Field | DocType |
parallel polynomial time,concept class,bounded-depth arithmetic network,kind o,concepts class,polynomial vc dimension,vapnik-chervonenkis dimension,parallel arithmetic computations,boolean-arithmetic circuit,upper bound,membership test,vc dimension,parallel computer,parallel computation,concept learning | Discrete mathematics,Combinatorics,VC dimension,Parameterized complexity,Polynomial,Concept learning,Arithmetic,Parallel running,Time complexity,Real number,Mathematics,Computation | Conference |
Volume | ISSN | Citations |
4754 | 0302-9743 | 1 |
PageRank | References | Authors |
0.38 | 10 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| César L. Alonso | 1 | 27 | 4.69 |
| Josè L. Montaña | 2 | 82 | 15.50 |