12 votes

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$, ...
user avatar
  • 14.1k
11 votes
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 ...
user avatar
6 votes

Largest cell in an arrangement

Somehow doing better than $O(n^d)$ looks hard. If the cell is significantly larger than its average expected size, one can use sampling, to find it. Formally, assume the bounded cells (in the plane) ...
user avatar
5 votes

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 ...
user avatar
3 votes

Far point queries in high dimensions

See the following paper. The two problems are equivalent more or less. To see that, assume that the points are on the unit sphere centered at the origin, and observe that if your NN query $q$ is on ...
user avatar
3 votes

VC dimension of intersection of half-spaces

It has been recently shown by Csikos, Kupavskii, Mustafa in "Optimal Bounds on the VC-dimension" that the VC dimension of $k$-fold unions (or intersections or XORs) of half-spaces in $R^d$ ...
user avatar
  • 10.1k
3 votes

Lower bound on probability of getting two close points in a sample of $n$ points

Here's a counter-example showing your desired bound is not possible, unless I am mistaken. It's a simple variant of the example in Roei's comment. Fix any $n$ and $N\ge 4n$. Take $D$ to contain $N/...
user avatar
  • 8,273
3 votes
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 ...
user avatar
1 vote

How to calculate complexity in a high dimensional space?

As far as I have understood, you aim to develop a framework to capture the hardness of combinatorial problems in 3D. However, there are major problems in your question. Your first sentence lacks a ...
user avatar
  • 93
1 vote

Multivariable concave function $(n - 1) f(x) >= \sum_{i=1}^{n} f(x_{-i})$

Consider the function $f(x, y) = 1 - e^{-(x + y)}$. Now $f(0, 0) = 0$, $f$ is increasing and concave, since $g(t) = -e^{-t}$ is concave. But $f(1, 0) + f(0, 1) = 2(1 - e^{-1}) > 1 - e^{-2} = f(1, ...
user avatar
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....
user avatar
  • 10.5k
1 vote
Accepted

Application of the inequality with expectations

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|...
user avatar
  • 10.1k
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)...
user avatar
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 ...
user avatar
  • 629
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 ...
user avatar
  • 1,085
1 vote

Is Locality preserving projections (LPP) method the same as Laplacian eigenmap method?

There is a subtle difference, which can be difficult to recognize. They both minimize the same objective: $\sum_{i,j} w_{ij} || y_i - y_j ||^2_2$ However, they parametrize the predictor on y ...
user avatar
1 vote

Batch membership testing for convex polyhedron specified in vertex representation

Instead of testing each point individually whether it is contained in the convex polyhedron, you should search for a supporting hyperplane of the polyhedron which separates the point from the ...
user avatar
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 $\leq$ $k + (d+...
user avatar
  • 46

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