More Like this

1. Computing β-Stretch Paths in Drawings of Graphs

   Arkin, E ; Darabi, F ; Efrat, A ; Frank, F ; Fulek, R ; Kobourov, S ; Mitchell, J ( October 2020 , 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT))

   Let f be a drawing in the Euclidean plane of a graph G, which is understood to be a 1-dimensional simplicial complex. We assume that every edge of G is drawn by f as a curve of constant algebraic complexity, and the ratio of the length of the longest simple path to the the length of the shortest edge is poly(n). In the drawing f, a path P of G, or its image in the drawing π = f(P), is β-stretch if π is a simple (non-self-intersecting) curve, and for every pair of distinct points p ∈ P and q ∈ P , the length of the sub-curve of π connecting f(p) with f(q) is at most β∥f(p) − f(q)∥, where ∥.∥ denotes the Euclidean distance. We introduce and study the β-stretch Path Problem (βSP for short), in which we are given a pair of vertices s and t of G, and we are to decide whether in the given drawing of G there exists a β-stretch path P connecting s and t. We also output P if it exists. The βSP quantifies a notion of “near straightness” for paths in a graph G, motivated by gerrymandering regions in amore »map, where edges of G represent natural geographical/political boundaries that may be chosen to bound election districts. The notion of a β-stretch path naturally extends to cycles, and the extension gives a measure of how gerrymandered a district is. Furthermore, we show that the extension is closely related to several studied measures of local fatness of geometric shapes. We prove that βSP is strongly NP-complete. We complement this result by giving a quasi-polynomial time algorithm, that for a given ε > 0, β ∈ O(poly(log |V (G)|)), and s, t ∈ V (G), outputs a β-stretch path between s and t, if a (1 − ε)β-stretch path between s and t exists in the drawing.« less
2. Infinite families of manifolds of positive $$k\mathrm{th}$$-intermediate Ricci curvature with k small

   https://doi.org/10.1007/s00208-022-02420-w  

   Domínguez-Vázquez, Miguel ; González-Álvaro, David ; Mouillé, Lawrence ( August 2022 , Mathematische Annalen)

   Positive$$k\mathrm{th}$$$k\mathrm{th}$-intermediate Ricci curvature on a Riemanniann-manifold, to be denoted by$${{\,\mathrm{Ric}\,}}_k>0$$${\mathrm{Ric}}_k>0$, is a condition that interpolates between positive sectional and positive Ricci curvature (when$$k =1$$$k=1$and$$k=n-1$$$k=n-1$respectively). In this work, we produce many examples of manifolds of$${{\,\mathrm{Ric}\,}}_k>0$$${\mathrm{Ric}}_k>0$withksmall by examining symmetric and normal homogeneous spaces, along with certain metric deformations of fat homogeneous bundles. As a consequence, we show that every dimension$$n\ge 7$$$n\ge 7$congruent to$$3\,{{\,\mathrm{mod}\,}}4$$$3\mathrm{mod}4$supports infinitely many closed simply connected manifolds of pairwise distinct homotopy type, all of which admit homogeneous metrics of$${{\,\mathrm{Ric}\,}}_k>0$$${\mathrm{Ric}}_k>0$for some$$k$k<n/2$. We also prove that each dimension$$n\ge 4$$$n\ge 4$congruent to 0 or$$1\,{{\,\mathrm{mod}\,}}4$$$1\mathrm{mod}4$supports closed manifolds which carry metrics of$${{\,\mathrm{Ric}\,}}_k>0$$${\mathrm{Ric}}_k>0$with$$k\le n/2$$$k\le n/2$, but do not admit metrics of positive sectional curvature.
3. Discrete Planar Map Matching

   Fu, Bin ; Schweller, Robert ; Wylie, Tim ( August 2019 , Proceedings of the 31st Canadian Conference in Computational Geometry (CCCG 2019))

   Route reconstruction is an important application for Geographic Information Systems (GIS) that rely heavily upon GPS data and other location data from IoT devices. Many of these techniques rely on geometric methods involving the \frechet\ distance to compare curve similarity. The goal of reconstruction, or map matching, is to find the most similar path within a given graph to a given input curve, which is often approximate location data. This process can be approximated by sampling the curves and using the \dfd. Due to power and coverage constraints, the GPS data itself may be sparse causing improper constraints along the edges during the reconstruction if only the continuous \frechet\ distance is used. Here, we look at two variations of discrete map matching: one constraining the walk length and the other limiting the number of vertices visited in the graph. %, and the constraint that the walk may not self-intersect. We give an efficient algorithm to solve the question based on walk length showing it is in \textbf{P}. We prove the other problem is \npc\ and the minimization variant is \apx\ while also giving a parameterized algorithm to solve the problem.
4. Absence of bubbling phenomena for non-convex anisotropic nearly umbilical and quasi-Einstein hypersurfaces

   https://doi.org/10.1515/crelle-2021-0038  

   De Rosa, Antonio ; Gioffrè, Stefano ( August 2021 , Journal für die reine und angewandte Mathematik (Crelles Journal))

   Abstract We prove that, for every closed (not necessarily convex) hypersurface Σ in ℝ n + 1 {\mathbb{R}^{n+1}} and every p > n {p>n} , the L p {L^{p}} -norm of the trace-free part of the anisotropic second fundamental form controls from above the W 2 , p {W^{2,p}} -closeness of Σ to the Wulff shape. In the isotropic setting, we provide a simpler proof. This result is sharp since in the subcritical regime p ≤ n {p\leq n} , the lack of convexity assumptions may lead in general to bubbling phenomena.Moreover, we obtain a stability theorem for quasi-Einstein (not necessarily convex) hypersurfaces and we improve the quantitative estimates in the convex setting.
5. Proximity Gaps for Reed–Solomon Codes

   https://doi.org/10.1109/FOCS46700.2020.00088  

   Ben-Sasson, Eli ; Carmon, Dan ; Ishai, Yuval ; Kopparty, Swastik ; Saraf, Shubhangi ( November 2020 , 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2020))

   A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are δ-close to the property in relative Hamming distance or (ii) only a tiny fraction of members are δ-close to the property. In particular, no set in the collection has roughly half of its members δ-close to the property and the others δ-far from it. We show that the collection of affine spaces displays a proximity gap with respect to Reed-Solomon (RS) codes, even over small fields, of size polynomial in the dimension of the code, and the gap applies to any δ smaller than the Johnson/Guruswami-Sudan list-decoding bound of the RS code. We also show near-optimal gap results, over fields of (at least) linear size in the RS code dimension, for δ smaller than the unique decoding radius. Concretely, if δ is smaller than half the minimal distance of an RS code V ⊂ Fq n , every affine space is either entirely δ-close to the code, or alternatively at most an ( n/q)-fraction of it is δ-close to the code. Finally, we discuss several applications of our proximity gap results to distributed storage, multi-partymore »cryptographic protocols, and concretely efficient proof systems. We prove the proximity gap results by analyzing the execution of classical algebraic decoding algorithms for Reed-Solomon codes (due to Berlekamp-Welch and Guruswami-Sudan) on a formal element of an affine space. This involves working with Reed-Solomon codes whose base field is an (infinite) rational function field. Our proofs are obtained by developing an extension (to function fields) of a strategy of Arora and Sudan for analyzing low-degree tests.« less