TY - JOUR
AB - Inside a two-dimensional region (``cake""), there are m nonoverlapping tiles of a certain kind (``toppings""). We want to expand the toppings while keeping them nonoverlapping, and possibly add some blank pieces of the same ``certain kind,"" such that the entire cake is covered. How many blanks must we add? We study this question in several cases: (1) The cake and toppings are general polygons. (2) The cake and toppings are convex figures. (3) The cake and toppings are axis-parallel rectangles. (4) The cake is an axis-parallel rectilinear polygon and the toppings are axis-parallel rectangles. In all four cases, we provide tight bounds on the number of blanks.
AU - Akopyan, Arseniy
AU - Segal Halevi, Erel
ID - 58
IS - 3
JF - SIAM Journal on Discrete Mathematics
TI - Counting blanks in polygonal arrangements
VL - 32
ER -
TY - JOUR
AB - CLE peptides have been implicated in various developmental processes of plants and mediate their responses to environmental stimuli. However, the biological relevance of most CLE genes remains to be functionally characterized. Here, we report that CLE9, which is expressed in stomata, acts as an essential regulator in the induction of stomatal closure. Exogenous application of CLE9 peptides or overexpression of CLE9 effectively led to stomatal closure and enhanced drought tolerance, whereas CLE9 loss-of-function mutants were sensitivity to drought stress. CLE9-induced stomatal closure was impaired in abscisic acid (ABA)-deficient mutants, indicating that ABA is required for CLE9-medaited guard cell signalling. We further deciphered that two guard cell ABA-signalling components, OST1 and SLAC1, were responsible for CLE9-induced stomatal closure. MPK3 and MPK6 were activated by the CLE9 peptide, and CLE9 peptides failed to close stomata in mpk3 and mpk6 mutants. In addition, CLE9 peptides stimulated the induction of hydrogen peroxide (H2O2) and nitric oxide (NO) synthesis associated with stomatal closure, which was abolished in the NADPH oxidase-deficient mutants or nitric reductase mutants, respectively. Collectively, our results reveal a novel ABA-dependent function of CLE9 in the regulation of stomatal apertures, thereby suggesting a potential role of CLE9 in the stress acclimatization of plants.
AU - Zhang, Luosha
AU - Shi, Xiong
AU - Zhang, Yutao
AU - Wang, Jiajing
AU - Yang, Jingwei
AU - Ishida, Takashi
AU - Jiang, Wenqian
AU - Han, Xiangyu
AU - Kang, Jingke
AU - Wang, Xuening
AU - Pan, Lixia
AU - Lv, Shuo
AU - Cao, Bing
AU - Zhang, Yonghong
AU - Wu, Jinbin
AU - Han, Huibin
AU - Hu, Zhubing
AU - Cui, Langjun
AU - Sawa, Shinichiro
AU - He, Junmin
AU - Wang, Guodong
ID - 5830
JF - Plant Cell and Environment
SN - 01407791
TI - CLE9 peptide-induced stomatal closure is mediated by abscisic acid, hydrogen peroxide, and nitric oxide in arabidopsis thaliana
ER -
TY - JOUR
AB - Spatial patterns are ubiquitous on the subcellular, cellular and tissue level, and can be studied using imaging techniques such as light and fluorescence microscopy. Imaging data provide quantitative information about biological systems; however, mechanisms causing spatial patterning often remain elusive. In recent years, spatio-temporal mathematical modelling has helped to overcome this problem. Yet, outliers and structured noise limit modelling of whole imaging data, and models often consider spatial summary statistics. Here, we introduce an integrated data-driven modelling approach that can cope with measurement artefacts and whole imaging data. Our approach combines mechanistic models of the biological processes with robust statistical models of the measurement process. The parameters of the integrated model are calibrated using a maximum-likelihood approach. We used this integrated modelling approach to study in vivo gradients of the chemokine (C-C motif) ligand 21 (CCL21). CCL21 gradients guide dendritic cells and are important in the adaptive immune response. Using artificial data, we verified that the integrated modelling approach provides reliable parameter estimates in the presence of measurement noise and that bias and variance of these estimates are reduced compared to conventional approaches. The application to experimental data allowed the parametrization and subsequent refinement of the model using additional mechanisms. Among other results, model-based hypothesis testing predicted lymphatic vessel-dependent concentration of heparan sulfate, the binding partner of CCL21. The selected model provided an accurate description of the experimental data and was partially validated using published data. Our findings demonstrate that integrated statistical modelling of whole imaging data is computationally feasible and can provide novel biological insights.
AU - Hross, Sabrina
AU - Theis, Fabian J.
AU - Sixt, Michael K
AU - Hasenauer, Jan
ID - 5858
IS - 149
JF - Journal of the Royal Society Interface
SN - 17425689
TI - Mechanistic description of spatial processes using integrative modelling of noise-corrupted imaging data
VL - 15
ER -
TY - JOUR
AB - The emergence of syntax during childhood is a remarkable example of how complex correlations unfold in nonlinear ways through development. In particular, rapid transitions seem to occur as children reach the age of two, which seems to separate a two-word, tree-like network of syntactic relations among words from the scale-free graphs associated with the adult, complex grammar. Here, we explore the evolution of syntax networks through language acquisition using the chromatic number, which captures the transition and provides a natural link to standard theories on syntactic structures. The data analysis is compared to a null model of network growth dynamics which is shown to display non-trivial and sensible differences. At a more general level, we observe that the chromatic classes define independent regions of the graph, and thus, can be interpreted as the footprints of incompatibility relations, somewhat as opposed to modularity considerations.
AU - Corominas-Murtra, Bernat
AU - Fibla, Martí Sànchez
AU - Valverde, Sergi
AU - Solé, Ricard
ID - 5859
IS - 12
JF - Royal Society Open Science
SN - 20545703
TI - Chromatic transitions in the emergence of syntax networks
VL - 5
ER -
TY - JOUR
AB - A major problem for evolutionary theory is understanding the so-called open-ended nature of evolutionary change, from its definition to its origins. Open-ended evolution (OEE) refers to the unbounded increase in complexity that seems to characterize evolution on multiple scales. This property seems to be a characteristic feature of biological and technological evolution and is strongly tied to the generative potential associated with combinatorics, which allows the system to grow and expand their available state spaces. Interestingly, many complex systems presumably displaying OEE, from language to proteins, share a common statistical property: the presence of Zipf's Law. Given an inventory of basic items (such as words or protein domains) required to build more complex structures (sentences or proteins) Zipf's Law tells us that most of these elements are rare whereas a few of them are extremely common. Using algorithmic information theory, in this paper we provide a fundamental definition for open-endedness, which can be understood as postulates. Its statistical counterpart, based on standard Shannon information theory, has the structure of a variational problem which is shown to lead to Zipf's Law as the expected consequence of an evolutionary process displaying OEE. We further explore the problem of information conservation through an OEE process and we conclude that statistical information (standard Shannon information) is not conserved, resulting in the paradoxical situation in which the increase of information content has the effect of erasing itself. We prove that this paradox is solved if we consider non-statistical forms of information. This last result implies that standard information theory may not be a suitable theoretical framework to explore the persistence and increase of the information content in OEE systems.
AU - Corominas-Murtra, Bernat
AU - Seoane, Luís F.
AU - Solé, Ricard
ID - 5860
IS - 149
JF - Journal of the Royal Society Interface
SN - 17425689
TI - Zipf's Law, unbounded complexity and open-ended evolution
VL - 15
ER -
TY - JOUR
AB - In zebrafish larvae, it is the cell type that determines how the cell responds to a chemokine signal.
AU - Alanko, Jonna H
AU - Sixt, Michael K
ID - 5861
JF - eLife
SN - 2050084X
TI - The cell sets the tone
VL - 7
ER -
TY - JOUR
AB - Despite the remarkable number of scientific breakthroughs of the last 100 years, the treatment of neurodevelopmental
disorders (e.g., autism spectrum disorder, intellectual disability) remains a great challenge. Recent advancements in
genomics, such as whole-exome or whole-genome sequencing, have enabled scientists to identify numerous
mutations underlying neurodevelopmental disorders. Given the few hundred risk genes that have been discovered,
the etiological variability and the heterogeneous clinical presentation, the need for genotype — along with phenotype-
based diagnosis of individual patients has become a requisite. In this review we look at recent advancements in
genomic analysis and their translation into clinical practice.
AU - Tarlungeanu, Dora-Clara
AU - Novarino, Gaia
ID - 5888
IS - 8
JF - Experimental & Molecular Medicine
SN - 2092-6413
TI - Genomics in neurodevelopmental disorders: an avenue to personalized medicine
VL - 50
ER -
TY - CHAP
AB - Graph-based games are an important tool in computer science. They have applications in synthesis, verification, refinement, and far beyond. We review graphbased games with objectives on infinite plays. We give definitions and algorithms to solve the games and to give a winning strategy. The objectives we consider are mostly Boolean, but we also look at quantitative graph-based games and their objectives. Synthesis aims to turn temporal logic specifications into correct reactive systems. We explain the reduction of synthesis to graph-based games (or equivalently tree automata) using synthesis of LTL specifications as an example. We treat the classical approach that uses determinization of parity automata and more modern approaches.
AU - Bloem, Roderick
AU - Chatterjee, Krishnendu
AU - Jobstmann, Barbara
ED - Henzinger, Thomas A
ED - Clarke, Edmund M.
ED - Veith, Helmut
ED - Bloem, Roderick
ID - 59
SN - 978-3-319-10574-1
T2 - Handbook of Model Checking
TI - Graph games and reactive synthesis
ER -
TY - CONF
AB - Formalizing properties of systems with continuous dynamics is a challenging task. In this paper, we propose a formal framework for specifying and monitoring rich temporal properties of real-valued signals. We introduce signal first-order logic (SFO) as a specification language that combines first-order logic with linear-real arithmetic and unary function symbols interpreted as piecewise-linear signals. We first show that while the satisfiability problem for SFO is undecidable, its membership and monitoring problems are decidable. We develop an offline monitoring procedure for SFO that has polynomial complexity in the size of the input trace and the specification, for a fixed number of quantifiers and function symbols. We show that the algorithm has computation time linear in the size of the input trace for the important fragment of bounded-response specifications interpreted over input traces with finite variability. We can use our results to extend signal temporal logic with first-order quantifiers over time and value parameters, while preserving its efficient monitoring. We finally demonstrate the practical appeal of our logic through a case study in the micro-electronics domain.
AU - Bakhirkin, Alexey
AU - Ferrere, Thomas
AU - Henzinger, Thomas A
AU - Nickovicl, Deian
ID - 5959
SN - 9781538655603
T2 - 2018 International Conference on Embedded Software
TI - Keynote: The first-order logic of signals
ER -
TY - JOUR
AB - In this paper we present a reliable method to verify the existence of loops along the uncertain trajectory of a robot, based on proprioceptive measurements only, within a bounded-error context. The loop closure detection is one of the key points in simultaneous localization and mapping (SLAM) methods, especially in homogeneous environments with difficult scenes recognitions. The proposed approach is generic and could be coupled with conventional SLAM algorithms to reliably reduce their computing burden, thus improving the localization and mapping processes in the most challenging environments such as unexplored underwater extents. To prove that a robot performed a loop whatever the uncertainties in its evolution, we employ the notion of topological degree that originates in the field of differential topology. We show that a verification tool based on the topological degree is an optimal method for proving robot loops. This is demonstrated both on datasets from real missions involving autonomous underwater vehicles and by a mathematical discussion.
AU - Rohou, Simon
AU - Franek, Peter
AU - Aubry, Clément
AU - Jaulin, Luc
ID - 5960
IS - 12
JF - The International Journal of Robotics Research
SN - 0278-3649
TI - Proving the existence of loops in robot trajectories
VL - 37
ER -
TY - CONF
AB - The area of machine learning has made considerable progress over the past decade, enabled by the widespread availability of large datasets, as well as by improved algorithms and models. Given the large computational demands of machine learning workloads, parallelism, implemented either through single-node concurrency or through multi-node distribution, has been a third key ingredient to advances in machine learning.
The goal of this tutorial is to provide the audience with an overview of standard distribution techniques in machine learning, with an eye towards the intriguing trade-offs between synchronization and communication costs of distributed machine learning algorithms, on the one hand, and their convergence, on the other.The tutorial will focus on parallelization strategies for the fundamental stochastic gradient descent (SGD) algorithm, which is a key tool when training machine learning models, from classical instances such as linear regression, to state-of-the-art neural network architectures.
The tutorial will describe the guarantees provided by this algorithm in the sequential case, and then move on to cover both shared-memory and message-passing parallelization strategies, together with the guarantees they provide, and corresponding trade-offs. The presentation will conclude with a broad overview of ongoing research in distributed and concurrent machine learning. The tutorial will assume no prior knowledge beyond familiarity with basic concepts in algebra and analysis.
AU - Alistarh, Dan-Adrian
ID - 5961
SN - 9781450357951
T2 - Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC '18
TI - A brief tutorial on distributed and concurrent machine learning
ER -
TY - CONF
AB - Stochastic Gradient Descent (SGD) is a fundamental algorithm in machine learning, representing the optimization backbone for training several classic models, from regression to neural networks. Given the recent practical focus on distributed machine learning, significant work has been dedicated to the convergence properties of this algorithm under the inconsistent and noisy updates arising from execution in a distributed environment. However, surprisingly, the convergence properties of this classic algorithm in the standard shared-memory model are still not well-understood. In this work, we address this gap, and provide new convergence bounds for lock-free concurrent stochastic gradient descent, executing in the classic asynchronous shared memory model, against a strong adaptive adversary. Our results give improved upper and lower bounds on the "price of asynchrony'' when executing the fundamental SGD algorithm in a concurrent setting. They show that this classic optimization tool can converge faster and with a wider range of parameters than previously known under asynchronous iterations. At the same time, we exhibit a fundamental trade-off between the maximum delay in the system and the rate at which SGD can converge, which governs the set of parameters under which this algorithm can still work efficiently.
AU - Alistarh, Dan-Adrian
AU - De Sa, Christopher
AU - Konstantinov, Nikola H
ID - 5962
SN - 9781450357951
T2 - Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC '18
TI - The convergence of stochastic gradient descent in asynchronous shared memory
ER -
TY - CONF
AB - There has been significant progress in understanding the parallelism inherent to iterative sequential algorithms: for many classic algorithms, the depth of the dependence structure is now well understood, and scheduling techniques have been developed to exploit this shallow dependence structure for efficient parallel implementations. A related, applied research strand has studied methods by which certain iterative task-based algorithms can be efficiently parallelized via relaxed concurrent priority schedulers. These allow for high concurrency when inserting and removing tasks, at the cost of executing superfluous work due to the relaxed semantics of the scheduler. In this work, we take a step towards unifying these two research directions, by showing that there exists a family of relaxed priority schedulers that can efficiently and deterministically execute classic iterative algorithms such as greedy maximal independent set (MIS) and matching. Our primary result shows that, given a randomized scheduler with an expected relaxation factor of k in terms of the maximum allowed priority inversions on a task, and any graph on n vertices, the scheduler is able to execute greedy MIS with only an additive factor of \poly(k) expected additional iterations compared to an exact (but not scalable) scheduler. This counter-intuitive result demonstrates that the overhead of relaxation when computing MIS is not dependent on the input size or structure of the input graph. Experimental results show that this overhead can be clearly offset by the gain in performance due to the highly scalable scheduler. In sum, we present an efficient method to deterministically parallelize iterative sequential algorithms, with provable runtime guarantees in terms of the number of executed tasks to completion.
AU - Alistarh, Dan-Adrian
AU - Brown, Trevor A
AU - Kopinsky, Justin
AU - Nadiradze, Giorgi
ID - 5963
SN - 9781450357951
T2 - Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC '18
TI - Relaxed schedulers can efficiently parallelize iterative algorithms
ER -
TY - CONF
AB - A standard design pattern found in many concurrent data structures, such as hash tables or ordered containers, is an alternation of parallelizable sections that incur no data conflicts and critical sections that must run sequentially and are protected with locks. A lock can be viewed as a queue that arbitrates the order in which the critical sections are executed, and a natural question is whether we can use stochastic analysis to predict the resulting throughput. As a preliminary evidence to the affirmative, we describe a simple model that can be used to predict the throughput of coarse-grained lock-based algorithms. We show that our model works well for CLH lock, and we expect it to work for other popular lock designs such as TTAS, MCS, etc.
AU - Aksenov, Vitaly
AU - Alistarh, Dan-Adrian
AU - Kuznetsov, Petr
ID - 5964
SN - 9781450357951
T2 - Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC '18
TI - Brief Announcement: Performance prediction for coarse-grained locking
ER -
TY - CONF
AB - Relaxed concurrent data structures have become increasingly popular, due to their scalability in graph processing and machine learning applications (\citeNguyen13, gonzalez2012powergraph ). Despite considerable interest, there exist families of natural, high performing randomized relaxed concurrent data structures, such as the popular MultiQueue~\citeMQ pattern for implementing relaxed priority queue data structures, for which no guarantees are known in the concurrent setting~\citeAKLN17. Our main contribution is in showing for the first time that, under a set of analytic assumptions, a family of relaxed concurrent data structures, including variants of MultiQueues, but also a new approximate counting algorithm we call the MultiCounter, provides strong probabilistic guarantees on the degree of relaxation with respect to the sequential specification, in arbitrary concurrent executions. We formalize these guarantees via a new correctness condition called distributional linearizability, tailored to concurrent implementations with randomized relaxations. Our result is based on a new analysis of an asynchronous variant of the classic power-of-two-choices load balancing algorithm, in which placement choices can be based on inconsistent, outdated information (this result may be of independent interest). We validate our results empirically, showing that the MultiCounter algorithm can implement scalable relaxed timestamps.
AU - Alistarh, Dan-Adrian
AU - Brown, Trevor A
AU - Kopinsky, Justin
AU - Li, Jerry Z.
AU - Nadiradze, Giorgi
ID - 5965
SN - 9781450357999
T2 - Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures - SPAA '18
TI - Distributionally linearizable data structures
ER -
TY - CONF
AB - The transactional conflict problem arises in transactional systems whenever two or more concurrent transactions clash on a data item. While the standard solution to such conflicts is to immediately abort one of the transactions, some practical systems consider the alternative of delaying conflict resolution for a short interval, which may allow one of the transactions to commit. The challenge in the transactional conflict problem is to choose the optimal length of this delay interval so as to minimize the overall running time penalty for the conflicting transactions. In this paper, we propose a family of optimal online algorithms for the transactional conflict problem. Specifically, we consider variants of this problem which arise in different implementations of transactional systems, namely "requestor wins'' and "requestor aborts'' implementations: in the former, the recipient of a coherence request is aborted, whereas in the latter, it is the requestor which has to abort. Both strategies are implemented by real systems. We show that the requestor aborts case can be reduced to a classic instance of the ski rental problem, while the requestor wins case leads to a new version of this classical problem, for which we derive optimal deterministic and randomized algorithms. Moreover, we prove that, under a simplified adversarial model, our algorithms are constant-competitive with the offline optimum in terms of throughput. We validate our algorithmic results empirically through a hardware simulation of hardware transactional memory (HTM), showing that our algorithms can lead to non-trivial performance improvements for classic concurrent data structures.
AU - Alistarh, Dan-Adrian
AU - Haider, Syed Kamran
AU - Kübler, Raphael
AU - Nadiradze, Giorgi
ID - 5966
SN - 9781450357999
T2 - Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures - SPAA '18
TI - The transactional conflict problem
ER -
TY - CONF
AB - The Big Match is a multi-stage two-player game. In each stage Player 1 hides one or two pebbles in his hand, and his opponent has to guess that number; Player 1 loses a point if Player 2 is correct, and otherwise he wins a point. As soon as Player 1 hides one pebble, the players cannot change their choices in any future stage.
Blackwell and Ferguson (1968) give an ε-optimal strategy for Player 1 that hides, in each stage, one pebble with a probability that depends on the entire past history. Any strategy that depends just on the clock or on a finite memory is worthless. The long-standing natural open problem has been whether every strategy that depends just on the clock and a finite memory is worthless. We prove that there is such a strategy that is ε-optimal. In fact, we show that just two states of memory are sufficient.
AU - Hansen, Kristoffer Arnsfelt
AU - Ibsen-Jensen, Rasmus
AU - Neyman, Abraham
ID - 5967
SN - 9781450358293
T2 - Proceedings of the 2018 ACM Conference on Economics and Computation - EC '18
TI - The Big Match with a clock and a bit of memory
ER -
TY - JOUR
AB - We consider a Wigner-type ensemble, i.e. large hermitian N×N random matrices H=H∗ with centered independent entries and with a general matrix of variances Sxy=𝔼∣∣Hxy∣∣2. The norm of H is asymptotically given by the maximum of the support of the self-consistent density of states. We establish a bound on this maximum in terms of norms of powers of S that substantially improves the earlier bound 2∥S∥1/2∞ given in [O. Ajanki, L. Erdős and T. Krüger, Universality for general Wigner-type matrices, Prob. Theor. Rel. Fields169 (2017) 667–727]. The key element of the proof is an effective Markov chain approximation for the contributions of the weighted Dyck paths appearing in the iterative solution of the corresponding Dyson equation.
AU - Erdös, László
AU - Mühlbacher, Peter
ID - 5971
JF - Random matrices: Theory and applications
SN - 2010-3263
TI - Bounds on the norm of Wigner-type random matrices
ER -
TY - JOUR
AB - We consider the recent formulation of the algorithmic Lov ́asz Local Lemma [N. Har-vey and J. Vondr ́ak, inProceedings of FOCS, 2015, pp. 1327–1345; D. Achlioptas and F. Iliopoulos,inProceedings of SODA, 2016, pp. 2024–2038; D. Achlioptas, F. Iliopoulos, and V. Kolmogorov,ALocal Lemma for Focused Stochastic Algorithms, arXiv preprint, 2018] for finding objects that avoid“bad features,” or “flaws.” It extends the Moser–Tardos resampling algorithm [R. A. Moser andG. Tardos,J. ACM, 57 (2010), 11] to more general discrete spaces. At each step the method picks aflaw present in the current state and goes to a new state according to some prespecified probabilitydistribution (which depends on the current state and the selected flaw). However, the recent formu-lation is less flexible than the Moser–Tardos method since it requires a specific flaw selection rule,whereas the algorithm of Moser and Tardos allows an arbitrary rule (and thus can potentially beimplemented more efficiently). We formulate a new “commutativity” condition and prove that it issufficient for an arbitrary rule to work. It also enables an efficient parallelization under an additionalassumption. We then show that existing resampling oracles for perfect matchings and permutationsdo satisfy this condition.
AU - Kolmogorov, Vladimir
ID - 5975
IS - 6
JF - SIAM Journal on Computing
SN - 0097-5397
TI - Commutativity in the algorithmic Lovász local lemma
VL - 47
ER -
TY - JOUR
AB - We propose FlexMaps, a novel framework for fabricating smooth shapes out of flat, flexible panels with tailored mechanical properties. We start by mapping the 3D surface onto a 2D domain as in traditional UV mapping to design a set of deformable flat panels called FlexMaps. For these panels, we design and obtain specific mechanical properties such that, once they are assembled, the static equilibrium configuration matches the desired 3D shape. FlexMaps can be fabricated from an almost rigid material, such as wood or plastic, and are made flexible in a controlled way by using computationally designed spiraling microstructures.
AU - Malomo, Luigi
AU - Perez Rodriguez, Jesus
AU - Iarussi, Emmanuel
AU - Pietroni, Nico
AU - Miguel, Eder
AU - Cignoni, Paolo
AU - Bickel, Bernd
ID - 5976
IS - 6
JF - ACM Transactions on Graphics
SN - 0730-0301
TI - FlexMaps: Computational design of flat flexible shells for shaping 3D objects
VL - 37
ER -
TY - CONF
AB - We consider the MAP-inference problem for graphical models,which is a valued constraint satisfaction problem defined onreal numbers with a natural summation operation. We proposea family of relaxations (different from the famous Sherali-Adams hierarchy), which naturally define lower bounds for itsoptimum. This family always contains a tight relaxation andwe give an algorithm able to find it and therefore, solve theinitial non-relaxed NP-hard problem.The relaxations we consider decompose the original probleminto two non-overlapping parts: an easy LP-tight part and adifficult one. For the latter part a combinatorial solver must beused. As we show in our experiments, in a number of applica-tions the second, difficult part constitutes only a small fractionof the whole problem. This property allows to significantlyreduce the computational time of the combinatorial solver andtherefore solve problems which were out of reach before.
AU - Haller, Stefan
AU - Swoboda, Paul
AU - Savchynskyy, Bogdan
ID - 5978
T2 - Proceedings of the 32st AAAI Conference on Artificial Intelligence
TI - Exact MAP-inference by confining combinatorial search with LP relaxation
ER -
TY - JOUR
AB - The problem of private set-intersection (PSI) has been traditionally treated as an instance of the more general problem of multi-party computation (MPC). Consequently, in order to argue security, or compose these protocols one has to rely on the general theory that was developed for the purpose of MPC. The pursuit of efficient protocols, however, has resulted in designs that exploit properties pertaining to PSI. In almost all practical applications where a PSI protocol is deployed, it is expected to be executed multiple times, possibly on related inputs. In this work we initiate a dedicated study of PSI in the multi-interaction (MI) setting. In this model a server sets up the common system parameters and executes set-intersection multiple times with potentially different clients. We discuss a few attacks that arise when protocols are naïvely composed in this manner and, accordingly, craft security definitions for the MI setting and study their inter-relation. Finally, we suggest a set of protocols that are MI-secure, at the same time almost as efficient as their parent, stand-alone, protocols.
AU - Chatterjee, Sanjit
AU - Kamath Hosdurg, Chethan
AU - Kumar, Vikas
ID - 5980
IS - 1
JF - American Institute of Mathematical Sciences
TI - Private set-intersection with common set-up
VL - 12
ER -
TY - JOUR
AB - In the present work, we detail a fast and simple solution-based method to synthesize hexagonal SnSe2 nanoplates (NPLs) and their use to produce crystallographically textured SnSe2 nanomaterials. We also demonstrate that the same strategy can be used to produce orthorhombic SnSe nanostructures and nanomaterials. NPLs are grown through a screw dislocation-driven mechanism. This mechanism typically results in pyramidal structures, but we demonstrate here that the growth from multiple dislocations results in flower-like structures. Crystallographically textured SnSe2 bulk nanomaterials obtained from the hot pressing of these SnSe2 structures display highly anisotropic charge and heat transport properties and thermoelectric (TE) figures of merit limited by relatively low electrical conductivities. To improve this parameter, SnSe2 NPLs are blended here with metal nanoparticles. The electrical conductivities of the blends are significantly improved with respect to bare SnSe2 NPLs, what translates into a three-fold increase of the TE Figure of merit, reaching unprecedented ZT values up to 0.65.
AU - Zhang, Yu
AU - Liu, Yu
AU - Lim, Khak Ho
AU - Xing, Congcong
AU - Li, Mengyao
AU - Zhang, Ting
AU - Tang, Pengyi
AU - Arbiol, Jordi
AU - Llorca, Jordi
AU - Ng, Ka Ming
AU - Ibáñez, Maria
AU - Guardia, Pablo
AU - Prato, Mirko
AU - Cadavid, Doris
AU - Cabot, Andreu
ID - 5982
IS - 52
JF - Angewandte Chemie International Edition
SN - 1433-7851
TI - Tin diselenide molecular precursor for solution-processable thermoelectric materials
VL - 57
ER -
TY - JOUR
AB - We study a quantum impurity possessing both translational and internal rotational degrees of freedom interacting with a bosonic bath. Such a system corresponds to a “rotating polaron,” which can be used to model, e.g., a rotating molecule immersed in an ultracold Bose gas or superfluid helium. We derive the Hamiltonian of the rotating polaron and study its spectrum in the weak- and strong-coupling regimes using a combination of variational, diagrammatic, and mean-field approaches. We reveal how the coupling between linear and angular momenta affects stable quasiparticle states, and demonstrate that internal rotation leads to an enhanced self-localization in the translational degrees of freedom.
AU - Yakaboylu, Enderalp
AU - Midya, Bikashkali
AU - Deuchert, Andreas
AU - Leopold, Nikolai K
AU - Lemeshko, Mikhail
ID - 5983
IS - 22
JF - Physical Review B
SN - 2469-9950
TI - Theory of the rotating polaron: Spectrum and self-localization
VL - 98
ER -
TY - JOUR
AB - G-protein-coupled receptors (GPCRs) form the largest receptor family, relay environmental stimuli to changes in cell behavior and represent prime drug targets. Many GPCRs are classified as orphan receptors because of the limited knowledge on their ligands and coupling to cellular signaling machineries. Here, we engineer a library of 63 chimeric receptors that contain the signaling domains of human orphan and understudied GPCRs functionally linked to the light-sensing domain of rhodopsin. Upon stimulation with visible light, we identify activation of canonical cell signaling pathways, including cAMP-, Ca2+-, MAPK/ERK-, and Rho-dependent pathways, downstream of the engineered receptors. For the human pseudogene GPR33, we resurrect a signaling function that supports its hypothesized role as a pathogen entry site. These results demonstrate that substituting unknown chemical activators with a light switch can reveal information about protein function and provide an optically controlled protein library for exploring the physiology and therapeutic potential of understudied GPCRs.
AU - Morri, Maurizio
AU - Sanchez-Romero, Inmaculada
AU - Tichy, Alexandra-Madelaine
AU - Kainrath, Stephanie
AU - Gerrard, Elliot J.
AU - Hirschfeld, Priscila
AU - Schwarz, Jan
AU - Janovjak, Harald L
ID - 5984
IS - 1
JF - Nature Communications
SN - 2041-1723
TI - Optical functionalization of human class A orphan G-protein-coupled receptors
VL - 9
ER -
TY - JOUR
AB - Schistosomes are the causative agents of schistosomiasis, a neglected tropical disease affecting over 230 million people worldwide.Additionally to their major impact on human health, they are also models of choice in evolutionary biology. These parasitic flatwormsare unique among the common hermaphroditic trematodes as they have separate sexes. This so-called “evolutionary scandal”displays a female heterogametic genetic sex-determination system (ZZ males and ZW females), as well as a pronounced adult sexualdimorphism. These phenotypic differences are determined by a shared set of genes in both sexes, potentially leading to intralocussexual conflicts. To resolve these conflicts in sexually selected traits, molecular mechanisms such as sex-biased gene expression couldoccur, but parent-of-origin gene expression also provides an alternative. In this work we investigated the latter mechanism, that is,genes expressed preferentially from either the maternal or the paternal allele, inSchistosoma mansonispecies. To this end, tran-scriptomes from male and female hybrid adults obtained by strain crosses were sequenced. Strain-specific single nucleotide poly-morphism (SNP) markers allowed us to discriminate the parental origin, while reciprocal crosses helped to differentiate parentalexpression from strain-specific expression. We identified genes containing SNPs expressed in a parent-of-origin manner consistentwith paternal and maternal imprints. Although the majority of the SNPs was identified in mitochondrial and Z-specific loci, theremaining SNPs found in male and female transcriptomes were situated in genes that have the potential to explain sexual differencesin schistosome parasites. Furthermore, we identified and validated four new Z-specific scaffolds.
AU - Kincaid-Smith, Julien
AU - Picard, Marion A L
AU - Cosseau, Céline
AU - Boissier, Jérôme
AU - Severac, Dany
AU - Grunau, Christoph
AU - Toulza, Eve
ID - 5989
IS - 3
JF - Genome Biology and Evolution
SN - 1759-6653
TI - Parent-of-Origin-Dependent Gene Expression in Male and Female Schistosome Parasites
VL - 10
ER -
TY - JOUR
AB - A Ge–Si core–shell nanowire is used to realize a Josephson field‐effect transistor with highly transparent contacts to superconducting leads. By changing the electric field, access to two distinct regimes, not combined before in a single device, is gained: in the accumulation mode the device is highly transparent and the supercurrent is carried by multiple subbands, while near depletion, the supercurrent is carried by single‐particle levels of a strongly coupled quantum dot operating in the few‐hole regime. These results establish Ge–Si nanowires as an important platform for hybrid superconductor–semiconductor physics and Majorana fermions.
AU - Ridderbos, Joost
AU - Brauns, Matthias
AU - Shen, Jie
AU - de Vries, Folkert K.
AU - Li, Ang
AU - Bakkers, Erik P. A. M.
AU - Brinkman, Alexander
AU - Zwanenburg, Floris A.
ID - 5990
IS - 44
JF - Advanced Materials
SN - 0935-9648
TI - Josephson effect in a few-hole quantum dot
VL - 30
ER -
TY - JOUR
AB - Lamellipodia are flat membrane protrusions formed during mesenchymal motion. Polymerization at the leading edge assembles the actin filament network and generates protrusion force. How this force is supported by the network and how the assembly rate is shared between protrusion and network retrograde flow determines the protrusion rate. We use mathematical modeling to understand experiments changing the F-actin density in lamellipodia of B16-F1 melanoma cells by modulation of Arp2/3 complex activity or knockout of the formins FMNL2 and FMNL3. Cells respond to a reduction of density with a decrease of protrusion velocity, an increase in the ratio of force to filament number, but constant network assembly rate. The relation between protrusion force and tension gradient in the F-actin network and the density dependency of friction, elasticity, and viscosity of the network explain the experimental observations. The formins act as filament nucleators and elongators with differential rates. Modulation of their activity suggests an effect on network assembly rate. Contrary to these expectations, the effect of changes in elongator composition is much weaker than the consequences of the density change. We conclude that the force acting on the leading edge membrane is the force required to drive F-actin network retrograde flow.
AU - Dolati, Setareh
AU - Kage, Frieda
AU - Mueller, Jan
AU - Müsken, Mathias
AU - Kirchner, Marieluise
AU - Dittmar, Gunnar
AU - Sixt, Michael K
AU - Rottner, Klemens
AU - Falcke, Martin
ID - 5992
IS - 22
JF - Molecular Biology of the Cell
SN - 1059-1524
TI - On the relation between filament density, force generation, and protrusion rate in mesenchymal cell motility
VL - 29
ER -
TY - JOUR
AB - In this article, we consider the termination problem of probabilistic programs with real-valued variables. Thequestions concerned are: qualitative ones that ask (i) whether the program terminates with probability 1(almost-sure termination) and (ii) whether the expected termination time is finite (finite termination); andquantitative ones that ask (i) to approximate the expected termination time (expectation problem) and (ii) tocompute a boundBsuch that the probability not to terminate afterBsteps decreases exponentially (con-centration problem). To solve these questions, we utilize the notion of ranking supermartingales, which isa powerful approach for proving termination of probabilistic programs. In detail, we focus on algorithmicsynthesis of linear ranking-supermartingales over affine probabilistic programs (Apps) with both angelic anddemonic non-determinism. An important subclass of Apps is LRApp which is defined as the class of all Appsover which a linear ranking-supermartingale exists.Our main contributions are as follows. Firstly, we show that the membership problem of LRApp (i) canbe decided in polynomial time for Apps with at most demonic non-determinism, and (ii) isNP-hard and inPSPACEfor Apps with angelic non-determinism. Moreover, theNP-hardness result holds already for Appswithout probability and demonic non-determinism. Secondly, we show that the concentration problem overLRApp can be solved in the same complexity as for the membership problem of LRApp. Finally, we show thatthe expectation problem over LRApp can be solved in2EXPTIMEand isPSPACE-hard even for Apps withoutprobability and non-determinism (i.e., deterministic programs). Our experimental results demonstrate theeffectiveness of our approach to answer the qualitative and quantitative questions over Apps with at mostdemonic non-determinism.
AU - Chatterjee, Krishnendu
AU - Fu, Hongfei
AU - Novotný, Petr
AU - Hasheminezhad, Rouzbeh
ID - 5993
IS - 2
JF - ACM Transactions on Programming Languages and Systems
SN - 0164-0925
TI - Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs
VL - 40
ER -
TY - JOUR
AB - Motivation
Computational prediction of the effect of mutations on protein stability is used by researchers in many fields. The utility of the prediction methods is affected by their accuracy and bias. Bias, a systematic shift of the predicted change of stability, has been noted as an issue for several methods, but has not been investigated systematically. Presence of the bias may lead to misleading results especially when exploring the effects of combination of different mutations.
Results
Here we use a protocol to measure the bias as a function of the number of introduced mutations. It is based on a self-consistency test of the reciprocity the effect of a mutation. An advantage of the used approach is that it relies solely on crystal structures without experimentally measured stability values. We applied the protocol to four popular algorithms predicting change of protein stability upon mutation, FoldX, Eris, Rosetta and I-Mutant, and found an inherent bias. For one program, FoldX, we manage to substantially reduce the bias using additional relaxation by Modeller. Authors using algorithms for predicting effects of mutations should be aware of the bias described here.
AU - Usmanova, Dinara R
AU - Bogatyreva, Natalya S
AU - Ariño Bernad, Joan
AU - Eremina, Aleksandra A
AU - Gorshkova, Anastasiya A
AU - Kanevskiy, German M
AU - Lonishin, Lyubov R
AU - Meister, Alexander V
AU - Yakupova, Alisa G
AU - Kondrashov, Fyodor
AU - Ivankov, Dmitry
ID - 5995
IS - 21
JF - Bioinformatics
SN - 1367-4803
TI - Self-consistency test reveals systematic bias in programs for prediction change of stability upon mutation
VL - 34
ER -
TY - JOUR
AB - In pipes, turbulence sets in despite the linear stability of the laminar Hagen–Poiseuille flow. The Reynolds number ( ) for which turbulence first appears in a given experiment – the ‘natural transition point’ – depends on imperfections of the set-up, or, more precisely, on the magnitude of finite amplitude perturbations. At onset, turbulence typically only occupies a certain fraction of the flow, and this fraction equally is found to differ from experiment to experiment. Despite these findings, Reynolds proposed that after sufficiently long times, flows may settle to steady conditions: below a critical velocity, flows should (regardless of initial conditions) always return to laminar, while above this velocity, eddying motion should persist. As will be shown, even in pipes several thousand diameters long, the spatio-temporal intermittent flow patterns observed at the end of the pipe strongly depend on the initial conditions, and there is no indication that different flow patterns would eventually settle to a (statistical) steady state. Exploiting the fact that turbulent puffs do not age (i.e. they are memoryless), we continuously recreate the puff sequence exiting the pipe at the pipe entrance, and in doing so introduce periodic boundary conditions for the puff pattern. This procedure allows us to study the evolution of the flow patterns for arbitrary long times, and we find that after times in excess of advective time units, indeed a statistical steady state is reached. Although the resulting flows remain spatio-temporally intermittent, puff splitting and decay rates eventually reach a balance, so that the turbulent fraction fluctuates around a well-defined level which only depends on . In accordance with Reynolds’ proposition, we find that at lower (here 2020), flows eventually always resume to laminar, while for higher ( ), turbulence persists. The critical point for pipe flow hence falls in the interval of $2020 , which is in very good agreement with the recently proposed value of . The latter estimate was based on single-puff statistics and entirely neglected puff interactions. Unlike in typical contact processes where such interactions strongly affect the percolation threshold, in pipe flow, the critical point is only marginally influenced. Interactions, on the other hand, are responsible for the approach to the statistical steady state. As shown, they strongly affect the resulting flow patterns, where they cause ‘puff clustering’, and these regions of large puff densities are observed to travel across the puff pattern in a wave-like fashion.
AU - Vasudevan, Mukund
AU - Hof, Björn
ID - 5996
JF - Journal of Fluid Mechanics
SN - 0022-1120
TI - The critical point of the transition to turbulence in pipe flow
VL - 839
ER -
TY - JOUR
AB - Genome amplification and cellular senescence are commonly associated with pathological processes. While physiological roles for polyploidization and senescence have been described in mouse development, controversy exists over their significance in humans. Here, we describe tetraploidization and senescence as phenomena of normal human placenta development. During pregnancy, placental extravillous trophoblasts (EVTs) invade the pregnant endometrium, termed decidua, to establish an adapted microenvironment required for the developing embryo. This process is critically dependent on continuous cell proliferation and differentiation, which is thought to follow the classical model of cell cycle arrest prior to terminal differentiation. Strikingly, flow cytometry and DNAseq revealed that EVT formation is accompanied with a genome-wide polyploidization, independent of mitotic cycles. DNA replication in these cells was analysed by a fluorescent cell-cycle indicator reporter system, cell cycle marker expression and EdU incorporation. Upon invasion into the decidua, EVTs widely lose their replicative potential and enter a senescent state characterized by high senescence-associated (SA) β-galactosidase activity, induction of a SA secretory phenotype as well as typical metabolic alterations. Furthermore, we show that the shift from endocycle-dependent genome amplification to growth arrest is disturbed in androgenic complete hydatidiform moles (CHM), a hyperplastic pregnancy disorder associated with increased risk of developing choriocarinoma. Senescence is decreased in CHM-EVTs, accompanied by exacerbated endoreduplication and hyperploidy. We propose induction of cellular senescence as a ploidy-limiting mechanism during normal human placentation and unravel a link between excessive polyploidization and reduced senescence in CHM.
AU - Velicky, Philipp
AU - Meinhardt, Gudrun
AU - Plessl, Kerstin
AU - Vondra, Sigrid
AU - Weiss, Tamara
AU - Haslinger, Peter
AU - Lendl, Thomas
AU - Aumayr, Karin
AU - Mairhofer, Mario
AU - Zhu, Xiaowei
AU - Schütz, Birgit
AU - Hannibal, Roberta L.
AU - Lindau, Robert
AU - Weil, Beatrix
AU - Ernerudh, Jan
AU - Neesen, Jürgen
AU - Egger, Gerda
AU - Mikula, Mario
AU - Röhrl, Clemens
AU - Urban, Alexander E.
AU - Baker, Julie
AU - Knöfler, Martin
AU - Pollheimer, Jürgen
ID - 5998
IS - 10
JF - PLOS Genetics
SN - 1553-7404
TI - Genome amplification and cellular senescence are hallmarks of human placenta development
VL - 14
ER -
TY - JOUR
AB - We introduce for each quiver Q and each algebraic oriented cohomology theory A, the cohomological Hall algebra (CoHA) of Q, as the A-homology of the moduli of representations of the preprojective algebra of Q. This generalizes the K-theoretic Hall algebra of commuting varieties defined by Schiffmann-Vasserot. When A is the Morava K-theory, we show evidence that this algebra is a candidate for Lusztig's reformulated conjecture on modular representations of algebraic groups.
We construct an action of the preprojective CoHA on the A-homology of Nakajima quiver varieties. We compare this with the action of the Borel subalgebra of Yangian when A is the intersection theory. We also give a shuffle algebra description of this CoHA in terms of the underlying formal group law of A. As applications, we obtain a shuffle description of the Yangian.
AU - Yang, Yaping
AU - Zhao, Gufang
ID - 5999
IS - 5
JF - Proceedings of the London Mathematical Society
SN - 0024-6115
TI - The cohomological Hall algebra of a preprojective algebra
VL - 116
ER -
TY - JOUR
AB - Lesion and electrode location verification are traditionally done via histological examination of stained brain slices, a time-consuming procedure that requires manual estimation. Here, we describe a simple, straightforward method for quantifying lesions and locating electrodes in the brain that is less laborious and yields more detailed results. Whole brains are stained with osmium tetroxide, embedded in resin, and imaged with a micro-CT scanner. The scans result in 3D digital volumes of the brains with resolutions and virtual section thicknesses dependent on the sample size (12-15 and 5-6 µm per voxel for rat and zebra finch brains, respectively). Surface and deep lesions can be characterized, and single tetrodes, tetrode arrays, electrolytic lesions, and silicon probes can also be localized. Free and proprietary software allows experimenters to examine the sample volume from any plane and segment the volume manually or automatically. Because this method generates whole brain volume, lesions and electrodes can be quantified to a much higher degree than in current methods, which will help standardize comparisons within and across studies.
AU - Masís, Javier
AU - Mankus, David
AU - Wolff, Steffen
AU - Guitchounts, Grigori
AU - Jösch, Maximilian A
AU - Cox, David
ID - 6
JF - Journal of visualized experiments (JoVE)
TI - A micro-CT-based method for characterising lesions and locating electrodes in small animal brains
VL - 141
ER -
TY - CHAP
AB - Model checking is a computer-assisted method for the analysis of dynamical systems that can be modeled by state-transition systems. Drawing from research traditions in mathematical logic, programming languages, hardware design, and theoretical computer science, model checking is now widely used for the verification of hardware and software in industry. This chapter is an introduction and short survey of model checking. The chapter aims to motivate and link the individual chapters of the handbook, and to provide context for readers who are not familiar with model checking.
AU - Clarke, Edmund
AU - Henzinger, Thomas A
AU - Veith, Helmut
ED - Henzinger, Thomas A
ID - 60
T2 - Handbook of Model Checking
TI - Introduction to model checking
ER -
TY - JOUR
AB - The concurrent memory reclamation problem is that of devising a way for a deallocating thread to verify that no other concurrent threads hold references to a memory block being deallocated. To date, in the absence of automatic garbage collection, there is no satisfactory solution to this problem; existing tracking methods like hazard pointers, reference counters, or epoch-based techniques like RCU are either prohibitively expensive or require significant programming expertise to the extent that implementing them efficiently can be worthy of a publication. None of the existing techniques are automatic or even semi-automated.
In this article, we take a new approach to concurrent memory reclamation. Instead of manually tracking access to memory locations as done in techniques like hazard pointers, or restricting shared accesses to specific epoch boundaries as in RCU, our algorithm, called ThreadScan, leverages operating system signaling to automatically detect which memory locations are being accessed by concurrent threads.
Initial empirical evidence shows that ThreadScan scales surprisingly well and requires negligible programming effort beyond the standard use of Malloc and Free.
AU - Alistarh, Dan-Adrian
AU - Leiserson, William
AU - Matveev, Alexander
AU - Shavit, Nir
ID - 6001
IS - 4
JF - ACM Transactions on Parallel Computing
SN - 2329-4949
TI - ThreadScan: Automatic and scalable memory reclamation
VL - 4
ER -
TY - JOUR
AB - The Bogoliubov free energy functional is analysed. The functional serves as a model of a translation-invariant Bose gas at positive temperature. We prove the existence of minimizers in the case of repulsive interactions given by a sufficiently regular two-body potential. Furthermore, we prove the existence of a phase transition in this model and provide its phase diagram.
AU - Napiórkowski, Marcin M
AU - Reuvers, Robin
AU - Solovej, Jan Philip
ID - 6002
IS - 3
JF - Archive for Rational Mechanics and Analysis
SN - 0003-9527
TI - The Bogoliubov free energy functional I: Existence of minimizers and phase diagram
VL - 229
ER -
TY - JOUR
AB - Digital fabrication devices are powerful tools for creating tangible reproductions of 3D digital models. Most available printing technologies aim at producing an accurate copy of a tridimensional shape. However, fabrication technologies can also be used to create a stylistic representation of a digital shape. We refer to this class of methods as ‘stylized fabrication methods’. These methods abstract geometric and physical features of a given shape to create an unconventional representation, to produce an optical illusion or to devise a particular interaction with the fabricated model. In this state‐of‐the‐art report, we classify and overview this broad and emerging class of approaches and also propose possible directions for future research.
AU - Bickel, Bernd
AU - Cignoni, Paolo
AU - Malomo, Luigi
AU - Pietroni, Nico
ID - 6003
IS - 6
JF - Computer Graphics Forum
SN - 0167-7055
TI - State of the art on stylized fabrication
VL - 37
ER -
TY - CONF
AB - Network games are widely used as a model for selfish resource-allocation problems. In the classicalmodel, each player selects a path connecting her source and target vertices. The cost of traversingan edge depends on theload; namely, number of players that traverse it. Thus, it abstracts the factthat different users may use a resource at different times and for different durations, which playsan important role in determining the costs of the users in reality. For example, when transmittingpackets in a communication network, routing traffic in a road network, or processing a task in aproduction system, actual sharing and congestion of resources crucially depends on time.In [13], we introducedtimed network games, which add a time component to network games.Each vertexvin the network is associated with a cost function, mapping the load onvto theprice that a player pays for staying invfor one time unit with this load. Each edge in thenetwork is guarded by the time intervals in which it can be traversed, which forces the players tospend time in the vertices. In this work we significantly extend the way time can be referred toin timed network games. In the model we study, the network is equipped withclocks, and, as intimed automata, edges are guarded by constraints on the values of the clocks, and their traversalmay involve a reset of some clocks. We argue that the stronger model captures many realisticnetworks. The addition of clocks breaks the techniques we developed in [13] and we developnew techniques in order to show that positive results on classic network games carry over to thestronger timed setting.
AU - Avni, Guy
AU - Guha, Shibashis
AU - Kupferman, Orna
ID - 6005
SN - 1868-8969
TI - Timed network games with clocks
VL - 117
ER -
TY - JOUR
AB - Network games (NGs) are played on directed graphs and are extensively used in network design and analysis. Search problems for NGs include finding special strategy profiles such as a Nash equilibrium and a globally-optimal solution. The networks modeled by NGs may be huge. In formal verification, abstraction has proven to be an extremely effective technique for reasoning about systems with big and even infinite state spaces. We describe an abstraction-refinement methodology for reasoning about NGs. Our methodology is based on an abstraction function that maps the state space of an NG to a much smaller state space. We search for a global optimum and a Nash equilibrium by reasoning on an under- and an over-approximation defined on top of this smaller state space. When the approximations are too coarse to find such profiles, we refine the abstraction function. We extend the abstraction-refinement methodology to labeled networks, where the objectives of the players are regular languages. Our experimental results demonstrate the effectiveness of the methodology.
AU - Avni, Guy
AU - Guha, Shibashis
AU - Kupferman, Orna
ID - 6006
IS - 3
JF - Games
SN - 2073-4336
TI - An abstraction-refinement methodology for reasoning about network games
VL - 9
ER -
TY - JOUR
AB - The optic tectum (TeO), or superior colliculus, is a multisensory midbrain center that organizes spatially orienting responses to relevant stimuli. To define the stimulus with the highest priority at each moment, a network of reciprocal connections between the TeO and the isthmi promotes competition between concurrent tectal inputs. In the avian midbrain, the neurons mediating enhancement and suppression of tectal inputs are located in separate isthmic nuclei, facilitating the analysis of the neural processes that mediate competition. A specific subset of radial neurons in the intermediate tectal layers relay retinal inputs to the isthmi, but at present it is unclear whether separate neurons innervate individual nuclei or a single neural type sends a common input to several of them. In this study, we used in vitro neural tracing and cell-filling experiments in chickens to show that single neurons innervate, via axon collaterals, the three nuclei that comprise the isthmotectal network. This demonstrates that the input signals representing the strength of the incoming stimuli are simultaneously relayed to the mechanisms promoting both enhancement and suppression of the input signals. By performing in vivo recordings in anesthetized chicks, we also show that this common input generates synchrony between both antagonistic mechanisms, demonstrating that activity enhancement and suppression are closely coordinated. From a computational point of view, these results suggest that these tectal neurons constitute integrative nodes that combine inputs from different sources to drive in parallel several concurrent neural processes, each performing complementary functions within the network through different firing patterns and connectivity.
AU - Garrido-Charad, Florencia
AU - Vega Zuniga, Tomas A
AU - Gutiérrez-Ibáñez, Cristián
AU - Fernandez, Pedro
AU - López-Jury, Luciana
AU - González-Cabrera, Cristian
AU - Karten, Harvey J.
AU - Luksch, Harald
AU - Marín, Gonzalo J.
ID - 6010
IS - 32
JF - Proceedings of the National Academy of Sciences
SN - 0027-8424
TI - “Shepherd’s crook” neurons drive and synchronize the enhancing and suppressive mechanisms of the midbrain stimulus selection network
VL - 115
ER -
TY - CONF
AB - We establish a data-dependent notion of algorithmic stability for Stochastic Gradient Descent (SGD), and employ it to develop novel generalization bounds. This is in contrast to previous distribution-free algorithmic stability results for SGD which depend on the worst-case constants. By virtue of the data-dependent argument, our bounds provide new insights into learning with SGD on convex and non-convex problems. In the convex case, we show that the bound on the generalization error depends on the risk at the initialization point. In the non-convex case, we prove that the expected curvature of the objective function around the initialization point has crucial influence on the generalization error. In both cases, our results suggest a simple data-driven strategy to stabilize SGD by pre-screening its initialization. As a corollary, our results allow us to show optimistic generalization bounds that exhibit fast convergence rates for SGD subject to a vanishing empirical risk and low noise of stochastic gradient.
AU - Kuzborskij, Ilja
AU - Lampert, Christoph
ID - 6011
T2 - Proceedings of the 35 th International Conference on Machine Learning
TI - Data-dependent stability of stochastic gradient descent
VL - 80
ER -
TY - CONF
AB - We present an approach to identify concise equations from data using a shallow neural network approach. In contrast to ordinary black-box regression, this approach allows understanding functional relations and generalizing them from observed data to unseen parts of the parameter space. We show how to extend the class of learnable equations for a recently proposed equation learning network to include divisions, and we improve the learning and model selection strategy to be useful for challenging real-world data. For systems governed by analytical expressions, our method can in many cases identify the true underlying equation and extrapolate to unseen domains. We demonstrate its effectiveness by experiments on a cart-pendulum system, where only 2 random rollouts are required to learn the forward dynamics and successfully achieve the swing-up task.
AU - Sahoo, Subham
AU - Lampert, Christoph
AU - Martius, Georg S
ID - 6012
T2 - Proceedings of the 35th International Conference on Machine Learning
TI - Learning equations for extrapolation and control
VL - 80
ER -
TY - CONF
AB - We introduce Clover, a new library for efficient computation using low-precision data, providing mathematical routines required by fundamental methods in optimization and sparse recovery. Our library faithfully implements variants of stochastic quantization that guarantee convergence at low precision, and supports data formats from 4-bit quantized to 32-bit IEEE-754 on current Intel processors. In particular, we show that 4-bit can be implemented efficiently using Intel AVX despite the lack of native support for this data format. Experimental results with dot product, matrix-vector multiplication (MVM), gradient descent (GD), and iterative hard thresholding (IHT) demonstrate that the attainable speedups are in many cases close to linear with respect to the reduction of precision due to reduced data movement. Finally, for GD and IHT, we show examples of absolute speedup achieved by 4-bit versus 32-bit, by iterating until a given target error is achieved.
AU - Stojanov, Alen
AU - Smith, Tyler Michael
AU - Alistarh, Dan-Adrian
AU - Puschel, Markus
ID - 6031
T2 - 2018 IEEE International Workshop on Signal Processing Systems
TI - Fast quantized arithmetic on x86: Trading compute for data movement
VL - 2018-October
ER -
TY - JOUR
AB - The main result of this article is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even Δ-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec. Using a reduction to even Δ-matroids, we then extend the tractability result to larger classes of Δ-matroids that we call efficiently coverable. It properly includes classes that were known to be tractable before, namely, co-independent, compact, local, linear, and binary, with the following caveat:We represent Δ-matroids by lists of tuples, while the last two use a representation by matrices. Since an n ×n matrix can represent exponentially many tuples, our tractability result is not strictly stronger than the known algorithm for linear and binary Δ-matroids.
AU - Kazda, Alexandr
AU - Kolmogorov, Vladimir
AU - Rolinek, Michal
ID - 6032
IS - 2
JF - ACM Transactions on Algorithms
TI - Even delta-matroids and the complexity of planar boolean CSPs
VL - 15
ER -
TY - JOUR
AB - We establish the existence of a global solution for a new family of fluid-like equations, which are obtained in certain regimes in as the mean-field evolution of the supercurrent density in a (2D section of a) type-II superconductor with pinning and with imposed electric current. We also consider general vortex-sheet initial data, and investigate the uniqueness and regularity properties of the solution. For some choice of parameters, the equation under investigation coincides with the so-called lake equation from 2D shallow water fluid dynamics, and our analysis then leads to a new existence result for rough initial data.
AU - Duerinckx, Mitia
AU - Fischer, Julian L
ID - 606
IS - 5
JF - Annales de l'Institut Henri Poincare (C) Non Linear Analysis
TI - Well-posedness for mean-field evolutions arising in superconductivity
VL - 35
ER -
TY - JOUR
AB - Animal social networks are shaped by multiple selection pressures, including the need to ensure efficient communication and functioning while simultaneously limiting disease transmission. Social animals could potentially further reduce epidemic risk by altering their social networks in the presence of pathogens, yet there is currently no evidence for such pathogen-triggered responses. We tested this hypothesis experimentally in the ant Lasius niger using a combination of automated tracking, controlled pathogen exposure, transmission quantification, and temporally explicit simulations. Pathogen exposure induced behavioral changes in both exposed ants and their nestmates, which helped contain the disease by reinforcing key transmission-inhibitory properties of the colony's contact network. This suggests that social network plasticity in response to pathogens is an effective strategy for mitigating the effects of disease in social groups.
AU - Stroeymeyt, Nathalie
AU - Grasse, Anna V
AU - Crespi, Alessandro
AU - Mersch, Danielle
AU - Cremer, Sylvia
AU - Keller, Laurent
ID - 7
IS - 6417
JF - Science
SN - 10959203
TI - Social network plasticity decreases disease transmission in a eusocial insect
VL - 362
ER -
TY - JOUR
AB - We consider the totally asymmetric simple exclusion process in a critical scaling parametrized by a≥0, which creates a shock in the particle density of order aT−1/3, T the observation time. When starting from step initial data, we provide bounds on the limiting law which in particular imply that in the double limit lima→∞limT→∞ one recovers the product limit law and the degeneration of the correlation length observed at shocks of order 1. This result is shown to apply to a general last-passage percolation model. We also obtain bounds on the two-point functions of several airy processes.
AU - Nejjar, Peter
ID - 70
IS - 2
JF - Latin American Journal of Probability and Mathematical Statistics
SN - 1980-0436
TI - Transition to shocks in TASEP and decoupling of last passage times
VL - 15
ER -
TY - JOUR
AB - We consider the NP-hard problem of MAP-inference for undirected discrete graphical models. We propose a polynomial time and practically efficient algorithm for finding a part of its optimal solution. Specifically, our algorithm marks some labels of the considered graphical model either as (i) optimal, meaning that they belong to all optimal solutions of the inference problem; (ii) non-optimal if they provably do not belong to any solution. With access to an exact solver of a linear programming relaxation to the MAP-inference problem, our algorithm marks the maximal possible (in a specified sense) number of labels. We also present a version of the algorithm, which has access to a suboptimal dual solver only and still can ensure the (non-)optimality for the marked labels, although the overall number of the marked labels may decrease. We propose an efficient implementation, which runs in time comparable to a single run of a suboptimal dual solver. Our method is well-scalable and shows state-of-the-art results on computational benchmarks from machine learning and computer vision.
AU - Shekhovtsov, Alexander
AU - Swoboda, Paul
AU - Savchynskyy, Bogdan
ID - 703
IS - 7
JF - IEEE Transactions on Pattern Analysis and Machine Intelligence
SN - 01628828
TI - Maximum persistency via iterative relaxed inference with graphical models
VL - 40
ER -
TY - JOUR
AB - Although dopamine receptors D1 and D2 play key roles in hippocampal function, their synaptic localization within the hippocampus has not been fully elucidated. In order to understand precise functions of pre- or postsynaptic dopamine receptors (DRs), the development of protocols to differentiate pre- and postsynaptic DRs is essential. So far, most studies on determination and quantification of DRs did not discriminate between subsynaptic localization. Therefore, the aim of the study was to generate a robust workflow for the localization of DRs. This work provides the basis for future work on hippocampal DRs, in light that DRs may have different functions at pre- or postsynaptic sites. Synaptosomes from rat hippocampi isolated by a sucrose gradient protocol were prepared for super-resolution direct stochastic optical reconstruction microscopy (dSTORM) using Bassoon as a presynaptic zone and Homer1 as postsynaptic density marker. Direct labeling of primary validated antibodies against dopamine receptors D1 (D1R) and D2 (D2R) with Alexa Fluor 594 enabled unequivocal assignment of D1R and D2R to both, pre- and postsynaptic sites. D1R immunoreactivity clusters were observed within the presynaptic active zone as well as at perisynaptic sites at the edge of the presynaptic active zone. The results may be useful for the interpretation of previous studies and the design of future work on DRs in the hippocampus. Moreover, the reduction of the complexity of brain tissue by the use of synaptosomal preparations and dSTORM technology may represent a useful tool for synaptic localization of brain proteins.
AU - Miklosi, Andras
AU - Del Favero, Giorgia
AU - Bulat, Tanja
AU - Höger, Harald
AU - Shigemoto, Ryuichi
AU - Marko, Doris
AU - Lubec, Gert
ID - 705
IS - 6
JF - Molecular Neurobiology
TI - Super resolution microscopical localization of dopamine receptors 1 and 2 in rat hippocampal synaptosomes
VL - 55
ER -
TY - JOUR
AB - We examine recent magnetic torque measurements in two compounds, γ−Li2IrO3 and RuCl3, which have been discussed as possible realizations of the Kitaev model. The analysis of the reported discontinuity in torque, as an external magnetic field is rotated across the c axis in both crystals, suggests that they have a translationally invariant chiral spin order of the form ⟨Si⋅(Sj×Sk)⟩≠0 in the ground state and persisting over a very wide range of magnetic field and temperature. An extraordinary |B|B2 dependence of the torque for small fields, beside the usual B2 part, is predicted by the chiral spin order. Data for small fields are available for γ−Li2IrO3 and are found to be consistent with the prediction upon further analysis. Other experiments such as inelastic scattering and thermal Hall effect and several questions raised by the discovery of chiral spin order, including its topological consequences, are discussed.
AU - Modic, Kimberly A
AU - Ramshaw, B. J.
AU - Shekhter, A.
AU - Varma, C. M.
ID - 7058
IS - 20
JF - Physical Review B
SN - 2469-9950
TI - Chiral spin order in some purported Kitaev spin-liquid compounds
VL - 98
ER -
TY - JOUR
AB - Unusual behavior in quantum materials commonly arises from their effective low-dimensional physics, reflecting the underlying anisotropy in the spin and charge degrees of freedom. Here we introduce the magnetotropic coefficient k = ∂2F/∂θ2, the second derivative of the free energy F with respect to the magnetic field orientation θ in the crystal. We show that the magnetotropic coefficient can be quantitatively determined from a shift in the resonant frequency of a commercially available atomic force microscopy cantilever under magnetic field. This detection method enables part per 100 million sensitivity and the ability to measure magnetic anisotropy in nanogram-scale samples, as demonstrated on the Weyl semimetal NbP. Measurement of the magnetotropic coefficient in the spin-liquid candidate RuCl3 highlights its sensitivity to anisotropic phase transitions and allows a quantitative comparison to other thermodynamic coefficients via the Ehrenfest relations.
AU - Modic, Kimberly A
AU - Bachmann, Maja D.
AU - Ramshaw, B. J.
AU - Arnold, F.
AU - Shirer, K. R.
AU - Estry, Amelia
AU - Betts, J. B.
AU - Ghimire, Nirmal J.
AU - Bauer, E. D.
AU - Schmidt, Marcus
AU - Baenitz, Michael
AU - Svanidze, E.
AU - McDonald, Ross D.
AU - Shekhter, Arkady
AU - Moll, Philip J. W.
ID - 7059
IS - 1
JF - Nature Communications
SN - 2041-1723
TI - Resonant torsion magnetometry in anisotropic quantum materials
VL - 9
ER -
TY - JOUR
AB - The anomalous metallic state in the high-temperature superconducting cuprates is masked by superconductivity near a quantum critical point. Applying high magnetic fields to suppress superconductivity has enabled detailed studies of the normal state, yet the direct effect of strong magnetic fields on the metallic state is poorly understood. We report the high-field magnetoresistance of thin-film La2–xSrxCuO4 cuprate in the vicinity of the critical doping, 0.161 ≤ p ≤ 0.190. We find that the metallic state exposed by suppressing superconductivity is characterized by magnetoresistance that is linear in magnetic fields up to 80 tesla. The magnitude of the linear-in-field resistivity mirrors the magnitude and doping evolution of the well-known linear-in-temperature resistivity that has been associated with quantum criticality in high-temperature superconductors.
AU - Giraldo-Gallo, P.
AU - Galvis, J. A.
AU - Stegen, Z.
AU - Modic, Kimberly A
AU - Balakirev, F. F.
AU - Betts, J. B.
AU - Lian, X.
AU - Moir, C.
AU - Riggs, S. C.
AU - Wu, J.
AU - Bollinger, A. T.
AU - He, X.
AU - Božović, I.
AU - Ramshaw, B. J.
AU - McDonald, R. D.
AU - Boebinger, G. S.
AU - Shekhter, A.
ID - 7060
IS - 6401
JF - Science
SN - 0036-8075
TI - Scale-invariant magnetoresistance in a cuprate superconductor
VL - 361
ER -
TY - JOUR
AB - Weyl fermions are a recently discovered ingredient for correlated states of electronic matter. A key difficulty has been that real materials also contain non-Weyl quasiparticles, and disentangling the experimental signatures has proven challenging. Here we use magnetic fields up to 95 T to drive the Weyl semimetal TaAs far into its quantum limit, where only the purely chiral 0th Landau levels of the Weyl fermions are occupied. We find the electrical resistivity to be nearly independent of magnetic field up to 50 T: unusual for conventional metals but consistent with the chiral anomaly for Weyl fermions. Above 50 T we observe a two-order-of-magnitude increase in resistivity, indicating that a gap opens in the chiral Landau levels. Above 80 T we observe strong ultrasonic attenuation below 2 K, suggesting a mesoscopically textured state of matter. These results point the way to inducing new correlated states of matter in the quantum limit of Weyl semimetals.
AU - Ramshaw, B. J.
AU - Modic, Kimberly A
AU - Shekhter, Arkady
AU - Zhang, Yi
AU - Kim, Eun-Ah
AU - Moll, Philip J. W.
AU - Bachmann, Maja D.
AU - Chan, M. K.
AU - Betts, J. B.
AU - Balakirev, F.
AU - Migliori, A.
AU - Ghimire, N. J.
AU - Bauer, E. D.
AU - Ronning, F.
AU - McDonald, R. D.
ID - 7062
IS - 1
JF - Nature Communications
SN - 2041-1723
TI - Quantum limit transport and destruction of the Weyl nodes in TaAs
VL - 9
ER -
TY - JOUR
AB - The high-pressure synthesis and incommensurately modulated structure are reported for the new compound Sr2Pt8−xAs, with x = 0.715 (5). The structure consists of Sr2Pt3As layers alternating with Pt-only corrugated grids. Ab initio calculations predict a metallic character with a dominant role of the Pt d electrons. The electrical resistivity (ρ) and Seebeck coefficient confirm the metallic character, but surprisingly, ρ showed a near-flat temperature dependence. This observation fits the description of the Mooij correlation for electrical resistivity in disordered metals, originally developed for statistically distributed point defects. The discussed material has a long-range crystallographic order, but the high concentration of Pt vacancies, incommensurately ordered, strongly influences the electronic conduction properties. This result extends the range of validity of the Mooij correlation to long-range ordered incommensurately modulated vacancies. Motivated by the layered structure, the resistivity anisotropy was measured in a focused-ion-beam micro-fabricated well oriented single crystal. A low resistivity anisotropy indicates that the layers are electrically coupled and conduction channels along different directions are intermixed.
AU - Martino, Edoardo
AU - Arakcheeva, Alla
AU - Autès, Gabriel
AU - Pisoni, Andrea
AU - Bachmann, Maja D.
AU - Modic, Kimberly A
AU - Helm, Toni
AU - Yazyev, Oleg V.
AU - Moll, Philip J. W.
AU - Forró, László
AU - Katrych, Sergiy
ID - 7063
IS - 4
JF - IUCrJ
TI - Sr2Pt8−xAs: A layered incommensurately modulated metal with saturated resistivity
VL - 5
ER -
TY - CONF
AB - Training deep learning models has received tremendous research interest recently. In particular, there has been intensive research on reducing the communication cost of training when using multiple computational devices, through reducing the precision of the underlying data representation. Naturally, such methods induce system trade-offs—lowering communication precision could de-crease communication overheads and improve scalability; but, on the other hand, it can also reduce the accuracy of training. In this paper, we study this trade-off space, and ask:Can low-precision communication consistently improve the end-to-end performance of training modern neural networks, with no accuracy loss?From the performance point of view, the answer to this question may appear deceptively easy: compressing communication through low precision should help when the ratio between communication and computation is high. However, this answer is less straightforward when we try to generalize this principle across various neural network architectures (e.g., AlexNet vs. ResNet),number of GPUs (e.g., 2 vs. 8 GPUs), machine configurations(e.g., EC2 instances vs. NVIDIA DGX-1), communication primitives (e.g., MPI vs. NCCL), and even different GPU architectures(e.g., Kepler vs. Pascal). Currently, it is not clear how a realistic realization of all these factors maps to the speed up provided by low-precision communication. In this paper, we conduct an empirical study to answer this question and report the insights.
AU - Grubic, Demjan
AU - Tam, Leo
AU - Alistarh, Dan-Adrian
AU - Zhang, Ce
ID - 7116
SN - 2367-2005
T2 - Proceedings of the 21st International Conference on Extending Database Technology
TI - Synchronous multi-GPU training for deep learning with low-precision communications: An empirical study
ER -
TY - CONF
AB - Population protocols are a popular model of distributed computing, in which n agents with limited local state interact randomly, and cooperate to collectively compute global predicates. Inspired by recent developments in DNA programming, an extensive series of papers, across different communities, has examined the computability and complexity characteristics of this model. Majority, or consensus, is a central task in this model, in which agents need to collectively reach a decision as to which one of two states A or B had a higher initial count. Two metrics are important: the time that a protocol requires to stabilize to an output decision, and the state space size that each agent requires to do so. It is known that majority requires Ω(log log n) states per agent to allow for fast (poly-logarithmic time) stabilization, and that O(log2 n) states are sufficient. Thus, there is an exponential gap between the space upper and lower bounds for this problem. This paper addresses this question.
On the negative side, we provide a new lower bound of Ω(log n) states for any protocol which stabilizes in O(n1–c) expected time, for any constant c > 0. This result is conditional on monotonicity and output assumptions, satisfied by all known protocols. Technically, it represents a departure from previous lower bounds, in that it does not rely on the existence of dense configurations. Instead, we introduce a new generalized surgery technique to prove the existence of incorrect executions for any algorithm which would contradict the lower bound. Subsequently, our lower bound also applies to general initial configurations, including ones with a leader. On the positive side, we give a new algorithm for majority which uses O(log n) states, and stabilizes in O(log2 n) expected time. Central to the algorithm is a new leaderless phase clock technique, which allows agents to synchronize in phases of Θ(n log n) consecutive interactions using O(log n) states per agent, exploiting a new connection between population protocols and power-of-two-choices load balancing mechanisms. We also employ our phase clock to build a leader election algorithm with a state space of size O(log n), which stabilizes in O(log2 n) expected time.
AU - Alistarh, Dan-Adrian
AU - Aspnes, James
AU - Gelashvili, Rati
ID - 7123
SN - 9781611975031
T2 - Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms
TI - Space-optimal majority in population protocols
ER -
TY - JOUR
AB - In the Minimum Description Length (MDL) principle, learning from the data is equivalent to an optimal coding problem. We show that the codes that achieve optimal compression in MDL are critical in a very precise sense. First, when they are taken as generative models of samples, they generate samples with broad empirical distributions and with a high value of the relevance, defined as the entropy of the empirical frequencies. These results are derived for different statistical models (Dirichlet model, independent and pairwise dependent spin models, and restricted Boltzmann machines). Second, MDL codes sit precisely at a second order phase transition point where the symmetry between the sampled outcomes is spontaneously broken. The order parameter controlling the phase transition is the coding cost of the samples. The phase transition is a manifestation of the optimality of MDL codes, and it arises because codes that achieve a higher compression do not exist. These results suggest a clear interpretation of the widespread occurrence of statistical criticality as a characterization of samples which are maximally informative on the underlying generative process.
AU - Cubero, Ryan J
AU - Marsili, Matteo
AU - Roudi, Yasser
ID - 7126
IS - 10
JF - Entropy
KW - Minimum Description Length
KW - normalized maximum likelihood
KW - statistical criticality
KW - phase transitions
KW - large deviations
SN - 1099-4300
TI - Minimum description length codes are critical
VL - 20
ER -
TY - JOUR
AB - Escaping local optima is one of the major obstacles to function optimisation. Using the metaphor of a fitness landscape, local optima correspond to hills separated by fitness valleys that have to be overcome. We define a class of fitness valleys of tunable difficulty by considering their length, representing the Hamming path between the two optima and their depth, the drop in fitness. For this function class we present a runtime comparison between stochastic search algorithms using different search strategies. The (1+1) EA is a simple and well-studied evolutionary algorithm that has to jump across the valley to a point of higher fitness because it does not accept worsening moves (elitism). In contrast, the Metropolis algorithm and the Strong Selection Weak Mutation (SSWM) algorithm, a famous process in population genetics, are both able to cross the fitness valley by accepting worsening moves. We show that the runtime of the (1+1) EA depends critically on the length of the valley while the runtimes of the non-elitist algorithms depend crucially on the depth of the valley. Moreover, we show that both SSWM and Metropolis can also efficiently optimise a rugged function consisting of consecutive valleys.
AU - Oliveto, Pietro
AU - Paixao, Tiago
AU - Pérez Heredia, Jorge
AU - Sudholt, Dirk
AU - Trubenova, Barbora
ID - 723
IS - 5
JF - Algorithmica
TI - How to escape local optima in black box optimisation when non elitism outperforms elitism
VL - 80
ER -
TY - JOUR
AB - The recent demand of multifunctional materials and devices for advanced applications in energy conversion and data storage resulted into a revival of multiferroics, that is, materials characterized by the coexistence of ferromagnetism and ferroelectricity. Despite intense efforts made in the past decade, single-phase room temperature multiferroics are yet to be discovered/fabricated. Nanostructured ferroic materials could potentially exhibit multiferroism since a high fraction of their atoms/ions are superficial, thereby altering significantly the properties of the bulk phase. Alternately, a magnetic order can be induced into ferroelectric materials upon aliovalent doping with magnetic ions. Here, we report on the synthesis of aggregate-free single-phase transition-metal-doped BaTiO3 quasi-monodisperse cuboidal nanocrystals (NC) which exhibit multiferroic properties at room temperature and can be suitable for applications in data storage. The proposed synthetic route allows the inclusion of a high concentration of magnetic ions such as Mn+ (M = Cr, Mn, Fe, Co) up to a nominal concentration of 4% without the formation of any secondary phase. The size of the nanocrystals was controlled in a wide range from ∼15 up to ∼70 nm by varying the reaction time from 48 to 144 h. The presence of unpaired electrons and their magnetic ordering have been probed by electron paramagnetic resonance spectroscopy (EPR), and a vibrating sample magnetometer (VSM). Likewise, an acentric structure, associated with the existence of a dielectric polarization, was observed by lattice dynamics analysis and piezoresponse force microscopy (PFM). These results show that high-quality titanium-containing perovskite nanocrystals which display multiferroic properties at room temperature can be fabricated via soft solution-based synthetic routes, and the properties of these materials can be modulated by changing the size of the nanocrystals and the concentration of the dopant thereby opening the door to the design and study of single-phase multiferroic materials.
AU - Costanzo, Tommaso
AU - McCracken, John
AU - Rotaru, Aurelian
AU - Caruntu, Gabriel
ID - 7271
IS - 9
JF - ACS Applied Nano Materials
SN - 2574-0970
TI - Quasi-monodisperse transition-metal-doped BaTiO3 (M = Cr, Mn, Fe, Co) colloidal nanocrystals with multiferroic properties
VL - 1
ER -
TY - JOUR
AB - Solid alkali metal carbonates are universal passivation layer components of intercalation battery materials and common side products in metal‐O2 batteries, and are believed to form and decompose reversibly in metal‐O2/CO2 cells. In these cathodes, Li2CO3 decomposes to CO2 when exposed to potentials above 3.8 V vs. Li/Li+. However, O2 evolution, as would be expected according to the decomposition reaction 2 Li2CO3→4 Li++4 e−+2 CO2+O2, is not detected. O atoms are thus unaccounted for, which was previously ascribed to unidentified parasitic reactions. Here, we show that highly reactive singlet oxygen (1O2) forms upon oxidizing Li2CO3 in an aprotic electrolyte and therefore does not evolve as O2. These results have substantial implications for the long‐term cyclability of batteries: they underpin the importance of avoiding 1O2 in metal‐O2 batteries, question the possibility of a reversible metal‐O2/CO2 battery based on a carbonate discharge product, and help explain the interfacial reactivity of transition‐metal cathodes with residual Li2CO3.
AU - Mahne, Nika
AU - Renfrew, Sara E.
AU - McCloskey, Bryan D.
AU - Freunberger, Stefan Alexander
ID - 7277
IS - 19
JF - Angewandte Chemie International Edition
SN - 1433-7851
TI - Electrochemical oxidation of Lithium Carbonate generates singlet oxygen
VL - 57
ER -
TY - JOUR
AB - Hydrogelation, the self-assembly of molecules into soft, water-loaded networks, is one way to bridge the structural gap between single molecules and functional materials. The potential of hydrogels, such as those based on perylene bisimides, lies in their chemical, physical, optical, and electronic properties, which are governed by the supramolecular structure of the gel. However, the structural motifs and their precise role for long-range conductivity are yet to be explored. Here, we present a comprehensive structural picture of a perylene bisimide hydrogel, suggesting that its long-range conductivity is limited by charge transfer between electronic backbones. We reveal nanocrystalline ribbon-like structures as the electronic and structural backbone units between which charge transfer is mediated by polar solvent bridges. We exemplify this effect with sensing, where exposure to polar vapor enhances conductivity by 5 orders of magnitude, emphasizing the crucial role of the interplay between structural motif and surrounding medium for the rational design of devices based on nanocrystalline hydrogels.
AU - Burian, Max
AU - Rigodanza, Francesco
AU - Demitri, Nicola
AU - D̵ord̵ević, Luka
AU - Marchesan, Silvia
AU - Steinhartova, Tereza
AU - Letofsky-Papst, Ilse
AU - Khalakhan, Ivan
AU - Mourad, Eléonore
AU - Freunberger, Stefan Alexander
AU - Amenitsch, Heinz
AU - Prato, Maurizio
AU - Syrgiannis, Zois
ID - 7285
IS - 6
JF - ACS Nano
SN - 1936-0851
TI - Inter-backbone charge transfer as prerequisite for long-range conductivity in perylene bisimide hydrogels
VL - 12
ER -
TY - JOUR
AB - The solid electrolyte interphase (SEI) in Li and Na ion batteries forms when highly reducing or oxidizing electrode materials come into contact with a liquid organic electrolyte. Its ability to form a mechanically robust, ion-conducting, and electron-insulating layer critically determines performance, cycle life, and safety. Li or Na alkyl carbonates (LiAC and NaAC, respectively) are lead SEI components in state-of-the-art carbonate based electrolytes, and our fundamental understanding of their charge transport and mechanical properties may hold the key to designing electrolytes forming an improved SEI. We synthesized a homologous series of LiACs and NaACs from methyl to octyl analogues and characterized them with respect to structure, ionic conductivity, and stiffness. The compounds assume layered structures except for the lithium methyl carbonate. Room-temperature conductivities were found to be ∼10–9 S cm–1 for lithium methyl carbonate, <10–12 S cm–1 for the other LiACs, and <10–12 S cm–1 for the NaACs with ion transport mostly attributed to grain boundaries. While LiACs show stiffnesses of ∼1 GPa, NaACs become significantly softer with increasing chain lengths. These findings will help to more precisely interpret the complex results from charge transport and mechanical characterization of real SEIs and can give a rationale for influencing the SEI’s mechanical properties via the electrolyte.
AU - Schafzahl, Lukas
AU - Ehmann, Heike
AU - Kriechbaum, Manfred
AU - Sattelkow, Jürgen
AU - Ganner, Thomas
AU - Plank, Harald
AU - Wilkening, Martin
AU - Freunberger, Stefan Alexander
ID - 7286
IS - 10
JF - Chemistry of Materials
SN - 0897-4756
TI - Long-chain Li and Na alkyl carbonates as solid electrolyte interphase components: Structure, ion transport, and mechanical properties
VL - 30
ER -
TY - JOUR
AB - Passivation layers on electrode materials are ubiquitous in nonaqueous battery chemistries and strongly govern performance and lifetime. They comprise breakdown products of the electrolyte including carbonate, alkyl carbonates, alkoxides, carboxylates, and polymers. Parasitic chemistry in metal–O2 batteries forms similar products and is tied to the deviation of the O2 balance from the ideal stoichiometry during formation/decomposition of alkaline peroxides or superoxides. Accurate and integral quantification of carbonaceous species and peroxides or superoxides in battery electrodes remains, however, elusive. We present a refined procedure to quantify them accurately and sensitively by pointing out and rectifying pitfalls of previous procedures. Carbonaceous compounds are differentiated into inorganic and organic ones. We combine mass and UV–vis spectrometry to quantify evolved O2 and complexed peroxide and CO2 evolved from carbonaceous compounds by acid treatment and Fenton’s reaction. The capabilities of the method are exemplified by means of Li–O2 and Na–O2 cathodes, graphite anodes, and LiNi0.8Co0.15Al0.05O2 cathodes.
AU - Schafzahl, Bettina
AU - Mourad, Eléonore
AU - Schafzahl, Lukas
AU - Petit, Yann K.
AU - Raju, Anjana R.
AU - Thotiyl, Musthafa Ottakam
AU - Wilkening, Martin
AU - Slugovc, Christian
AU - Freunberger, Stefan Alexander
ID - 7287
IS - 1
JF - ACS Energy Letters
SN - 2380-8195
TI - Quantifying total superoxide, peroxide, and carbonaceous compounds in metal–O2 batteries and the solid electrolyte interphase
VL - 3
ER -
TY - JOUR
AB - This paper is devoted to automatic competitive analysis of real-time scheduling algorithms for firm-deadline tasksets, where only completed tasks con- tribute some utility to the system. Given such a taskset T , the competitive ratio of an on-line scheduling algorithm A for T is the worst-case utility ratio of A over the utility achieved by a clairvoyant algorithm. We leverage the theory of quantitative graph games to address the competitive analysis and competitive synthesis problems. For the competitive analysis case, given any taskset T and any finite-memory on- line scheduling algorithm A , we show that the competitive ratio of A in T can be computed in polynomial time in the size of the state space of A . Our approach is flexible as it also provides ways to model meaningful constraints on the released task sequences that determine the competitive ratio. We provide an experimental study of many well-known on-line scheduling algorithms, which demonstrates the feasibility of our competitive analysis approach that effectively replaces human ingenuity (required Preliminary versions of this paper have appeared in Chatterjee et al. ( 2013 , 2014 ). B Andreas Pavlogiannis pavlogiannis@ist.ac.at Krishnendu Chatterjee krish.chat@ist.ac.at Alexander Kößler koe@ecs.tuwien.ac.at Ulrich Schmid s@ecs.tuwien.ac.at 1 IST Austria (Institute of Science and Technology Austria), Am Campus 1, 3400 Klosterneuburg, Austria 2 Embedded Computing Systems Group, Vienna University of Technology, Treitlstrasse 3, 1040 Vienna, Austria 123 Real-Time Syst for finding worst-case scenarios) by computing power. For the competitive synthesis case, we are just given a taskset T , and the goal is to automatically synthesize an opti- mal on-line scheduling algorithm A , i.e., one that guarantees the largest competitive ratio possible for T . We show how the competitive synthesis problem can be reduced to a two-player graph game with partial information, and establish that the compu- tational complexity of solving this game is Np -complete. The competitive synthesis problem is hence in Np in the size of the state space of the non-deterministic labeled transition system encoding the taskset. Overall, the proposed framework assists in the selection of suitable scheduling algorithms for a given taskset, which is in fact the most common situation in real-time systems design.
AU - Chatterjee, Krishnendu
AU - Pavlogiannis, Andreas
AU - Kößler, Alexander
AU - Schmid, Ulrich
ID - 738
IS - 1
JF - Real-Time Systems
TI - Automated competitive analysis of real time scheduling with graph games
VL - 54
ER -
TY - CONF
AB - Proofs of space (PoS) [Dziembowski et al., CRYPTO'15] are proof systems where a prover can convince a verifier that he "wastes" disk space. PoS were introduced as a more ecological and economical replacement for proofs of work which are currently used to secure blockchains like Bitcoin. In this work we investigate extensions of PoS which allow the prover to embed useful data into the dedicated space, which later can be recovered. Our first contribution is a security proof for the original PoS from CRYPTO'15 in the random oracle model (the original proof only applied to a restricted class of adversaries which can store a subset of the data an honest prover would store). When this PoS is instantiated with recent constructions of maximally depth robust graphs, our proof implies basically optimal security. As a second contribution we show three different extensions of this PoS where useful data can be embedded into the space required by the prover. Our security proof for the PoS extends (non-trivially) to these constructions. We discuss how some of these variants can be used as proofs of catalytic space (PoCS), a notion we put forward in this work, and which basically is a PoS where most of the space required by the prover can be used to backup useful data. Finally we discuss how one of the extensions is a candidate construction for a proof of replication (PoR), a proof system recently suggested in the Filecoin whitepaper.
AU - Pietrzak, Krzysztof Z
ID - 7407
SN - 1868-8969
T2 - 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
TI - Proofs of catalytic space
VL - 124
ER -
TY - JOUR
AB - We give a detailed and easily accessible proof of Gromov’s Topological Overlap Theorem. Let X be a finite simplicial complex or, more generally, a finite polyhedral cell complex of dimension d. Informally, the theorem states that if X has sufficiently strong higher-dimensional expansion properties (which generalize edge expansion of graphs and are defined in terms of cellular cochains of X) then X has the following topological overlap property: for every continuous map (Formula presented.) there exists a point (Formula presented.) that is contained in the images of a positive fraction (Formula presented.) of the d-cells of X. More generally, the conclusion holds if (Formula presented.) is replaced by any d-dimensional piecewise-linear manifold M, with a constant (Formula presented.) that depends only on d and on the expansion properties of X, but not on M.
AU - Dotterrer, Dominic
AU - Kaufman, Tali
AU - Wagner, Uli
ID - 742
IS - 1
JF - Geometriae Dedicata
TI - On expansion and topological overlap
VL - 195
ER -
TY - JOUR
AB - The coupling between magnetic and electric subsystems in composites of ferromagnetic and ferroelectric phases is a product property that is facilitated by mechanical strain that arises due to magnetostriction and the piezoelectric effect in the constituent phases. Such multiferroic composites are of immense interests for studies on the physics of electromagnetic coupling and for use in a variety of applications. Here, we focus on magneto-electric (ME) coupling in nanocomposites. Particular emphasis is on core-shell particles and coaxial fibers, thin film heterostructures, and planar structures with a variety of mechanical connectivity. A brief review of models that predict strong ME effects in nanostructures is followed by synthesis and characterization. Core-shell particulate composites can be prepared by hydrothermal processes and chemical or deoxyribonucleic acid-assisted assembly. Electrospinning techniques have been utilized to prepare defect free core-shell nanofibers. Core-shell particles and fibers can be assembled into superstructures with the aid of magnetic and electric fields and characterized for possible use in advanced technologies. Chemical-vapor deposition techniques have been shown to be effective for the preparation of heterostructures of ferrites and ferroelectrics. Exotic planar multiferroic structures with potential for enhancing ME coupling strengths are also considered. Scanning probe microscopy techniques are ideal for probing the nature of direct- and converse-ME coupling in individual nanostructures. Magnetoelectric characterization of assemblies of nanocomposites can be done by ME voltage coefficient, magnetic field induced polarization, and magneto-dielectric effects. We conclude with a brief discussion on possible avenues for strengthening the product properties in the nanocomposites.
AU - Viehland, Dwight
AU - Li, Jie Fang
AU - Yang, Yaodong
AU - Costanzo, Tommaso
AU - Yourdkhani, Amin
AU - Caruntu, Gabriel
AU - Zhou, Peng
AU - Zhang, Tianjin
AU - Li, Tianqian
AU - Gupta, Arunava
AU - Popov, Maksym
AU - Srinivasan, Gopalan
ID - 7458
IS - 6
JF - Journal of Applied Physics
SN - 0021-8979
TI - Tutorial: Product properties in multiferroic nanocomposites
VL - 124
ER -
TY - GEN
AB - We prove that any convex body in the plane can be partitioned into m convex parts of equal areas and perimeters for any integer m≥2; this result was previously known for prime powers m=pk. We also give a higher-dimensional generalization.
AU - Akopyan, Arseniy
AU - Avvakumov, Sergey
AU - Karasev, Roman
ID - 75
TI - Convex fair partitions into arbitrary number of pieces
ER -
TY - JOUR
AB - Consider a fully-connected synchronous distributed system consisting of n nodes, where up to f nodes may be faulty and every node starts in an arbitrary initial state. In the synchronous C-counting problem, all nodes need to eventually agree on a counter that is increased by one modulo C in each round for given C>1. In the self-stabilising firing squad problem, the task is to eventually guarantee that all non-faulty nodes have simultaneous responses to external inputs: if a subset of the correct nodes receive an external “go” signal as input, then all correct nodes should agree on a round (in the not-too-distant future) in which to jointly output a “fire” signal. Moreover, no node should generate a “fire” signal without some correct node having previously received a “go” signal as input. We present a framework reducing both tasks to binary consensus at very small cost. For example, we obtain a deterministic algorithm for self-stabilising Byzantine firing squads with optimal resilience f<n/3, asymptotically optimal stabilisation and response time O(f), and message size O(log f). As our framework does not restrict the type of consensus routines used, we also obtain efficient randomised solutions.
AU - Lenzen, Christoph
AU - Rybicki, Joel
ID - 76
JF - Distributed Computing
TI - Near-optimal self-stabilising counting and firing squads
ER -
TY - JOUR
AB - Motor output varies along the rostro-caudal axis of the tetrapod spinal cord. At limb levels, ∼60 motor pools control the alternation of flexor and extensor muscles about each joint, whereas at thoracic levels as few as 10 motor pools supply muscle groups that support posture, inspiration, and expiration. Whether such differences in motor neuron identity and muscle number are associated with segmental distinctions in interneuron diversity has not been resolved. We show that select combinations of nineteen transcription factors that specify lumbar V1 inhibitory interneurons generate subpopulations enriched at limb and thoracic levels. Specification of limb and thoracic V1 interneurons involves the Hox gene Hoxc9 independently of motor neurons. Thus, early Hox patterning of the spinal cord determines the identity of V1 interneurons and motor neurons. These studies reveal a developmental program of V1 interneuron diversity, providing insight into the organization of inhibitory interneurons associated with differential motor output.
AU - Sweeney, Lora Beatrice Jaeger
AU - Bikoff, Jay B.
AU - Gabitto, Mariano I.
AU - Brenner-Morton, Susan
AU - Baek, Myungin
AU - Yang, Jerry H.
AU - Tabak, Esteban G.
AU - Dasen, Jeremy S.
AU - Kintner, Christopher R.
AU - Jessell, Thomas M.
ID - 7698
IS - 2
JF - Neuron
SN - 0896-6273
TI - Origin and segmental diversity of spinal inhibitory interneurons
VL - 97
ER -
TY - JOUR
AB - Holes confined in quantum dots have gained considerable interest in the past few years due to their potential as spin qubits. Here we demonstrate two-axis control of a spin 3/2 qubit in natural Ge. The qubit is formed in a hut wire double quantum dot device. The Pauli spin blockade principle allowed us to demonstrate electric dipole spin resonance by applying a radio frequency electric field to one of the electrodes defining the double quantum dot. Coherent hole spin oscillations with Rabi frequencies reaching 140 MHz are demonstrated and dephasing times of 130 ns are measured. The reported results emphasize the potential of Ge as a platform for fast and electrically tunable hole spin qubit devices.
AU - Watzinger, Hannes
AU - Kukucka, Josip
AU - Vukusic, Lada
AU - Gao, Fei
AU - Wang, Ting
AU - Schäffler, Friedrich
AU - Zhang, Jian
AU - Katsaros, Georgios
ID - 77
IS - 3902
JF - Nature Communications
TI - A germanium hole spin qubit
VL - 9
ER -
TY - JOUR
AB - Male pattern baldness (MPB) is a sex-limited, age-related, complex trait. We study MPB genetics in 205,327 European males from the UK Biobank. Here we show that MPB is strongly heritable and polygenic, with pedigree-heritability of 0.62 (SE = 0.03) estimated from close relatives, and SNP-heritability of 0.39 (SE = 0.01) from conventionally-unrelated males. We detect 624 near-independent genome-wide loci, contributing SNP-heritability of 0.25 (SE = 0.01), of which 26 X-chromosome loci explain 11.6%. Autosomal genetic variance is enriched for common variants and regions of lower linkage disequilibrium. We identify plausible genetic correlations between MPB and multiple sex-limited markers of earlier puberty, increased bone mineral density (rg = 0.15) and pancreatic β-cell function (rg = 0.12). Correlations with reproductive traits imply an effect on fitness, consistent with an estimated linear selection gradient of -0.018 per MPB standard deviation. Overall, we provide genetic insights into MPB: a phenotype of interest in its own right, with value as a model sex-limited, complex trait.
AU - Yap, Chloe X.
AU - Sidorenko, Julia
AU - Wu, Yang
AU - Kemper, Kathryn E.
AU - Yang, Jian
AU - Wray, Naomi R.
AU - Robinson, Matthew Richard
AU - Visscher, Peter M.
ID - 7712
JF - Nature Communications
SN - 2041-1723
TI - Dissection of genetic variation and evidence for pleiotropy in male pattern baldness
VL - 9
ER -
TY - JOUR
AB - There are mean differences in complex traits among global human populations. We hypothesize that part of the phenotypic differentiation is due to natural selection. To address this hypothesis, we assess the differentiation in allele frequencies of trait-associated SNPs among African, Eastern Asian, and European populations for ten complex traits using data of large sample size (up to ~405,000). We show that SNPs associated with height (P=2.46×10−5), waist-to-hip ratio (P=2.77×10−4), and schizophrenia (P=3.96×10−5) are significantly more differentiated among populations than matched “control” SNPs, suggesting that these trait-associated SNPs have undergone natural selection. We further find that SNPs associated with height (P=2.01×10−6) and schizophrenia (P=5.16×10−18) show significantly higher variance in linkage disequilibrium (LD) scores across populations than control SNPs. Our results support the hypothesis that natural selection has shaped the genetic differentiation of complex traits, such as height and schizophrenia, among worldwide populations.
AU - Guo, Jing
AU - Wu, Yang
AU - Zhu, Zhihong
AU - Zheng, Zhili
AU - Trzaskowski, Maciej
AU - Zeng, Jian
AU - Robinson, Matthew Richard
AU - Visscher, Peter M.
AU - Yang, Jian
ID - 7713
JF - Nature Communications
SN - 2041-1723
TI - Global genetic differentiation of complex traits shaped by natural selection in humans
VL - 9
ER -
TY - JOUR
AB - Health risk factors such as body mass index (BMI) and serum cholesterol are associated with many common diseases. It often remains unclear whether the risk factors are cause or consequence of disease, or whether the associations are the result of confounding. We develop and apply a method (called GSMR) that performs a multi-SNP Mendelian randomization analysis using summary-level data from genome-wide association studies to test the causal associations of BMI, waist-to-hip ratio, serum cholesterols, blood pressures, height, and years of schooling (EduYears) with common diseases (sample sizes of up to 405,072). We identify a number of causal associations including a protective effect of LDL-cholesterol against type-2 diabetes (T2D) that might explain the side effects of statins on T2D, a protective effect of EduYears against Alzheimer’s disease, and bidirectional associations with opposite effects (e.g., higher BMI increases the risk of T2D but the effect of T2D on BMI is negative).
AU - Zhu, Zhihong
AU - Zheng, Zhili
AU - Zhang, Futao
AU - Wu, Yang
AU - Trzaskowski, Maciej
AU - Maier, Robert
AU - Robinson, Matthew Richard
AU - McGrath, John J.
AU - Visscher, Peter M.
AU - Wray, Naomi R.
AU - Yang, Jian
ID - 7714
JF - Nature Communications
SN - 2041-1723
TI - Causal associations between risk factors and common diseases inferred from GWAS summary data
VL - 9
ER -
TY - JOUR
AB - Preference for mates with similar phenotypes; that is, assortative mating, is widely observed in humans1,2,3,4,5 and has evolutionary consequences6,7,8. Under Fisher's classical theory6, assortative mating is predicted to induce a signature in the genome at trait-associated loci that can be detected and quantified. Here, we develop and apply a method to quantify assortative mating on a specific trait by estimating the correlation (θ) between genetic predictors of the trait from single nucleotide polymorphisms on odd- versus even-numbered chromosomes. We show by theory and simulation that the effect of assortative mating can be quantified in the presence of population stratification. We applied this approach to 32 complex traits and diseases using single nucleotide polymorphism data from ~400,000 unrelated individuals of European ancestry. We found significant evidence of assortative mating for height (θ = 3.2%) and educational attainment (θ = 2.7%), both of which were consistent with theoretical predictions. Overall, our results imply that assortative mating involves multiple traits and affects the genomic architecture of loci that are associated with these traits, and that the consequence of mate choice can be detected from a random sample of genomes.
AU - Yengo, Loic
AU - Robinson, Matthew Richard
AU - Keller, Matthew C.
AU - Kemper, Kathryn E.
AU - Yang, Yuanhao
AU - Trzaskowski, Maciej
AU - Gratten, Jacob
AU - Turley, Patrick
AU - Cesarini, David
AU - Benjamin, Daniel J.
AU - Wray, Naomi R.
AU - Goddard, Michael E.
AU - Yang, Jian
AU - Visscher, Peter M.
ID - 7715
IS - 12
JF - Nature Human Behaviour
SN - 2397-3374
TI - Imprint of assortative mating on the human genome
VL - 2
ER -
TY - JOUR
AB - Genomic prediction has the potential to contribute to precision medicine. However, to date, the utility of such predictors is limited due to low accuracy for most traits. Here theory and simulation study are used to demonstrate that widespread pleiotropy among phenotypes can be utilised to improve genomic risk prediction. We show how a genetic predictor can be created as a weighted index that combines published genome-wide association study (GWAS) summary statistics across many different traits. We apply this framework to predict risk of schizophrenia and bipolar disorder in the Psychiatric Genomics consortium data, finding substantial heterogeneity in prediction accuracy increases across cohorts. For six additional phenotypes in the UK Biobank data, we find increases in prediction accuracy ranging from 0.7% for height to 47% for type 2 diabetes, when using a multi-trait predictor that combines published summary statistics from multiple traits, as compared to a predictor based only on one trait.
AU - Maier, Robert M.
AU - Zhu, Zhihong
AU - Lee, Sang Hong
AU - Trzaskowski, Maciej
AU - Ruderfer, Douglas M.
AU - Stahl, Eli A.
AU - Ripke, Stephan
AU - Wray, Naomi R.
AU - Yang, Jian
AU - Visscher, Peter M.
AU - Robinson, Matthew Richard
ID - 7716
JF - Nature Communications
SN - 2041-1723
TI - Improving genetic prediction by leveraging genetic correlations among human diseases and traits
VL - 9
ER -
TY - JOUR
AB - Background: DNA methylation levels change along with age, but few studies have examined the variation in the rate of such changes between individuals.
Methods: We performed a longitudinal analysis to quantify the variation in the rate of change of DNA methylation between individuals using whole blood DNA methylation array profiles collected at 2–4 time points (N = 2894) in 954 individuals (67–90 years).
Results: After stringent quality control, we identified 1507 DNA methylation CpG sites (rsCpGs) with statistically significant variation in the rate of change (random slope) of DNA methylation among individuals in a mixed linear model analysis. Genes in the vicinity of these rsCpGs were found to be enriched in Homeobox transcription factors and the Wnt signalling pathway, both of which are related to ageing processes. Furthermore, we investigated the SNP effect on the random slope. We found that 4 out of 1507 rsCpGs had one significant (P < 5 × 10−8/1507) SNP effect and 343 rsCpGs had at least one SNP effect (436 SNP-probe pairs) reaching genome-wide significance (P < 5 × 10−8). Ninety-five percent of the significant (P < 5 × 10−8) SNPs are on different chromosomes from their corresponding probes.
Conclusions: We identified CpG sites that have variability in the rate of change of DNA methylation between individuals, and our results suggest a genetic basis of this variation. Genes around these CpG sites have been reported to be involved in the ageing process.
AU - Zhang, Qian
AU - Marioni, Riccardo E
AU - Robinson, Matthew Richard
AU - Higham, Jon
AU - Sproul, Duncan
AU - Wray, Naomi R
AU - Deary, Ian J
AU - McRae, Allan F
AU - Visscher, Peter M
ID - 7717
IS - 1
JF - Genome Medicine
SN - 1756-994X
TI - Genotype effects contribute to variation in longitudinal methylome patterns in older people
VL - 10
ER -
TY - JOUR
AB - Flores Island, Indonesia, was inhabited by the small-bodied hominin species Homo floresiensis, which has an unknown evolutionary relationship to modern humans. This island is also home to an extant human pygmy population. Here we describe genome-scale single-nucleotide polymorphism data and whole-genome sequences from a contemporary human pygmy population living on Flores near the cave where H. floresiensis was found. The genomes of Flores pygmies reveal a complex history of admixture with Denisovans and Neanderthals but no evidence for gene flow with other archaic hominins. Modern individuals bear the signatures of recent positive selection encompassing the FADS (fatty acid desaturase) gene cluster, likely related to diet, and polygenic selection acting on standing variation that contributed to their short-stature phenotype. Thus, multiple independent instances of hominin insular dwarfism occurred on Flores.
AU - Tucci, Serena
AU - Vohr, Samuel H.
AU - McCoy, Rajiv C.
AU - Vernot, Benjamin
AU - Robinson, Matthew Richard
AU - Barbieri, Chiara
AU - Nelson, Brad J.
AU - Fu, Wenqing
AU - Purnomo, Gludhug A.
AU - Sudoyo, Herawati
AU - Eichler, Evan E.
AU - Barbujani, Guido
AU - Visscher, Peter M.
AU - Akey, Joshua M.
AU - Green, Richard E.
ID - 7718
IS - 6401
JF - Science
SN - 0036-8075
TI - Evolutionary history and adaptation of a human pygmy population of Flores Island, Indonesia
VL - 361
ER -
TY - JOUR
AB - The availability of genome-wide genetic data on hundreds of thousands of people has led to an equally rapid growth in methodologies available to analyse these data. While the motivation for undertaking genome-wide association studies (GWAS) is identification of genetic markers associated with complex traits, once generated these data can be used for many other analyses. GWAS have demonstrated that complex traits exhibit a highly polygenic genetic architecture, often with shared genetic risk factors across traits. New methods to analyse data from GWAS are increasingly being used to address a diverse set of questions about the aetiology of complex traits and diseases, including psychiatric disorders. Here, we give an overview of some of these methods and present examples of how they have contributed to our understanding of psychiatric disorders. We consider: (i) estimation of the extent of genetic influence on traits, (ii) uncovering of shared genetic control between traits, (iii) predictions of genetic risk for individuals, (iv) uncovering of causal relationships between traits, (v) identifying causal single-nucleotide polymorphisms and genes or (vi) the detection of genetic heterogeneity. This classification helps organise the large number of recently developed methods, although some could be placed in more than one category. While some methods require GWAS data on individual people, others simply use GWAS summary statistics data, allowing novel well-powered analyses to be conducted at a low computational burden.
AU - Maier, R. M.
AU - Visscher, P. M.
AU - Robinson, Matthew Richard
AU - Wray, N. R.
ID - 7721
IS - 7
JF - Psychological Medicine
SN - 0033-2917
TI - Embracing polygenicity: A review of methods and tools for psychiatric genetics research
VL - 48
ER -
TY - JOUR
AB - We develop a Bayesian mixed linear model that simultaneously estimates single-nucleotide polymorphism (SNP)-based heritability, polygenicity (proportion of SNPs with nonzero effects), and the relationship between SNP effect size and minor allele frequency for complex traits in conventionally unrelated individuals using genome-wide SNP data. We apply the method to 28 complex traits in the UK Biobank data (N = 126,752) and show that on average, 6% of SNPs have nonzero effects, which in total explain 22% of phenotypic variance. We detect significant (P < 0.05/28) signatures of natural selection in the genetic architecture of 23 traits, including reproductive, cardiovascular, and anthropometric traits, as well as educational attainment. The significant estimates of the relationship between effect size and minor allele frequency in complex traits are consistent with a model of negative (or purifying) selection, as confirmed by forward simulation. We conclude that negative selection acts pervasively on the genetic variants associated with human complex traits.
AU - Zeng, Jian
AU - de Vlaming, Ronald
AU - Wu, Yang
AU - Robinson, Matthew Richard
AU - Lloyd-Jones, Luke R.
AU - Yengo, Loic
AU - Yap, Chloe X.
AU - Xue, Angli
AU - Sidorenko, Julia
AU - McRae, Allan F.
AU - Powell, Joseph E.
AU - Montgomery, Grant W.
AU - Metspalu, Andres
AU - Esko, Tonu
AU - Gibson, Greg
AU - Wray, Naomi R.
AU - Visscher, Peter M.
AU - Yang, Jian
ID - 7722
IS - 5
JF - Nature Genetics
SN - 1061-4036
TI - Signatures of negative selection in the genetic architecture of human complex traits
VL - 50
ER -
TY - JOUR
AB - Genome-wide association studies (GWAS) have identified thousands of loci that are robustly associated with complex diseases. The use of linear mixed model (LMM) methodology for GWAS is becoming more prevalent due to its ability to control for population structure and cryptic relatedness and to increase power. The odds ratio (OR) is a common measure of the association of a disease with an exposure (e.g., a genetic variant) and is readably available from logistic regression. However, when the LMM is applied to all-or-none traits it provides estimates of genetic effects on the observed 0–1 scale, a different scale to that in logistic regression. This limits the comparability of results across studies, for example in a meta-analysis, and makes the interpretation of the magnitude of an effect from an LMM GWAS difficult. In this study, we derived transformations from the genetic effects estimated under the LMM to the OR that only rely on summary statistics. To test the proposed transformations, we used real genotypes from two large, publicly available data sets to simulate all-or-none phenotypes for a set of scenarios that differ in underlying model, disease prevalence, and heritability. Furthermore, we applied these transformations to GWAS summary statistics for type 2 diabetes generated from 108,042 individuals in the UK Biobank. In both simulation and real-data application, we observed very high concordance between the transformed OR from the LMM and either the simulated truth or estimates from logistic regression. The transformations derived and validated in this study improve the comparability of results from prospective and already performed LMM GWAS on complex diseases by providing a reliable transformation to a common comparative scale for the genetic effects.
AU - Lloyd-Jones, Luke R.
AU - Robinson, Matthew Richard
AU - Yang, Jian
AU - Visscher, Peter M.
ID - 7723
IS - 4
JF - Genetics
SN - 0016-6731
TI - Transformation of summary statistics from linear mixed model association on all-or-none traits to odds ratio
VL - 208
ER -
TY - JOUR
AB - Modern molecular genetic datasets, primarily collected to study the biology of human health and disease, can be used to directly measure the action of natural selection and reveal important features of contemporary human evolution. Here we leverage the UK Biobank data to test for the presence of linear and nonlinear natural selection in a contemporary population of the United Kingdom. We obtain phenotypic and genetic evidence consistent with the action of linear/directional selection. Phenotypic evidence suggests that stabilizing selection, which acts to reduce variance in the population without necessarily modifying the population mean, is widespread and relatively weak in comparison with estimates from other species.
AU - Sanjak, Jaleal S.
AU - Sidorenko, Julia
AU - Robinson, Matthew Richard
AU - Thornton, Kevin R.
AU - Visscher, Peter M.
ID - 7724
IS - 1
JF - Proceedings of the National Academy of Sciences
SN - 0027-8424
TI - Evidence of directional and stabilizing selection in contemporary humans
VL - 115
ER -
TY - JOUR
AB - Creating a selective gel that filters particles based on their interactions is a major goal of nanotechnology, with far-reaching implications from drug delivery to controlling assembly pathways. However, this is particularly difficult when the particles are larger than the gel’s characteristic mesh size because such particles cannot passively pass through the gel. Thus, filtering requires the interacting particles to transiently reorganize the gel’s internal structure. While significant advances, e.g., in DNA engineering, have enabled the design of nano-materials with programmable interactions, it is not clear what physical principles such a designer gel could exploit to achieve selective permeability. We present an equilibrium mechanism where crosslink binding dynamics are affected by interacting particles such that particle diffusion is enhanced. In addition to revealing specific design rules for manufacturing selective gels, our results have the potential to explain the origin of selective permeability in certain biological materials, including the nuclear pore complex.
AU - Goodrich, Carl Peter
AU - Brenner, Michael P.
AU - Ribbeck, Katharina
ID - 7754
JF - Nature Communications
SN - 2041-1723
TI - Enhanced diffusion by binding to the crosslinks of a polymer gel
VL - 9
ER -
TY - JOUR
AB - The goal of this article is to introduce the reader to the theory of intrinsic geometry of convex surfaces. We illustrate the power of the tools by proving a theorem on convex surfaces containing an arbitrarily long closed simple geodesic. Let us remind ourselves that a curve in a surface is called geodesic if every sufficiently short arc of the curve is length minimizing; if, in addition, it has no self-intersections, we call it simple geodesic. A tetrahedron with equal opposite edges is called isosceles. The axiomatic method of Alexandrov geometry allows us to work with the metrics of convex surfaces directly, without approximating it first by a smooth or polyhedral metric. Such approximations destroy the closed geodesics on the surface; therefore it is difficult (if at all possible) to apply approximations in the proof of our theorem. On the other hand, a proof in the smooth or polyhedral case usually admits a translation into Alexandrov’s language; such translation makes the result more general. In fact, our proof resembles a translation of the proof given by Protasov. Note that the main theorem implies in particular that a smooth convex surface does not have arbitrarily long simple closed geodesics. However we do not know a proof of this corollary that is essentially simpler than the one presented below.
AU - Akopyan, Arseniy
AU - Petrunin, Anton
ID - 106
IS - 3
JF - Mathematical Intelligencer
TI - Long geodesics on convex surfaces
VL - 40
ER -
TY - JOUR
AB - Owing to their wide tunability, multiple internal degrees of freedom, and low disorder, graphene heterostructures are emerging as a promising experimental platform for fractional quantum Hall (FQH) studies. Here, we report FQH thermal activation gap measurements in dual graphite-gated monolayer graphene devices fabricated in an edgeless Corbino geometry. In devices with substrate-induced sublattice splitting, we find a tunable crossover between single- and multicomponent FQH states in the zero energy Landau level. Activation gaps in the single-component regime show excellent agreement with numerical calculations using a single broadening parameter
Γ≈7.2K. In the first excited Landau level, in contrast, FQH gaps are strongly influenced by Landau level mixing, and we observe an unexpected valley-ordered state at integer filling ν=−4.
AU - Polshyn, Hryhoriy
AU - Zhou, H.
AU - Spanton, E. M.
AU - Taniguchi, T.
AU - Watanabe, K.
AU - Young, A. F.
ID - 10626
IS - 22
JF - Physical Review Letters
KW - general physics and astronomy
SN - 0031-9007
TI - Quantitative transport measurements of fractional quantum Hall energy gaps in edgeless graphene devices
VL - 121
ER -
TY - JOUR
AB - We present a scanning probe technique for measuring the dynamics of individual fluxoid transitions in multiply connected superconducting structures. In these measurements, a small magnetic particle attached to the tip of a silicon cantilever is scanned over a micron-size superconducting ring fabricated from a thin aluminum film. We find that near the superconducting transition temperature of the aluminum, the dissipation and frequency of the cantilever changes significantly at particular locations where the tip-induced magnetic flux penetrating the ring causes the two lowest-energy fluxoid states to become nearly degenerate. In this regime, we show that changes in the cantilever frequency and dissipation are well-described by a stochastic resonance (SR) process, wherein small oscillations of the cantilever in the presence of thermally activated phase slips (TAPS) in the ring give rise to a dynamical force that modifies the mechanical properties of the cantilever. Using the SR model, we calculate the average fluctuation rate of the TAPS as a function of temperature over a 32-dB range in frequency, and we compare it to the Langer-Ambegaokar-McCumber-Halperin theory for TAPS in one-dimensional superconducting structures.
AU - Polshyn, Hryhoriy
AU - Naibert, Tyler R.
AU - Budakian, Raffi
ID - 10627
IS - 18
JF - Physical Review B
SN - 2469-9950
TI - Imaging phase slip dynamics in micron-size superconducting rings
VL - 97
ER -
TY - JOUR
AB - In 1945, A.W. Goodman and R.E. Goodman proved the following conjecture by P. Erdős: Given a family of (round) disks of radii r1, … , rn in the plane, it is always possible to cover them by a disk of radius R= ∑ ri, provided they cannot be separated into two subfamilies by a straight line disjoint from the disks. In this note we show that essentially the same idea may work for different analogues and generalizations of their result. In particular, we prove the following: Given a family of positive homothetic copies of a fixed convex body K⊂ Rd with homothety coefficients τ1, … , τn> 0 , it is always possible to cover them by a translate of d+12(∑τi)K, provided they cannot be separated into two subfamilies by a hyperplane disjoint from the homothets.
AU - Akopyan, Arseniy
AU - Balitskiy, Alexey
AU - Grigorev, Mikhail
ID - 1064
IS - 4
JF - Discrete & Computational Geometry
SN - 01795376
TI - On the circle covering theorem by A.W. Goodman and R.E. Goodman
VL - 59
ER -
TY - JOUR
AB - We introduce the notion of “non-malleable codes” which relaxes the notion of error correction and error detection. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. In contrast to error correction and error detection, non-malleability can be achieved for very rich classes of modifications. We construct an efficient code that is non-malleable with respect to modifications that affect each bit of the codeword arbitrarily (i.e., leave it untouched, flip it, or set it to either 0 or 1), but independently of the value of the other bits of the codeword. Using the probabilistic method, we also show a very strong and general statement: there exists a non-malleable code for every “small enough” family F of functions via which codewords can be modified. Although this probabilistic method argument does not directly yield efficient constructions, it gives us efficient non-malleable codes in the random-oracle model for very general classes of tampering functions—e.g., functions where every bit in the tampered codeword can depend arbitrarily on any 99% of the bits in the original codeword. As an application of non-malleable codes, we show that they provide an elegant algorithmic solution to the task of protecting functionalities implemented in hardware (e.g., signature cards) against “tampering attacks.” In such attacks, the secret state of a physical system is tampered, in the hopes that future interaction with the modified system will reveal some secret information. This problem was previously studied in the work of Gennaro et al. in 2004 under the name “algorithmic tamper proof security” (ATP). We show that non-malleable codes can be used to achieve important improvements over the prior work. In particular, we show that any functionality can be made secure against a large class of tampering attacks, simply by encoding the secret state with a non-malleable code while it is stored in memory.
AU - Dziembowski, Stefan
AU - Pietrzak, Krzysztof Z
AU - Wichs, Daniel
ID - 107
IS - 4
JF - Journal of the ACM
TI - Non-malleable codes
VL - 65
ER -
TY - CONF
AB - Universal hashing found a lot of applications in computer science. In cryptography the most important fact about universal families is the so called Leftover Hash Lemma, proved by Impagliazzo, Levin and Luby. In the language of modern cryptography it states that almost universal families are good extractors. In this work we provide a somewhat surprising characterization in the opposite direction. Namely, every extractor with sufficiently good parameters yields a universal family on a noticeable fraction of its inputs. Our proof technique is based on tools from extremal graph theory applied to the \'collision graph\' induced by the extractor, and may be of independent interest. We discuss possible applications to the theory of randomness extractors and non-malleable codes.
AU - Obremski, Marciej
AU - Skorski, Maciej
ID - 108
TI - Inverted leftover hash lemma
VL - 2018
ER -
TY - CHAP
AB - We prove that every congruence distributive variety has directed Jónsson terms, and every congruence modular variety has directed Gumm terms. The directed terms we construct witness every case of absorption witnessed by the original Jónsson or Gumm terms. This result is equivalent to a pair of claims about absorption for admissible preorders in congruence distributive and congruence modular varieties, respectively. For finite algebras, these absorption theorems have already seen significant applications, but until now, it was not clear if the theorems hold for general algebras as well. Our method also yields a novel proof of a result by P. Lipparini about the existence of a chain of terms (which we call Pixley terms) in varieties that are at the same time congruence distributive and k-permutable for some k.
AU - Kazda, Alexandr
AU - Kozik, Marcin
AU - McKenzie, Ralph
AU - Moore, Matthew
ED - Czelakowski, J
ID - 10864
SN - 2211-2758
T2 - Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science
TI - Absorption and directed Jónsson terms
VL - 16
ER -
TY - JOUR
AB - Acquisition of evolutionary novelties is a fundamental process for adapting to the external environment and invading new niches and results in the diversification of life, which we can see in the world today. How such novel phenotypic traits are acquired in the course of evolution and are built up in developing embryos has been a central question in biology. Whole-genome duplication (WGD) is a process of genome doubling that supplies raw genetic materials and increases genome complexity. Recently, it has been gradually revealed that WGD and subsequent fate changes of duplicated genes can facilitate phenotypic evolution. Here, we review the current understanding of the relationship between WGD and the acquisition of evolutionary novelties. We show some examples of this link and discuss how WGD and subsequent duplicated genes can facilitate phenotypic evolution as well as when such genomic doubling can be advantageous for adaptation.
AU - Yuuta, Moriyama
AU - Koshiba-Takeuchi, Kazuko
ID - 10880
IS - 5
JF - Briefings in Functional Genomics
KW - Genetics
KW - Molecular Biology
KW - Biochemistry
KW - General Medicine
SN - 2041-2649
TI - Significance of whole-genome duplications on the emergence of evolutionary novelties
VL - 17
ER -
TY - JOUR
AB - Strigolactones (SLs) are a relatively recent addition to the list of plant hormones that control different aspects of plant development. SL signalling is perceived by an α/β hydrolase, DWARF 14 (D14). A close homolog of D14, KARRIKIN INSENSTIVE2 (KAI2), is involved in perception of an uncharacterized molecule called karrikin (KAR). Recent studies in Arabidopsis identified the SUPPRESSOR OF MAX2 1 (SMAX1) and SMAX1-LIKE 7 (SMXL7) to be potential SCF–MAX2 complex-mediated proteasome targets of KAI2 and D14, respectively. Genetic studies on SMXL7 and SMAX1 demonstrated distinct developmental roles for each, but very little is known about these repressors in terms of their sequence features. In this study, we performed an extensive comparative analysis of SMXLs and determined their phylogenetic and evolutionary history in the plant lineage. Our results show that SMXL family members can be sub-divided into four distinct phylogenetic clades/classes, with an ancient SMAX1. Further, we identified the clade-specific motifs that have evolved and that might act as determinants of SL-KAR signalling specificity. These specificities resulted from functional diversities among the clades. Our results suggest that a gradual co-evolution of SMXL members with their upstream receptors D14/KAI2 provided an increased specificity to both the SL perception and response in land plants.
AU - Moturu, Taraka Ramji
AU - Thula, Sravankumar
AU - Singh, Ravi Kumar
AU - Nodzyński, Tomasz
AU - Vařeková, Radka Svobodová
AU - Friml, Jiří
AU - Simon, Sibu
ID - 10881
IS - 9
JF - Journal of Experimental Botany
KW - Plant Science
KW - Physiology
SN - 0022-0957
TI - Molecular evolution and diversification of the SMXL gene family
VL - 69
ER -
TY - JOUR
AB - A graphical model encodes conditional independence relations via the Markov properties. For an undirected graph these conditional independence relations can be represented by a simple polytope known as the graph associahedron, which can be constructed as a Minkowski sum of standard simplices. We show that there is an analogous polytope for conditional independence relations coming from a regular Gaussian model, and it can be defined using multiinformation or relative entropy. For directed acyclic graphical models we give a construction of this polytope as a Minkowski sum of matroid polytopes. Finally, we apply this geometric insight to construct a new ordering-based search algorithm for causal inference via directed acyclic graphical models.
AU - Mohammadi, Fatemeh
AU - Uhler, Caroline
AU - Wang, Charles
AU - Yu, Josephine
ID - 1092
IS - 1
JF - SIAM Journal on Discrete Mathematics
TI - Generalized permutohedra from probabilistic graphical models
VL - 32
ER -
TY - CONF
AB - We report on a novel strategy to derive mean-field limits of quantum mechanical systems in which a large number of particles weakly couple to a second-quantized radiation field. The technique combines the method of counting and the coherent state approach to study the growth of the correlations among the particles and in the radiation field. As an instructional example, we derive the Schrödinger–Klein–Gordon system of equations from the Nelson model with ultraviolet cutoff and possibly massless scalar field. In particular, we prove the convergence of the reduced density matrices (of the nonrelativistic particles and the field bosons) associated with the exact time evolution to the projectors onto the solutions of the Schrödinger–Klein–Gordon equations in trace norm. Furthermore, we derive explicit bounds on the rate of convergence of the one-particle reduced density matrix of the nonrelativistic particles in Sobolev norm.
AU - Leopold, Nikolai K
AU - Pickl, Peter
ID - 11
TI - Mean-field limits of particles in interaction with quantised radiation fields
VL - 270
ER -
TY - JOUR
AB - We give a lower bound on the ground state energy of a system of two fermions of one species interacting with two fermions of another species via point interactions. We show that there is a critical mass ratio m2 ≈ 0.58 such that the system is stable, i.e., the energy is bounded from below, for m∈[m2,m2−1]. So far it was not known whether this 2 + 2 system exhibits a stable region at all or whether the formation of four-body bound states causes an unbounded spectrum for all mass ratios, similar to the Thomas effect. Our result gives further evidence for the stability of the more general N + M system.
AU - Moser, Thomas
AU - Seiringer, Robert
ID - 154
IS - 3
JF - Mathematical Physics Analysis and Geometry
SN - 13850172
TI - Stability of the 2+2 fermionic system with point interactions
VL - 21
ER -
TY - CONF
AB - There is currently significant interest in operating devices in the quantum regime, where their behaviour cannot be explained through classical mechanics. Quantum states, including entangled states, are fragile and easily disturbed by excessive thermal noise. Here we address the question of whether it is possible to create non-reciprocal devices that encourage the flow of thermal noise towards or away from a particular quantum device in a network. Our work makes use of the cascaded systems formalism to answer this question in the affirmative, showing how a three-port device can be used as an effective thermal transistor, and illustrates how this formalism maps onto an experimentally-realisable optomechanical system. Our results pave the way to more resilient quantum devices and to the use of thermal noise as a resource.
AU - Xuereb, André
AU - Aquilina, Matteo
AU - Barzanjeh, Shabir
ED - Andrews, D L
ED - Ostendorf, A
ED - Bain, A J
ED - Nunzi, J M
ID - 155
TI - Routing thermal noise through quantum networks
VL - 10672
ER -
TY - CONF
AB - Imprecision in timing can sometimes be beneficial: Metric interval temporal logic (MITL), disabling the expression of punctuality constraints, was shown to translate to timed automata, yielding an elementary decision procedure. We show how this principle extends to other forms of dense-time specification using regular expressions. By providing a clean, automaton-based formal framework for non-punctual languages, we are able to recover and extend several results in timed systems. Metric interval regular expressions (MIRE) are introduced, providing regular expressions with non-singular duration constraints. We obtain that MIRE are expressively complete relative to a class of one-clock timed automata, which can be determinized using additional clocks. Metric interval dynamic logic (MIDL) is then defined using MIRE as temporal modalities. We show that MIDL generalizes known extensions of MITL, while translating to timed automata at comparable cost.
AU - Ferrere, Thomas
ID - 156
TI - The compound interest in relaxing punctuality
VL - 10951
ER -
TY - JOUR
AB - Social dilemmas occur when incentives for individuals are misaligned with group interests 1-7 . According to the 'tragedy of the commons', these misalignments can lead to overexploitation and collapse of public resources. The resulting behaviours can be analysed with the tools of game theory 8 . The theory of direct reciprocity 9-15 suggests that repeated interactions can alleviate such dilemmas, but previous work has assumed that the public resource remains constant over time. Here we introduce the idea that the public resource is instead changeable and depends on the strategic choices of individuals. An intuitive scenario is that cooperation increases the public resource, whereas defection decreases it. Thus, cooperation allows the possibility of playing a more valuable game with higher payoffs, whereas defection leads to a less valuable game. We analyse this idea using the theory of stochastic games 16-19 and evolutionary game theory. We find that the dependence of the public resource on previous interactions can greatly enhance the propensity for cooperation. For these results, the interaction between reciprocity and payoff feedback is crucial: neither repeated interactions in a constant environment nor single interactions in a changing environment yield similar cooperation rates. Our framework shows which feedbacks between exploitation and environment - either naturally occurring or designed - help to overcome social dilemmas.
AU - Hilbe, Christian
AU - Šimsa, Štepán
AU - Chatterjee, Krishnendu
AU - Nowak, Martin
ID - 157
IS - 7713
JF - Nature
TI - Evolution of cooperation in stochastic games
VL - 559
ER -
TY - JOUR
AB - The angiosperm seed is composed of three genetically distinct tissues: the diploid embryo that originates from the fertilized egg cell, the triploid endosperm that is produced from the fertilized central cell, and the maternal sporophytic integuments that develop into the seed coat1. At the onset of embryo development in Arabidopsis thaliana, the zygote divides asymmetrically, producing a small apical embryonic cell and a larger basal cell that connects the embryo to the maternal tissue2. The coordinated and synchronous development of the embryo and the surrounding integuments, and the alignment of their growth axes, suggest communication between maternal tissues and the embryo. In contrast to animals, however, where a network of maternal factors that direct embryo patterning have been identified3,4, only a few maternal mutations have been described to affect embryo development in plants5–7. Early embryo patterning in Arabidopsis requires accumulation of the phytohormone auxin in the apical cell by directed transport from the suspensor8–10. However, the origin of this auxin has remained obscure. Here we investigate the source of auxin for early embryogenesis and provide evidence that the mother plant coordinates seed development by supplying auxin to the early embryo from the integuments of the ovule. We show that auxin response increases in ovules after fertilization, due to upregulated auxin biosynthesis in the integuments, and this maternally produced auxin is required for correct embryo development.
AU - Robert, Hélène
AU - Park, Chulmin
AU - Gutièrrez, Carla
AU - Wójcikowska, Barbara
AU - Pěnčík, Aleš
AU - Novák, Ondřej
AU - Chen, Junyi
AU - Grunewald, Wim
AU - Dresselhaus, Thomas
AU - Friml, Jirí
AU - Laux, Thomas
ID - 158
IS - 8
JF - Nature Plants
TI - Maternal auxin supply contributes to early embryo patterning in Arabidopsis
VL - 4
ER -