12

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$, and suppose that it preserves distances up to a factor of $C$. In particular, the $n$ points $\varphi(e_1),\ldots,\varphi(e_n)$ are within distance $C$ of $\...


11

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 volume simplices and sub-determinants", arXiv:1406.3512 and SODA 2015. (They talk about the largest volume simplex contained in the convex hull, rather than the ...


8

From any choice of a polytope $P$ in ${\mathbb R}^k$, $\epsilon$, and a point $q$ in ${\mathbb R}^k$ it is possible to find a polytope $\hat P$ in ${\mathbb R}^{k+1}$, together with an embedding of ${\mathbb R}^k$ into ${\mathbb R}^{k+1}$, such that $\hat P$ is within $\epsilon$ Hausdorff distance of (the embedded image of) $P$ and such that (the embedded ...


7

You can try and use qhull http://www.qhull.org/ - it can compute the volume of the convex hull of the vertices. However, a priori I do not see any reason for it to perform reasonably for your range of numbers. If qhull does not work, you can try CGAL/GALIA. In the worst case, you can try and impelement one of the random walk algorithms you mentioned - they ...


6

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) form a polygon of area $1$ (this polygon $Q$ can be computed in near linear time in the plane). Assume the largest bounded cell $C$ in the arrangement of lines ...


5

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 is GI-hard (Agrawal-Saxena STACS '06, author's freely available version), and in fact is at least as hard as testing isomorphism of algebras. Now, GI-hardness is ...


3

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 the sphere, then the far neighbour for the antipodal point $-q$ is the NN to $q$. There might be a full version written somewhere on the web... http://dblp.org/...


3

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/2$ points that are all the same (or all within distance 1 from each other), and $N/2$ points that are all widely separated (at distance at least 1 from every ...


2

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$ behaves as $$ \Theta(dk\log k).$$


2

If your goal is to find a point in $P$ or determine that $P$ is empty, why don't you do the following. Let $H$ be a set of half-spaces, initially empty. Let $x$ be a point, initially equal to $0^k$. Give $x$ to the oracle. If the oracle said $x \in P$, you've done. Otherwise, let $S$ be the violated half-space returned by the oracle. Let $y$ be the ...


1

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, 1)$, hence the claim doesn't hold even when $n = 2$. The claim doesn't hold for convex functions either. $f(x, y) = 2(x + y) + |x - y|$ is one counterexample: $...


1

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

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|X|=m<\infty$ while $E|X|^2=\infty$; one such example is the Pareto family https://math.stackexchange.com/questions/236181/example-of-a-general-random-...


1

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 with coordinates smaller in all dimensions below your query point. Actually what you are looking for is a dynamic orthogonal range reporting datastructure. But I ...


1

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 differently. Locality preserving projections is linear because the parameterization is linear: $y_i = x_iW$. Laplacian eigenmaps is non-linear because the ...


1

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 polyhedron. If a supporting hyperplane does not exists, you know that the point is contained in the polyhedron. Otherwise, the supporting hyperplane helps you to ...


1

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+1)k^2\log k$.


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