@article{9402, abstract = {Direct and indirect reciprocity are key mechanisms for the evolution of cooperation. Direct reciprocity means that individuals use their own experience to decide whether to cooperate with another person. Indirect reciprocity means that they also consider the experiences of others. Although these two mechanisms are intertwined, they are typically studied in isolation. Here, we introduce a mathematical framework that allows us to explore both kinds of reciprocity simultaneously. We show that the well-known ‘generous tit-for-tat’ strategy of direct reciprocity has a natural analogue in indirect reciprocity, which we call ‘generous scoring’. Using an equilibrium analysis, we characterize under which conditions either of the two strategies can maintain cooperation. With simulations, we additionally explore which kind of reciprocity evolves when members of a population engage in social learning to adapt to their environment. Our results draw unexpected connections between direct and indirect reciprocity while highlighting important differences regarding their evolvability.}, author = {Schmid, Laura and Chatterjee, Krishnendu and Hilbe, Christian and Nowak, Martin A.}, issn = {2397-3374}, journal = {Nature Human Behaviour}, number = {10}, pages = {1292–1302}, publisher = {Springer Nature}, title = {{A unified framework of direct and indirect reciprocity}}, doi = {10.1038/s41562-021-01114-8}, volume = {5}, year = {2021}, } @inbook{9403, abstract = {Optimal decision making requires individuals to know their available options and to anticipate correctly what consequences these options have. In many social interactions, however, we refrain from gathering all relevant information, even if this information would help us make better decisions and is costless to obtain. This chapter examines several examples of “deliberate ignorance.” Two simple models are proposed to illustrate how ignorance can evolve among self-interested and payoff - maximizing individuals, and open problems are highlighted that lie ahead for future research to explore.}, author = {Schmid, Laura and Hilbe, Christian}, booktitle = {Deliberate Ignorance: Choosing Not To Know}, editor = {Hertwig, Ralph and Engel, Christoph}, isbn = {978-0-262-04559-9}, pages = {139--152}, publisher = {MIT Press}, title = {{The evolution of strategic ignorance in strategic interaction}}, volume = {29}, year = {2021}, } @inproceedings{9416, abstract = {We study the inductive bias of two-layer ReLU networks trained by gradient flow. We identify a class of easy-to-learn (`orthogonally separable') datasets, and characterise the solution that ReLU networks trained on such datasets converge to. Irrespective of network width, the solution turns out to be a combination of two max-margin classifiers: one corresponding to the positive data subset and one corresponding to the negative data subset. The proof is based on the recently introduced concept of extremal sectors, for which we prove a number of properties in the context of orthogonal separability. In particular, we prove stationarity of activation patterns from some time onwards, which enables a reduction of the ReLU network to an ensemble of linear subnetworks.}, author = {Bui Thi Mai, Phuong and Lampert, Christoph}, booktitle = {9th International Conference on Learning Representations}, location = {Virtual}, title = {{The inductive bias of ReLU networks on orthogonally separable data}}, year = {2021}, } @phdthesis{9418, abstract = {Deep learning is best known for its empirical success across a wide range of applications spanning computer vision, natural language processing and speech. Of equal significance, though perhaps less known, are its ramifications for learning theory: deep networks have been observed to perform surprisingly well in the high-capacity regime, aka the overfitting or underspecified regime. Classically, this regime on the far right of the bias-variance curve is associated with poor generalisation; however, recent experiments with deep networks challenge this view. This thesis is devoted to investigating various aspects of underspecification in deep learning. First, we argue that deep learning models are underspecified on two levels: a) any given training dataset can be fit by many different functions, and b) any given function can be expressed by many different parameter configurations. We refer to the second kind of underspecification as parameterisation redundancy and we precisely characterise its extent. Second, we characterise the implicit criteria (the inductive bias) that guide learning in the underspecified regime. Specifically, we consider a nonlinear but tractable classification setting, and show that given the choice, neural networks learn classifiers with a large margin. Third, we consider learning scenarios where the inductive bias is not by itself sufficient to deal with underspecification. We then study different ways of ‘tightening the specification’: i) In the setting of representation learning with variational autoencoders, we propose a hand- crafted regulariser based on mutual information. ii) In the setting of binary classification, we consider soft-label (real-valued) supervision. We derive a generalisation bound for linear networks supervised in this way and verify that soft labels facilitate fast learning. Finally, we explore an application of soft-label supervision to the training of multi-exit models.}, author = {Bui Thi Mai, Phuong}, issn = {2663-337X}, pages = {125}, publisher = {Institute of Science and Technology Austria}, title = {{Underspecification in deep learning}}, doi = {10.15479/AT:ISTA:9418}, year = {2021}, } @article{9558, abstract = {We show that turbulent dynamics that arise in simulations of the three-dimensional Navier--Stokes equations in a triply-periodic domain under sinusoidal forcing can be described as transient visits to the neighborhoods of unstable time-periodic solutions. Based on this description, we reduce the original system with more than 10^5 degrees of freedom to a 17-node Markov chain where each node corresponds to the neighborhood of a periodic orbit. The model accurately reproduces long-term averages of the system's observables as weighted sums over the periodic orbits. }, author = {Yalniz, Gökhan and Hof, Björn and Budanur, Nazmi B}, issn = {1079-7114}, journal = {Physical Review Letters}, number = {24}, publisher = {American Physical Society}, title = {{Coarse graining the state space of a turbulent flow using periodic orbits}}, doi = {10.1103/PhysRevLett.126.244502}, volume = {126}, year = {2021}, } @phdthesis{9562, abstract = {Left-right asymmetries can be considered a fundamental organizational principle of the vertebrate central nervous system. The hippocampal CA3-CA1 pyramidal cell synaptic connection shows an input-side dependent asymmetry where the hemispheric location of the presynaptic CA3 neuron determines the synaptic properties. Left-input synapses terminating on apical dendrites in stratum radiatum have a higher density of NMDA receptor subunit GluN2B, a lower density of AMPA receptor subunit GluA1 and smaller areas with less often perforated PSDs. On the other hand, left-input synapses terminating on basal dendrites in stratum oriens have lower GluN2B densities than right-input ones. Apical and basal synapses further employ different signaling pathways involved in LTP. SDS-digested freeze-fracture replica labeling can visualize synaptic membrane proteins with high sensitivity and resolution, and has been used to reveal the asymmetry at the electron microscopic level. However, it requires time-consuming manual demarcation of the synaptic surface for quantitative measurements. To facilitate the analysis of replica labeling, I first developed a software named Darea, which utilizes deep-learning to automatize this demarcation. With Darea I characterized the synaptic distribution of NMDA and AMPA receptors as well as the voltage-gated Ca2+ channels in CA1 stratum radiatum and oriens. Second, I explored the role of GluN2B and its carboxy-terminus in the establishment of input-side dependent hippocampal asymmetry. In conditional knock-out mice lacking GluN2B expression in CA1 and GluN2B-2A swap mice, where GluN2B carboxy-terminus was exchanged to that of GluN2A, no significant asymmetries of GluN2B, GluA1 and PSD area were detected. We further discovered a previously unknown functional asymmetry of GluN2A, which was also lost in the swap mouse. These results demonstrate that GluN2B carboxy-terminus plays a critical role in normal formation of input-side dependent asymmetry.}, author = {Kleindienst, David}, issn = {2663-337X}, pages = {124}, publisher = {Institute of Science and Technology Austria}, title = {{2B or not 2B: Hippocampal asymmetries mediated by NMDA receptor subunit GluN2B C-terminus and high-throughput image analysis by Deep-Learning}}, doi = {10.15479/at:ista:9562}, year = {2021}, } @inproceedings{9592, abstract = {The convex grabbing game is a game where two players, Alice and Bob, alternate taking extremal points from the convex hull of a point set on the plane. Rational weights are given to the points. The goal of each player is to maximize the total weight over all points that they obtain. We restrict the setting to the case of binary weights. We show a construction of an arbitrarily large odd-sized point set that allows Bob to obtain almost 3/4 of the total weight. This construction answers a question asked by Matsumoto, Nakamigawa, and Sakuma in [Graphs and Combinatorics, 36/1 (2020)]. We also present an arbitrarily large even-sized point set where Bob can obtain the entirety of the total weight. Finally, we discuss conjectures about optimum moves in the convex grabbing game for both players in general.}, author = {Dvorak, Martin and Nicholson, Sara}, booktitle = {Proceedings of the 33rd Canadian Conference on Computational Geometry}, keywords = {convex grabbing game, graph grabbing game, combinatorial game, convex geometry}, location = {Halifax, NS, Canada}, title = {{Massively winning configurations in the convex grabbing game on the plane}}, year = {2021}, } @phdthesis{9623, abstract = {Cytoplasmic reorganizations are essential for morphogenesis. In large cells like oocytes, these reorganizations become crucial in patterning the oocyte for later stages of embryonic development. Ascidians oocytes reorganize their cytoplasm (ooplasm) in a spectacular manner. Ooplasmic reorganization is initiated at fertilization with the contraction of the actomyosin cortex along the animal-vegetal axis of the oocyte, driving the accumulation of cortical endoplasmic reticulum (cER), maternal mRNAs associated to it and a mitochondria-rich subcortical layer – the myoplasm – in a region of the vegetal pole termed contraction pole (CP). Here we have used the species Phallusia mammillata to investigate the changes in cell shape that accompany these reorganizations and the mechanochemical mechanisms underlining CP formation. We report that the length of the animal-vegetal (AV) axis oscillates upon fertilization: it first undergoes a cycle of fast elongation-lengthening followed by a slow expansion of mainly the vegetal pole (VP) of the cell. We show that the fast oscillation corresponds to a dynamic polarization of the actin cortex as a result of a fertilization-induced increase in cortical tension in the oocyte that triggers a rupture of the cortex at the animal pole and the establishment of vegetal-directed cortical flows. These flows are responsible for the vegetal accumulation of actin causing the VP to flatten. We find that the slow expansion of the VP, leading to CP formation, correlates with a relaxation of the vegetal cortex and that the myoplasm plays a role in the expansion. We show that the myoplasm is a solid-like layer that buckles under compression forces arising from the contracting actin cortex at the VP. Straightening of the myoplasm when actin flows stops, facilitates the expansion of the VP and the CP. Altogether, our results present a previously unrecognized role for the myoplasm in ascidian ooplasmic segregation. }, author = {Caballero Mancebo, Silvia}, isbn = {978-3-99078-012-1}, issn = {2663-337X}, pages = {111}, publisher = {Institute of Science and Technology Austria}, title = {{Fertilization-induced deformations are controlled by the actin cortex and a mitochondria-rich subcortical layer in ascidian oocytes}}, doi = {10.15479/at:ista:9623}, year = {2021}, } @phdthesis{10007, abstract = {The present thesis is concerned with the derivation of weak-strong uniqueness principles for curvature driven interface evolution problems not satisfying a comparison principle. The specific examples being treated are two-phase Navier-Stokes flow with surface tension, modeling the evolution of two incompressible, viscous and immiscible fluids separated by a sharp interface, and multiphase mean curvature flow, which serves as an idealized model for the motion of grain boundaries in an annealing polycrystalline material. Our main results - obtained in joint works with Julian Fischer, Tim Laux and Theresa M. Simon - state that prior to the formation of geometric singularities due to topology changes, the weak solution concept of Abels (Interfaces Free Bound. 9, 2007) to two-phase Navier-Stokes flow with surface tension and the weak solution concept of Laux and Otto (Calc. Var. Partial Differential Equations 55, 2016) to multiphase mean curvature flow (for networks in R^2 or double bubbles in R^3) represents the unique solution to these interface evolution problems within the class of classical solutions, respectively. To the best of the author's knowledge, for interface evolution problems not admitting a geometric comparison principle the derivation of a weak-strong uniqueness principle represented an open problem, so that the works contained in the present thesis constitute the first positive results in this direction. The key ingredient of our approach consists of the introduction of a novel concept of relative entropies for a class of curvature driven interface evolution problems, for which the associated energy contains an interfacial contribution being proportional to the surface area of the evolving (network of) interface(s). The interfacial part of the relative entropy gives sufficient control on the interface error between a weak and a classical solution, and its time evolution can be computed, at least in principle, for any energy dissipating weak solution concept. A resulting stability estimate for the relative entropy essentially entails the above mentioned weak-strong uniqueness principles. The present thesis contains a detailed introduction to our relative entropy approach, which in particular highlights potential applications to other problems in curvature driven interface evolution not treated in this thesis.}, author = {Hensel, Sebastian}, issn = {2663-337X}, pages = {300}, publisher = {Institute of Science and Technology Austria}, title = {{Curvature driven interface evolution: Uniqueness properties of weak solution concepts}}, doi = {10.15479/at:ista:10007}, year = {2021}, } @phdthesis{10030, abstract = {This PhD thesis is primarily focused on the study of discrete transport problems, introduced for the first time in the seminal works of Maas [Maa11] and Mielke [Mie11] on finite state Markov chains and reaction-diffusion equations, respectively. More in detail, my research focuses on the study of transport costs on graphs, in particular the convergence and the stability of such problems in the discrete-to-continuum limit. This thesis also includes some results concerning non-commutative optimal transport. The first chapter of this thesis consists of a general introduction to the optimal transport problems, both in the discrete, the continuous, and the non-commutative setting. Chapters 2 and 3 present the content of two works, obtained in collaboration with Peter Gladbach, Eva Kopfer, and Jan Maas, where we have been able to show the convergence of discrete transport costs on periodic graphs to suitable continuous ones, which can be described by means of a homogenisation result. We first focus on the particular case of quadratic costs on the real line and then extending the result to more general costs in arbitrary dimension. Our results are the first complete characterisation of limits of transport costs on periodic graphs in arbitrary dimension which do not rely on any additional symmetry. In Chapter 4 we turn our attention to one of the intriguing connection between evolution equations and optimal transport, represented by the theory of gradient flows. We show that discrete gradient flow structures associated to a finite volume approximation of a certain class of diffusive equations (Fokker–Planck) is stable in the limit of vanishing meshes, reproving the convergence of the scheme via the method of evolutionary Γ-convergence and exploiting a more variational point of view on the problem. This is based on a collaboration with Dominik Forkert and Jan Maas. Chapter 5 represents a change of perspective, moving away from the discrete world and reaching the non-commutative one. As in the discrete case, we discuss how classical tools coming from the commutative optimal transport can be translated into the setting of density matrices. In particular, in this final chapter we present a non-commutative version of the Schrödinger problem (or entropic regularised optimal transport problem) and discuss existence and characterisation of minimisers, a duality result, and present a non-commutative version of the well-known Sinkhorn algorithm to compute the above mentioned optimisers. This is based on a joint work with Dario Feliciangeli and Augusto Gerolin. Finally, Appendix A and B contain some additional material and discussions, with particular attention to Harnack inequalities and the regularity of flows on discrete spaces.}, author = {Portinale, Lorenzo}, issn = {2663-337X}, publisher = {Institute of Science and Technology Austria}, title = {{Discrete-to-continuum limits of transport problems and gradient flows in the space of measures}}, doi = {10.15479/at:ista:10030}, year = {2021}, } @phdthesis{10035, abstract = {Many security definitions come in two flavors: a stronger “adaptive” flavor, where the adversary can arbitrarily make various choices during the course of the attack, and a weaker “selective” flavor where the adversary must commit to some or all of their choices a-priori. For example, in the context of identity-based encryption, selective security requires the adversary to decide on the identity of the attacked party at the very beginning of the game whereas adaptive security allows the attacker to first see the master public key and some secret keys before making this choice. Often, it appears to be much easier to achieve selective security than it is to achieve adaptive security. A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption [Pan07][FJP15], constrained PRFs [FKPR14], and Yao’s garbled circuits [JW16]. Although the above works expressed vague intuition that they share a common technique, the connection was never made precise. In this work we present a new framework (published at Crypto ’17 [JKK+17a]) that connects all of these works and allows us to present them in a unified and simplified fashion. Having the framework in place, we show how to achieve adaptive security for proxy re-encryption schemes (published at PKC ’19 [FKKP19]) and provide the first adaptive security proofs for continuous group key agreement protocols (published at S&P ’21 [KPW+21]). Questioning optimality of our framework, we then show that currently used proof techniques cannot lead to significantly better security guarantees for "graph-building" games (published at TCC ’21 [KKPW21a]). These games cover generalized selective decryption, as well as the security of prominent constructions for constrained PRFs, continuous group key agreement, and proxy re-encryption. Finally, we revisit the adaptive security of Yao’s garbled circuits and extend the analysis of Jafargholi and Wichs in two directions: While they prove adaptive security only for a modified construction with increased online complexity, we provide the first positive results for the original construction by Yao (published at TCC ’21 [KKP21a]). On the negative side, we prove that the results of Jafargholi and Wichs are essentially optimal by showing that no black-box reduction can provide a significantly better security bound (published at Crypto ’21 [KKPW21c]).}, author = {Klein, Karen}, issn = {2663-337X}, pages = {276}, publisher = {Institute of Science and Technology Austria}, title = {{On the adaptive security of graph-based games}}, doi = {10.15479/at:ista:10035}, year = {2021}, } @unpublished{10045, abstract = {Given a fixed finite metric space (V,μ), the {\em minimum 0-extension problem}, denoted as 0-Ext[μ], is equivalent to the following optimization problem: minimize function of the form minx∈Vn∑ifi(xi)+∑ijcijμ(xi,xj) where cij,cvi are given nonnegative costs and fi:V→R are functions given by fi(xi)=∑v∈Vcviμ(xi,v). The computational complexity of 0-Ext[μ] has been recently established by Karzanov and by Hirai: if metric μ is {\em orientable modular} then 0-Ext[μ] can be solved in polynomial time, otherwise 0-Ext[μ] is NP-hard. To prove the tractability part, Hirai developed a theory of discrete convex functions on orientable modular graphs generalizing several known classes of functions in discrete convex analysis, such as L♮-convex functions. We consider a more general version of the problem in which unary functions fi(xi) can additionally have terms of the form cuv;iμ(xi,{u,v}) for {u,v}∈F, where set F⊆(V2) is fixed. We extend the complexity classification above by providing an explicit condition on (μ,F) for the problem to be tractable. In order to prove the tractability part, we generalize Hirai's theory and define a larger class of discrete convex functions. It covers, in particular, another well-known class of functions, namely submodular functions on an integer lattice. Finally, we improve the complexity of Hirai's algorithm for solving 0-Ext on orientable modular graphs. }, author = {Dvorak, Martin and Kolmogorov, Vladimir}, booktitle = {arXiv}, keywords = {minimum 0-extension problem, metric labeling problem, discrete metric spaces, metric extensions, computational complexity, valued constraint satisfaction problems, discrete convex analysis, L-convex functions}, title = {{Generalized minimum 0-extension problem and discrete convexity}}, doi = {10.48550/arXiv.2109.10203}, year = {2021}, } @phdthesis{10058, abstract = {Quantum information and computation has become a vast field paved with opportunities for researchers and investors. As large multinational companies and international funds are heavily investing in quantum technologies it is still a question which platform is best suited for the task of realizing a scalable quantum processor. In this work we investigate hole spins in Ge quantum wells. These hold great promise as they possess several favorable properties: a small effective mass, a strong spin-orbit coupling, long relaxation time and an inherent immunity to hyperfine noise. All these characteristics helped Ge hole spin qubits to evolve from a single qubit to a fully entangled four qubit processor in only 3 years. Here, we investigated a qubit approach leveraging the large out-of-plane g-factors of heavy hole states in Ge quantum dots. We found this qubit to be reproducibly operable at extremely low magnetic field and at large speeds while maintaining coherence. This was possible because large differences of g-factors in adjacent dots can be achieved in the out-of-plane direction. In the in-plane direction the small g-factors, on the other hand, can be altered very effectively by the confinement potentials. Here, we found that this can even lead to a sign change of the g-factors. The resulting g-factor difference alters the dynamics of the system drastically and produces effects typically attributed to a spin-orbit induced spin-flip term. The investigations carried out in this thesis give further insights into the possibilities of holes in Ge and reveal new physical properties that need to be considered when designing future spin qubit experiments.}, author = {Jirovec, Daniel}, issn = {2663-337X}, keywords = {qubits, quantum computing, holes}, pages = {151}, publisher = {Institute of Science and Technology Austria}, title = {{Singlet-Triplet qubits and spin-orbit interaction in 2-dimensional Ge hole gases}}, doi = {10.15479/at:ista:10058}, year = {2021}, } @unpublished{10077, abstract = {Although much is known about how single neurons in the hippocampus represent an animal’s position, how cell-cell interactions contribute to spatial coding remains poorly understood. Using a novel statistical estimator and theoretical modeling, both developed in the framework of maximum entropy models, we reveal highly structured cell-to-cell interactions whose statistics depend on familiar vs. novel environment. In both conditions the circuit interactions optimize the encoding of spatial information, but for regimes that differ in the signal-to-noise ratio of their spatial inputs. Moreover, the topology of the interactions facilitates linear decodability, making the information easy to read out by downstream circuits. These findings suggest that the efficient coding hypothesis is not applicable only to individual neuron properties in the sensory periphery, but also to neural interactions in the central brain.}, author = {Nardin, Michele and Csicsvari, Jozsef L and Tkačik, Gašper and Savin, Cristina}, booktitle = {bioRxiv}, publisher = {Cold Spring Harbor Laboratory}, title = {{The structure of hippocampal CA1 interactions optimizes spatial coding across experience}}, doi = {10.1101/2021.09.28.460602}, year = {2021}, } @unpublished{10080, abstract = {Hippocampal and neocortical neural activity is modulated by the position of the individual in space. While hippocampal neurons provide the basis for a spatial map, prefrontal cortical neurons generalize over environmental features. Whether these generalized representations result from a bidirectional interaction with, or are mainly derived from hippocampal spatial representations is not known. By examining simultaneously recorded hippocampal and medial prefrontal neurons, we observed that prefrontal spatial representations show a delayed coherence with hippocampal ones. We also identified subpopulations of cells in the hippocampus and medial prefrontal cortex that formed functional cross-area couplings; these resembled the optimal connections predicted by a probabilistic model of spatial information transfer and generalization. Moreover, cross-area couplings were strongest and had the shortest delay preceding spatial decision-making. Our results suggest that generalized spatial coding in the medial prefrontal cortex is inherited from spatial representations in the hippocampus, and that the routing of information can change dynamically with behavioral demands.}, author = {Nardin, Michele and Käfer, Karola and Csicsvari, Jozsef L}, booktitle = {bioRxiv}, publisher = {Cold Spring Harbor Laboratory}, title = {{The generalized spatial representation in the prefrontal cortex is inherited from the hippocampus}}, doi = {10.1101/2021.09.30.462269}, year = {2021}, } @phdthesis{10083, abstract = {Plant motions occur across a wide spectrum of timescales, ranging from seed dispersal through bursting (milliseconds) and stomatal opening (minutes) to long-term adaptation of gross architecture. Relatively fast motions include water-driven growth as exemplified by root cell expansion under abiotic/biotic stresses or during gravitropism. A showcase is a root growth inhibition in 30 seconds triggered by the phytohormone auxin. However, the cellular and molecular mechanisms are still largely unknown. This thesis covers the studies about this topic as follows. By taking advantage of microfluidics combined with live imaging, pharmaceutical tools, and transgenic lines, we examined the kinetics of and causal relationship among various auxininduced rapid cellular changes in root growth, apoplastic pH, cytosolic Ca2+, cortical microtubule (CMT) orientation, and vacuolar morphology. We revealed that CMT reorientation and vacuolar constriction are the consequence of growth itself instead of responding directly to auxin. In contrast, auxin induces apoplast alkalinization to rapidly inhibit root growth in 30 seconds. This auxin-triggered apoplast alkalinization results from rapid H+- influx that is contributed by Ca2+ inward channel CYCLIC NUCLEOTIDE-GATED CHANNEL 14 (CNGC14)-dependent Ca2+ signaling. To dissect which auxin signaling mediates the rapid apoplast alkalinization, we combined microfluidics and genetic engineering to verify that TIR1/AFB receptors conduct a non-transcriptional regulation on Ca2+ and H+ -influx. This non-canonical pathway is mostly mediated by the cytosolic portion of TIR1/AFB. On the other hand, we uncovered, using biochemical and phospho-proteomic analysis, that auxin cell surface signaling component TRANSMEMBRANE KINASE 1 (TMK1) plays a negative role during auxin-trigger apoplast alkalinization and root growth inhibition through directly activating PM H+ -ATPases. Therefore, we discovered that PM H+ -ATPases counteract instead of mediate the auxintriggered rapid H+ -influx, and that TIR1/AFB and TMK1 regulate root growth antagonistically. This opposite effect of TIR1/AFB and TMK1 is consistent during auxin-induced hypocotyl elongation, leading us to explore the relation of two signaling pathways. Assisted with biochemistry and fluorescent imaging, we verified for the first time that TIR1/AFB and TMK1 can interact with each other. The ability of TIR1/AFB binding to membrane lipid provides a basis for the interaction of plasma membrane- and cytosol-localized proteins. Besides, transgenic analysis combined with genetic engineering and biochemistry showed that vi they do function in the same pathway. Particularly, auxin-induced TMK1 increase is TIR1/AFB dependent, suggesting TIR1/AFB regulation on TMK1. Conversely, TMK1 also regulates TIR1/AFB protein levels and thus auxin canonical signaling. To follow the study of rapid growth regulation, we analyzed another rapid growth regulator, signaling peptide RALF1. We showed that RALF1 also triggers a rapid and reversible growth inhibition caused by H + influx, highly resembling but not dependent on auxin. Besides, RALF1 promotes auxin biosynthesis by increasing expression of auxin biosynthesis enzyme YUCCAs and thus induces auxin signaling in ca. 1 hour, contributing to the sustained RALF1-triggered growth inhibition. These studies collectively contribute to understanding rapid regulation on plant cell growth, novel auxin signaling pathway as well as auxin-peptide crosstalk. }, author = {Li, Lanxin}, issn = {2663-337X}, publisher = {Institute of Science and Technology Austria}, title = {{Rapid cell growth regulation in Arabidopsis}}, doi = {10.15479/at:ista:10083}, year = {2021}, } @phdthesis{10135, abstract = {Plants maintain the capacity to develop new organs e.g. lateral roots post-embryonically throughout their whole life and thereby flexibly adapt to ever-changing environmental conditions. Plant hormones auxin and cytokinin are the main regulators of the lateral root organogenesis. Additionally to their solo activities, the interaction between auxin and cytokinin plays crucial role in fine-tuning of lateral root development and growth. In particular, cytokinin modulates auxin distribution within the developing lateral root by affecting the endomembrane trafficking of auxin transporter PIN1 and promoting its vacuolar degradation (Marhavý et al., 2011, 2014). This effect is independent of transcription and translation. Therefore, it suggests novel, non-canonical cytokinin activity occuring possibly on the posttranslational level. Impact of cytokinin and other plant hormones on auxin transporters (including PIN1) on the posttranslational level is described in detail in the introduction part of this thesis in a form of a review (Semeradova et al., 2020). To gain insights into the molecular machinery underlying cytokinin effect on the endomembrane trafficking in the plant cell, in particular on the PIN1 degradation, we conducted two large proteomic screens: 1) Identification of cytokinin binding proteins using chemical proteomics. 2) Monitoring of proteomic and phosphoproteomic changes upon cytokinin treatment. In the first screen, we identified DYNAMIN RELATED PROTEIN 2A (DRP2A). We found that DRP2A plays a role in cytokinin regulated processes during the plant growth and that cytokinin treatment promotes destabilization of DRP2A protein. However, the role of DRP2A in the PIN1 degradation remains to be elucidated. In the second screen, we found VACUOLAR PROTEIN SORTING 9A (VPS9A). VPS9a plays crucial role in plant’s response to cytokin and in cytokinin mediated PIN1 degradation. Altogether, we identified proteins, which bind to cytokinin and proteins that in response to cytokinin exhibit significantly changed abundance or phosphorylation pattern. By combining information from these two screens, we can pave our way towards understanding of noncanonical cytokinin effects.}, author = {Semerádová, Hana}, isbn = {978-3-99078-014-5}, issn = {2663-337X}, publisher = {Institute of Science and Technology Austria}, title = {{Molecular mechanisms of the cytokinin-regulated endomembrane trafficking to coordinate plant organogenesis}}, doi = {10.15479/at:ista:10135}, year = {2021}, } @article{10191, abstract = {In this work we solve the algorithmic problem of consistency verification for the TSO and PSO memory models given a reads-from map, denoted VTSO-rf and VPSO-rf, respectively. For an execution of n events over k threads and d variables, we establish novel bounds that scale as nk+1 for TSO and as nk+1· min(nk2, 2k· d) for PSO. Moreover, based on our solution to these problems, we develop an SMC algorithm under TSO and PSO that uses the RF equivalence. The algorithm is exploration-optimal, in the sense that it is guaranteed to explore each class of the RF partitioning exactly once, and spends polynomial time per class when k is bounded. Finally, we implement all our algorithms in the SMC tool Nidhugg, and perform a large number of experiments over benchmarks from existing literature. Our experimental results show that our algorithms for VTSO-rf and VPSO-rf provide significant scalability improvements over standard alternatives. Moreover, when used for SMC, the RF partitioning is often much coarser than the standard Shasha-Snir partitioning for TSO/PSO, which yields a significant speedup in the model checking task. }, author = {Bui, Truc Lam and Chatterjee, Krishnendu and Gautam, Tushar and Pavlogiannis, Andreas and Toman, Viktor}, issn = {2475-1421}, journal = {Proceedings of the ACM on Programming Languages}, keywords = {safety, risk, reliability and quality, software}, number = {OOPSLA}, publisher = {Association for Computing Machinery}, title = {{The reads-from equivalence for the TSO and PSO memory models}}, doi = {10.1145/3485541}, volume = {5}, year = {2021}, } @phdthesis{10199, abstract = {The design and verification of concurrent systems remains an open challenge due to the non-determinism that arises from the inter-process communication. In particular, concurrent programs are notoriously difficult both to be written correctly and to be analyzed formally, as complex thread interaction has to be accounted for. The difficulties are further exacerbated when concurrent programs get executed on modern-day hardware, which contains various buffering and caching mechanisms for efficiency reasons. This causes further subtle non-determinism, which can often produce very unintuitive behavior of the concurrent programs. Model checking is at the forefront of tackling the verification problem, where the task is to decide, given as input a concurrent system and a desired property, whether the system satisfies the property. The inherent state-space explosion problem in model checking of concurrent systems causes naïve explicit methods not to scale, thus more inventive methods are required. One such method is stateless model checking (SMC), which explores in memory-efficient manner the program executions rather than the states of the program. State-of-the-art SMC is typically coupled with partial order reduction (POR) techniques, which argue that certain executions provably produce identical system behavior, thus limiting the amount of executions one needs to explore in order to cover all possible behaviors. Another method to tackle the state-space explosion is symbolic model checking, where the considered techniques operate on a succinct implicit representation of the input system rather than explicitly accessing the system. In this thesis we present new techniques for verification of concurrent systems. We present several novel POR methods for SMC of concurrent programs under various models of semantics, some of which account for write-buffering mechanisms. Additionally, we present novel algorithms for symbolic model checking of finite-state concurrent systems, where the desired property of the systems is to ensure a formally defined notion of fairness.}, author = {Toman, Viktor}, issn = {2663-337X}, keywords = {concurrency, verification, model checking}, pages = {166}, publisher = {Institute of Science and Technology Austria}, title = {{Improved verification techniques for concurrent systems}}, doi = {10.15479/at:ista:10199}, year = {2021}, } @phdthesis{10293, abstract = {Indirect reciprocity in evolutionary game theory is a prominent mechanism for explaining the evolution of cooperation among unrelated individuals. In contrast to direct reciprocity, which is based on individuals meeting repeatedly, and conditionally cooperating by using their own experiences, indirect reciprocity is based on individuals’ reputations. If a player helps another, this increases the helper’s public standing, benefitting them in the future. This lets cooperation in the population emerge without individuals having to meet more than once. While the two modes of reciprocity are intertwined, they are difficult to compare. Thus, they are usually studied in isolation. Direct reciprocity can maintain cooperation with simple strategies, and is robust against noise even when players do not remember more than their partner’s last action. Meanwhile, indirect reciprocity requires its successful strategies, or social norms, to be more complex. Exhaustive search previously identified eight such norms, called the “leading eight”, which excel at maintaining cooperation. However, as the first result of this thesis, we show that the leading eight break down once we remove the fundamental assumption that information is synchronized and public, such that everyone agrees on reputations. Once we consider a more realistic scenario of imperfect information, where reputations are private, and individuals occasionally misinterpret or miss observations, the leading eight do not promote cooperation anymore. Instead, minor initial disagreements can proliferate, fragmenting populations into subgroups. In a next step, we consider ways to mitigate this issue. We first explore whether introducing “generosity” can stabilize cooperation when players use the leading eight strategies in noisy environments. This approach of modifying strategies to include probabilistic elements for coping with errors is known to work well in direct reciprocity. However, as we show here, it fails for the more complex norms of indirect reciprocity. Imperfect information still prevents cooperation from evolving. On the other hand, we succeeded to show in this thesis that modifying the leading eight to use “quantitative assessment”, i.e. tracking reputation scores on a scale beyond good and bad, and making overall judgments of others based on a threshold, is highly successful, even when noise increases in the environment. Cooperation can flourish when reputations are more nuanced, and players have a broader understanding what it means to be “good.” Finally, we present a single theoretical framework that unites the two modes of reciprocity despite their differences. Within this framework, we identify a novel simple and successful strategy for indirect reciprocity, which can cope with noisy environments and has an analogue in direct reciprocity. We can also analyze decision making when different sources of information are available. Our results help highlight that for sustaining cooperation, already the most simple rules of reciprocity can be sufficient.}, author = {Schmid, Laura}, issn = {2663-337X}, pages = {171}, publisher = {Institute of Science and Technology Austria}, title = {{Evolution of cooperation via (in)direct reciprocity under imperfect information}}, doi = {10.15479/at:ista:10293}, year = {2021}, }