skip to main content

This content will become publicly available on June 2, 2024

Title: Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓ p Norms
Award ID(s):
2107345 2006455 2228287 2211972
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
Proceedings of the 55th Annual ACM Symposium on Theory of Computing
Page Range / eLocation ID:
553 to 566
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    With the increasing use of Li batteries for storage, their safety issues and energy densities are attracting considerable attention. Recently, replacing liquid organic electrolytes with solid‐state electrolytes (SSE) has been hailed as the key to developing safe and high‐energy‐density Li batteries. In particular, Li1+xAlxTi2−x(PO4)3(LATP) has been identified as a very attractive SSE for Li batteries due to its excellent electrochemical stability, low production costs, and good chemical compatibility. However, interfacial reactions with electrodes and poor thermal stability at high temperatures severely restrict the practical use of LATP in solid‐state batteries (SSB). Herein, a systematic review of recent advances in LATP for SSBs is provided. This review starts with a brief introduction to the development history of LATP and then summarizes its structure, ion transport mechanism, and synthesis methods. Challenges (e.g., intrinsic brittleness, interfacial resistance, and compatibility) and corresponding solutions (ionic substitution, additives, protective layers, composite electrolytes, etc.) that are critical for practical applications are then discussed. Last, an outlook on the future research direction of LATP‐based SSB is provided.

    more » « less
  2. Summary

    The collaborative non‐self‐recognition model for S‐RNase‐based self‐incompatibility predicts that multiple S‐locus F‐box proteins (SLFs) produced by pollen of a givenS‐haplotype collectively mediate ubiquitination and degradation of all non‐self S‐RNases, but not self S‐RNases, in the pollen tube, thereby resulting in cross‐compatible pollination but self‐incompatible pollination. We had previously used pollen extracts containingGFP‐fused S2SLF1 (SLF1 with anS2‐haplotype) ofPetunia inflatafor co‐immunoprecipitation (Co‐IP) and mass spectrometry (MS), and identified PiCUL1‐P (a pollen‐specific Cullin1), PiSSK1 (a pollen‐specific Skp1‐like protein) and PiRBX1 (a conventional Rbx1) as components of theSCFS2–SLF1complex. Using pollen extracts containing PiSSK1:FLAG:GFPfor Co‐IP/MS, we identified two additionalSLFs (SLF4 andSLF13) that were assembled intoSCFSLFcomplexes. As 17SLFgenes (SLF1toSLF17) have been identified inS2andS3pollen, here we examined whether all 17SLFs are assembled into similar complexes and, if so, whether these complexes are unique toSLFs. We modified the previous Co‐IP/MSprocedure, including the addition of style extracts from four differentS‐genotypes to pollen extracts containing PiSSK1:FLAG:GFP, to perform four separate experiments. The results taken together show that all 17SLFs and anSLF‐like protein,SLFLike1 (encoded by anS‐locus‐linked gene), co‐immunoprecipitated with PiSSK1:FLAG:GFP. Moreover, of the 179 other F‐box proteins predicted byS2andS3pollen transcriptomes, only a pair with 94.9% identity and another pair with 99.7% identity co‐immunoprecipitated with PiSSK1:FLAG:GFP. These results suggest thatSCFSLFcomplexes have evolved specifically to function in self‐incompatibility.

    more » « less
  3. The V 1−x Mo x O 2 phase diagram has high structural and electronic complexity that is driven by strong, short-range correlations that compete with the long-range rutile crystal structure. The substitution regime near 50% Mo occupancy is no exception, but there has so far been no significant progress in determining the actual structure. Reported here is a combined study using single crystal X-ray diffraction, powder X-ray diffraction, and representational analysis to examine both the local and crystallographically averaged atomic structures simultaneously near x = 0.50. Between about x = 0.50 and 0.60, the average structure of V 1−x Mo x O 2 is the parent rutile phase, but the local symmetry is broken by atomic displacements that are best described using the orthorhombic subgroup Fmmm . This model is locally similar to the two-dimensionally ordered 2D-M2 phase recently reported in the compositional range 0.19 ≤ x ≤ 0.30, except the correlation length is much shorter in the 2D plane, and longer in the frustrated one, making it more isotropic. This work also extends the 2D-M2 phase regime up to x = 0.43, and suggests that the local- Fmmm phase observed here can be seen as the end result of the continued suppression of the 2D-M2 phase through enhanced geometric frustration between the intrinsic order parameters. This suggests that other doped-rutile phases with elusive structures may also be dominated by similar short-range correlations that are hidden in the diffuse scattering. 
    more » « less
  4. Abstract Chord measures are newly discovered translation-invariant geometric measures of convex bodies in R n {{\mathbb{R}}}^{n} , in addition to Aleksandrov-Fenchel-Jessen’s area measures. They are constructed from chord integrals of convex bodies and random lines. Prescribing the L p {L}_{p} chord measures is called the L p {L}_{p} chord Minkowski problem in the L p {L}_{p} Brunn-Minkowski theory, which includes the L p {L}_{p} Minkowski problem as a special case. This article solves the L p {L}_{p} chord Minkowski problem when p > 1 p\gt 1 and the symmetric case of 0 < p < 1 0\lt p\lt 1 . 
    more » « less
  5. null (Ed.)
    Given an element set E of order n, a collection of subsets [Formula: see text], a cost c S on each set [Formula: see text], a covering requirement r e for each element [Formula: see text], and an integer k, the goal of a minimum partial set multicover problem (MinPSMC) is to find a subcollection [Formula: see text] to fully cover at least k elements such that the cost of [Formula: see text] is as small as possible and element e is fully covered by [Formula: see text] if it belongs to at least r e sets of [Formula: see text]. This problem generalizes the minimum k-union problem (MinkU) and is believed not to admit a subpolynomial approximation ratio. In this paper, we present a [Formula: see text]-approximation algorithm for MinPSMC, in which [Formula: see text] is the maximum size of a set in S. And when [Formula: see text], we present a bicriteria algorithm fully covering at least [Formula: see text] elements with approximation ratio [Formula: see text], where [Formula: see text] is a fixed number. These results are obtained by studying the minimum density subcollection problem with (or without) cardinality constraint, which might be of interest by itself. 
    more » « less