The (maximum receiver-centric) interference of a geometric graph (von (2005)) is studied. It is shown that, with high probability, the following results hold for a set, V, of n points independently and uniformly distributed in the unit d-cube, for constant dimension d: (1) there exists a connected graph with vertex set V that has interference O((log n)^ 1 3 ); (2) no connected graph with vertex set V has interference o((log n)^ 1 4 ); and (3) the minimum spanning tree of @math has interference Theta(( n)^ 1 2 ).
The definition of interference used in this paper was introduced by von Rickenbach al @cite_1 who proved upper and lower bounds on the interference of one dimensional point sets: The point set, @math , in this lower-bound consists of any sequence of points @math , all on a line, such that @math , for all @math . That is, the gaps between consecutive points decrease exponentially.
@cite_1
2121101422
We show a worst-case lower bound and a smoothed upper bound on the number of iterations performed by the Iterative Closest Point (ICP) algorithm. First proposed by Besl and McKay, the algorithm is widely used in computational geometry, where it is known for its simplicity and its observed speed. The theoretical study of ICP was initiated by Ezra, Sharir, and Efrat, who showed that the worst-case running time to align two sets of @math points in @math is between @math and @math . We substantially tighten this gap by improving the lower bound to @math . To help reconcile this bound with the algorithm's observed speed, we also show that the smoothed complexity of ICP is polynomial, independent of the dimensionality of the data. Using similar methods, we improve the best known smoothed upper bound for the popular k-means method to @math , once again independent of the dimension. Coalescence of semi-infinite geodesics remains a central question in planar first passage percolation. In this paper we study finer properties of the coalescence structure of finite and semi-infinite geodesics for exactly solvable models of last passage percolation. Consider directed last passage percolation on @math with i.i.d. exponential weights on the vertices. Fix two points @math and @math for some @math , and consider the maximal paths @math and @math starting at @math and @math respectively to the point @math for @math . Our object of study is the point of coalescence, i.e., the point @math with smallest @math . We establish that the distance to coalescence @math scales as @math , by showing the upper tail bound @math for some @math . We also consider the problem of coalescence for semi-infinite geodesics. For the almost surely unique semi-infinite geodesics in the direction @math starting from @math and @math , we establish the optimal tail estimate @math , for the point of coalescence @math . This answers a question left open by Pimentel (Ann. Probab., 2016) who proved the corresponding lower bound. We describe an @math -time algorithm for computing the exact probability that two @math -dimensional probabilistic point sets are linearly separable, for any fixed @math . A probabilistic point in @math -space is a normal point, but with an associated probability of existence; the existence probabilities of all points are independent. We also show that the @math -dimensional separability problem is equivalent to a @math -dimensional convex hull membership problem, which asks for the probability that a query point lies inside the convex hull of @math probabilistic points. Using this reduction, we improve the current best bound for the convex hull membership problem by a factor of @math . In addition, our algorithms can handle input degeneracies in which more than @math points may lie on a @math -dimensional subspace, thus resolving an open problem in 2013. Finally, we prove lower bounds for the separability problem via a reduction from the @math -SUM problem, which show in particular that our @math algorithms for @math -dimensional separability and @math -dimensional convex hull membership are nearly optimal. We prove lower bounds on the complexity of finding @math -stationary points (points @math such that @math ) of smooth, high-dimensional, and potentially non-convex functions @math . We consider oracle-based complexity measures, where an algorithm is given access to the value and all derivatives of @math at a query point @math . We show that for any (potentially randomized) algorithm @math , there exists a function @math with Lipschitz @math th order derivatives such that @math requires at least @math queries to find an @math -stationary point. Our lower bounds are sharp to within constants, and they show that gradient descent, cubic-regularized Newton's method, and generalized @math th order regularization are worst-case optimal within their natural function classes.