An α-centerpoint of a set of \(n\) input points in \(\mathbb R^d\), is a point such that any halfspace containing it, also contains an α-fraction of the input points. Recently a remarkable result of Cherapanamjeri [FOCS, 2024] gave the first polynomial time randomized algorithm for computing \(\Omega(1/d)\)-centerpoints. Here we give a practical and efficient polynomial time randomized algorithm for computing \(\Omega \left(\frac{1}{d\log^2d}\right)\)-centerpoints of arbitrary pointsets. Our algorithm is significantly simpler to implement, though it gives slightly worse quality centerpoints, and improves on the longstanding \(d^{O(d)}\) running time of Clarkson, Eppstein, Miller, Sturtivant and Teng [IJCGA, 1996] for obtaining such centerpoints.

In this work, we propose a novel dimensionality reduction technique, \textit{DiffRed}, which first projects the data matrix, A, along first $k_1$ principal components and the residual matrix $A^{*}$ (left after subtracting its $k_1$-rank approximation) along $k_2$ Gaussian random vectors. We evaluate \emph{M1}, the distortion of mean-squared pair-wise distance, and \emph{Stress}, the normalized value of RMS of distortion of the pairwise distances. We rigorously prove that \textit{DiffRed} achieves a general upper bound of $O\left(\sqrt{\frac{1-p}{k_2}}\right)$ on \emph{Stress} and $O\left(\frac{1-p}{\sqrt{k_2*\rho(A^{*})}}\right)$ on \emph{M1} where $p$ is the fraction of variance explained by the first $k_1$ principal components and $\rho(A^{*})$ is the \textit{stable rank} of $A^{*}$. These bounds are tighter than the currently known results for Random maps. Our extensive experiments on a variety of real-world datasets demonstrate that \textit{DiffRed} achieves near zero \emph{M1} and much lower values of \emph{Stress} as compared to the well-known dimensionality reduction techniques. In particular, \textit{DiffRed} can map a 6 million dimensional dataset to 10 dimensions with 54% lower \emph{Stress} than PCA.

International audience

Abstract. The concentration of the sizes of largest induced paths and cycles (holes) is studied in Erdős–Rényi random graphs. A 2-point concentration is proved for the size of the largest induced path and cycle for all [Formula: see text] satisfying [Formula: see text] and [Formula: see text] where [Formula: see text] is any constant. No such tight concentration (within two consecutive values) was previously known for induced paths and cycles. As a corollary, a significant additive improvement is obtained over a 40-year-old result of Erdős and Palka [ Discrete Math., 46 (1983), pp. 145–150] concerning the size of the largest induced tree in a dense random graph. Further, the induced path decomposition number and induced tree decomposition number, i.e., the smallest number of parts into which the vertex set of a graph can be partitioned such that every part induces a (i) path or (ii) tree, respectively, are studied for [Formula: see text]. The arguments involve the second moment method together with an adaptation of a martingale-based technique of Krivelevich et al. [ Random Structures Algorithms, 22 (2003), pp. 1–14] for monotone high-degree polynomial random variables to the nonmonotone setting. A lower bound is proved showing the tightness of the application of the inequality up to logarithmic factors in the exponent. The modified inequality is then stated and proved in a general setting, which may be of independent interest.

We study the connections between three seemingly different combinatorial structures - uniform brackets in statistics and probability theory, containers in online and distributed learning theory, and combinatorial Macbeath regions, or Mnets in discrete and computational geometry. We show that these three concepts are manifestations of a single combinatorial property that can be expressed under a unified framework along the lines of Vapnik-Chervonenkis type theory for uniform convergence. These new connections help us to bring tools from discrete and computational geometry to prove improved bounds for these objects. Our improved bounds help to get an optimal algorithm for distributed learning of halfspaces, an improved algorithm for the distributed convex set disjointness problem, and improved regret bounds for online algorithms against σ-smoothed adversary for a large class of semi-algebraic threshold functions.

Abstract Randomized incremental construction (RIC) is one of the most important paradigms for building geometric data structures. Clarkson and Shor developed a general theory that led to numerous algorithms which are both simple and efficient in theory and in practice. Randomized incremental constructions are usually space-optimal and time-optimal in the worst case, as exemplified by the construction of convex hulls, Delaunay triangulations, and arrangements of line segments. However, the worst-case scenario occurs rarely in practice and we would like to understand how RIC behaves when the input is nice in the sense that the associated output is significantly smaller than in the worst case. For example, it is known that the Delaunay triangulation of nicely distributed points in $${\mathbb {E}}^d$$ E d or on polyhedral surfaces in $${\mathbb {E}}^3$$ E 3 has linear complexity, as opposed to a worst-case complexity of $$\Theta (n^{\lfloor d/2\rfloor })$$ Θ ( n ⌊ d / 2 ⌋ ) in the first case and quadratic in the second. The standard analysis does not provide accurate bounds on the complexity of such cases and we aim at establishing such bounds in this paper. More precisely, we will show that, in the two cases above and variants of them, the complexity of the usual RIC is $$O(n\log n)$$ O ( n log n ) , which is optimal. In other words, without any modification, RIC nicely adapts to good cases of practical value. At the heart of our proof is a bound on the complexity of the Delaunay triangulation of random subsets of $${\varepsilon }$$ ε -nets. Along the way, we prove a probabilistic lemma for sampling without replacement, which may be of independent interest.

Given a set P of n points and a constant k, we are interested in computing the persistent homology of the Čech filtration of P for the k-distance, and investigate the effectiveness of dimensionality reduction for this problem, answering an open question of Sheehy [Proc. SoCG, 2014]. We show that any linear transformation that preserves pairwise distances up to a (1±ε) multiplicative factor, must preserve the persistent homology of the Čech filtration up to a factor of (1-ε)^{-1}. Our results also show that the Vietoris-Rips and Delaunay filtrations for the k-distance, as well as the Čech filtration for the approximate k-distance of Buchet et al. are preserved up to a (1±ε) factor. We also prove extensions of our main theorem, for point sets (i) lying in a region of bounded Gaussian width or (ii) on a low-dimensional manifold, obtaining the target dimension bounds of Lotz [Proc. Roy. Soc. , 2019] and Clarkson [Proc. SoCG, 2008 ] respectively.

Randomized incremental construction (RIC) is one of the most important paradigms for building geometric data structures. Clarkson and Shor developed a general theory that led to numerous algorithms that are both simple and efficient in theory and in practice. Randomized incremental constructions are most of the time space and time optimal in the worst-case, as exemplified by the construction of convex hulls, Delaunay triangulations and arrangements of line segments. However, the worst-case scenario occurs rarely in practice and we would like to understand how RIC behaves when the input is nice in the sense that the associated output is significantly smaller than in the worst-case. For example, it is known that the Delaunay triangulations of nicely distributed points on polyhedral surfaces in E^3 has linear complexity, as opposed to a worst-case quadratic complexity. The standard analysis does not provide accurate bounds on the complexity of such cases and we aim at establishing such bounds in this paper. More precisely, we will show that, in the case of nicely distributed points on polyhedral surfaces, the complexity of the usual RIC is O(n log n), which is optimal. In other words, without any modification, RIC nicely adapts to good cases of practical value. Our proofs also work for some other notions of nicely distributed point sets, such as (epsilon, kappa)-samples. Along the way, we prove a probabilistic lemma for sampling without replacement, which may be of independent interest.

Given a set system $$(X, \mathcal {R})$$ such that every pair of sets in $$\mathcal {R}$$ have large symmetric difference, the Shallow Packing Lemma gives an upper bound on $$|\mathcal {R}|$$ as a function of the shallow-cell complexity of $$\mathcal {R}$$ . In this paper, we first present a matching lower bound. Then we give our main theorem, an application of the Shallow Packing Lemma: given a semialgebraic set system $$(X, \mathcal {R})$$ with shallow-cell complexity $$\varphi (\cdot , \cdot )$$ and a parameter $$\epsilon > 0$$ , there exists a collection, called an $$\epsilon $$ -Mnet, consisting of $$O\bigl ( \frac{1}{\epsilon } \,\varphi \bigl ( O\bigl (\frac{1}{\epsilon } \bigr ), O(1)\bigr ) \bigr )$$ subsets of X, each of size $$\Omega ( \epsilon |X| )$$ , such that any $$R \in \mathcal {R}$$ with $$|R| \ge \epsilon |X|$$ contains at least one set in this collection. We observe that as an immediate corollary an alternate proof of the optimal $$\epsilon $$ -net bound follows.

In this paper, we consider variants of the Geometric Subset General Position problem. In defining this problem, a geometric subsystem is specified, like a subsystem of lines, hyperplanes or spheres. The input of the problem is a set of n points in \mathbb{R}^d and a positive integer k. The objective is to find a subset of at least k input points such that this subset is in general position with respect to the specified subsystem. For example, a set of points is in general position with respect to a subsystem of hyperplanes in \mathbb{R}^d if no d+1 points lie on the same hyperplane. In this paper, we study the Hyperplane Subset General Position problem under two parameterizations. When parameterized by k then we exhibit a polynomial kernelization for the problem. When parameterized by h=n-k, or the dual parameter, then we exhibit polynomial kernels which are also tight, under standard complexity theoretic assumptions. We can also exhibit similar kernelization results for d-Polynomial Subset General Position, where a vector space of polynomials of degree at most d are specified as the underlying subsystem such that the size of the basis for this vector space is b. The objective is to find a set of at least k input points, or in the dual delete at most h = n-k points, such that no b+1 points lie on the same polynomial. Notice that this is a generalization of many well-studied geometric variants of the Set Cover problem, such as Circle Subset General Position. We also study general projective variants of these problems. These problems are also related to other geometric problems like Subset Delaunay Triangulation problem.

Given a simple directed graph $D = (V,A)$, let the size of the largest induced acyclic subgraph \em(dag) of $D$ be denoted by mas$(D)$. Let $D \in \mathcal{D}(n,p)$ be a random instance, obtained by choosing each of the ${{n}\choose{2}}$ possible undirected edges independently with probability $2p$ and then orienting each chosen edge independently in one of two possible directions with probability $1/2$. We obtain improved bounds on the range of concentration, upper and lower bounds of mas$(D)$. Our main result is that mas$(D) \geq \lfloor 2\log_{q} np - X \rfloor$, where $q = (1-p)^{-1}$, $X=1$ if $p \geq n^{-1/3+\epsilon}$ ($\epsilon > 0$ is any constant), $X=W/(\ln q)$ if $p \geq C/n$, where $W>4$ is any constant (and $C=C(W)$ is a suitably large constant). This improves the previously known lower bounds of [J. Spencer and C. Subramanian, Discrete Math. Theor. Comput. Sci., 10 (2008); C. R. Subramanian, Electron. J. Combin., 10 (2003)], where there is an $O(\ln \ln np/\ln q)$ term instead of $X$. We also obtain a slight improvement on the upper bound, using an upper bound on the number of acyclic orientations of an undirected graph. Limitations on further improvements on the upper bound (using first moment arguments) are also established. We also analyze a polynomial-time heuristic to find a large induced dag and show that it produces a solution whose size is at least $\log_{q} np + \Theta(\sqrt{\log_{q} np})$. Our results also carry over to a related model $\mathcal{D}_2(n,p)$ in which each possible directed arc is chosen independently with probability $p$.

We refine the bound on the packing number, originally shown by Haussler, for shallow geometric set systems. Specifically, let V be a finite set system defined over an n-point set X; we view V as a set of indicator vectors over the n-dimensional unit cube. A delta-separated set of V is a subcollection W, s.t. the Hamming distance between each pair u, v in W is greater than delta, where delta > 0 is an integer parameter. The delta-packing number is then defined as the cardinality of the largest delta-separated subcollection of V. Haussler showed an asymptotically tight bound of Theta((n / delta)^d) on the delta-packing number if V has VC-dimension (or primal shatter dimension) d. We refine this bound for the scenario where, for any subset, X' of X of size m <= n and for any parameter 1 <= k <= m, the number of vectors of length at most k in the restriction of V to X' is only O(m^{d_1} k^{d-d_1}), for a fixed integer d > 0 and a real parameter 1 <= d_1 <= d (this generalizes the standard notion of bounded primal shatter dimension when d_1 = d). In this case when V is "k-shallow" (all vector lengths are at most k), we show that its delta-packing number is O(n^{d_1} k^{d-d_1} / delta^d), matching Haussler's bound for the special cases where d_1=d or k=n. We present two proofs, the first is an extension of Haussler's approach, and the second extends the proof of Chazelle, originally presented as a simplification for Haussler's proof.

We obtain new lower bounds for the independence number of $K_r$-free graphs and linear $k$-uniform hypergraphs in terms of the degree sequence. This answers some old questions raised by Caro and Tuza [J. Graph Theory, 15 (1991), pp. 99--107]. Our proof technique is an extension of a method of Caro [New Results on the Independence Number, Technical report, Tel Aviv University, 1979] and Wei [A Lower Bound on the Stability Number of a Simple Graph, TM 81-11217-9, Bell Laboratories, Berkley Heights, NJ, 1981], and we also give a new short proof of the main result of Caro and Tuza using this approach. As byproducts, we also obtain some nontrivial identities involving binomial coefficients, which may be of independent interest.