More Like this

1. A deterministic near-linear time approximation scheme for geometric transportation

   https://doi.org/10.1109/FOCS57990.2023.00078  

   Fox, Emily; Lu, Jiashuai (November 2023, IEEE)

   Given a set of points $$P = (P^+ \sqcup P^-) \subset \mathbb{R}^d$$ for some constant $$d$$ and a supply function $$\mu:P\to \mathbb{R}$$ such that $$\mu(p) > 0~\forall p \in P^+$$, $$\mu(p) < 0~\forall p \in P^-$$, and $$\sum_{p\in P}{\mu(p)} = 0$$, the geometric transportation problem asks one to find a transportation map $$\tau: P^+\times P^-\to \mathbb{R}_{\ge 0}$$ such that $$\sum_{q\in P^-}{\tau(p, q)} = \mu(p)~\forall p \in P^+$$, $$\sum_{p\in P^+}{\tau(p, q)} = -\mu(q) \forall q \in P^-$$, and the weighted sum of Euclidean distances for the pairs $$\sum_{(p,q)\in P^+\times P^-}\tau(p, q)\cdot ||q-p||_2$$ is minimized. We present the first deterministic algorithm that computes, in near-linear time, a transportation map whose cost is within a $$(1 + \varepsilon)$$ factor of optimal. More precisely, our algorithm runs in $$O(n\varepsilon^{-(d+2)}\log^5{n}\log{\log{n}})$$ time for any constant $$\varepsilon > 0$$. While a randomized $$n\varepsilon^{-O(d)}\log^{O(d)}{n}$$ time algorithm for this problem was discovered in the last few years, all previously known deterministic $$(1 + \varepsilon)$$-approximation algorithms run in~$$\Omega(n^{3/2})$$ time. A similar situation existed for geometric bipartite matching, the special case of geometric transportation where all supplies are unit, until a deterministic $$n\varepsilon^{-O(d)}\log^{O(d)}{n}$$ time $$(1 + \varepsilon)$$-approximation algorithm was presented at STOC 2022. Surprisingly, our result is not only a generalization of the bipartite matching one to arbitrary instances of geometric transportation, but it also reduces the running time for all previously known $$(1 + \varepsilon)$$-approximation algorithms, randomized or deterministic, even for geometric bipartite matching. In particular, we give the first $$(1 + \varepsilon)$$-approximate deterministic algorithm for geometric bipartite matching and the first $$(1 + \varepsilon)$$-approximate deterministic or randomized algorithm for geometric transportation with no dependence on $$d$$ in the exponent of the running time's polylog. As an additional application of our main ideas, we also give the first randomized near-linear $$O(\varepsilon^{-2} m \log^{O(1)} n)$$ time $$(1 + \varepsilon)$$-approximation algorithm for the uncapacitated minimum cost flow (transshipment) problem in undirected graphs with arbitrary \emph{real} edge costs. 

   more » « less
2. Bacterial Community Structure Modulates Soil Phosphorus Turnover at Early Stages of Primary Succession

   https://doi.org/10.1029/2024GB008174  

   Wang, Yuhan; Bing, Haijian; Moorhead, Daryl L; Hou, Enqing; Wu, Yanhong; Wang, Jipeng; Duan, Chengjiao; Cui, Qingliang; Zhang, Zhiqin; Zhu, He; et al (October 2024, Global Biogeochemical Cycles)

   Abstract Microbes are the drivers of soil phosphorus (P) cycling in terrestrial ecosystems; however, the role of soil microbes in mediating P cycling in P‐rich soils during primary succession remains uncertain. This study examined the impacts of bacterial community structure (diversity and composition) and its functional potential (absolute abundances of P‐cycling functional genes) on soil P cycling along a 130‐year glacial chronosequence on the eastern Tibetan Plateau. Bacterial community structure was a better predictor of soil P fractions than P‐cycling genes along the chronosequence. After glacier retreat, the solubilization of inorganic P and the mineralization of organic P were significantly enhanced by increased bacterial diversity, changed interspecific interactions, and abundant species involved in soil P mineralization, thereby increasing P availability. Although 84% of P‐cycling genes were associated with organic P mineralization, these genes were more closely associated with soil organic carbon than with organic P. Bacterial carbon demand probably determined soil P turnover, indicating the dominant role of organic matter decomposition processes in P‐rich alpine soils. Moreover, the significant decrease in the complexity of the bacterial co‐occurrence network and the taxa‐gene‐P network at the later stage indicates a declining dominance of the bacterial community in driving soil P cycling with succession. Our results reveal that bacteria with a complex community structure have a prominent potential for biogeochemical P cycling in P‐rich soils during the early stages of primary succession. 

   more » « less
3. Ni- and Pd-Catalyzed Enantioselective 1,2-Dicarbofunctionalization of Alkenes

   https://doi.org/10.1055/a-2108-9549  

   Kang, Taeho; Apolinar, Omar; Engle, Keary M (December 2023, Synthesis)

   Abstract Catalytic enantioselective 1,2-dicarbofunctionalization (1,2-DCF) of alkenes is a powerful transformation of growing importance in organic synthesis for constructing chiral building blocks, bioactive molecules, and agrochemicals. Both in a two- and three-component context, this family of reactions generates densely functionalized, structurally complex products in a single step. Across several distinct mechanistic pathways at play in these transformations with nickel or palladium catalysts, stereocontrol can be obtained through tailored chiral ligands. In this Review we discuss the various strategies, mechanisms, and catalysts that have been applied to achieve enantioinduction in alkene 1,2-DCF. 1 Introduction 2 Two-Component Enantioselective 1,2-DCF via Migratory Insertion 3 Two-Component Enantioselective 1,2-DCF via Radical Capture 4 Three-Component Enantioselective 1,2-DCF via Radical Capture 5 Three-Component Enantioselective 1,2-DCF via Migratory Insertion 6 Miscellaneous Mechanisms 7 Conclusion 

   more » « less
4. A simple proof of reflexivity and separability of N^{1,p} Sobolev spaces

   https://doi.org/10.54330/afm.127419  

   Alvarado, Ryan; Hajłasz, Piotr; Malý, Lukáš (October 2022, Annales Fennici Mathematici)

   We present an elementary proof of a well-known theorem of Cheeger which states that if a metric-measure space \(X\) supports a \(p\)-Poincaré inequality, then the \(N^{1,p}(X)\) Sobolev space is reflexive and separable whenever \(p\in (1,\infty)\). We also prove separability of the space when \(p=1\). Our proof is based on a straightforward construction of an equivalent norm on \(N^{1,p}(X)\), \(p\in [1,\infty)\), that is uniformly convex when \(p\in (1,\infty)\). Finally, we explicitly construct a functional that is pointwise comparable to the minimal \(p\)-weak upper gradient, when \(p\in (1,\infty)\). 

   more » « less
5. Towards a nomenclatural clarification of the Peltigera ponojensis/monticola clade including metagenomic sequencing of type material and the introduction of P. globulata Miadl. & Magain sp. nov.

   https://doi.org/10.1017/S0024282923000373  

   Miadlikowska, Jolanta; Magain, Nicolas; Medeiros, Ian D.; Pardo-De la Hoz, Carlos J.; Carbone, Ignazio; LaGreca, Scott; Barlow, Thomas; Myllys, Leena; Schmull, Michaela; Lutzoni, François (September 2023, The Lichenologist)

   Abstract Peltigera globulata Miadl. & Magain, a new species in the P. ponojensis/monticola species complex of section Peltigera , is formally described. This clade was previously given the interim designation Peltigera sp. 17. It is found in sun-exposed and xeric habitats at high altitudes in Peru and Ecuador. Peltigera globulata can be easily recognized by its irregularly globulated margins covered mostly by thick, white pruina, somewhat resembling the sorediate thallus margins of P. soredians , another South American species from section Peltigera . The hypervariable region of ITS1 (ITS1-HR), which is in general highly variable among species of section Peltigera , does not have diagnostic value for species identification within the P. ponojensis/monticola complex. Nevertheless, no significant level of gene flow was detected among eight lineages representing a clade of putative species (including P. globulata ) within this complex. ITS sequences from the holotype specimens of P. monticola Vitik. (collected in 1979) and P. soredians Vitik. (collected in 1981) and lectotype specimens of P. antarctica C. W. Dodge (collected in 1941) and P. aubertii C. W. Dodge (collected in 1952) were successfully obtained through Sanger and Illumina metagenomic sequencing. BLAST results of these sequences revealed that the type specimen of P. monticola falls within the P. monticola/ponojensis 7 clade, which represents P. monticola s. str., and confirmed that the type specimen of P. aubertii falls within a clade identified previously as P. aubertii based on morphology. The ITS sequence from the type specimen of P. soredians , which superficially resembles P. globulata , confirms its placement in the P. rufescens clade. Finally, we discovered that the name P. antarctica was erroneously applied to a lineage in the P. ponojensis/monticola clade. The ITS sequence from the type specimen of P. antarctica represents a lineage within the P. rufescens clade, which is sister to the P. ponojensis/monticola clade. 

   more » « less