More Like this

1. Algorithms for Radon Partitions with Tolerance

   https://doi.org/10.1007/978-3-030-39219-2_38  

   Bereg Sergey, Haghpanah Mohammadreza (February 2020, Lecture notes in computer science)

   Let P be a set n points in a d-dimensional space. Tverberg theorem says that, if n is at least (k − 1)(d + 1), then P can be par- titioned into k sets whose convex hulls intersect. Partitions with this property are called Tverberg partitions. A partition has tolerance t if the partition remains a Tverberg partition after removal of any set of t points from P. A tolerant Tverberg partition exists in any dimensions provided that n is sufficiently large. Let N(d,k,t) be the smallest value of n such that tolerant Tverberg partitions exist for any set of n points in R d . Only few exact values of N(d,k,t) are known. In this paper, we study the problem of finding Radon partitions (Tver- berg partitions for k = 2) for a given set of points. We develop several algorithms and found new lower bounds for N(d,2,t). 

   more » « less
2. Variation of canonical height for\break Fatou points on ℙ ¹

   https://doi.org/10.1515/crelle-2022-0078  

   DeMarco, Laura; Mavraki, Niki Myrto (December 2022, Journal für die reine und angewandte Mathematik (Crelles Journal))

   Abstract Let f : ℙ 1 → ℙ 1 {f:\mathbb{P}^{1}\to\mathbb{P}^{1}} be a map of degree > 1 {>1} defined over a function field k = K ⁢ ( X ) {k=K(X)} , where K is a number field and X is a projective curve over K . For each point a ∈ ℙ 1 ⁢ ( k ) {a\in\mathbb{P}^{1}(k)} satisfying a dynamical stability condition, we prove that the Call–Silverman canonical height for specialization f t {f_{t}} at point a t {a_{t}} , for t ∈ X ⁢ ( ℚ ¯ ) {t\in X(\overline{\mathbb{Q}})} outside a finite set, induces a Weil height on the curve X ; i.e., we prove the existence of a ℚ {\mathbb{Q}} -divisor D = D f , a {D=D_{f,a}} on X so that the function t ↦ h ^ f t ⁢ ( a t ) - h D ⁢ ( t ) {t\mapsto\hat{h}_{f_{t}}(a_{t})-h_{D}(t)} is bounded on X ⁢ ( ℚ ¯ ) {X(\overline{\mathbb{Q}})} for any choice of Weil height associated to D . We also prove a local version, that the local canonical heights t ↦ λ ^ f t , v ⁢ ( a t ) {t\mapsto\hat{\lambda}_{f_{t},v}(a_{t})} differ from a Weil function for D by a continuous function on X ⁢ ( ℂ v ) {X(\mathbb{C}_{v})} , at each place v of the number field K . These results were known for polynomial maps f and all points a ∈ ℙ 1 ⁢ ( k ) {a\in\mathbb{P}^{1}(k)} without the stability hypothesis,[21, 14],and for maps f that are quotients of endomorphisms of elliptic curves E over k and all points a ∈ ℙ 1 ⁢ ( k ) {a\in\mathbb{P}^{1}(k)} . [32, 29].Finally, we characterize our stability condition in terms of the geometry of the induced map f ~ : X × ℙ 1 ⇢ X × ℙ 1 {\tilde{f}:X\times\mathbb{P}^{1}\dashrightarrow X\times\mathbb{P}^{1}} over K ; and we prove the existence of relative Néron models for the pair ( f , a ) {(f,a)} , when a is a Fatou point at a place γ of k , where the local canonical height λ ^ f , γ ⁢ ( a ) {\hat{\lambda}_{f,\gamma}(a)} can be computed as an intersection number. 

   more » « less
3. Rank varieties and 𝜋-points for elementary supergroup schemes

   https://doi.org/10.1090/btran/74  

   Benson, Dave; Iyengar, Srikanth; Krause, Henning; Pevtsova, Julia (November 2021, Transactions of the American Mathematical Society, Series B)

   We develop a support theory for elementary supergroup schemes, over a field of positive characteristic p ⩾ 3 p\geqslant 3 , starting with a definition of a π \pi -point generalising cyclic shifted subgroups of Carlson for elementary abelian groups and π \pi -points of Friedlander and Pevtsova for finite group schemes. These are defined in terms of maps from the graded algebra k [ t , τ ] / ( t p − τ 2 ) k[t,\tau ]/(t^p-\tau ^2) , where t t has even degree and τ \tau has odd degree. The strength of the theory is demonstrated by classifying the parity change invariant localising subcategories of the stable module category of an elementary supergroup scheme. 

   more » « less
4. Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence

   https://doi.org/10.1109/FOCS54457.2022.00019  

   Anari, Nima; Liu, Yang P.; Vuong, Thuy-Duong (October 2022, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS))

   We design fast algorithms for repeatedly sampling from strongly Rayleigh distributions, which include as special cases random spanning tree distributions and determinantal point processes. For a graph $G=(V, E)$, we show how to approximately sample uniformly random spanning trees from $$G$$ in $$\widetilde{O}(\lvert V\rvert)$$\footnote{Throughout, $$\widetilde{O}(\cdot)$$ hides polylogarithmic factors in $$n$$.} time per sample after an initial $$\widetilde{O}(\lvert E\rvert)$$ time preprocessing. This is the first nearly-linear runtime in the output size, which is clearly optimal. For a determinantal point process on $$k$$-sized subsets of a ground set of $$n$$ elements, defined via an $$n\times n$$ kernel matrix, we show how to approximately sample in $$\widetilde{O}(k^\omega)$$ time after an initial $$\widetilde{O}(nk^{\omega-1})$$ time preprocessing, where $$\omega<2.372864$$ is the matrix multiplication exponent. The time to compute just the weight of the output set is simply $$\simeq k^\omega$$, a natural barrier that suggests our runtime might be optimal for determinantal point processes as well. As a corollary, we even improve the state of the art for obtaining a single sample from a determinantal point process, from the prior runtime of $$\widetilde{O}(\min\{nk^2, n^\omega\})$$ to $$\widetilde{O}(nk^{\omega-1})$$. In our main technical result, we achieve the optimal limit on domain sparsification for strongly Rayleigh distributions. In domain sparsification, sampling from a distribution $$\mu$$ on $$\binom{[n]}{k}$$ is reduced to sampling from related distributions on $$\binom{[t]}{k}$$ for $$t\ll n$$. We show that for strongly Rayleigh distributions, the domain size can be reduced to nearly linear in the output size $$t=\widetilde{O}(k)$$, improving the state of the art from $$t= \widetilde{O}(k^2)$$ for general strongly Rayleigh distributions and the more specialized $$t=\widetilde{O}(k^{1.5})$$ for spanning tree distributions. Our reduction involves sampling from $$\widetilde{O}(1)$$ domain-sparsified distributions, all of which can be produced efficiently assuming approximate overestimates for marginals of $$\mu$$ are known and stored in a convenient data structure. Having access to marginals is the discrete analog of having access to the mean and covariance of a continuous distribution, or equivalently knowing ``isotropy'' for the distribution, the key behind optimal samplers in the continuous setting based on the famous Kannan-Lov\'asz-Simonovits (KLS) conjecture. We view our result as analogous in spirit to the KLS conjecture and its consequences for sampling, but rather for discrete strongly Rayleigh measures. 

   more » « less
5. Online Spanners in Metric Spaces

   Bhore, Sujoy; Filtser, Arnold; Khodabandeh, Hadi; Toth, Csaba D. (September 2022, 30th Annual European Symposium on Algorithms (ESA 2022))

   Given a metric space ℳ = (X,δ), a weighted graph G over X is a metric t-spanner of ℳ if for every u,v ∈ X, δ(u,v) ≤ δ_G(u,v) ≤ t⋅ δ(u,v), where δ_G is the shortest path metric in G. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points (s₁, …, s_n), where the points are presented one at a time (i.e., after i steps, we have seen S_i = {s₁, … , s_i}). The algorithm is allowed to add edges to the spanner when a new point arrives, however, it is not allowed to remove any edge from the spanner. The goal is to maintain a t-spanner G_i for S_i for all i, while minimizing the number of edges, and their total weight. Under the L₂-norm in ℝ^d for arbitrary constant d ∈ ℕ, we present an online (1+ε)-spanner algorithm with competitive ratio O_d(ε^{-d} log n), improving the previous bound of O_d(ε^{-(d+1)}log n). Moreover, the spanner maintained by the algorithm has O_d(ε^{1-d}log ε^{-1})⋅ n edges, almost matching the (offline) optimal bound of O_d(ε^{1-d})⋅ n. In the plane, a tighter analysis of the same algorithm provides an almost quadratic improvement of the competitive ratio to O(ε^{-3/2}logε^{-1}log n), by comparing the online spanner with an instance-optimal spanner directly, bypassing the comparison to an MST (i.e., lightness). As a counterpart, we design a sequence of points that yields a Ω_d(ε^{-d}) lower bound for the competitive ratio for online (1+ε)-spanner algorithms in ℝ^d under the L₁-norm. Then we turn our attention to online spanners in general metrics. Note that, it is not possible to obtain a spanner with stretch less than 3 with a subquadratic number of edges, even in the offline setting, for general metrics. We analyze an online version of the celebrated greedy spanner algorithm, dubbed ordered greedy. With stretch factor t = (2k-1)(1+ε) for k ≥ 2 and ε ∈ (0,1), we show that it maintains a spanner with O(ε^{-1}logε^{-1})⋅ n^{1+1/k} edges and O(ε^{-1}n^{1/k}log² n) lightness for a sequence of n points in a metric space. We show that these bounds cannot be significantly improved, by introducing an instance that achieves an Ω(1/k⋅ n^{1/k}) competitive ratio on both sparsity and lightness. Furthermore, we establish the trade-off among stretch, number of edges and lightness for points in ultrametrics, showing that one can maintain a (2+ε)-spanner for ultrametrics with O(ε^{-1}logε^{-1})⋅ n edges and O(ε^{-2}) lightness. 

   more » « less