Name
Abstract | ||
|---|---|---|
We show that learning a convex body in $\RR^d$, given random samples from the body, requires $2^{\Omega(\sqrt{d/\eps})}$ samples. By learning a convex body we mean finding a set having at most $\eps$ relative symmetric difference with the input body. To prove the lower bound we construct a hard to learn family of convex bodies. Our construction of this family is very simple and based on error correcting codes. |
Year | Venue | Keywords |
|---|---|---|
2009 | Clinical Orthopaedics and Related Research | error correction code,computational geometry,lower bound,convex body,random sampling |
DocType | Volume | Citations |
Conference | abs/0904.1227 | 8 |
PageRank | References | Authors |
0.76 | 7 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Navin Goyal | 1 | 85 | 6.51 |
| Luis Rademacher | 2 | 269 | 21.60 |