skip to main content


Title: Local decoding and testing of polynomials over grids

We study the local decodability and (tolerant) local testability of low‐degreen‐variate polynomials over arbitrary fields, evaluated over the domain {0,1}n. We show that for every field there is a tolerant local test whose query complexity depends only on the degree. In contrast we show that decodability is possible over fields of positive characteristic, but not over the reals.

 
more » « less
Award ID(s):
1715187
NSF-PAR ID:
10165610
Author(s) / Creator(s):
 ;  ;  
Publisher / Repository:
Wiley Blackwell (John Wiley & Sons)
Date Published:
Journal Name:
Random Structures & Algorithms
Volume:
57
Issue:
3
ISSN:
1042-9832
Page Range / eLocation ID:
p. 658-694
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    We propose a new scalable platform for quantum computing (QC)—an array of optically trapped symmetric-top molecules (STMs) of the alkaline earth monomethoxide (MOCH3) family. Individual STMs form qubits, and the system is readily scalable to 100–1000 qubits. STM qubits have desirable features for QC compared to atoms and diatomic molecules. The additional rotational degree of freedom about the symmetric-top axis gives rise to closely spaced opposite parityK-doublets that allow full alignment at low electric fields, and the hyperfine structure naturally provides magnetically insensitive states with switchable electric dipole moments. These features lead to much reduced requirements for electric field control, provide minimal sensitivity to environmental perturbations, and allow for 2-qubit interactions that can be switched on at will. We examine in detail the internal structure of STMs relevant to our proposed platform, taking into account the full effective molecular Hamiltonian including hyperfine interactions, and identify useable STM qubit states. We then examine the effects of the electric dipolar interaction in STMs, which not only guide the design of high-fidelity gates, but also elucidate the nature of dipolar exchange in STMs. Under realistic experimental parameters, we estimate that the proposed QC platform could yield gate errors at the 10−3level, approaching that required for fault-tolerant QC.

     
    more » « less
  2. A collection of sets displays aproximity gapwith 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)linearsize 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\subset {\mathbb {F}}_q^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-party 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 aformal elementof 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.

     
    more » « less
  3. Abstract

    As plant species expand their upper limits of distribution under current warming, some retain both traditional climate space and biotic environment while others encounter novel conditions. The latter is the case forRhododendron campanulatum, a woody shrub that grows both above and below treeline at our study site in the Eastern Himalayas where a very conspicuous, stable treeline was defined by a nearly contiguous canopy of tallAbies spectabilistrees, many of which are over a century old. Prior work showed that treeline had remained static in this region whileR. campanulatumexpanded its elevational range limit. We tested local adaptation ofR. campanulatumby performing reciprocal transplants between the species' current elevational range limit (4023 m above sea level [asl]) and just above treeline (3876 m asl). Contrary to expectation, the coldest temperatures of late winter and early mid‐spring were experienced by plants at the lower elevation:R. campanulatumat species' limit (upper site) were covered by snow for a longer period (40 more days) and escaped the coldest temperatures suffered by conspecifics at treeline (lower site). The harsher spring conditions at treeline likely explain why leaves were smaller at treeline (15.3 cm2) than at species limit (21.3 cm2). Contrary to results from equivalent studies in other regions, survival was reduced more by downslope than by upslope movement, again potentially due to extreme cold temperatures observed at treeline in spring. Upslope transplantation had no effect on mortality, but mortality of species limit saplings transplanted downslope was three times higher than that of residents at both sites. A general expectation is that locals should survive better than foreign transplants, but survival of locals and immigrants at our species limit site was identical. However, those species limit saplings that survived the transplant to treeline grew faster than both locals at treeline and the transplants at species limit. Overall, we found asymmetric adaptation: Compared with treeline saplings, those at species limit (147 m above treeline) were more tolerant of extremes in the growing season but less tolerant of extremes in winter and early mid‐spring, displaying local adaptation in a more complex manner than simply home advantage, and complicating predictions about impacts of future regional climate change.

     
    more » « less
  4. Abstract

    We use medium- and high-resolution spectroscopy of close pairs of quasars to analyze the circumgalactic medium (CGM) surrounding 32 damped Lyαabsorption systems (DLAs). The primary quasar sightline in each pair probes an intervening DLA in the redshift range 1.6 <zabs< 3.5, such that the secondary sightline probes absorption from Lyαand a large suite of metal-line transitions (including Oi, Cii, Civ, Siii, and Siiv) in the DLA host galaxy’s CGM at transverse distances 24 kpc ≤R≤ 284 kpc. Analysis of Lyαin the CGM sightlines shows an anticorrelation betweenRand Hicolumn density (NHI) with 99.8% confidence, similar to that observed around luminous galaxies. The incidences of Ciiand SiiiwithN> 1013cm−2within 100 kpc of DLAs are larger by 2σthan those measured in the CGM of Lyman break galaxies (Cf(NCII) > 0.89 andCf(NSiII)=0.750.17+0.12). Metallicity constraints derived from ionic ratios for nine CGM systems with negligible ionization corrections andNHI> 1018.5cm−2show a significant degree of scatter (with metallicities/limits across the range2.06logZ/Z0.75), suggesting inhomogeneity in the metal distribution in these environments. Velocity widths of Civλ1548 and low-ionization metal species in the DLA versus CGM sightlines are strongly (>2σ) correlated, suggesting that they trace the potential well of the host halo overR≲ 300 kpc scales. At the same time, velocity centroids for Civλ1548 differ in DLA versus CGM sightlines by >100 km s−1for ∼50% of velocity components, but few components have velocities that would exceed the escape velocity assuming dark matter host halos of ≥1012M.

     
    more » « less
  5. Abstract

    The optical and near-ultraviolet (NUV) continuum radiation in M-dwarf flares is thought to be the impulsive response of the lower stellar atmosphere to magnetic energy release and electron acceleration at coronal altitudes. This radiation is sometimes interpreted as evidence of a thermal photospheric spectrum withT≈ 104K. However, calculations show that standard solar flare coronal electron beams lose their energy in a thick target of gas in the upper and middle chromosphere (log10column mass/[g cm−2] ≲ −3). At larger beam injection fluxes, electric fields and instabilities are expected to further inhibit propagation to low altitudes. We show that recent numerical solutions of the time-dependent equations governing the power-law electrons and background coronal plasma (Langmuir and ion-acoustic) waves from Kontar et al. produce order-of-magnitude larger heating rates than those that occur in the deep chromosphere through standard solar flare electron beam power-law distributions. We demonstrate that the redistribution of beam energy aboveE≳ 100 keV in this theory results in a local heating maximum that is similar to a radiative-hydrodynamic model with a large, low-energy cutoff and a hard power-law index. We use this semiempirical forward-modeling approach to produce opaque NUV and optical continua at gas temperaturesT≳ 12,000 K over the deep chromosphere with log10column mass/[g cm−2] of −1.2 to −2.3. These models explain the color temperatures and Balmer jump strengths in high-cadence M-dwarf flare observations, and they clarify the relation among atmospheric, radiation, and optical color temperatures in stellar flares.

     
    more » « less