Search for: All records

Longest Increasing Subsequence (LIS) is a fundamental problem in combinatorics and computer science. Previously, there have been numerous works on both upper bounds and lower bounds of the time complexity of computing and approximating , yet only a few on the equally important space complexity. In this paper, we further study the space complexity of computing and approximating LIS in various models. Specifically, we prove non-trivial space lower bounds in the following two models: (1) the adaptive query-once model or read-once branching programs, and (2) the streaming model where the order of streaming is different from the natural order. As far as we know, there are no previous works on the space complexity of LIS in these models. Besides the bounds, our work also leaves many intriguing open problems. 

Key Points A framework merging unsupervised clustering and supervised convolutional neural network (CNN) for lightning classification is developed Clustering of positive polarity energetic lightning radio pulses (>150 kA) identifies three processes: +EIPs (6%–7%), +NBEs, and +CGs CNNs detect 95.2% of manually identified +EIPs with up to 98.7% accuracy, enabling studying EIP‐TGF link with lower peak current (>50 kA) 

Understanding the mechanisms governing biological invasions has implications for population dynamics, biodiversity, and community assembly. The enemy escape hypothesis posits that escape from enemies such as herbivores and predators that were limiting in the native range helps explain rapid spread in the introduced range. While the enemy escape hypothesis has been widely tested aboveground, data limitations have prevented comparisons of belowground mechanisms for invasive and noninvasive introduced species, which limits our understanding of why only some introduced species become invasive. We assessed the role of soil biota in driving plant invasions in a phylogenetic meta−analysis, incorporating phylogeny in the error structure of the models, and comparing live and sterilized conditioned soils. We found 29 studies and 396 effect size estimates across 103 species that compared live and sterilized soils. We found general positive effects of soil biota for plants (0.099, 95% CI = 0.0266, 0.1714), consistent with a role of soil mutualists. The effect size of soil biota among invaders was 3.2× higher than for natives, the strength of effects was weaker for older conditioning species with a longer introduced history, and enemy escape was stronger for distant relatives. In addition, invasive species had a weaker allocation tradeoff than natives. By demonstrating that the net effect of soil biota is more positive for invasive than native and noninvasive introduced species, weakens over time since introduction, and strengthens as phylogenetic distance increasing, we provide mechanistic insights into the considerable role of soil biota in biological invasions, consistent with the predictions of the enemy escape hypothesis. 

Altered tissue mechanics is an important signature of invasive solid tumors. While the phenomena have been extensively studied by measuring the bulk rheology of the extracellular matrix (ECM) surrounding tumors, micromechanical remodeling at the cellular scale remains poorly understood. By combining holographic optical tweezers and confocal microscopy on in vitro tumor models, we show that the micromechanics of collagen ECM surrounding an invading tumor demonstrate directional anisotropy, spatial heterogeneity and significant variations in time as tumors invade. To test the cellular mechanisms of ECM micromechanical remodeling, we construct a simple computational model and verify its predictions with experiments. We find that collective force generation of a tumor stiffens the ECM and leads to anisotropic local mechanics such that the extension direction is more rigid than the compression direction. ECM degradation by cell-secreted matrix metalloproteinase softens the ECM, and active traction forces from individual disseminated cells re-stiffen the matrix. Together, these results identify plausible biophysical mechanisms responsible for the remodeled ECM micromechanics surrounding an invading tumor.