skip to main content


Title: Non-Adaptive Adaptive Sampling on Turnstile Streams
Award ID(s):
1815840
NSF-PAR ID:
10159766
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
STOC
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Meyer, Axel (Ed.)
    Adaptive radiations offer an excellent opportunity to understand the eco-evolutionary dynamics of gut microbiota and host niche specialization. In a laboratory common garden, we compared the gut microbiota of two novel derived trophic specialist pupfishes, a scale-eater and a molluscivore, to closely related and distant outgroup generalist populations, spanning both rapid trophic evolution within 10 kya and stable generalist diets persisting over 11 Mya. We predicted an adaptive and highly divergent microbiome composition in the trophic specialists reflecting their rapid rates of craniofacial and behavioral diversification. We sequenced 16S rRNA amplicons of gut microbiomes from lab-reared adult pupfishes raised under identical conditions and fed the same high protein diet. In contrast to our predictions, gut microbiota largely reflected phylogenetic distance among species, rather than generalist or specialist life history, in support of phylosymbiosis. However, we did find significant enrichment of Burkholderiaceae bacteria in replicated lab-reared scale-eater populations. These bacteria sometimes digest collagen, the major component of fish scales, supporting an adaptive shift. We also found some enrichment of Rhodobacteraceae and Planctomycetia in lab-reared molluscivore populations, but these bacteria target cellulose. Overall phylogenetic conservation of microbiome composition contrasts with predictions of adaptive radiation theory and observations of rapid diversification in all other trophic traits in these hosts, including craniofacial morphology, foraging behavior, aggression, and gene expression, suggesting that the functional role of these minor shifts in microbiota will be important for understanding the role of the microbiome in trophic diversification. 
    more » « less
  2. We study the relation between the query complexity of adaptive and non-adaptive testers in the dense graph model. It has been known for a couple of decades that the query complexity of non-adaptive testers is at most quadratic in the query complexity of adaptive testers. We show that this general result is essentially tight; that is, there exist graph properties for which any non-adaptive tester must have query complexity that is almost quadratic in the query complexity of the best general (i.e., adaptive) tester. More generally, for every q: N→N such that q(n)≤n−−√ and constant c∈[1,2], we show a graph property that is testable in Θ(q(n)) queries, but its non-adaptive query complexity is Θ(q(n)c), omitting poly(log n) factors and ignoring the effect of the proximity parameter ϵ. Furthermore, the upper bounds hold for one-sided error testers, and are at most quadratic in 1/ϵ. These results are obtained through the use of general reductions that transport properties of ordered structured (like bit strings) to those of unordered structures (like unlabeled graphs). The main features of these reductions are query-efficiency and preservation of distance to the properties. This method was initiated in our prior work (ECCC, TR20-149), and we significantly extend it here. 
    more » « less
  3. Schmidt, Dirk ; Schreiber, Laura ; Vernet, Elise (Ed.)
    We present evaluations of the Keck Telescope’s adaptive optics (AO) performance on Milky Way Galactic center imaging and spectroscopic observations using three different AO setups: laser guide star with infrared (IR) tip-tilt correction, laser guide star with visible tip-tilt correction, and infrared natural guide star with a pyramid wavefront sensor. Observations of the Galactic Center can utilize a bright IR tip-tilt star (K′ = 7.4 mag) for corrections, which is over 10 arcseconds closer than the optical tip-tilt star. The proximity of this IR star enables the comparison of the aforementioned AO configurations. We present performance metrics such as full-width-at-half-maximum (FWHM), Strehl ratio, and spectral signal to noise ratio and their relations to atmospheric seeing conditions. The IR tip-tilt star decreases the median spatial FWHM by 31% in imaging data and 30% in spectroscopy. Median Strehl for imaging data improves by 24%. Additionally, the IR star removes the seeing dependence from differential tip-tilt error in both imaging and spectroscopic data. This evaluation provides important work for ongoing upgrades to AO systems, such as the Keck All sky Precision Adaptive Optics (KAPA) upgrade on the Keck I Telescope, and the development of new AO systems for extremely large telescopes. 
    more » « less