More Like this

1. A $$d^{1/2+o(1)}$$ Monotonicity Tester for Boolean Functions on $$d$$-Dimensional Hypergrids

   Hadley Black, Deeparnab Chakrabarty (November 2023, Annual Symposium on Foundations of Computer Science)

   Monotonicity testing of Boolean functions on the hypergrid, $$f:[n]^d \to \{0,1\}$$, is a classic topic in property testing. Determining the non-adaptive complexity of this problem is an important open question. For arbitrary $$n$$, [Black-Chakrabarty-Seshadhri, SODA 2020] describe a tester with query complexity $$\widetilde{O}(\varepsilon^{-4/3}d^{5/6})$$. This complexity is independent of $$n$$, but has a suboptimal dependence on $$d$$. Recently, [Braverman-Khot-Kindler-Minzer, ITCS 2023] and [Black-Chakrabarty-Seshadhri, STOC 2023] describe $$\widetilde{O}(\varepsilon^{-2} n^3\sqrt{d})$$ and $$\widetilde{O}(\varepsilon^{-2} n\sqrt{d})$$-query testers, respectively. These testers have an almost optimal dependence on $$d$$, but a suboptimal polynomial dependence on $$n$$. \smallskip In this paper, we describe a non-adaptive, one-sided monotonicity tester with query complexity $$O(\varepsilon^{-2} d^{1/2 + o(1)})$$, \emph{independent} of $$n$$. Up to the $$d^{o(1)}$$-factors, our result resolves the non-adaptive complexity of monotonicity testing for Boolean functions on hypergrids. The independence of $$n$$ yields a non-adaptive, one-sided $$O(\varepsilon^{-2} d^{1/2 + o(1)})$$-query monotonicity tester for Boolean functions $$f:\mathbb{R}^d \to \{0,1\}$$ associated with an arbitrary product measure. 

   more » « less
2. On the Automorphism Groups of Hyperbolic Manifolds

   https://doi.org/10.1093/imrn/rnaf083  

   Budney, Ryan; Gabai, David (April 2025, International Mathematics Research Notices)

   Abstract Let $${\mathrm{Diff}}_{0}(N)$$ represent the subgroup of diffeomorphisms that are homotopic to the identity. We show that if $$N$$ is a closed hyperbolic 4-manifold, then $$\pi _{0}{\mathrm{Diff}}_{0}(N)$$ is not finitely generated with similar results holding topologically. This proves in dimension-4 results previously known for $$n$$-dimensional hyperbolic manifolds of dimension $$n\ge 11$$ by Farrell and Jones in 1989 and $$n\ge 10$$ by Farrell and Ontaneda in 2010. Our proof relies on the technical result that $$\pi _{0}{\mathrm{Homeo}}(S^{1}\times D^{3})$$ is not finitely generated, which extends to the topological category smooth results of the authors. We also show that $$\pi _{n-4} {\mathrm{Homeo}}(S^{1} \times D^{n-1})$$ is not finitely generated for $$n \geq 4$$ and in particular $$\pi _{0}{\mathrm{Homeo}}(S^{1}\times D^{3})$$ is not finitely generated. These results are new for $n=4, 5$ and $$7$$. We also introduce higher dimensional barbell maps and establish some of their basic properties. 

   more » « less
3. Sparse Bounded Hop-Spanners for Geometric Intersection Graphs

   https://doi.org/10.4230/LIPIcs.SoCG.2025.17  

   Bhore, Sujoy; Chan, Timothy M; Huang, Zhengcheng; Smorodinsky, Shakhar; Tóth, Csaba D (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Aichholzer, Oswin; Wang, Haitao (Ed.)

   We present new results on 2- and 3-hop spanners for geometric intersection graphs. These include improved upper and lower bounds for 2- and 3-hop spanners for many geometric intersection graphs in ℝ^d. For example, we show that the intersection graph of n balls in ℝ^d admits a 2-hop spanner of size O^*(n^{3/2 - 1/(2(2⌊d/2⌋ + 1))}) and the intersection graph of n fat axis-parallel boxes in ℝ^d admits a 2-hop spanner of size O(n log^{d+1}n). Furthermore, we show that the intersection graph of general semi-algebraic objects in ℝ^d admits a 3-hop spanner of size O^*(n^{3/2 - 1/(2(2D-1))}), where D is a parameter associated with the description complexity of the objects. For such families (or more specifically, for tetrahedra in ℝ³), we provide a lower bound of Ω(n^{4/3}). For 3-hop and axis-parallel boxes in ℝ^d, we provide the upper bound O(n log ^{d-1}n) and lower bound Ω(n ({log n}/{log log n})^{d-2}). 

   more » « less
4. On Euclidean Steiner (1+ε)-Spanners

   https://doi.org/10.4230/LIPIcs.STACS.2021.13  

   Bhore, Sujoy; Toth, Csaba D. (March 2021, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021))

   null (Ed.)

   Lightness and sparsity are two natural parameters for Euclidean (1+ε)-spanners. Classical results show that, when the dimension d ∈ ℕ and ε > 0 are constant, every set S of n points in d-space admits an (1+ε)-spanners with O(n) edges and weight proportional to that of the Euclidean MST of S. Tight bounds on the dependence on ε > 0 for constant d ∈ ℕ have been established only recently. Le and Solomon (FOCS 2019) showed that Steiner points can substantially improve the lightness and sparsity of a (1+ε)-spanner. They gave upper bounds of Õ(ε^{-(d+1)/2}) for the minimum lightness in dimensions d ≥ 3, and Õ(ε^{-(d-1))/2}) for the minimum sparsity in d-space for all d ≥ 1. They obtained lower bounds only in the plane (d = 2). Le and Solomon (ESA 2020) also constructed Steiner (1+ε)-spanners of lightness O(ε^{-1}logΔ) in the plane, where Δ ∈ Ω(log n) is the spread of S, defined as the ratio between the maximum and minimum distance between a pair of points. In this work, we improve several bounds on the lightness and sparsity of Euclidean Steiner (1+ε)-spanners. Using a new geometric analysis, we establish lower bounds of Ω(ε^{-d/2}) for the lightness and Ω(ε^{-(d-1)/2}) for the sparsity of such spanners in Euclidean d-space for all d ≥ 2. We use the geometric insight from our lower bound analysis to construct Steiner (1+ε)-spanners of lightness O(ε^{-1}log n) for n points in Euclidean plane. 

   more » « less
5. Almost Sharp Bounds on the Number of Discrete Chains in the Plane

   Frankl, N; Kupavskii, A. (June 2020, Proceedings of 36th International Symposium on Computational Geometry (SoCG 2020))

   The following generalisation of the Erdős unit distance problem was recently suggested by Palsson, Senger and Sheffer. For a sequence δ=(δ₁,… ,δ_k) of k distances, a (k+1)-tuple (p₁,… ,p_{k+1}) of distinct points in ℝ^d is called a (k,δ)-chain if ‖p_j-p_{j+1}‖ = δ_j for every 1 ≤ j ≤ k. What is the maximum number C_k^d(n) of (k,δ)-chains in a set of n points in ℝ^d, where the maximum is taken over all δ? Improving the results of Palsson, Senger and Sheffer, we essentially determine this maximum for all k in the planar case. It is only for k ≡ 1 (mod 3) that the answer depends on the maximum number of unit distances in a set of n points. We also obtain almost sharp results for even k in dimension 3. 

   more » « less