@article{9431,
abstract = {Inositol hexakisphosphate (IP6) is an assembly cofactor for HIV-1. We report here that IP6 is also used for assembly of Rous sarcoma virus (RSV), a retrovirus from a different genus. IP6 is ~100-fold more potent at promoting RSV mature capsid protein (CA) assembly than observed for HIV-1 and removal of IP6 in cells reduces infectivity by 100-fold. Here, visualized by cryo-electron tomography and subtomogram averaging, mature capsid-like particles show an IP6-like density in the CA hexamer, coordinated by rings of six lysines and six arginines. Phosphate and IP6 have opposing effects on CA in vitro assembly, inducing formation of T = 1 icosahedrons and tubes, respectively, implying that phosphate promotes pentamer and IP6 hexamer formation. Subtomogram averaging and classification optimized for analysis of pleomorphic retrovirus particles reveal that the heterogeneity of mature RSV CA polyhedrons results from an unexpected, intrinsic CA hexamer flexibility. In contrast, the CA pentamer forms rigid units organizing the local architecture. These different features of hexamers and pentamers determine the structural mechanism to form CA polyhedrons of variable shape in mature RSV particles.},
author = {Obr, Martin and Ricana, Clifton L. and Nikulin, Nadia and Feathers, Jon-Philip R. and Klanschnig, Marco and Thader, Andreas and Johnson, Marc C. and Vogt, Volker M. and Schur, Florian KM and Dick, Robert A.},
issn = {2041-1723},
journal = {Nature Communications},
keywords = {General Biochemistry, Genetics and Molecular Biology, General Physics and Astronomy, General Chemistry},
number = {1},
publisher = {Nature Research},
title = {{Structure of the mature Rous sarcoma virus lattice reveals a role for IP6 in the formation of the capsid hexamer}},
doi = {10.1038/s41467-021-23506-0},
volume = {12},
year = {2021},
}
@article{9540,
abstract = {The hexameric AAA-ATPase Drg1 is a key factor in eukaryotic ribosome biogenesis and initiates cytoplasmic maturation of the large ribosomal subunit by releasing the shuttling maturation factor Rlp24. Drg1 monomers contain two AAA-domains (D1 and D2) that act in a concerted manner. Rlp24 release is inhibited by the drug diazaborine which blocks ATP hydrolysis in D2. The mode of inhibition was unknown. Here we show the first cryo-EM structure of Drg1 revealing the inhibitory mechanism. Diazaborine forms a covalent bond to the 2′-OH of the nucleotide in D2, explaining its specificity for this site. As a consequence, the D2 domain is locked in a rigid, inactive state, stalling the whole Drg1 hexamer. Resistance mechanisms identified include abolished drug binding and altered positioning of the nucleotide. Our results suggest nucleotide-modifying compounds as potential novel inhibitors for AAA-ATPases.},
author = {Prattes, Michael and Grishkovskaya, Irina and Hodirnau, Victor-Valentin and Rössler, Ingrid and Klein, Isabella and Hetzmannseder, Christina and Zisser, Gertrude and Gruber, Christian C. and Gruber, Karl and Haselbach, David and Bergler, Helmut},
issn = {2041-1723},
journal = {Nature Communications},
keywords = {General Biochemistry, Genetics and Molecular Biology, General Physics and Astronomy, General Chemistry},
number = {1},
publisher = {Springer Nature},
title = {{Structural basis for inhibition of the AAA-ATPase Drg1 by diazaborine}},
doi = {10.1038/s41467-021-23854-x},
volume = {12},
year = {2021},
}
@article{9407,
abstract = {High impact epidemics constitute one of the largest threats humanity is facing in the 21st century. In the absence of pharmaceutical interventions, physical distancing together with testing, contact tracing and quarantining are crucial in slowing down epidemic dynamics. Yet, here we show that if testing capacities are limited, containment may fail dramatically because such combined countermeasures drastically change the rules of the epidemic transition: Instead of continuous, the response to countermeasures becomes discontinuous. Rather than following the conventional exponential growth, the outbreak that is initially strongly suppressed eventually accelerates and scales faster than exponential during an explosive growth period. As a consequence, containment measures either suffice to stop the outbreak at low total case numbers or fail catastrophically if marginally too weak, thus implying large uncertainties in reliably estimating overall epidemic dynamics, both during initial phases and during second wave scenarios.},
author = {Scarselli, Davide and Budanur, Nazmi B and Timme, Marc and Hof, Björn},
issn = {20411723},
journal = {Nature Communications},
number = {1},
publisher = {Springer Nature},
title = {{Discontinuous epidemic transition due to limited testing}},
doi = {10.1038/s41467-021-22725-9},
volume = {12},
year = {2021},
}
@article{9428,
abstract = {Thermalization is the inevitable fate of many complex quantum systems, whose dynamics allow them to fully explore the vast configuration space regardless of the initial state---the behaviour known as quantum ergodicity. In a quest for experimental realizations of coherent long-time dynamics, efforts have focused on ergodicity-breaking mechanisms, such as integrability and localization. The recent discovery of persistent revivals in quantum simulators based on Rydberg atoms have pointed to the existence of a new type of behaviour where the system rapidly relaxes for most initial conditions, while certain initial states give rise to non-ergodic dynamics. This collective effect has been named ”quantum many-body scarring’by analogy with a related form of weak ergodicity breaking that occurs for a single particle inside a stadium billiard potential. In this Review, we provide a pedagogical introduction to quantum many-body scars and highlight the emerging connections with the semiclassical quantization of many-body systems. We discuss the relation between scars and more general routes towards weak violations of ergodicity due to embedded algebras and non-thermal eigenstates, and highlight possible applications of scars in quantum technology.},
author = {Serbyn, Maksym and Abanin, Dmitry A. and Papić, Zlatko},
issn = {1745-2481},
journal = {Nature Physics},
number = {6},
pages = {675–685},
title = {{Quantum many-body scars and weak breaking of ergodicity}},
doi = {10.1038/s41567-021-01230-2},
volume = {17},
year = {2021},
}
@article{9462,
abstract = {We consider a system of N trapped bosons with repulsive interactions in a combined semiclassical mean-field limit at positive temperature. We show that the free energy is well approximated by the minimum of the Hartree free energy functional – a natural extension of the Hartree energy functional to positive temperatures. The Hartree free energy functional converges in the same limit to a semiclassical free energy functional, and we show that the system displays Bose–Einstein condensation if and only if it occurs in the semiclassical free energy functional. This allows us to show that for weak coupling the critical temperature decreases due to the repulsive interactions.},
author = {Deuchert, Andreas and Seiringer, Robert},
issn = {10960783},
journal = {Journal of Functional Analysis},
number = {6},
publisher = {Elsevier},
title = {{Semiclassical approximation and critical temperature shift for weakly interacting trapped bosons}},
doi = {10.1016/j.jfa.2021.109096},
volume = {281},
year = {2021},
}
@article{9547,
abstract = {With the wider availability of full-color 3D printers, color-accurate 3D-print preparation has received increased attention. A key challenge lies in the inherent translucency of commonly used print materials that blurs out details of the color texture. Previous work tries to compensate for these scattering effects through strategic assignment of colored primary materials to printer voxels. To date, the highest-quality approach uses iterative optimization that relies on computationally expensive Monte Carlo light transport simulation to predict the surface appearance from subsurface scattering within a given print material distribution; that optimization, however, takes in the order of days on a single machine. In our work, we dramatically speed up the process by replacing the light transport simulation with a data-driven approach. Leveraging a deep neural network to predict the scattering within a highly heterogeneous medium, our method performs around two orders of magnitude faster than Monte Carlo rendering while yielding optimization results of similar quality level. The network is based on an established method from atmospheric cloud rendering, adapted to our domain and extended by a physically motivated weight sharing scheme that substantially reduces the network size. We analyze its performance in an end-to-end print preparation pipeline and compare quality and runtime to alternative approaches, and demonstrate its generalization to unseen geometry and material values. This for the first time enables full heterogenous material optimization for 3D-print preparation within time frames in the order of the actual printing time.},
author = {Rittig, Tobias and Sumin, Denis and Babaei, Vahid and Didyk, Piotr and Voloboy, Alexey and Wilkie, Alexander and Bickel, Bernd and Myszkowski, Karol and Weyrich, Tim and Křivánek, Jaroslav},
issn = {14678659},
journal = {Computer Graphics Forum},
number = {2},
pages = {205--219},
publisher = {Wiley},
title = {{Neural acceleration of scattering-aware color 3D printing}},
doi = {10.1111/cgf.142626},
volume = {40},
year = {2021},
}
@article{9541,
abstract = {The Massively Parallel Computation (MPC) model is an emerging model that distills core aspects of distributed and parallel computation, developed as a tool to solve combinatorial (typically graph) problems in systems of many machines with limited space. Recent work has focused on the regime in which machines have sublinear (in n, the number of nodes in the input graph) space, with randomized algorithms presented for the fundamental problems of Maximal Matching and Maximal Independent Set. However, there have been no prior corresponding deterministic algorithms. A major challenge underlying the sublinear space setting is that the local space of each machine might be too small to store all edges incident to a single node. This poses a considerable obstacle compared to classical models in which each node is assumed to know and have easy access to its incident edges. To overcome this barrier, we introduce a new graph sparsification technique that deterministically computes a low-degree subgraph, with the additional property that solving the problem on this subgraph provides significant progress towards solving the problem for the original input graph. Using this framework to derandomize the well-known algorithm of Luby [SICOMP’86], we obtain O(log Δ + log log n)-round deterministic MPC algorithms for solving the problems of Maximal Matching and Maximal Independent Set with O(nɛ) space on each machine for any constant ɛ > 0. These algorithms also run in O(log Δ) rounds in the closely related model of CONGESTED CLIQUE, improving upon the state-of-the-art bound of O(log 2Δ) rounds by Censor-Hillel et al. [DISC’17].},
author = {Czumaj, Artur and Davies, Peter and Parter, Merav},
issn = {1549-6333},
journal = {ACM Transactions on Algorithms},
number = {2},
publisher = {ACM},
title = {{Graph sparsification for derandomizing massively parallel computation with low space}},
doi = {10.1145/3451992},
volume = {17},
year = {2021},
}
@article{9558,
abstract = {We show that turbulent dynamics that arise in simulations of the three-dimensional Navier--Stokes equations in a triply-periodic domain under sinusoidal forcing can be described as transient visits to the neighborhoods of unstable time-periodic solutions. Based on this description, we reduce the original system with more than 10^5 degrees of freedom to a 17-node Markov chain where each node corresponds to the neighborhood of a periodic orbit. The model accurately reproduces long-term averages of the system's observables as weighted sums over the periodic orbits.
},
author = {Yalniz, Gökhan and Hof, Björn and Budanur, Nazmi B},
issn = {1079-7114},
journal = {Physical Review Letters},
number = {24},
publisher = {American Physical Society},
title = {{Coarse graining the state space of a turbulent flow using periodic orbits}},
doi = {10.1103/PhysRevLett.126.244502},
volume = {126},
year = {2021},
}
@article{9570,
abstract = {We present conductance-matrix measurements in long, three-terminal hybrid superconductor-semiconductor nanowires, and compare with theoretical predictions of a magnetic-field-driven, topological quantum phase transition. By examining the nonlocal conductance, we identify the closure of the excitation gap in the bulk of the semiconductor before the emergence of zero-bias peaks, ruling out spurious gap-closure signatures from localized states. We observe that after the gap closes, nonlocal signals and zero-bias peaks fluctuate strongly at both ends, inconsistent with a simple picture of clean topological superconductivity.},
author = {Puglia, Denise and Martinez, E. A. and Ménard, G. C. and Pöschl, A. and Gronin, S. and Gardner, G. C. and Kallaher, R. and Manfra, M. J. and Marcus, C. M. and Higginbotham, Andrew P and Casparis, L.},
issn = {24699969},
journal = {Physical Review B},
number = {23},
publisher = {American Physical Society},
title = {{Closing of the induced gap in a hybrid superconductor-semiconductor nanowire}},
doi = {10.1103/PhysRevB.103.235201},
volume = {103},
year = {2021},
}
@article{9607,
abstract = {While high risk of failure is an inherent part of developing innovative therapies, it can be reduced by adherence to evidence-based rigorous research practices. Numerous analyses conducted to date have clearly identified measures that need to be taken to improve research rigor. Supported through the European Union's Innovative Medicines Initiative, the EQIPD consortium has developed a novel preclinical research quality system that can be applied in both public and private sectors and is free for anyone to use. The EQIPD Quality System was designed to be suited to boost innovation by ensuring the generation of robust and reliable preclinical data while being lean, effective and not becoming a burden that could negatively impact the freedom to explore scientific questions. EQIPD defines research quality as the extent to which research data are fit for their intended use. Fitness, in this context, is defined by the stakeholders, who are the scientists directly involved in the research, but also their funders, sponsors, publishers, research tool manufacturers and collaboration partners such as peers in a multi-site research project. The essence of the EQIPD Quality System is the set of 18 core requirements that can be addressed flexibly, according to user-specific needs and following a user-defined trajectory. The EQIPD Quality System proposes guidance on expectations for quality-related measures, defines criteria for adequate processes (i.e., performance standards) and provides examples of how such measures can be developed and implemented. However, it does not prescribe any pre-determined solutions. EQIPD has also developed tools (for optional use) to support users in implementing the system and assessment services for those research units that successfully implement the quality system and seek formal accreditation. Building upon the feedback from users and continuous improvement, a sustainable EQIPD Quality System will ultimately serve the entire community of scientists conducting non-regulated preclinical research, by helping them generate reliable data that are fit for their intended use.},
author = {Bespalov, Anton and Bernard, René and Gilis, Anja and Gerlach, Björn and Guillén, Javier and Castagné, Vincent and Lefevre, Isabel A. and Ducrey, Fiona and Monk, Lee and Bongiovanni, Sandrine and Altevogt, Bruce and Arroyo-Araujo, María and Bikovski, Lior and De Bruin, Natasja and Castaños-Vélez, Esmeralda and Dityatev, Alexander and Emmerich, Christoph H. and Fares, Raafat and Ferland-Beckham, Chantelle and Froger-Colléaux, Christelle and Gailus-Durner, Valerie and Hölter, Sabine M. and Hofmann, Martine Cj and Kabitzke, Patricia and Kas, Martien Jh and Kurreck, Claudia and Moser, Paul and Pietraszek, Malgorzata and Popik, Piotr and Potschka, Heidrun and Prado Montes De Oca, Ernesto and Restivo, Leonardo and Riedel, Gernot and Ritskes-Hoitinga, Merel and Samardzic, Janko and Schunn, Michael and Stöger, Claudia and Voikar, Vootele and Vollert, Jan and Wever, Kimberley E. and Wuyts, Kathleen and Macleod, Malcolm R. and Dirnagl, Ulrich and Steckler, Thomas},
issn = {2050084X},
journal = {eLife},
publisher = {eLife Sciences Publications},
title = {{Introduction to the EQIPD quality system}},
doi = {10.7554/eLife.63294},
volume = {10},
year = {2021},
}
@article{9569,
abstract = {We report the synthesis and characterization of graphene functionalized with iron (Fe3+) oxide (G-Fe3O4) nanohybrids for radio-frequency magnetic hyperthermia application. We adopted the wet chemical procedure, using various contents of Fe3O4 (magnetite) from 0–100% for making two-dimensional graphene–Fe3O4 nanohybrids. The homogeneous dispersal of Fe3O4 nanoparticles decorated on the graphene surface combined with their biocompatibility and high thermal conductivity make them an excellent material for magnetic hyperthermia. The morphological and magnetic properties of the nanohybrids were studied using scanning electron microscopy (SEM) and a vibrating sample magnetometer (VSM), respectively. The smart magnetic platforms were exposed to an alternating current (AC) magnetic field of 633 kHz and of strength 9.1 mT for studying their hyperthermic performance. The localized antitumor effects were investigated with artificial neural network modeling. A neural net time-series model was developed for the assessment of the best nanohybrid composition to serve the purpose with an accuracy close to 100%. Six Nonlinear Autoregressive with External Input (NARX) models were obtained, one for each of the components. The assessment of the accuracy of the predicted results has been done on the basis of Mean Squared Error (MSE). The highest Mean Squared Error value was obtained for the nanohybrid containing 45% magnetite and 55% graphene (F45G55) in the training phase i.e., 0.44703, which is where the model achieved optimal results after 71 epochs. The F45G55 nanohybrid was found to be the best for hyperthermia applications in low dosage with the highest specific absorption rate (SAR) and mean squared error values.},
author = {Dar, M. S. and Akram, Khush Bakhat and Sohail, Ayesha and Arif, Fatima and Zabihi, Fatemeh and Yang, Shengyuan and Munir, Shamsa and Zhu, Meifang and Abid, M. and Nauman, Muhammad},
issn = {2046-2069},
journal = {RSC Advances},
number = {35},
pages = {21702--21715},
publisher = {Royal Society of Chemistry},
title = {{Heat induction in two-dimensional graphene–Fe3O4 nanohybrids for magnetic hyperthermia applications with artificial neural network modeling}},
doi = {10.1039/d1ra03428f},
volume = {11},
year = {2021},
}
@article{9606,
abstract = {Sound propagation is a macroscopic manifestation of the interplay between the equilibrium thermodynamics and the dynamical transport properties of fluids. Here, for a two-dimensional system of ultracold fermions, we calculate the first and second sound velocities across the whole BCS-BEC crossover, and we analyze the system response to an external perturbation. In the low-temperature regime we reproduce the recent measurements [Phys. Rev. Lett. 124, 240403 (2020)] of the first sound velocity, which, due to the decoupling of density and entropy fluctuations, is the sole mode excited by a density probe. Conversely, a heat perturbation excites only the second sound, which, being sensitive to the superfluid depletion, vanishes in the deep BCS regime and jumps discontinuously to zero at the Berezinskii-Kosterlitz-Thouless superfluid transition. A mixing between the modes occurs only in the finite-temperature BEC regime, where our theory converges to the purely bosonic results.},
author = {Tononi, A. and Cappellaro, Alberto and Bighin, Giacomo and Salasnich, L.},
issn = {24699934},
journal = {Physical Review A},
number = {6},
publisher = {American Physical Society},
title = {{Propagation of first and second sound in a two-dimensional Fermi superfluid}},
doi = {10.1103/PhysRevA.103.L061303},
volume = {103},
year = {2021},
}
@article{9603,
abstract = {Mosaic analysis with double markers (MADM) offers one approach to visualize and concomitantly manipulate genetically defined cells in mice with single-cell resolution. MADM applications include the analysis of lineage, single-cell morphology and physiology, genomic imprinting phenotypes, and dissection of cell-autonomous gene functions in vivo in health and disease. Yet, MADM can only be applied to <25% of all mouse genes on select chromosomes to date. To overcome this limitation, we generate transgenic mice with knocked-in MADM cassettes near the centromeres of all 19 autosomes and validate their use across organs. With this resource, >96% of the entire mouse genome can now be subjected to single-cell genetic mosaic analysis. Beyond a proof of principle, we apply our MADM library to systematically trace sister chromatid segregation in distinct mitotic cell lineages. We find striking chromosome-specific biases in segregation patterns, reflecting a putative mechanism for the asymmetric segregation of genetic determinants in somatic stem cell division.},
author = {Contreras, Ximena and Amberg, Nicole and Davaatseren, Amarbayasgalan and Hansen, Andi H and Sonntag, Johanna and Andersen, Lill and Bernthaler, Tina and Streicher, Carmen and Heger, Anna-Magdalena and Johnson, Randy L. and Schwarz, Lindsay A. and Luo, Liqun and Rülicke, Thomas and Hippenmeyer, Simon},
issn = {22111247},
journal = {Cell Reports},
number = {12},
publisher = {Cell Press},
title = {{A genome-wide library of MADM mice for single-cell genetic mosaic analysis}},
doi = {10.1016/j.celrep.2021.109274},
volume = {35},
year = {2021},
}
@article{9601,
abstract = {In mammalian genomes, differentially methylated regions (DMRs) and histone marks including trimethylation of histone 3 lysine 27 (H3K27me3) at imprinted genes are asymmetrically inherited to control parentally-biased gene expression. However, neither parent-of-origin-specific transcription nor imprints have been comprehensively mapped at the blastocyst stage of preimplantation development. Here, we address this by integrating transcriptomic and epigenomic approaches in mouse preimplantation embryos. We find that seventy-one genes exhibit previously unreported parent-of-origin-specific expression in blastocysts (nBiX: novel blastocyst-imprinted expressed). Uniparental expression of nBiX genes disappears soon after implantation. Micro-whole-genome bisulfite sequencing (µWGBS) of individual uniparental blastocysts detects 859 DMRs. We further find that 16% of nBiX genes are associated with a DMR, whereas most are associated with parentally-biased H3K27me3, suggesting a role for Polycomb-mediated imprinting in blastocysts. nBiX genes are clustered: five clusters contained at least one published imprinted gene, and five clusters exclusively contained nBiX genes. These data suggest that early development undergoes a complex program of stage-specific imprinting involving different tiers of regulation.},
author = {Santini, Laura and Halbritter, Florian and Titz-Teixeira, Fabian and Suzuki, Toru and Asami, Maki and Ma, Xiaoyan and Ramesmayer, Julia and Lackner, Andreas and Warr, Nick and Pauler, Florian and Hippenmeyer, Simon and Laue, Ernest and Farlik, Matthias and Bock, Christoph and Beyer, Andreas and Perry, Anthony C.F. and Leeb, Martin},
issn = {20411723},
journal = {Nature Communications},
number = {1},
publisher = {Springer Nature},
title = {{Genomic imprinting in mouse blastocysts is predominantly associated with H3K27me3}},
doi = {10.1038/s41467-021-23510-4},
volume = {12},
year = {2021},
}
@article{9602,
abstract = {An ordered graph is a graph with a linear ordering on its vertex set. We prove that for every positive integer k, there exists a constant ck > 0 such that any ordered graph G on n vertices with the property that neither G nor its complement contains an induced monotone path of size k, has either a clique or an independent set of size at least n^ck . This strengthens a result of Bousquet, Lagoutte, and Thomassé, who proved the analogous result for unordered graphs.
A key idea of the above paper was to show that any unordered graph on n vertices that does not contain an induced path of size k, and whose maximum degree is at most c(k)n for some small c(k) > 0, contains two disjoint linear size subsets with no edge between them. This approach fails for ordered graphs, because the analogous statement is false for k ≥ 3, by a construction of Fox. We provide some further examples showing that this statement also fails for ordered graphs avoiding other ordered trees.},
author = {Pach, János and Tomon, István},
issn = {00958956},
journal = {Journal of Combinatorial Theory. Series B},
pages = {21--37},
publisher = {Elsevier},
title = {{Erdős-Hajnal-type results for monotone paths}},
doi = {10.1016/j.jctb.2021.05.004},
volume = {151},
year = {2021},
}
@inproceedings{9604,
abstract = {Generalizing Lee’s inductive argument for counting the cells of higher order Voronoi tessellations in ℝ² to ℝ³, we get precise relations in terms of Morse theoretic quantities for piecewise constant functions on planar arrangements. Specifically, we prove that for a generic set of n ≥ 5 points in ℝ³, the number of regions in the order-k Voronoi tessellation is N_{k-1} - binom(k,2)n + n, for 1 ≤ k ≤ n-1, in which N_{k-1} is the sum of Euler characteristics of these function’s first k-1 sublevel sets. We get similar expressions for the vertices, edges, and polygons of the order-k Voronoi tessellation.},
author = {Biswas, Ranita and Cultrera di Montesano, Sebastiano and Edelsbrunner, Herbert and Saghafian, Morteza},
booktitle = {Leibniz International Proceedings in Informatics},
isbn = {9783959771849},
issn = {18688969},
location = {Online},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Counting cells of order-k voronoi tessellations in ℝ^{3} with morse theory}},
doi = {10.4230/LIPIcs.SoCG.2021.16},
volume = {189},
year = {2021},
}
@article{8909,
abstract = {Spin qubits are considered to be among the most promising candidates for building a quantum processor. Group IV hole spin qubits have moved into the focus of interest due to the ease of operation and compatibility with Si technology. In addition, Ge offers the option for monolithic superconductor-semiconductor integration. Here we demonstrate a hole spin qubit operating at fields below 10 mT, the critical field of Al, by exploiting the large out-of-plane hole g-factors in planar Ge and by encoding the qubit into the singlet-triplet states of a double quantum dot. We observe electrically controlled X and Z-rotations with tunable frequencies exceeding 100 MHz and dephasing times of 1μs which we extend beyond 15μs with echo techniques. These results show that Ge hole singlet triplet qubits outperform their electronic Si and GaAs based counterparts in speed and coherence, respectively. In addition, they are on par with Ge single spin qubits, but can be operated at much lower fields underlining their potential for on chip integration with superconducting technologies.},
author = {Jirovec, Daniel and Hofmann, Andrea C and Ballabio, Andrea and Mutter, Philipp M. and Tavani, Giulio and Botifoll, Marc and Crippa, Alessandro and Kukucka, Josip and Sagi, Oliver and Martins, Frederico and Saez Mollejo, Jaime and Prieto Gonzalez, Ivan and Borovkov, Maksim and Arbiol, Jordi and Chrastina, Daniel and Isella, Giovanni and Katsaros, Georgios},
issn = {1476-4660},
journal = {Nature Materials},
publisher = {Springer Nature},
title = {{A singlet triplet hole spin qubit in planar Ge}},
doi = {10.1038/s41563-021-01022-2},
year = {2021},
}
@misc{9323,
abstract = {This .zip File contains the data for figures presented in the main text and supplementary material of "A singlet triplet hole spin qubit in planar Ge" by D. Jirovec, et. al. The measurements were done using Labber Software and the data is stored in the hdf5 file format. The files can be opened using either the Labber Log Browser (https://labber.org/overview/) or Labber Python API (http://labber.org/online-doc/api/LogFile.html). A single file is acquired with QCodes and features the corresponding data type. XRD data are in .dat format and a code to open the data is provided. The code for simulations is as well provided in Python.},
author = {Jirovec, Daniel},
publisher = {IST Austria},
title = {{Research data for "A singlet-triplet hole spin qubit planar Ge"}},
doi = {10.15479/AT:ISTA:9323},
year = {2021},
}
@inproceedings{9356,
abstract = {In runtime verification, a monitor watches a trace of a system and, if possible, decides after observing each finite prefix whether or not the unknown infinite trace satisfies a given specification. We generalize the theory of runtime verification to monitors that attempt to estimate numerical values of quantitative trace properties (instead of attempting to conclude boolean values of trace specifications), such as maximal or average response time along a trace. Quantitative monitors are approximate: with every finite prefix, they can improve their estimate of the infinite trace's unknown property value. Consequently, quantitative monitors can be compared with regard to a precision-cost trade-off: better approximations of the property value require more monitor resources, such as states (in the case of finite-state monitors) or registers, and additional resources yield better approximations. We introduce a formal framework for quantitative and approximate monitoring, show how it conservatively generalizes the classical boolean setting for monitoring, and give several precision-cost trade-offs for monitors. For example, we prove that there are quantitative properties for which every additional register improves monitoring precision.},
author = {Henzinger, Thomas A and Sarac, Naci E},
booktitle = {Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science},
location = {Online},
publisher = {Association for Computing Machinery},
title = {{Quantitative and approximate monitoring}},
year = {2021},
}
@inproceedings{9592,
abstract = {The convex grabbing game is a game where two players, Alice and Bob, alternate taking extremal points from the convex hull of a point set on the plane. Rational weights are given to the points. The goal of each player is to maximize the total weight over all points that they obtain. We restrict the setting to the case of binary weights. We show a construction of an arbitrarily large odd-sized point set that allows Bob to obtain almost 3/4 of the total weight. This construction answers a question asked by Matsumoto, Nakamigawa, and Sakuma in [Graphs and Combinatorics, 36/1 (2020)]. We also present an arbitrarily large even-sized point set where Bob can obtain the entirety of the total weight. Finally, we discuss conjectures about optimum moves in the convex grabbing game for both players in general.},
author = {Dvorak, Martin and Nicholson, Sara},
booktitle = {Proceedings of the 33rd Canadian Conference on Computational Geometry},
keywords = {convex grabbing game, graph grabbing game, combinatorial game, convex geometry},
location = {Online},
title = {{Massively winning configurations in the convex grabbing game on the plane}},
year = {2021},
}
@article{8198,
abstract = {We investigate how the critical driving amplitude at the Floquet many-body localized (MBL) to ergodic phase transition differs between smooth and nonsmooth drives. To this end, we numerically study a disordered spin-1/2 chain which is periodically driven by a sine or square-wave drive over a wide range of driving frequencies. In both cases the critical driving amplitude increases monotonically with the frequency, and at large frequencies it is identical for the two drives. However, at low and intermediate frequencies the critical amplitude of the square-wave drive depends strongly on the frequency, while that of the sinusoidal drive is almost constant over a wide frequency range. By analyzing the density of drive-induced resonances we conclude that this difference is due to resonances induced by the higher harmonics which are present (absent) in the Fourier spectrum of the square-wave (sine) drive. Furthermore, we suggest a numerically efficient method for estimating the frequency dependence of the critical driving amplitudes for different drives which is based on calculating the density of drive-induced resonances. We conclude that delocalization occurs once the density of drive-induced resonances reaches a critical value determined only by the static system.},
author = {Diringer, Asaf A. and Gulden, Tobias},
issn = {24699969},
journal = {Physical Review B},
number = {21},
publisher = {American Physical Society},
title = {{Impact of drive harmonics on the stability of Floquet many-body localization}},
doi = {10.1103/PhysRevB.103.214204},
volume = {103},
year = {2021},
}
@article{8317,
abstract = {When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present sufficient conditions for a polyomino with one or several holes to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special “basic” holes guarantee foldability.},
author = {Aichholzer, Oswin and Akitaya, Hugo A. and Cheung, Kenneth C. and Demaine, Erik D. and Demaine, Martin L. and Fekete, Sándor P. and Kleist, Linda and Kostitsyna, Irina and Löffler, Maarten and Masárová, Zuzana and Mundilova, Klara and Schmidt, Christiane},
issn = {09257721},
journal = {Computational Geometry: Theory and Applications},
publisher = {Elsevier},
title = {{Folding polyominoes with holes into a cube}},
doi = {10.1016/j.comgeo.2020.101700},
volume = {93},
year = {2021},
}
@article{7463,
abstract = {Resting-state brain activity is characterized by the presence of neuronal avalanches showing absence of characteristic size. Such evidence has been interpreted in the context of criticality and associated with the normal functioning of the brain. A distinctive attribute of systems at criticality is the presence of long-range correlations. Thus, to verify the hypothesis that the brain operates close to a critical point and consequently assess deviations from criticality for diagnostic purposes, it is of primary importance to robustly and reliably characterize correlations in resting-state brain activity. Recent works focused on the analysis of narrow-band electroencephalography (EEG) and magnetoencephalography (MEG) signal amplitude envelope, showing evidence of long-range temporal correlations (LRTC) in neural oscillations. However, brain activity is a broadband phenomenon, and a significant piece of information useful to precisely discriminate between normal (critical) and pathological behavior (non-critical), may be encoded in the broadband spatio-temporal cortical dynamics. Here we propose to characterize the temporal correlations in the broadband brain activity through the lens of neuronal avalanches. To this end, we consider resting-state EEG and long-term MEG recordings, extract the corresponding neuronal avalanche sequences, and study their temporal correlations. We demonstrate that the broadband resting-state brain activity consistently exhibits long-range power-law correlations in both EEG and MEG recordings, with similar values of the scaling exponents. Importantly, although we observe that the avalanche size distribution depends on scale parameters, scaling exponents characterizing long-range correlations are quite robust. In particular, they are independent of the temporal binning (scale of analysis), indicating that our analysis captures intrinsic characteristics of the underlying dynamics. Because neuronal avalanches constitute a fundamental feature of neural systems with universal characteristics, the proposed approach may serve as a general, systems- and experiment-independent procedure to infer the existence of underlying long-range correlations in extended neural systems, and identify pathological behaviors in the complex spatio-temporal interplay of cortical rhythms.},
author = {Lombardi, Fabrizio and Shriki, Oren and Herrmann, Hans J and de Arcangelis, Lucilla},
issn = {18728286},
journal = {Neurocomputing},
publisher = {Elsevier},
title = {{Long-range temporal correlations in the broadband resting state activity of the human brain revealed by neuronal avalanches}},
doi = {10.1016/j.neucom.2020.05.126},
year = {2021},
}
@inproceedings{9605,
abstract = {Given a finite set A ⊂ ℝ^d, let Cov_{r,k} denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called the multicover bifiltration. Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a Čech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors as well. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness. },
author = {Corbet, René and Kerber, Michael and Lesnick, Michael and Osang, Georg F},
booktitle = {Leibniz International Proceedings in Informatics},
isbn = {9783959771849},
issn = {18688969},
location = {Online},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Computing the multicover bifiltration}},
doi = {10.4230/LIPIcs.SoCG.2021.27},
volume = {189},
year = {2021},
}
@article{9618,
abstract = {The control of nonequilibrium quantum dynamics in many-body systems is challenging because interactions typically lead to thermalization and a chaotic spreading throughout Hilbert space. We investigate nonequilibrium dynamics after rapid quenches in a many-body system composed of 3 to 200 strongly interacting qubits in one and two spatial dimensions. Using a programmable quantum simulator based on Rydberg atom arrays, we show that coherent revivals associated with so-called quantum many-body scars can be stabilized by periodic driving, which generates a robust subharmonic response akin to discrete time-crystalline order. We map Hilbert space dynamics, geometry dependence, phase diagrams, and system-size dependence of this emergent phenomenon, demonstrating new ways to steer complex dynamics in many-body systems and enabling potential applications in quantum information science.},
author = {Bluvstein, D. and Omran, A. and Levine, H. and Keesling, A. and Semeghini, G. and Ebadi, S. and Wang, T. T. and Michailidis, Alexios and Maskara, N. and Ho, W. W. and Choi, S. and Serbyn, Maksym and Greiner, M. and Vuletić, V. and Lukin, M. D.},
issn = {1095-9203},
journal = {Science},
keywords = {Multidisciplinary},
number = {6536},
pages = {1355--1359},
publisher = {AAAS},
title = {{Controlling quantum many-body dynamics in driven Rydberg atom arrays}},
doi = {10.1126/science.abg2530},
volume = {371},
year = {2021},
}
@article{9571,
abstract = {As the size and complexity of models and datasets grow, so does the need for communication-efficient variants of stochastic gradient descent that can be deployed to perform parallel model training. One popular communication-compression method for data-parallel SGD is QSGD (Alistarh et al., 2017), which quantizes and encodes gradients to reduce communication costs. The baseline variant of QSGD provides strong theoretical guarantees, however, for practical purposes, the authors proposed a heuristic variant which we call QSGDinf, which demonstrated impressive empirical gains for distributed training of large neural networks. In this paper, we build on this work to propose a new gradient quantization scheme, and show that it has both stronger theoretical guarantees than QSGD, and matches and exceeds the empirical performance of the QSGDinf heuristic and of other compression methods.},
author = {Ramezani-Kebrya, Ali and Faghri, Fartash and Markov, Ilya and Aksenov, Vitalii and Alistarh, Dan-Adrian and Roy, Daniel M.},
issn = {15337928},
journal = {Journal of Machine Learning Research},
number = {114},
pages = {1−43},
publisher = {Journal of Machine Learning Research},
title = {{NUQSGD: Provably communication-efficient data-parallel SGD via nonuniform quantization}},
volume = {22},
year = {2021},
}
@article{9642,
abstract = {Perineuronal nets (PNNs), components of the extracellular matrix, preferentially coat parvalbumin-positive interneurons and constrain critical-period plasticity in the adult cerebral cortex. Current strategies to remove PNN are long-lasting, invasive, and trigger neuropsychiatric symptoms. Here, we apply repeated anesthetic ketamine as a method with minimal behavioral effect. We find that this paradigm strongly reduces PNN coating in the healthy adult brain and promotes juvenile-like plasticity. Microglia are critically involved in PNN loss because they engage with parvalbumin-positive neurons in their defined cortical layer. We identify external 60-Hz light-flickering entrainment to recapitulate microglia-mediated PNN removal. Importantly, 40-Hz frequency, which is known to remove amyloid plaques, does not induce PNN loss, suggesting microglia might functionally tune to distinct brain frequencies. Thus, our 60-Hz light-entrainment strategy provides an alternative form of PNN intervention in the healthy adult brain.},
author = {Venturino, Alessandro and Schulz, Rouven and De Jesús-Cortés, Héctor and Maes, Margaret E and Nagy, Balint and Reilly-Andújar, Francis and Colombo, Gloria and Cubero, Ryan J and Schoot Uiterkamp, Florianne E and Bear, Mark F. and Siegert, Sandra},
issn = {22111247},
journal = {Cell Reports},
number = {1},
publisher = {Elsevier},
title = {{Microglia enable mature perineuronal nets disassembly upon anesthetic ketamine exposure or 60-Hz light entrainment in the healthy brain}},
doi = {10.1016/j.celrep.2021.109313},
volume = {36},
year = {2021},
}
@article{9641,
abstract = {At the encounter with a novel environment, contextual memory formation is greatly enhanced, accompanied with increased arousal and active exploration. Although this phenomenon has been widely observed in animal and human daily life, how the novelty in the environment is detected and contributes to contextual memory formation has lately started to be unveiled. The hippocampus has been studied for many decades for its largely known roles in encoding spatial memory, and a growing body of evidence indicates a differential involvement of dorsal and ventral hippocampal divisions in novelty detection. In this brief review article, we discuss the recent findings of the role of mossy cells in the ventral hippocampal moiety in novelty detection and put them in perspective with other novelty-related pathways in the hippocampus. We propose a mechanism for novelty-driven memory acquisition in the dentate gyrus by the direct projection of ventral mossy cells to dorsal dentate granule cells. By this projection, the ventral hippocampus sends novelty signals to the dorsal hippocampus, opening a gate for memory encoding in dentate granule cells based on information coming from the entorhinal cortex. We conclude that, contrary to the presently accepted functional independence, the dorsal and ventral hippocampi cooperate to link the novelty and contextual information, and this dorso-ventral interaction is crucial for the novelty-dependent memory formation.},
author = {Fredes, Felipe and Shigemoto, Ryuichi},
issn = {10959564},
journal = {Neurobiology of Learning and Memory},
publisher = {Elsevier},
title = {{The role of hippocampal mossy cells in novelty detection}},
doi = {10.1016/j.nlm.2021.107486},
volume = {183},
year = {2021},
}
@article{9679,
abstract = {The relative motion of three impenetrable particles on a ring, in our case two identical fermions and one impurity, is isomorphic to a triangular quantum billiard. Depending on the ratio κ of the impurity and fermion masses, the billiards can be integrable or non-integrable (also referred to in the main text as chaotic). To set the stage, we first investigate the energy level distributions of the billiards as a function of 1/κ ∈ [0, 1] and find no evidence of integrable cases beyond the limiting values 1/κ = 1 and 1/κ = 0. Then, we use machine learning tools to analyze properties of probability distributions of individual quantum states. We find that convolutional neural networks can correctly classify integrable and non-integrable states. The decisive features of the wave functions are the normalization and a large number of zero elements, corresponding to the existence of a nodal line. The network achieves typical accuracies of 97%, suggesting that machine learning tools can be used to analyze and classify the morphology of probability densities obtained in theory or experiment.},
author = {Huber, David and Marchukov, Oleksandr V. and Hammer, Hans Werner and Volosniev, Artem},
issn = {13672630},
journal = {New Journal of Physics},
number = {6},
publisher = {IOP Publishing},
title = {{Morphology of three-body quantum states from machine learning}},
doi = {10.1088/1367-2630/ac0576},
volume = {23},
year = {2021},
}
@article{9657,
abstract = {To overcome nitrogen deficiency, legume roots establish symbiotic interactions with nitrogen-fixing rhizobia that is fostered in specialized organs (nodules). Similar to other organs, nodule formation is determined by a local maximum of the phytohormone auxin at the primordium site. However, how auxin regulates nodule development remains poorly understood. Here, we found that in soybean, (Glycine max), dynamic auxin transport driven by PIN-FORMED (PIN) transporter GmPIN1 is involved in nodule primordium formation. GmPIN1 was specifically expressed in nodule primordium cells and GmPIN1 was polarly localized in these cells. Two nodulation regulators, (iso)flavonoids trigger expanded distribution of GmPIN1b to root cortical cells, and cytokinin rearranges GmPIN1b polarity. Gmpin1abc triple mutants generated with CRISPR-Cas9 showed impaired establishment of auxin maxima in nodule meristems and aberrant divisions in the nodule primordium cells. Moreover, overexpression of GmPIN1 suppressed nodule primordium initiation. GmPIN9d, an ortholog of Arabidopsis thaliana PIN2, acts together with GmPIN1 later in nodule development to acropetally transport auxin in vascular bundles, fine-tuning the auxin supply for nodule enlargement. Our findings reveal how PIN-dependent auxin transport modulates different aspects of soybean nodule development and suggest that establishment of auxin gradient is a prerequisite for the proper interaction between legumes and rhizobia.},
author = {Gao, Z and Chen, Z and Cui, Y and Ke, M and Xu, H and Xu, Q and Chen, J and Li, Y and Huang, L and Zhao, H and Huang, D and Mai, S and Xu, T and Liu, X and Li, S and Guan, Y and Yang, W and Friml, Jiří and Petrášek, J and Zhang, J and Chen, X},
issn = {1532-298x},
journal = {Plant Cell},
publisher = {American Society of Plant Biologists},
title = {{GmPIN-dependent polar auxin transport is involved in soybean nodule development}},
doi = {10.1093/plcell/koab183},
year = {2021},
}
@article{8910,
abstract = {A semiconducting nanowire fully wrapped by a superconducting shell has been proposed as a platform for obtaining Majorana modes at small magnetic fields. In this study, we demonstrate that the appearance of subgap states in such structures is actually governed by the junction region in tunneling spectroscopy measurements and not the full-shell nanowire itself. Short tunneling regions never show subgap states, whereas longer junctions always do. This can be understood in terms of quantum dots forming in the junction and hosting Andreev levels in the Yu-Shiba-Rusinov regime. The intricate magnetic field dependence of the Andreev levels, through both the Zeeman and Little-Parks effects, may result in robust zero-bias peaks—features that could be easily misinterpreted as originating from Majorana zero modes but are unrelated to topological superconductivity.},
author = {Valentini, Marco and Peñaranda, Fernando and Hofmann, Andrea C and Brauns, Matthias and Hauschild, Robert and Krogstrup, Peter and San-Jose, Pablo and Prada, Elsa and Aguado, Ramón and Katsaros, Georgios},
issn = {10959203},
journal = {Science},
number = {6550},
publisher = {American Association for the Advancement of Science},
title = {{Nontopological zero-bias peaks in full-shell nanowires induced by flux-tunable Andreev states}},
doi = {10.1126/science.abf1513},
volume = {373},
year = {2021},
}
@article{9627,
abstract = {We compute the deficiency spaces of operators of the form 𝐻𝐴⊗̂ 𝐼+𝐼⊗̂ 𝐻𝐵, for symmetric 𝐻𝐴 and self-adjoint 𝐻𝐵. This enables us to construct self-adjoint extensions (if they exist) by means of von Neumann's theory. The structure of the deficiency spaces for this case was asserted already in Ibort et al. [Boundary dynamics driven entanglement, J. Phys. A: Math. Theor. 47(38) (2014) 385301], but only proven under the restriction of 𝐻𝐵 having discrete, non-degenerate spectrum.},
author = {Lenz, Daniel and Weinmann, Timon and Wirth, Melchior},
issn = {14643839},
journal = {Proceedings of the Edinburgh Mathematical Society},
pages = {1--15},
publisher = {Cambridge University Press},
title = {{Self-adjoint extensions of bipartite Hamiltonians}},
doi = {10.1017/S0013091521000080},
year = {2021},
}
@unpublished{9651,
abstract = {We introduce a hierachy of equivalence relations on the set of separated nets of a given Euclidean space, indexed by concave increasing functions ϕ:(0,∞)→(0,∞). Two separated nets are called ϕ-displacement equivalent if, roughly speaking, there is a bijection between them which, for large radii R, displaces points of norm at most R by something of order at most ϕ(R). We show that the spectrum of ϕ-displacement equivalence spans from the established notion of bounded displacement equivalence, which corresponds to bounded ϕ, to the indiscrete equivalence relation, coresponding to ϕ(R)∈Ω(R), in which all separated nets are equivalent. In between the two ends of this spectrum, the notions of ϕ-displacement equivalence are shown to be pairwise distinct with respect to the asymptotic classes of ϕ(R) for R→∞. We further undertake a comparison of our notion of ϕ-displacement equivalence with previously studied relations on separated nets. Particular attention is given to the interaction of the notions of ϕ-displacement equivalence with that of bilipschitz equivalence.},
author = {Dymond, Michael and Kaluza, Vojtech},
booktitle = {arXiv},
title = {{Divergence of separated nets with respect to displacement equivalence}},
year = {2021},
}
@article{9647,
abstract = {Gene expression is regulated by the set of transcription factors (TFs) that bind to the promoter. The ensuing regulating function is often represented as a combinational logic circuit, where output (gene expression) is determined by current input values (promoter bound TFs) only. However, the simultaneous arrival of TFs is a strong assumption, since transcription and translation of genes introduce intrinsic time delays and there is no global synchronisation among the arrival times of different molecular species at their targets. We present an experimentally implementable genetic circuit with two inputs and one output, which in the presence of small delays in input arrival, exhibits qualitatively distinct population-level phenotypes, over timescales that are longer than typical cell doubling times. From a dynamical systems point of view, these phenotypes represent long-lived transients: although they converge to the same value eventually, they do so after a very long time span. The key feature of this toy model genetic circuit is that, despite having only two inputs and one output, it is regulated by twenty-three distinct DNA-TF configurations, two of which are more stable than others (DNA looped states), one promoting and another blocking the expression of the output gene. Small delays in input arrival time result in a majority of cells in the population quickly reaching the stable state associated with the first input, while exiting of this stable state occurs at a slow timescale. In order to mechanistically model the behaviour of this genetic circuit, we used a rule-based modelling language, and implemented a grid-search to find parameter combinations giving rise to long-lived transients. Our analysis shows that in the absence of feedback, there exist path-dependent gene regulatory mechanisms based on the long timescale of transients. The behaviour of this toy model circuit suggests that gene regulatory networks can exploit event timing to create phenotypes, and it opens the possibility that they could use event timing to memorise events, without regulatory feedback. The model reveals the importance of (i) mechanistically modelling the transitions between the different DNA-TF states, and (ii) employing transient analysis thereof.},
author = {Petrov, Tatjana and Igler, Claudia and Sezgin, Ali and Henzinger, Thomas A and Guet, Calin C},
issn = {03043975},
journal = {Theoretical Computer Science},
publisher = {Elsevier},
title = {{Long lived transients in gene regulation}},
doi = {10.1016/j.tcs.2021.05.023},
year = {2021},
}
@inproceedings{9646,
abstract = {We consider the fundamental problem of deriving quantitative bounds on the probability that a given assertion is violated in a probabilistic program. We provide automated algorithms that obtain both lower and upper bounds on the assertion violation probability. The main novelty of our approach is that we prove new and dedicated fixed-point theorems which serve as the theoretical basis of our algorithms and enable us to reason about assertion violation bounds in terms of pre and post fixed-point functions. To synthesize such fixed-points, we devise algorithms that utilize a wide range of mathematical tools, including repulsing ranking supermartingales, Hoeffding's lemma, Minkowski decompositions, Jensen's inequality, and convex optimization. On the theoretical side, we provide (i) the first automated algorithm for lower-bounds on assertion violation probabilities, (ii) the first complete algorithm for upper-bounds of exponential form in affine programs, and (iii) provably and significantly tighter upper-bounds than the previous approaches. On the practical side, we show our algorithms can handle a wide variety of programs from the literature and synthesize bounds that are remarkably tighter than previous results, in some cases by thousands of orders of magnitude.},
author = {Wang, Jinyi and Sun, Yican and Fu, Hongfei and Chatterjee, Krishnendu and Goharshady, Amir Kafshdar},
booktitle = {Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation},
isbn = {9781450383912},
location = {Online},
pages = {1171--1186},
publisher = {Association for Computing Machinery},
title = {{Quantitative analysis of assertion violations in probabilistic programs}},
doi = {10.1145/3453483.3454102},
year = {2021},
}
@inproceedings{9645,
abstract = {We consider the fundamental problem of reachability analysis over imperative programs with real variables. Previous works that tackle reachability are either unable to handle programs consisting of general loops (e.g. symbolic execution), or lack completeness guarantees (e.g. abstract interpretation), or are not automated (e.g. incorrectness logic). In contrast, we propose a novel approach for reachability analysis that can handle general and complex loops, is complete, and can be entirely automated for a wide family of programs. Through the notion of Inductive Reachability Witnesses (IRWs), our approach extends ideas from both invariant generation and termination to reachability analysis.
We first show that our IRW-based approach is sound and complete for reachability analysis of imperative programs. Then, we focus on linear and polynomial programs and develop automated methods for synthesizing linear and polynomial IRWs. In the linear case, we follow the well-known approaches using Farkas' Lemma. Our main contribution is in the polynomial case, where we present a push-button semi-complete algorithm. We achieve this using a novel combination of classical theorems in real algebraic geometry, such as Putinar's Positivstellensatz and Hilbert's Strong Nullstellensatz. Finally, our experimental results show we can prove complex reachability objectives over various benchmarks that were beyond the reach of previous methods.},
author = {Asadi, Ali and Chatterjee, Krishnendu and Fu, Hongfei and Goharshady, Amir Kafshdar and Mahdavi, Mohammad},
booktitle = {Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation},
isbn = {9781450383912},
location = {Online},
pages = {772--787},
publisher = {Association for Computing Machinery},
title = {{Polynomial reachability witnesses via Stellensätze}},
doi = {10.1145/3453483.3454076},
year = {2021},
}
@inproceedings{9644,
abstract = {We present a new approach to proving non-termination of non-deterministic integer programs. Our technique is rather simple but efficient. It relies on a purely syntactic reversal of the program's transition system followed by a constraint-based invariant synthesis with constraints coming from both the original and the reversed transition system. The latter task is performed by a simple call to an off-the-shelf SMT-solver, which allows us to leverage the latest advances in SMT-solving. Moreover, our method offers a combination of features not present (as a whole) in previous approaches: it handles programs with non-determinism, provides relative completeness guarantees and supports programs with polynomial arithmetic. The experiments performed with our prototype tool RevTerm show that our approach, despite its simplicity and stronger theoretical guarantees, is at least on par with the state-of-the-art tools, often achieving a non-trivial improvement under a proper configuration of its parameters.},
author = {Chatterjee, Krishnendu and Goharshady, Ehsan Kafshdar and Novotný, Petr and Zikelic, Dorde},
booktitle = {Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation},
isbn = {9781450383912},
location = {Online},
pages = {1033--1048},
publisher = {Association for Computing Machinery},
title = {{Proving non-termination by program reversal}},
doi = {10.1145/3453483.3454093},
year = {2021},
}
@article{9649,
abstract = {Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. manifolds defined as the zero set of some multivariate vector-valued smooth function f : Rd → Rd−n. A natural (and efficient) way to approximate an isomanifold is to consider its Piecewise-Linear (PL) approximation based on a triangulation T of the ambient space Rd. In this paper, we give conditions under which the PL-approximation of an isomanifold is topologically equivalent to the isomanifold. The conditions are easy to satisfy in the sense that they can always be met by taking a sufficiently
fine triangulation T . This contrasts with previous results on the triangulation of manifolds where, in arbitrary dimensions, delicate perturbations are needed to guarantee topological correctness, which leads to strong limitations in practice. We further give a bound on the Fréchet distance between the original isomanifold and its PL-approximation. Finally we show analogous results for the PL-approximation of an isomanifold with boundary.},
author = {Boissonnat, Jean-Daniel and Wintraecken, Mathijs},
journal = {Foundations of Computational Mathematics },
publisher = {Springer Nature},
title = {{The topological correctness of PL approximations of isomanifolds}},
doi = {10.1007/s10208-021-09520-0},
year = {2021},
}
@inproceedings{9678,
abstract = {We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for stable orientations and more generally for locally optimal semi-matchings. The prior work by Czygrinow et al. (DISC 2012) finds a stable orientation in O(Δ^5) rounds in graphs of maximum degree Δ, while we improve it to O(Δ^4) and also prove a lower bound of Ω(Δ). For the more general problem of locally optimal semi-matchings, the prior upper bound is O(S^5) and our new algorithm runs in O(C · S^4) rounds, which is an improvement for C = o(S); here C and S are the maximum degrees of customers and servers, respectively.},
author = {Brandt, Sebastian and Keller, Barbara and Rybicki, Joel and Suomela, Jukka and Uitto, Jara},
booktitle = {Annual ACM Symposium on Parallelism in Algorithms and Architectures},
isbn = {9781450380706},
location = { Virtual Event, United States},
pages = {129--139},
title = {{Efficient load-balancing through distributed token dropping}},
doi = {10.1145/3409964.3461785},
year = {2021},
}
@inproceedings{9441,
abstract = {Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. submanifolds of ℝ^d defined as the zero set of some multivariate multivalued smooth function f: ℝ^d → ℝ^{d-n}, where n is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold M is to consider its Piecewise-Linear (PL) approximation M̂ based on a triangulation 𝒯 of the ambient space ℝ^d. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary dimensions n and d, and any precision D. Our main result is that, when f (or M) has bounded complexity, the complexity of the algorithm is polynomial in d and δ = 1/D (and unavoidably exponential in n). Since it is known that for δ = Ω (d^{2.5}), M̂ is O(D²)-close and isotopic to M, our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in d. Combining this algorithm with dimensionality reduction techniques, the dependency on d in the size of M̂ can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art. },
author = {Boissonnat, Jean-Daniel and Kachanovich, Siargey and Wintraecken, Mathijs},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
isbn = {978-3-95977-184-9},
issn = {1868-8969},
location = {Virtual},
pages = {17:1--17:16},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations}},
doi = {10.4230/LIPIcs.SoCG.2021.17},
volume = {189},
year = {2021},
}
@inproceedings{9620,
abstract = {In this note, we introduce a distributed twist on the classic coupon collector problem: a set of m collectors wish to each obtain a set of n coupons; for this, they can each sample coupons uniformly at random, but can also meet in pairwise interactions, during which they can exchange coupons. By doing so, they hope to reduce the number of coupons that must be sampled by each collector in order to obtain a full set. This extension is natural when considering real-world manifestations of the coupon collector phenomenon, and has been remarked upon and studied empirically (Hayes and Hannigan 2006, Ahmad et al. 2014, Delmarcelle 2019).
We provide the first theoretical analysis for such a scenario. We find that “coupon collecting with friends” can indeed significantly reduce the number of coupons each collector must sample, and raises interesting connections to the more traditional variants of the problem. While our analysis is in most cases asymptotically tight, there are several open questions raised, regarding finer-grained analysis of both “coupon collecting with friends,” and of a long-studied variant of the original problem in which a collector requires multiple full sets of coupons.},
author = {Alistarh, Dan-Adrian and Davies, Peter},
booktitle = {Structural Information and Communication Complexity},
isbn = {9783030795269},
issn = {1611-3349},
location = {Wrocław, Poland},
pages = {3--12},
publisher = {Springer Nature},
title = {{Collecting coupons is faster with friends}},
doi = {10.1007/978-3-030-79527-6_1},
volume = {12810},
year = {2021},
}
@inproceedings{9200,
abstract = {Formal design of embedded and cyber-physical systems relies on mathematical modeling. In this paper, we consider the model class of hybrid automata whose dynamics are defined by affine differential equations. Given a set of time-series data, we present an algorithmic approach to synthesize a hybrid automaton exhibiting behavior that is close to the data, up to a specified precision, and changes in synchrony with the data. A fundamental problem in our synthesis algorithm is to check membership of a time series in a hybrid automaton. Our solution integrates reachability and optimization techniques for affine dynamical systems to obtain both a sufficient and a necessary condition for membership, combined in a refinement framework. The algorithm processes one time series at a time and hence can be interrupted, provide an intermediate result, and be resumed. We report experimental results demonstrating the applicability of our synthesis approach.},
author = {Garcia Soto, Miriam and Henzinger, Thomas A and Schilling, Christian},
booktitle = {HSCC '21: Proceedings of the 24th International Conference on Hybrid Systems: Computation and Control},
isbn = {9781450383394},
keywords = {hybrid automaton, membership, system identification},
location = {Nashville, TN, United States},
pages = {2102.12734},
publisher = {Association for Computing Machinery},
title = {{Synthesis of hybrid automata with affine dynamics from time-series data}},
doi = {10.1145/3447928.3456704},
year = {2021},
}
@inproceedings{9345,
abstract = {Modeling a crystal as a periodic point set, we present a fingerprint consisting of density functionsthat facilitates the efficient search for new materials and material properties. We prove invarianceunder isometries, continuity, and completeness in the generic case, which are necessary featuresfor the reliable comparison of crystals. The proof of continuity integrates methods from discretegeometry and lattice theory, while the proof of generic completeness combines techniques fromgeometry with analysis. The fingerprint has a fast algorithm based on Brillouin zones and relatedinclusion-exclusion formulae. We have implemented the algorithm and describe its application tocrystal structure prediction.},
author = {Edelsbrunner, Herbert and Heiss, Teresa and Kurlin , Vitaliy and Smith, Philip and Wintraecken, Mathijs},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
issn = {1868-8969},
location = {Virtual},
pages = {32:1--32:16},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{The density fingerprint of a periodic point set}},
doi = {10.4230/LIPIcs.SoCG.2021.32},
volume = {189},
year = {2021},
}
@inproceedings{9296,
abstract = { matching is compatible to two or more labeled point sets of size n with labels {1,…,n} if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of n points there exists a compatible matching with ⌊2n−−√⌋ edges. More generally, for any ℓ labeled point sets we construct compatible matchings of size Ω(n1/ℓ) . As a corresponding upper bound, we use probabilistic arguments to show that for any ℓ given sets of n points there exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1)) edges. Finally, we show that Θ(logn) copies of any set of n points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge.},
author = {Aichholzer, Oswin and Arroyo Guevara, Alan M and Masárová, Zuzana and Parada, Irene and Perz, Daniel and Pilz, Alexander and Tkadlec, Josef and Vogtenhuber, Birgit},
booktitle = {15th International Conference on Algorithms and Computation},
isbn = {9783030682101},
issn = {16113349},
location = {Yangon, Myanmar},
pages = {221--233},
publisher = {Springer Nature},
title = {{On compatible matchings}},
doi = {10.1007/978-3-030-68211-8_18},
volume = {12635},
year = {2021},
}
@article{9640,
abstract = {Selection and random drift determine the probability that novel mutations fixate in a population. Population structure is known to affect the dynamics of the evolutionary process. Amplifiers of selection are population structures that increase the fixation probability of beneficial mutants compared to well-mixed populations. Over the past 15 years, extensive research has produced remarkable structures called strong amplifiers which guarantee that every beneficial mutation fixates with high probability. But strong amplification has come at the cost of considerably delaying the fixation event, which can slow down the overall rate of evolution. However, the precise relationship between fixation probability and time has remained elusive. Here we characterize the slowdown effect of strong amplification. First, we prove that all strong amplifiers must delay the fixation event at least to some extent. Second, we construct strong amplifiers that delay the fixation event only marginally as compared to the well-mixed populations. Our results thus establish a tight relationship between fixation probability and time: Strong amplification always comes at a cost of a slowdown, but more than a marginal slowdown is not needed.},
author = {Tkadlec, Josef and Pavlogiannis, Andreas and Chatterjee, Krishnendu and Nowak, Martin A.},
issn = {20411723},
journal = {Nature Communications},
number = {1},
publisher = {Springer Nature},
title = {{Fast and strong amplifiers of natural selection}},
doi = {10.1038/s41467-021-24271-w},
volume = {12},
year = {2021},
}
@phdthesis{9418,
abstract = {Deep learning is best known for its empirical success across a wide range of applications
spanning computer vision, natural language processing and speech. Of equal significance,
though perhaps less known, are its ramifications for learning theory: deep networks have
been observed to perform surprisingly well in the high-capacity regime, aka the overfitting
or underspecified regime. Classically, this regime on the far right of the bias-variance curve
is associated with poor generalisation; however, recent experiments with deep networks
challenge this view.
This thesis is devoted to investigating various aspects of underspecification in deep learning.
First, we argue that deep learning models are underspecified on two levels: a) any given
training dataset can be fit by many different functions, and b) any given function can be
expressed by many different parameter configurations. We refer to the second kind of
underspecification as parameterisation redundancy and we precisely characterise its extent.
Second, we characterise the implicit criteria (the inductive bias) that guide learning in the
underspecified regime. Specifically, we consider a nonlinear but tractable classification
setting, and show that given the choice, neural networks learn classifiers with a large margin.
Third, we consider learning scenarios where the inductive bias is not by itself sufficient to
deal with underspecification. We then study different ways of ‘tightening the specification’: i)
In the setting of representation learning with variational autoencoders, we propose a hand-
crafted regulariser based on mutual information. ii) In the setting of binary classification, we
consider soft-label (real-valued) supervision. We derive a generalisation bound for linear
networks supervised in this way and verify that soft labels facilitate fast learning. Finally, we
explore an application of soft-label supervision to the training of multi-exit models.},
author = {Bui Thi Mai, Phuong},
pages = {125},
publisher = {IST Austria},
title = {{Underspecification in Deep Learning}},
doi = {10.15479/AT:ISTA:9418},
year = {2021},
}
@inproceedings{9543,
abstract = {We consider the problem ofdistributed mean estimation (DME), in which n machines are each given a local d-dimensional vector xv∈Rd, and must cooperate to estimate the mean of their inputs μ=1n∑nv=1xv, while minimizing total communication cost. DME is a fundamental construct in distributed machine learning, and there has been considerable work on variants of this problem, especially in the context of distributed variance reduction for stochastic gradients in parallel SGD. Previous work typically assumes an upper bound on the norm of the input vectors, and achieves an error bound in terms of this norm. However, in many real applications, the input vectors are concentrated around the correct output μ, but μ itself has large norm. In such cases, previous output error bounds perform poorly. In this paper, we show that output error bounds need not depend on input norm. We provide a method of quantization which allows distributed mean estimation to be performed with solution quality dependent only on the distance between inputs, not on input norm, and show an analogous result for distributed variance reduction. The technique is based on a new connection with lattice theory. We also provide lower bounds showing that the communication to error trade-off of our algorithms is asymptotically optimal. As the lattices achieving optimal bounds under l2-norm can be computationally impractical, we also present an extension which leverages easy-to-use cubic lattices, and is loose only up to a logarithmic factor ind. We show experimentally that our method yields practical improvements for common applications, relative to prior approaches.},
author = {Davies, Peter and Gurunanthan, Vijaykrishna and Moshrefi, Niusha and Ashkboos, Saleh and Alistarh, Dan-Adrian},
booktitle = {9th International Conference on Learning Representations},
location = {Virtual},
title = {{New bounds for distributed mean estimation and variance reduction}},
year = {2021},
}
@inproceedings{9416,
abstract = {We study the inductive bias of two-layer ReLU networks trained by gradient flow. We identify a class of easy-to-learn (`orthogonally separable') datasets, and characterise the solution that ReLU networks trained on such datasets converge to. Irrespective of network width, the solution turns out to be a combination of two max-margin classifiers: one corresponding to the positive data subset and one corresponding to the negative data subset. The proof is based on the recently introduced concept of extremal sectors, for which we prove a number of properties in the context of orthogonal separability. In particular, we prove stationarity of activation patterns from some time onwards, which enables a reduction of the ReLU network to an ensemble of linear subnetworks.},
author = {Bui Thi Mai, Phuong and Lampert, Christoph},
booktitle = {9th International Conference on Learning Representations},
location = {Virtual},
title = {{The inductive bias of ReLU networks on orthogonally separable data}},
year = {2021},
}
@phdthesis{8934,
abstract = {In this thesis, we consider several of the most classical and fundamental problems in static analysis and formal verification, including invariant generation, reachability analysis, termination analysis of probabilistic programs, data-flow analysis, quantitative analysis of Markov chains and Markov decision processes, and the problem of data packing in cache management.
We use techniques from parameterized complexity theory, polyhedral geometry, and real algebraic geometry to significantly improve the state-of-the-art, in terms of both scalability and completeness guarantees, for the mentioned problems. In some cases, our results are the first theoretical improvements for the respective problems in two or three decades.},
author = {Goharshady, Amir Kafshdar},
issn = {2663-337X},
pages = {278},
publisher = {IST Austria},
title = {{Parameterized and algebro-geometric advances in static program analysis}},
doi = {10.15479/AT:ISTA:8934},
year = {2021},
}
@article{7956,
abstract = {When short-range attractions are combined with long-range repulsions in colloidal particle systems, complex microphases can emerge. Here, we study a system of isotropic particles, which can form lamellar structures or a disordered fluid phase when temperature is varied. We show that, at equilibrium, the lamellar structure crystallizes, while out of equilibrium, the system forms a variety of structures at different shear rates and temperatures above melting. The shear-induced ordering is analyzed by means of principal component analysis and artificial neural networks, which are applied to data of reduced dimensionality. Our results reveal the possibility of inducing ordering by shear, potentially providing a feasible route to the fabrication of ordered lamellar structures from isotropic particles.},
author = {Pȩkalski, J. and Rzadkowski, Wojciech and Panagiotopoulos, A. Z.},
issn = {10897690},
journal = {The Journal of chemical physics},
number = {20},
publisher = {AIP},
title = {{Shear-induced ordering in systems with competing interactions: A machine learning study}},
doi = {10.1063/5.0005194},
volume = {152},
year = {2020},
}