@phdthesis{11362,
abstract = {Deep learning has enabled breakthroughs in challenging computing problems and has emerged as the standard problem-solving tool for computer vision and natural language processing tasks.
One exception to this trend is safety-critical tasks where robustness and resilience requirements contradict the black-box nature of neural networks.
To deploy deep learning methods for these tasks, it is vital to provide guarantees on neural network agents' safety and robustness criteria.
This can be achieved by developing formal verification methods to verify the safety and robustness properties of neural networks.
Our goal is to design, develop and assess safety verification methods for neural networks to improve their reliability and trustworthiness in real-world applications.
This thesis establishes techniques for the verification of compressed and adversarially trained models as well as the design of novel neural networks for verifiably safe decision-making.
First, we establish the problem of verifying quantized neural networks. Quantization is a technique that trades numerical precision for the computational efficiency of running a neural network and is widely adopted in industry.
We show that neglecting the reduced precision when verifying a neural network can lead to wrong conclusions about the robustness and safety of the network, highlighting that novel techniques for quantized network verification are necessary. We introduce several bit-exact verification methods explicitly designed for quantized neural networks and experimentally confirm on realistic networks that the network's robustness and other formal properties are affected by the quantization.
Furthermore, we perform a case study providing evidence that adversarial training, a standard technique for making neural networks more robust, has detrimental effects on the network's performance. This robustness-accuracy tradeoff has been studied before regarding the accuracy obtained on classification datasets where each data point is independent of all other data points. On the other hand, we investigate the tradeoff empirically in robot learning settings where a both, a high accuracy and a high robustness, are desirable.
Our results suggest that the negative side-effects of adversarial training outweigh its robustness benefits in practice.
Finally, we consider the problem of verifying safety when running a Bayesian neural network policy in a feedback loop with systems over the infinite time horizon. Bayesian neural networks are probabilistic models for learning uncertainties in the data and are therefore often used on robotic and healthcare applications where data is inherently stochastic.
We introduce a method for recalibrating Bayesian neural networks so that they yield probability distributions over safe decisions only.
Our method learns a safety certificate that guarantees safety over the infinite time horizon to determine which decisions are safe in every possible state of the system.
We demonstrate the effectiveness of our approach on a series of reinforcement learning benchmarks.},
author = {Lechner, Mathias},
isbn = {978-3-99078-017-6},
keywords = {neural networks, verification, machine learning},
pages = {124},
publisher = {Institute of Science and Technology Austria},
title = {{Learning verifiable representations}},
doi = {10.15479/at:ista:11362},
year = {2022},
}
@article{22196,
abstract = {We explore two questions about pseudo-polynomials, which
are functions f : N → Z such that k divides f(n + k) −
f(n) for all n, k. First, for certain arbitrarily sparse sets R, we
construct pseudo-polynomials f with p|f(n) for some n only if
p ∈ R. This implies that not all pseudo-polynomials satisfy an
assumption of a recent paper of Kowalski and Soundararajan.
We also consider α-primary pseudo-polynomials, where the
pseudo-polynomial condition is only required for k lying in
a set of primes of density α. We show that if an α-primary
pseudo-polynomial is O(e(β−)n), where β = √7
3 − 1
6 ≈ 0.715,
then it is a polynomial.},
author = {Kuperberg, Vivian Zieve},
issn = {0022-314X},
journal = {Journal of Number Theory},
keywords = {Pseudo-polynomials, Chinese remainder theorem, Ruzsa’s conjecture},
pages = {531--541},
publisher = {Elsevier},
title = {{On pseudo-polynomials divisible only by a sparse set of primes and α-primary pseudo-polynomials}},
doi = {10.1016/j.jnt.2022.04.006},
volume = {241},
year = {2022},
}
@unpublished{18293,
abstract = {Given a non-singular diagonal cubic hypersurface X⊂Pn−1 over Fq(t) with char(Fq)≠3, we show that the number of rational points of height at most |P| is O(|P|3+ε) for n=6 and O(|P|2+ε) for n=4. In fact, if n=4 and char(Fq)>3 we prove that the number of rational points away from any rational line contained in X is bounded by O(|P|3/2+ε). From the result in 6 variables we deduce weak approximation for diagonal cubic hypersurfaces for n≥7 over Fq(t) when char(Fq)>3 and handle Waring's problem for cubes in 7 variables over Fq(t) when char(Fq)≠3. Our results answer a question of Davenport regarding the number of solutions of bounded height to x31+x32+x33=x34+x35+x36 with xi∈Fq[t].},
author = {Glas, Jakob and Hochfilzer, Leonhard},
booktitle = {arXiv},
title = {{On a question of Davenport and diagonal cubic forms over Fq(t)}},
doi = {10.48550/arXiv.2208.05422},
year = {2022},
}
@article{12244,
abstract = {Environmental cues influence the highly dynamic morphology of microglia. Strategies to characterize these changes usually involve user-selected morphometric features, which preclude the identification of a spectrum of context-dependent morphological phenotypes. Here we develop MorphOMICs, a topological data analysis approach, which enables semiautomatic mapping of microglial morphology into an atlas of cue-dependent phenotypes and overcomes feature-selection biases and biological variability. We extract spatially heterogeneous and sexually dimorphic morphological phenotypes for seven adult mouse brain regions. This sex-specific phenotype declines with maturation but increases over the disease trajectories in two neurodegeneration mouse models, with females showing a faster morphological shift in affected brain regions. Remarkably, microglia morphologies reflect an adaptation upon repeated exposure to ketamine anesthesia and do not recover to control morphologies. Finally, we demonstrate that both long primary processes and short terminal processes provide distinct insights to morphological phenotypes. MorphOMICs opens a new perspective to characterize microglial morphology.},
author = {Colombo, Gloria and Cubero, Ryan J and Kanari, Lida and Venturino, Alessandro and Schulz, Rouven and Scolamiero, Martina and Agerberg, Jens and Mathys, Hansruedi and Tsai, Li-Huei and Chachólski, Wojciech and Hess, Kathryn and Siegert, Sandra},
issn = {1546-1726},
journal = {Nature Neuroscience},
keywords = {General Neuroscience},
number = {10},
pages = {1379--1393},
publisher = {Springer Nature},
title = {{A tool for mapping microglial morphology, morphOMICs, reveals brain-region and sex-dependent phenotypes}},
doi = {10.1038/s41593-022-01167-6},
volume = {25},
year = {2022},
}
@phdthesis{11388,
abstract = {In evolve and resequence experiments, a population is sequenced, subjected to selection and
then sequenced again, so that genetic changes before and after selection can be observed at
the genetic level. Here, I use these studies to better understand the genetic basis of complex
traits - traits which depend on more than a few genes.
In the first chapter, I discuss the first evolve and resequence experiment, in which a population
of mice, the so-called "Longshanks" mice, were selected for tibia length while their body mass
was kept constant. The full pedigree is known. We observed a selection response on all
chromosomes and used the infinitesimal model with linkage, a model which assumes an infinite
number of genes with infinitesimally small effect sizes, as a null model. Results implied a very
polygenic basis with a few loci of major effect standing out and changing in parallel. There
was large variability between the different chromosomes in this study, probably due to LD.
In chapter two, I go on to discuss the impact of LD, on the variability in an allele-frequency
based summary statistic, giving an equation based on the initial allele frequencies, average
pairwise LD, and the first four moments of the haplotype block copy number distribution. I
describe this distribution by referring back to the founder generation. I then demonstrate
how to infer selection via a maximum likelihood scheme on the example of a single locus and
discuss how to extend this to more realistic scenarios.
In chapter three, I discuss the second evolve and resequence experiment, in which a small
population of Drosophila melanogaster was selected for increased pupal case size over 6
generations. The experiment was highly replicated with 27 lines selected within family and a
known pedigree. We observed a phenotypic selection response of over one standard deviation.
I describe the patterns in allele frequency data, including allele frequency changes and patterns
of heterozygosity, and give ideas for future work.},
author = {Belohlavy, Stefanie},
isbn = {978-3-99078-018-3},
pages = {98},
publisher = {Institute of Science and Technology Austria},
title = {{The genetic basis of complex traits studied via analysis of evolve and resequence experiments}},
doi = {10.15479/at:ista:11388},
year = {2022},
}
@unpublished{11943,
abstract = {Complex wiring between neurons underlies the information-processing network enabling all brain functions, including cognition and memory. For understanding how the network is structured, processes information, and changes over time, comprehensive visualization of the architecture of living brain tissue with its cellular and molecular components would open up major opportunities. However, electron microscopy (EM) provides nanometre-scale resolution required for full in-silico reconstruction1–5, yet is limited to fixed specimens and static representations. Light microscopy allows live observation, with super-resolution approaches6–12 facilitating nanoscale visualization, but comprehensive 3D-reconstruction of living brain tissue has been hindered by tissue photo-burden, photobleaching, insufficient 3D-resolution, and inadequate signal-to-noise ratio (SNR). Here we demonstrate saturated reconstruction of living brain tissue. We developed an integrated imaging and analysis technology, adapting stimulated emission depletion (STED) microscopy6,13 in extracellularly labelled tissue14 for high SNR and near-isotropic resolution. Centrally, a two-stage deep-learning approach leveraged previously obtained information on sample structure to drastically reduce photo-burden and enable automated volumetric reconstruction down to single synapse level. Live reconstruction provides unbiased analysis of tissue architecture across time in relation to functional activity and targeted activation, and contextual understanding of molecular labelling. This adoptable technology will facilitate novel insights into the dynamic functional architecture of living brain tissue.},
author = {Velicky, Philipp and Miguel Villalba, Eder and Michalska, Julia M and Wei, Donglai and Lin, Zudi and Watson, Jake and Troidl, Jakob and Beyer, Johanna and Ben Simon, Yoav and Sommer, Christoph M and Jahr, Wiebke and Cenameri, Alban and Broichhagen, Johannes and Grant, Seth G. N. and Jonas, Peter M and Novarino, Gaia and Pfister, Hanspeter and Bickel, Bernd and Danzl, Johann G},
booktitle = {bioRxiv},
title = {{Saturated reconstruction of living brain tissue}},
doi = {10.1101/2022.03.16.484431},
year = {2022},
}
@article{11498,
abstract = {Rest-frame ultraviolet (UV) emission lines probe electron densities, gas-phase abundances, metallicities, and ionization parameters of the emitting star-forming galaxies and their environments. The strongest main UV emission line, Lyα, has been instrumental in advancing the general knowledge of galaxy formation in the early universe. However, observing Lyα emission becomes increasingly challenging at z ≳ 6 when the neutral hydrogen fraction of the circumgalactic and intergalactic media increases. Secondary weaker UV emission lines provide important alternative methods for studying galaxy properties at high redshift. We present a large sample of rest-frame UV emission line sources at intermediate redshift for calibrating and exploring the connection between secondary UV lines and the emitting galaxies’ physical properties and their Lyα emission. The sample of 2052 emission line sources with 1.5 < z < 6.4 was collected from integral field data from the MUSE-Wide and MUSE-Deep surveys taken as part of Guaranteed Time Observations. The objects were selected through untargeted source detection (i.e., no preselection of sources as in dedicated spectroscopic campaigns) in the three-dimensional MUSE data cubes. We searched optimally extracted one-dimensional spectra of the full sample for UV emission features via emission line template matching, resulting in a sample of more than 100 rest-frame UV emission line detections. We show that the detection efficiency of (non-Lyα) UV emission lines increases with survey depth, and that the emission line strength of He IIλ1640 Å, [O III] λ1661 + O III] λ1666, and [Si III] λ1883 + Si III] λ1892 correlate with the strength of [C III] λ1907 + C III] λ1909. The rest-frame equivalent width (EW0) of [C III] λ1907 + C III] λ1909 is found to be roughly 0.22 ± 0.18 of EW0(Lyα). We measured the velocity offsets of resonant emission lines with respect to systemic tracers. For C IVλ1548 + C IVλ1551 we find that ΔvC IV ≲ 250 km s−1, whereas ΔvLyα falls in the range of 250−500 km s−1 which is in agreement with previous results from the literature. The electron density ne measured from [Si III] λ1883 + Si III] λ1892 and [C III] λ1907 + C III] λ1909 line flux ratios is generally < 105 cm−3 and the gas-phase abundance is below solar at 12 + log10(O/H)≈8. Lastly, we used “PhotoIonization Model Probability Density Functions” to infer physical parameters of the full sample and individual systems based on photoionization model parameter grids and observational constraints from our UV emission line searches. This reveals that the UV line emitters generally have ionization parameter log10(U) ≈ −2.5 and metal mass fractions that scatter around Z ≈ 10−2, that is Z ≈ 0.66 Z⊙. Value-added catalogs of the full sample of MUSE objects studied in this work and a collection of UV line emitters from the literature are provided with this paper.},
author = {Schmidt, K. B. and Kerutt, J. and Wisotzki, L. and Urrutia, T. and Feltre, A. and Maseda, M. V. and Nanayakkara, T. and Bacon, R. and Boogaard, L. A. and Conseil, S. and Contini, T. and Herenz, E. C. and Kollatschny, W. and Krumpe, M. and Leclercq, F. and Mahler, G. and Matthee, Jorryt J and Mauerhofer, V. and Richard, J. and Schaye, J.},
issn = {1432-0746},
journal = {Astronomy & Astrophysics},
keywords = {Space and Planetary Science, Astronomy and Astrophysics, ultraviolet: galaxies / galaxies: high-redshift / galaxies: ISM / ISM: lines and bands / methods: observational / techniques: imaging spectroscopy},
publisher = {EDP Sciences},
title = {{Recovery and analysis of rest-frame UV emission lines in 2052 galaxies observed with MUSE at 1.5 < z < 6.4}},
doi = {10.1051/0004-6361/202140876},
volume = {654},
year = {2021},
}
@article{11500,
abstract = {We report the discovery of diffuse extended Lyα emission from redshift 3.1 to 4.5, tracing cosmic web filaments on scales of 2.5−4 cMpc. These structures have been observed in overdensities of Lyα emitters in the MUSE Extremely Deep Field, a 140 h deep MUSE observation located in the Hubble Ultra-Deep Field. Among the 22 overdense regions identified, five are likely to harbor very extended Lyα emission at high significance with an average surface brightness of 5 × 10−20 erg s−1 cm−2 arcsec−2. Remarkably, 70% of the total Lyα luminosity from these filaments comes from beyond the circumgalactic medium of any identified Lyα emitter. Fluorescent Lyα emission powered by the cosmic UV background can only account for less than 34% of this emission at z ≈ 3 and for not more than 10% at higher redshift. We find that the bulk of this diffuse emission can be reproduced by the unresolved Lyα emission of a large population of ultra low-luminosity Lyα emitters (< 1040 erg s−1), provided that the faint end of the Lyα luminosity function is steep (α ⪅ −1.8), it extends down to luminosities lower than 1038 − 1037 erg s−1, and the clustering of these Lyα emitters is significant (filling factor < 1/6). If these Lyα emitters are powered by star formation, then this implies their luminosity function needs to extend down to star formation rates < 10−4 M⊙ yr−1. These observations provide the first detection of the cosmic web in Lyα emission in typical filamentary environments and the first observational clue indicating the existence of a large population of ultra low-luminosity Lyα emitters at high redshift.},
author = {Bacon, R. and Mary, D. and Garel, T. and Blaizot, J. and Maseda, M. and Schaye, J. and Wisotzki, L. and Conseil, S. and Brinchmann, J. and Leclercq, F. and Abril-Melgarejo, V. and Boogaard, L. and Bouché, N. F. and Contini, T. and Feltre, A. and Guiderdoni, B. and Herenz, C. and Kollatschny, W. and Kusakabe, H. and Matthee, Jorryt J and Michel-Dansac, L. and Nanayakkara, T. and Richard, J. and Roth, M. and Schmidt, K. B. and Steinmetz, M. and Tresse, L. and Urrutia, T. and Verhamme, A. and Weilbacher, P. M. and Zabl, J. and Zoutendijk, S. L.},
issn = {1432-0746},
journal = {Astronomy & Astrophysics},
keywords = {Space and Planetary Science, Astronomy and Astrophysics, galaxies: high-redshift / galaxies: groups: general / cosmology: observations},
publisher = {EDP Sciences},
title = {{The MUSE Extremely Deep Field: The cosmic web in emission at high redshift}},
doi = {10.1051/0004-6361/202039887},
volume = {647},
year = {2021},
}
@article{11522,
abstract = {The decline in abundance of Lyman-α (Lyα) emitting galaxies at z ≳ 6 is a powerful and commonly used probe to constrain the progress of cosmic reionization. We use the CODAII simulation, which is a radiation hydrodynamic simulation featuring a box of ∼94 comoving Mpc side length, to compute the Lyα transmission properties of the intergalactic medium (IGM) at z ∼ 5.8 to 7. Our results mainly confirm previous studies, i.e. we find a declining Lyα transmission with redshift and a large sightline-to-sightline variation. However, motivated by the recent discovery of blue Lyα peaks at high redshift, we also analyse the IGM transmission on the blue side, which shows a rapid decline at z ≳ 6 of the blue transmission. This low transmission can be attributed not only to the presence of neutral regions but also to the residual neutral hydrogen within ionized regions, for which a density even as low as nHI∼10−9cm−3 (sometimes combined with kinematic effects) leads to a significantly reduced visibility. Still, we find that ∼1 per cent of sightlines towards M1600AB ∼ −21 galaxies at z ∼ 7 are transparent enough to allow a transmission of a blue Lyα peak. We discuss our results in the context of the interpretation of observations.},
author = {Gronke, Max and Ocvirk, Pierre and Mason, Charlotte and Matthee, Jorryt J and Bosman, Sarah E I and Sorce, Jenny G and Lewis, Joseph and Ahn, Kyungjin and Aubert, Dominique and Dawoodbhoy, Taha and Iliev, Ilian T and Shapiro, Paul R and Yepes, Gustavo},
issn = {1365-2966},
journal = {Monthly Notices of the Royal Astronomical Society},
keywords = {dark ages, reionization, first stars, intergalactic medium, galaxies: formation},
number = {3},
pages = {3697--3709},
publisher = {Oxford University Press},
title = {{Lyman-α transmission properties of the intergalactic medium in the CoDaII simulation}},
doi = {10.1093/mnras/stab2762},
volume = {508},
year = {2021},
}
@article{11524,
abstract = {We measure the evolution of the rest-frame UV luminosity function (LF) and the stellar mass function (SMF) of Lyman-α (Ly α) emitters (LAEs) from z ∼ 2 to z ∼ 6 by exploring ∼4000 LAEs from the SC4K sample. We find a correlation between Ly α luminosity (LLy α) and rest-frame UV (MUV), with best fit MUV=−1.6+0.2−0.3log10(LLyα/ergs−1)+47+12−11 and a shallower relation between LLy α and stellar mass (M⋆), with best fit log10(M⋆/M⊙)=0.9+0.1−0.1log10(LLyα/ergs−1)−28+4.0−3.8. An increasing LLy α cut predominantly lowers the number density of faint MUV and low M⋆ LAEs. We estimate a proxy for the full UV LFs and SMFs of LAEs with simple assumptions of the faint end slope. For the UV LF, we find a brightening of the characteristic UV luminosity (M∗UV) with increasing redshift and a decrease of the characteristic number density (Φ*). For the SMF, we measure a characteristic stellar mass (M∗⋆/M⊙) increase with increasing redshift, and a Φ* decline. However, if we apply a uniform luminosity cut of log10(LLyα/ergs−1)≥43.0, we find much milder to no evolution in the UV and SMF of LAEs. The UV luminosity density (ρUV) of the full sample of LAEs shows moderate evolution and the stellar mass density (ρM) decreases, with both being always lower than the total ρUV and ρM of more typical galaxies but slowly approaching them with increasing redshift. Overall, our results indicate that both ρUV and ρM of LAEs slowly approach the measurements of continuum-selected galaxies at z > 6, which suggests a key role of LAEs in the epoch of reionization.},
author = {Santos, S and Sobral, D and Butterworth, J and Paulino-Afonso, A and Ribeiro, B and da Cunha, E and Calhau, J and Khostovan, A A and Matthee, Jorryt J and Arrabal Haro, P},
issn = {1365-2966},
journal = {Monthly Notices of the Royal Astronomical Society},
keywords = {Space and Planetary Science, Astronomy and Astrophysics, galaxies: evolution, galaxies: high-redshift, galaxies: luminosity function, mass function},
number = {1},
pages = {1117--1134},
publisher = {Oxford University Press},
title = {{The evolution of the UV luminosity and stellar mass functions of Lyman-α emitters from z ∼ 2 to z ∼ 6}},
doi = {10.1093/mnras/stab1218},
volume = {505},
year = {2021},
}
@article{11756,
abstract = {We give two fully dynamic algorithms that maintain a (1 + ε)-approximation of the weight M of a minimum spanning forest (MSF) of an n-node graph G with edges weights in [1, W ], for any ε > 0. (1) Our deterministic algorithm takes O (W 2 log W /ε3) worst-case update time, which is O (1) if both W and ε are constants. (2) Our randomized (Monte-Carlo style) algorithm works with high probability and runs in worst-case O (log W /ε4) update time if W = O ((m∗)1/6/log2/3 n), where m∗ is the minimum number of edges in the graph throughout all the updates. It works even against an adaptive adversary. We complement our algorithmic results with two cell-probe lower bounds for dynamically maintaining an approximation of the weight of an MSF of a graph.},
author = {Henzinger, Monika H and Peng, Pan},
issn = {0890-5401},
journal = {Information and Computation},
number = {12},
publisher = {Elsevier},
title = {{Constant-time dynamic weight approximation for minimum spanning forest}},
doi = {10.1016/j.ic.2021.104805},
volume = {281},
year = {2021},
}
@article{11886,
abstract = {We present a deterministic (1+𝑜(1))-approximation (𝑛1/2+𝑜(1)+𝐷1+𝑜(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the \sf CONGEST model); here 𝑛 is the number of nodes in the network, 𝐷 is its (hop) diameter, and edge weights are positive integers from 1 to poly(𝑛). This is the first nontrivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1+𝑜(1))-approximation 𝑂̃ (𝑛√𝐷1/4+𝐷)-time algorithm of Nanongkai [in Proceedings of STOC, 2014, pp. 565--573] by a factor of as large as 𝑛1/8, and (ii) the 𝑂(𝜖−1log𝜖−1)-approximation factor of Lenzen and Patt-Shamir's 𝑂̃ (𝑛1/2+𝜖+𝐷)-time algorithm [in Proceedings of STOC, 2013, pp. 381--390] within the same running time. (Throughout, we use 𝑂̃ (⋅) to hide polylogarithmic factors in 𝑛.) Our running time matches the known time lower bound of Ω(𝑛/log𝑛‾‾‾‾‾‾‾√+𝐷) [M. Elkin, SIAM J. Comput., 36 (2006), pp. 433--456], thus essentially settling the status of this problem which was raised at least a decade ago [M. Elkin, SIGACT News, 35 (2004), pp. 40--57]. It also implies a (2+𝑜(1))-approximation (𝑛1/2+𝑜(1)+𝐷1+𝑜(1))-time algorithm for approximating a network's weighted diameter which almost matches the lower bound by Holzer and Pinsker [in Proceedings of OPODIS, 2015, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2016, 6]. In achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the “hitting set argument” commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic construction of an (𝑛𝑜(1),𝑜(1))-hop set of size 𝑛1+𝑜(1). We combine these techniques with many distributed algorithmic techniques, some of which are from problems that are not directly related to shortest paths, e.g., ruling sets [A. V. Goldberg, S. A. Plotkin, and G. E. Shannon, SIAM J. Discrete Math., 1 (1988), pp. 434--446], source detection [C. Lenzen and D. Peleg, in Proceedings of PODC, 2013, pp. 375--382], and partial distance estimation [C. Lenzen and B. Patt-Shamir, in Proceedings of PODC, 2015, pp. 153--162]. Our hop set construction also leads to single-source shortest paths algorithms in two other settings: (i) a (1+𝑜(1))-approximation 𝑛𝑜(1)-time algorithm on congested cliques, and (ii) a (1+𝑜(1))-approximation 𝑛𝑜(1)-pass 𝑛1+𝑜(1)-space streaming algorithm. The first result answers an open problem in [D. Nanongkai, in Proceedings of STOC, 2014, pp. 565--573]. The second result partially answers an open problem raised by McGregor in 2006 [List of Open Problems in Sublinear Algorithms: Problem 14].},
author = {Henzinger, Monika H and Krinninger, Sebastian and Nanongkai, Danupon},
issn = {1095-7111},
journal = {SIAM Journal on Computing},
number = {3},
pages = {STOC16--98--STOC16--137},
publisher = {Society for Industrial & Applied Mathematics},
title = {{A deterministic almost-tight distributed algorithm for approximating single-source shortest paths}},
doi = {10.1137/16m1097808},
volume = {50},
year = {2021},
}
@misc{13072,
abstract = {CpGs and corresponding mean weights for DNAm-based prediction of cognitive abilities (6 traits)},
author = {McCartney, Daniel L and Hillary, Robert F and Conole, Eleanor LS and Trejo Banos, Daniel and Gadd, Danni A and Walker, Rosie M and Nangle, Cliff and Flaig, Robin and Campbell, Archie and Murray, Alison D and Munoz Maniega, Susana and del C Valdes-Hernandez, Maria and Harris, Mathew A and Bastin, Mark E and Wardlaw, Joanna M and Harris, Sarah E and Porteous, David J and Tucker-Drob, Elliot M and McIntosh, Andrew M and Evans, Kathryn L and Deary, Ian J and Cox, Simon R and Robinson, Matthew Richard and Marioni, Riccardo E},
publisher = {Zenodo},
title = {{Blood-based epigenome-wide analyses of cognitive abilities}},
doi = {10.5281/ZENODO.5794028},
year = {2021},
}
@article{15219,
abstract = {We have carried out a search for massive white dwarfs (WDs) in the direction of young open star clusters using the Gaia DR2 database. The aim of this survey was (1) to provide robust data for new and previously known high-mass WDs regarding cluster membership, (2) to highlight WDs previously included in the initial final mass relation (IFMR) that are unlikely members of their respective clusters according to Gaia astrometry, and (3) to select an unequivocal WD sample that could then be compared with the host clusters' turnoff masses. All promising WD candidates in each cluster color–magnitude diagram were followed up with spectroscopy from Gemini in order to determine whether they were indeed WDs and derive their masses, temperatures, and ages. In order to be considered cluster members, white dwarfs were required to (1) have proper motions and parallaxes within 2σ, 3σ, or 4σ of those of their potential parent cluster based on how contaminated the field was in their region of the sky, (2) have a cooling age that was less than the cluster age, and (3) have a mass that was broadly consistent with the IFMR. A number of WDs included in current versions of the IFMR turned out to be nonmembers, and a number of apparent members, based on Gaia's astrometric data alone, were rejected, as their mass and/or cooling times were incompatible with cluster membership. In this way, we developed a highly selected IFMR sample for high-mass WDs that, surprisingly, contained no precursor masses significantly in excess of ∼ 6 M⊙.},
author = {Richer, Harvey B. and Caiazzo, Ilaria and Du, Helen and Grondin, Steffani and Hegarty, James and Heyl, Jeremy and Kerr, Ronan and Miller, David R. and Thiele, Sarah},
issn = {1538-4357},
journal = {The Astrophysical Journal},
keywords = {Space and Planetary Science, Astronomy and Astrophysics},
number = {2},
publisher = {American Astronomical Society},
title = {{Massive white dwarfs in young star clusters}},
doi = {10.3847/1538-4357/abdeb7},
volume = {912},
year = {2021},
}
@article{19492,
abstract = {Kuroda’s formula relates the class number of a multiquadratic number field K to the class numbers of its quadratic subfields ki. A key component in this formula is the unit group index (math formular). We study how Q(K) behaves on average in certain natural families of totally real biquadratic fields K parametrized by prime numbers.},
author = {Chan, Yik Tung and Milovic, Djordjo},
issn = {1432-1823},
journal = {Mathematische Zeitschrift},
number = {2},
pages = {1509--1527},
publisher = {Springer Nature},
title = {{Kuroda’s formula and arithmetic statistics}},
doi = {10.1007/s00209-021-02823-6},
volume = {300},
year = {2021},
}
@article{20619,
abstract = {The first author’s previous work established Solomon’s WDVV-type relations for Welschinger’s invariant curve counts in real symplectic fourfolds by lifting geometric relations over possibly unorientable morphisms. We apply her framework to obtain WDVV-style relations for the disk invariants of real symplectic sixfolds with some symmetry, in particular confirming Alcolado’s prediction for P^3 and extending it to other spaces. These relations reduce the computation of Welschinger’s invariants of many real symplectic sixfolds to invariants in small degrees and provide lower bounds for counts of real rational curves with positive-dimensional insertions in some cases. In the case of P^3, our lower bounds fit perfectly with Kollár’s vanishing results.},
author = {Chen, Xujia and Zinger, Aleksey},
issn = {1432-1807},
journal = {Mathematische Annalen},
number = {3-4},
pages = {1231--1313},
publisher = {Springer Nature},
title = {{WDVV-type relations for disk Gromov–Witten invariants in dimension 6}},
doi = {10.1007/s00208-020-02130-1},
volume = {379},
year = {2021},
}
@inproceedings{10002,
abstract = {We present a faster symbolic algorithm for the following central problem in probabilistic verification: Compute the maximal end-component (MEC) decomposition of Markov decision processes (MDPs). This problem generalizes the SCC decomposition problem of graphs and closed recurrent sets of Markov chains. The model of symbolic algorithms is widely used in formal verification and model-checking, where access to the input model is restricted to only symbolic operations (e.g., basic set operations and computation of one-step neighborhood). For an input MDP with n vertices and m edges, the classical symbolic algorithm from the 1990s for the MEC decomposition requires O(n2) symbolic operations and O(1) symbolic space. The only other symbolic algorithm for the MEC decomposition requires O(nm−−√) symbolic operations and O(m−−√) symbolic space. A main open question is whether the worst-case O(n2) bound for symbolic operations can be beaten. We present a symbolic algorithm that requires O˜(n1.5) symbolic operations and O˜(n−−√) symbolic space. Moreover, the parametrization of our algorithm provides a trade-off between symbolic operations and symbolic space: for all 0<ϵ≤1/2 the symbolic algorithm requires O˜(n2−ϵ) symbolic operations and O˜(nϵ) symbolic space ( O˜ hides poly-logarithmic factors). Using our techniques we present faster algorithms for computing the almost-sure winning regions of ω -regular objectives for MDPs. We consider the canonical parity objectives for ω -regular objectives, and for parity objectives with d -priorities we present an algorithm that computes the almost-sure winning region with O˜(n2−ϵ) symbolic operations and O˜(nϵ) symbolic space, for all 0<ϵ≤1/2 .},
author = {Chatterjee, Krishnendu and Dvorak, Wolfgang and Henzinger, Monika H and Svozil, Alexander},
booktitle = {Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science},
isbn = {978-1-6654-4896-3},
issn = {1043-6871},
keywords = {Computer science, Computational modeling, Markov processes, Probabilistic logic, Formal verification, Game Theory},
location = {Rome, Italy},
pages = {1--13},
publisher = {Institute of Electrical and Electronics Engineers},
title = {{Symbolic time and space tradeoffs for probabilistic verification}},
doi = {10.1109/LICS52264.2021.9470739},
year = {2021},
}
@inproceedings{10004,
abstract = {Markov chains are the de facto finite-state model for stochastic dynamical systems, and Markov decision processes (MDPs) extend Markov chains by incorporating non-deterministic behaviors. Given an MDP and rewards on states, a classical optimization criterion is the maximal expected total reward where the MDP stops after T steps, which can be computed by a simple dynamic programming algorithm. We consider a natural generalization of the problem where the stopping times can be chosen according to a probability distribution, such that the expected stopping time is T, to optimize the expected total reward. Quite surprisingly we establish inter-reducibility of the expected stopping-time problem for Markov chains with the Positivity problem (which is related to the well-known Skolem problem), for which establishing either decidability or undecidability would be a major breakthrough. Given the hardness of the exact problem, we consider the approximate version of the problem: we show that it can be solved in exponential time for Markov chains and in exponential space for MDPs.},
author = {Chatterjee, Krishnendu and Doyen, Laurent},
booktitle = {Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science},
isbn = {978-1-6654-4896-3},
issn = {1043-6871},
keywords = {Computer science, Heuristic algorithms, Memory management, Automata, Markov processes, Probability distribution, Complexity theory},
location = {Rome, Italy},
pages = {1--13},
publisher = {Institute of Electrical and Electronics Engineers},
title = {{Stochastic processes with expected stopping time}},
doi = {10.1109/LICS52264.2021.9470595},
year = {2021},
}
@article{10223,
abstract = {Growth regulation tailors development in plants to their environment. A prominent example of this is the response to gravity, in which shoots bend up and roots bend down1. This paradox is based on opposite effects of the phytohormone auxin, which promotes cell expansion in shoots while inhibiting it in roots via a yet unknown cellular mechanism2. Here, by combining microfluidics, live imaging, genetic engineering and phosphoproteomics in Arabidopsis thaliana, we advance understanding of how auxin inhibits root growth. We show that auxin activates two distinct, antagonistically acting signalling pathways that converge on rapid regulation of apoplastic pH, a causative determinant of growth. Cell surface-based TRANSMEMBRANE KINASE1 (TMK1) interacts with and mediates phosphorylation and activation of plasma membrane H+-ATPases for apoplast acidification, while intracellular canonical auxin signalling promotes net cellular H+ influx, causing apoplast alkalinization. Simultaneous activation of these two counteracting mechanisms poises roots for rapid, fine-tuned growth modulation in navigating complex soil environments.},
author = {Li, Lanxin and Verstraeten, Inge and Roosjen, Mark and Takahashi, Koji and Rodriguez Solovey, Lesia and Merrin, Jack and Chen, Jian and Shabala, Lana and Smet, Wouter and Ren, Hong and Vanneste, Steffen and Shabala, Sergey and De Rybel, Bert and Weijers, Dolf and Kinoshita, Toshinori and Gray, William M. and Friml, Jiří},
issn = {1476-4687},
journal = {Nature},
keywords = {Multidisciplinary},
number = {7884},
pages = {273--277},
publisher = {Springer Nature},
title = {{Cell surface and intracellular auxin signalling for H+ fluxes in root growth}},
doi = {10.1038/s41586-021-04037-6},
volume = {599},
year = {2021},
}
@article{10280,
abstract = {Machines enabled the Industrial Revolution and are central to modern technological progress: A machine’s parts transmit forces, motion, and energy to one another in a predetermined manner. Today’s engineering frontier, building artificial micromachines that emulate the biological machinery of living organisms, requires faithful assembly and energy consumption at the microscale. Here, we demonstrate the programmable assembly of active particles into autonomous metamachines using optical templates. Metamachines, or machines made of machines, are stable, mobile and autonomous architectures, whose dynamics stems from the geometry. We use the interplay between anisotropic force generation of the active colloids with the control of their orientation by local geometry. This allows autonomous reprogramming of active particles of the metamachines to achieve multiple functions. It permits the modular assembly of metamachines by fusion, reconfiguration of metamachines and, we anticipate, a shift in focus of self-assembly towards active matter and reprogrammable materials.},
author = {Aubret, Antoine and Martinet, Quentin and Palacci, Jérémie A},
issn = {2041-1723},
journal = {Nature Communications},
number = {1},
publisher = {Springer Nature},
title = {{Metamachines of pluripotent colloids}},
doi = {10.1038/s41467-021-26699-6},
volume = {12},
year = {2021},
}