skip to main content

Search for: All records

Creators/Authors contains: "Zheng, Yu"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. 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. 
    more » « less
  2. Free, publicly-accessible full text available July 5, 2024
  3. Free, publicly-accessible full text available July 10, 2024
  4. Abstract

    Stretchable polymer semiconductors (PSCs) have seen great advancements alongside the development of soft electronics. But it remains a challenge to simultaneously achieve high charge carrier mobility and stretchability. Herein, we report the finding that stretchable PSC thin films (<100-nm-thick) with high stretchability tend to exhibit multi-modal energy dissipation mechanisms and have a large relative stretchability (rS) defined by the ratio of the entropic energy dissipation to the enthalpic energy dissipation under strain. They effectively recovered the original molecular ordering, as well as electrical performance, after strain was released. The highestrSvalue with a model polymer (P4) exhibited an average charge carrier mobility of 0.2 cm2V−1s−1under 100% biaxial strain, while PSCs with lowrSvalues showed irreversible morphology changes and rapid degradation of electrical performance under strain. These results suggestrScan be used as a parameter to compare the reliability and reversibility of stretchable PSC thin films.

    more » « less
  5. 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) 
    more » « less
  6. 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. 
    more » « less
  7. 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. 
    more » « less
  8. Etessami, Kousha ; Feige, Uriel ; Puppis, Gabriele (Ed.)
    This work continues the study of linear error correcting codes against adversarial insertion deletion errors (insdel errors). Previously, the work of Cheng, Guruswami, Haeupler, and Li [Kuan Cheng et al., 2021] showed the existence of asymptotically good linear insdel codes that can correct arbitrarily close to 1 fraction of errors over some constant size alphabet, or achieve rate arbitrarily close to 1/2 even over the binary alphabet. As shown in [Kuan Cheng et al., 2021], these bounds are also the best possible. However, known explicit constructions in [Kuan Cheng et al., 2021], and subsequent improved constructions by Con, Shpilka, and Tamo [Con et al., 2022] all fall short of meeting these bounds. Over any constant size alphabet, they can only achieve rate < 1/8 or correct < 1/4 fraction of errors; over the binary alphabet, they can only achieve rate < 1/1216 or correct < 1/54 fraction of errors. Apparently, previous techniques face inherent barriers to achieve rate better than 1/4 or correct more than 1/2 fraction of errors. In this work we give new constructions of such codes that meet these bounds, namely, asymptotically good linear insdel codes that can correct arbitrarily close to 1 fraction of errors over some constant size alphabet, and binary asymptotically good linear insdel codes that can achieve rate arbitrarily close to 1/2. All our constructions are efficiently encodable and decodable. Our constructions are based on a novel approach of code concatenation, which embeds the index information implicitly into codewords. This significantly differs from previous techniques and may be of independent interest. Finally, we also prove the existence of linear concatenated insdel codes with parameters that match random linear codes, and propose a conjecture about linear insdel codes. 
    more » « less
  9. Ta-Shma, Amnon (Ed.)
    Locally Decodable Codes (LDCs) are error-correcting codes C:Σⁿ → Σ^m, encoding messages in Σⁿ to codewords in Σ^m, with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best constructions so far have codeword length m that is super-polynomial in n, for codes with constant query complexity and constant alphabet size. In a very surprising result, Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (SICOMP 2006) show how to construct a relaxed version of LDCs (RLDCs) with constant query complexity and almost linear codeword length over the binary alphabet, and used them to obtain significantly-improved constructions of Probabilistically Checkable Proofs. In this work, we study RLDCs in the standard Hamming-error setting, and introduce their variants in the insertion and deletion (Insdel) error setting. Standard LDCs for Insdel errors were first studied by Ostrovsky and Paskin-Cherniavsky (Information Theoretic Security, 2015), and are further motivated by recent advances in DNA random access bio-technologies. Our first result is an exponential lower bound on the length of Hamming RLDCs making 2 queries (even adaptively), over the binary alphabet. This answers a question explicitly raised by Gur and Lachish (SICOMP 2021) and is the first exponential lower bound for RLDCs. Combined with the results of Ben-Sasson et al., our result exhibits a "phase-transition"-type behavior on the codeword length for some constant-query complexity. We achieve these lower bounds via a transformation of RLDCs to standard Hamming LDCs, using a careful analysis of restrictions of message bits that fix codeword bits. We further define two variants of RLDCs in the Insdel-error setting, a weak and a strong version. On the one hand, we construct weak Insdel RLDCs with almost linear codeword length and constant query complexity, matching the parameters of the Hamming variants. On the other hand, we prove exponential lower bounds for strong Insdel RLDCs. These results demonstrate that, while these variants are equivalent in the Hamming setting, they are significantly different in the insdel setting. Our results also prove a strict separation between Hamming RLDCs and Insdel RLDCs. 
    more » « less