# Tag Info

### Johnson and Lindenstrauss lemma for hamming space

Consider the $n$ vectors $e_1,\ldots,e_n$ of weight $1$, and the zero vector $e_0$. The Hamming distance between $e_0$ to any $e_i$ is $1$. Let $\varphi$ be a map into a Hamming cube of dimension $m$, ...
Accepted

### Maximum Polyhedron Volume in Given $n$ Points

This was shown to be hard (more precisely $\mathsf{NP}$-hard to approximate to better than exponential in $k$) by Marco Di Summa, Friedrich Eisenbrand, Yuri Faenza, Carsten Moldenhauer, "On largest ...

### Complexity of testing if two sets of $m$ points in $\mathbb{R}^n$ differ only by rotation?

I think this is open. Note that if instead of testing equivalence under rotations you ask for equivalence under the general linear group, then already testing equivalence of degree three polynomials ...
Accepted

### How to find the size of an ϵ-net of a vector space?

Note that $\mathcal{W}_{\epsilon}$ is an epsilon-net in the parametrization space, which is just $p$-dimensional Euclidean space. (So there is no need to think about covering numbers in e.g. spaces of ...

1 vote

### Lattice generation inside d-dimensional unit ball

In general, even telling whether any such point exists is hard; it is equivalent to the Shortest Vector Problem (SVP), and it is conjectured that there is no polynomial-time algorithm for this problem....
1 vote
Accepted

I don't think the claim is correct. Take $n=1$ (so the norm is just absolute value), $N=1$, and $u_1=1$. Let $X$ be any random variable with a finite first moment and infinite second moment (i.e., $E|... 1 vote ### Johnson and Lindenstrauss lemma for hamming space While other answers are correct, I want to mention one result from Polynomial Time Approximation Schemes for Geometric k-Clustering, which is weaker, which roughly says that there exists a (randomized)... 1 vote Accepted ### Johnson and Lindenstrauss lemma for hamming space Let the matrix consist of$n$points in$d$-dimensional space. We first generate a projection matrix$d\times K$whose each entry is sampled from the Cauchy distribution. Then the sketch matrix is ... 1 vote Accepted ### Data structure for storing points and finding a predecessor of a point What about first computing the skyline (a.k.a. maximal vectors, etc.) of all points, then maintain a data structure for orthogonal range reporting? The range you are interested in is the orthant ... 1 vote Accepted ### VC dimension of Voronoi cells in R^d? Please check Theorem 21.5, Section 21 in the book "A probabilistic Theory of Pattern Recognition (1996)" from Devroye, Gyorfi, and Lugosi. I think the following upper bound is valid: VC$\leqk + (d+...

Only top scored, non community-wiki answers of a minimum length are eligible