|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Optimal Multivalued Shattering | | Zoltán Füredi
; Attila Sali
; | | Date: |
8 Sep 2011 | | Abstract: | We have found the most general extension of the celebrated Sauer, Perles and
Shelah, Vapnik and Chervonenkis result from 0-1 sequences to $k$-ary codes
still giving a polynomial bound. Let $mathcal{C}subseteq {0,1,..., k-1}^n$
be a $k$-ary code of length $n$. For a subset of coordinates
$Ssubset{1,2,...,n}$ the projection of $mathcal{C}$ to $S$ is denoted by
$mathcal{C}|_S$. We say that $mathcal{C}$ $(i,j)$-{em shatters} $S$ if
$mathcal{C}|_S$ contains all the $2^{|S|}$ distinct vectors (codewords) with
coordinates $i$ and $j$. Suppose that $mathcal{C}$ does not $(i,j)$-shatter
any coordinate set of size $s_{i,j}geq 1$ for every $1leq i< jleq q$ and let
$p=sum (s_{i,j}-1)$. Using a natural induction we prove that $$ |{mathcal
C}|leq O(n^p)$$ for any given $p$ as $n o infty$ and give a construction
showing that this exponent is the best possible. Several open problems are
mentioned. | | Source: | arXiv, 1109.1748 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER