@unpublished{7675, abstract = {In prokaryotes, thermodynamic models of gene regulation provide a highly quantitative mapping from promoter sequences to gene expression levels that is compatible with in vivo and in vitro bio-physical measurements. Such concordance has not been achieved for models of enhancer function in eukaryotes. In equilibrium models, it is difficult to reconcile the reported short transcription factor (TF) residence times on the DNA with the high specificity of regulation. In non-equilibrium models, progress is difficult due to an explosion in the number of parameters. Here, we navigate this complexity by looking for minimal non-equilibrium enhancer models that yield desired regulatory phenotypes: low TF residence time, high specificity and tunable cooperativity. We find that a single extra parameter, interpretable as the “linking rate” by which bound TFs interact with Mediator components, enables our models to escape equilibrium bounds and access optimal regulatory phenotypes, while remaining consistent with the reported phenomenology and simple enough to be inferred from upcoming experiments. We further find that high specificity in non-equilibrium models is in a tradeoff with gene expression noise, predicting bursty dynamics — an experimentally-observed hallmark of eukaryotic transcription. By drastically reducing the vast parameter space to a much smaller subspace that optimally realizes biological function prior to inference from data, our normative approach holds promise for mathematical models in systems biology.}, author = {Grah, Rok and Zoller, Benjamin and Tkačik, Gašper}, booktitle = {bioRxiv}, publisher = {Cold Spring Harbor Laboratory}, title = {{Normative models of enhancer function}}, doi = {10.1101/2020.04.08.029405}, year = {2020}, } @phdthesis{7460, abstract = {Many methods for the reconstruction of shapes from sets of points produce ordered simplicial complexes, which are collections of vertices, edges, triangles, and their higher-dimensional analogues, called simplices, in which every simplex gets assigned a real value measuring its size. This thesis studies ordered simplicial complexes, with a focus on their topology, which reflects the connectedness of the represented shapes and the presence of holes. We are interested both in understanding better the structure of these complexes, as well as in developing algorithms for applications. For the Delaunay triangulation, the most popular measure for a simplex is the radius of the smallest empty circumsphere. Based on it, we revisit Alpha and Wrap complexes and experimentally determine their probabilistic properties for random data. Also, we prove the existence of tri-partitions, propose algorithms to open and close holes, and extend the concepts from Euclidean to Bregman geometries.}, author = {Ölsböck, Katharina}, issn = {2663-337X}, keywords = {shape reconstruction, hole manipulation, ordered complexes, Alpha complex, Wrap complex, computational topology, Bregman geometry}, pages = {155}, publisher = {Institute of Science and Technology Austria}, title = {{The hole system of triangulated shapes}}, doi = {10.15479/AT:ISTA:7460}, year = {2020}, } @phdthesis{7896, abstract = {A search problem lies in the complexity class FNP if a solution to the given instance of the problem can be verified efficiently. The complexity class TFNP consists of all search problems in FNP that are total in the sense that a solution is guaranteed to exist. TFNP contains a host of interesting problems from fields such as algorithmic game theory, computational topology, number theory and combinatorics. Since TFNP is a semantic class, it is unlikely to have a complete problem. Instead, one studies its syntactic subclasses which are defined based on the combinatorial principle used to argue totality. Of particular interest is the subclass PPAD, which contains important problems like computing Nash equilibrium for bimatrix games and computational counterparts of several fixed-point theorems as complete. In the thesis, we undertake the study of averagecase hardness of TFNP, and in particular its subclass PPAD. Almost nothing was known about average-case hardness of PPAD before a series of recent results showed how to achieve it using a cryptographic primitive called program obfuscation. However, it is currently not known how to construct program obfuscation from standard cryptographic assumptions. Therefore, it is desirable to relax the assumption under which average-case hardness of PPAD can be shown. In the thesis we take a step in this direction. First, we show that assuming the (average-case) hardness of a numbertheoretic problem related to factoring of integers, which we call Iterated-Squaring, PPAD is hard-on-average in the random-oracle model. Then we strengthen this result to show that the average-case hardness of PPAD reduces to the (adaptive) soundness of the Fiat-Shamir Transform, a well-known technique used to compile a public-coin interactive protocol into a non-interactive one. As a corollary, we obtain average-case hardness for PPAD in the random-oracle model assuming the worst-case hardness of #SAT. Moreover, the above results can all be strengthened to obtain average-case hardness for the class CLS ⊆ PPAD. Our main technical contribution is constructing incrementally-verifiable procedures for computing Iterated-Squaring and #SAT. By incrementally-verifiable, we mean that every intermediate state of the computation includes a proof of its correctness, and the proof can be updated and verified in polynomial time. Previous constructions of such procedures relied on strong, non-standard assumptions. Instead, we introduce a technique called recursive proof-merging to obtain the same from weaker assumptions. }, author = {Kamath Hosdurg, Chethan}, issn = {2663-337X}, pages = {126}, publisher = {Institute of Science and Technology Austria}, title = {{On the average-case hardness of total search problems}}, doi = {10.15479/AT:ISTA:7896}, year = {2020}, } @inproceedings{7936, abstract = {State-of-the-art detection systems are generally evaluated on their ability to exhaustively retrieve objects densely distributed in the image, across a wide variety of appearances and semantic categories. Orthogonal to this, many real-life object detection applications, for example in remote sensing, instead require dealing with large images that contain only a few small objects of a single class, scattered heterogeneously across the space. In addition, they are often subject to strict computational constraints, such as limited battery capacity and computing power.To tackle these more practical scenarios, we propose a novel flexible detection scheme that efficiently adapts to variable object sizes and densities: We rely on a sequence of detection stages, each of which has the ability to predict groups of objects as well as individuals. Similar to a detection cascade, this multi-stage architecture spares computational effort by discarding large irrelevant regions of the image early during the detection process. The ability to group objects provides further computational and memory savings, as it allows working with lower image resolutions in early stages, where groups are more easily detected than individuals, as they are more salient. We report experimental results on two aerial image datasets, and show that the proposed method is as accurate yet computationally more efficient than standard single-shot detectors, consistently across three different backbone architectures.}, author = {Royer, Amélie and Lampert, Christoph}, booktitle = {IEEE Winter Conference on Applications of Computer Vision}, isbn = {9781728165530}, location = { Snowmass Village, CO, United States}, publisher = {IEEE}, title = {{Localizing grouped instances for efficient detection in low-resource scenarios}}, doi = {10.1109/WACV45572.2020.9093288}, year = {2020}, } @inproceedings{7937, abstract = {Fine-tuning is a popular way of exploiting knowledge contained in a pre-trained convolutional network for a new visual recognition task. However, the orthogonal setting of transferring knowledge from a pretrained network to a visually different yet semantically close source is rarely considered: This commonly happens with real-life data, which is not necessarily as clean as the training source (noise, geometric transformations, different modalities, etc.).To tackle such scenarios, we introduce a new, generalized form of fine-tuning, called flex-tuning, in which any individual unit (e.g. layer) of a network can be tuned, and the most promising one is chosen automatically. In order to make the method appealing for practical use, we propose two lightweight and faster selection procedures that prove to be good approximations in practice. We study these selection criteria empirically across a variety of domain shifts and data scarcity scenarios, and show that fine-tuning individual units, despite its simplicity, yields very good results as an adaptation technique. As it turns out, in contrast to common practice, rather than the last fully-connected unit it is best to tune an intermediate or early one in many domain- shift scenarios, which is accurately detected by flex-tuning.}, author = {Royer, Amélie and Lampert, Christoph}, booktitle = {2020 IEEE Winter Conference on Applications of Computer Vision}, isbn = {9781728165530}, location = {Snowmass Village, CO, United States}, publisher = {IEEE}, title = {{A flexible selection scheme for minimum-effort transfer learning}}, doi = {10.1109/WACV45572.2020.9093635}, year = {2020}, } @inbook{8092, abstract = {Image translation refers to the task of mapping images from a visual domain to another. Given two unpaired collections of images, we aim to learn a mapping between the corpus-level style of each collection, while preserving semantic content shared across the two domains. We introduce xgan, a dual adversarial auto-encoder, which captures a shared representation of the common domain semantic content in an unsupervised way, while jointly learning the domain-to-domain image translations in both directions. We exploit ideas from the domain adaptation literature and define a semantic consistency loss which encourages the learned embedding to preserve semantics shared across domains. We report promising qualitative results for the task of face-to-cartoon translation. The cartoon dataset we collected for this purpose, “CartoonSet”, is also publicly available as a new benchmark for semantic style transfer at https://google.github.io/cartoonset/index.html.}, author = {Royer, Amélie and Bousmalis, Konstantinos and Gouws, Stephan and Bertsch, Fred and Mosseri, Inbar and Cole, Forrester and Murphy, Kevin}, booktitle = {Domain Adaptation for Visual Understanding}, editor = {Singh, Richa and Vatsa, Mayank and Patel, Vishal M. and Ratha, Nalini}, isbn = {9783030306717}, pages = {33--49}, publisher = {Springer Nature}, title = {{XGAN: Unsupervised image-to-image translation for many-to-many mappings}}, doi = {10.1007/978-3-030-30671-7_3}, year = {2020}, } @phdthesis{7944, abstract = {This thesis considers two examples of reconfiguration problems: flipping edges in edge-labelled triangulations of planar point sets and swapping labelled tokens placed on vertices of a graph. In both cases the studied structures – all the triangulations of a given point set or all token placements on a given graph – can be thought of as vertices of the so-called reconfiguration graph, in which two vertices are adjacent if the corresponding structures differ by a single elementary operation – by a flip of a diagonal in a triangulation or by a swap of tokens on adjacent vertices, respectively. We study the reconfiguration of one instance of a structure into another via (shortest) paths in the reconfiguration graph. For triangulations of point sets in which each edge has a unique label and a flip transfers the label from the removed edge to the new edge, we prove a polynomial-time testable condition, called the Orbit Theorem, that characterizes when two triangulations of the same point set lie in the same connected component of the reconfiguration graph. The condition was first conjectured by Bose, Lubiw, Pathak and Verdonschot. We additionally provide a polynomial time algorithm that computes a reconfiguring flip sequence, if it exists. Our proof of the Orbit Theorem uses topological properties of a certain high-dimensional cell complex that has the usual reconfiguration graph as its 1-skeleton. In the context of token swapping on a tree graph, we make partial progress on the problem of finding shortest reconfiguration sequences. We disprove the so-called Happy Leaf Conjecture and demonstrate the importance of swapping tokens that are already placed at the correct vertices. We also prove that a generalization of the problem to weighted coloured token swapping is NP-hard on trees but solvable in polynomial time on paths and stars.}, author = {Masárová, Zuzana}, isbn = {978-3-99078-005-3}, issn = {2663-337X}, keywords = {reconfiguration, reconfiguration graph, triangulations, flip, constrained triangulations, shellability, piecewise-linear balls, token swapping, trees, coloured weighted token swapping}, pages = {160}, publisher = {Institute of Science and Technology Austria}, title = {{Reconfiguration problems}}, doi = {10.15479/AT:ISTA:7944}, year = {2020}, } @article{8587, abstract = {Inspired by the possibility to experimentally manipulate and enhance chemical reactivity in helium nanodroplets, we investigate the effective interaction and the resulting correlations between two diatomic molecules immersed in a bath of bosons. By analogy with the bipolaron, we introduce the biangulon quasiparticle describing two rotating molecules that align with respect to each other due to the effective attractive interaction mediated by the excitations of the bath. We study this system in different parameter regimes and apply several theoretical approaches to describe its properties. Using a Born–Oppenheimer approximation, we investigate the dependence of the effective intermolecular interaction on the rotational state of the two molecules. In the strong-coupling regime, a product-state ansatz shows that the molecules tend to have a strong alignment in the ground state. To investigate the system in the weak-coupling regime, we apply a one-phonon excitation variational ansatz, which allows us to access the energy spectrum. In comparison to the angulon quasiparticle, the biangulon shows shifted angulon instabilities and an additional spectral instability, where resonant angular momentum transfer between the molecules and the bath takes place. These features are proposed as an experimentally observable signature for the formation of the biangulon quasiparticle. Finally, by using products of single angulon and bare impurity wave functions as basis states, we introduce a diagonalization scheme that allows us to describe the transition from two separated angulons to a biangulon as a function of the distance between the two molecules.}, author = {Li, Xiang and Yakaboylu, Enderalp and Bighin, Giacomo and Schmidt, Richard and Lemeshko, Mikhail and Deuchert, Andreas}, issn = {1089-7690}, journal = {The Journal of Chemical Physics}, keywords = {Physical and Theoretical Chemistry, General Physics and Astronomy}, number = {16}, publisher = {AIP Publishing}, title = {{Intermolecular forces and correlations mediated by a phonon bath}}, doi = {10.1063/1.5144759}, volume = {152}, year = {2020}, } @phdthesis{8341, abstract = {One of the most striking hallmarks of the eukaryotic cell is the presence of intracellular vesicles and organelles. Each of these membrane-enclosed compartments has a distinct composition of lipids and proteins, which is essential for accurate membrane traffic and homeostasis. Interestingly, their biochemical identities are achieved with the help of small GTPases of the Rab family, which cycle between GDP- and GTP-bound forms on the selected membrane surface. While this activity switch is well understood for an individual protein, how Rab GTPases collectively transition between states to generate decisive signal propagation in space and time is unclear. In my PhD thesis, I present in vitro reconstitution experiments with theoretical modeling to systematically study a minimal Rab5 activation network from bottom-up. We find that positive feedback based on known molecular interactions gives rise to bistable GTPase activity switching on system’s scale. Furthermore, we determine that collective transition near the critical point is intrinsically stochastic and provide evidence that the inactive Rab5 abundance on the membrane can shape the network response. Finally, we demonstrate that collective switching can spread on the lipid bilayer as a traveling activation wave, representing a possible emergent activity pattern in endosomal maturation. Together, our findings reveal new insights into the self-organization properties of signaling networks away from chemical equilibrium. Our work highlights the importance of systematic characterization of biochemical systems in well-defined physiological conditions. This way, we were able to answer long-standing open questions in the field and close the gap between regulatory processes on a molecular scale and emergent responses on system’s level.}, author = {Bezeljak, Urban}, issn = {2663-337X}, pages = {215}, publisher = {Institute of Science and Technology Austria}, title = {{In vitro reconstitution of a Rab activation switch}}, doi = {10.15479/AT:ISTA:8341}, year = {2020}, } @article{7580, abstract = {The eukaryotic endomembrane system is controlled by small GTPases of the Rab family, which are activated at defined times and locations in a switch-like manner. While this switch is well understood for an individual protein, how regulatory networks produce intracellular activity patterns is currently not known. Here, we combine in vitro reconstitution experiments with computational modeling to study a minimal Rab5 activation network. We find that the molecular interactions in this system give rise to a positive feedback and bistable collective switching of Rab5. Furthermore, we find that switching near the critical point is intrinsically stochastic and provide evidence that controlling the inactive population of Rab5 on the membrane can shape the network response. Notably, we demonstrate that collective switching can spread on the membrane surface as a traveling wave of Rab5 activation. Together, our findings reveal how biochemical signaling networks control vesicle trafficking pathways and how their nonequilibrium properties define the spatiotemporal organization of the cell.}, author = {Bezeljak, Urban and Loya, Hrushikesh and Kaczmarek, Beata M and Saunders, Timothy E. and Loose, Martin}, issn = {1091-6490}, journal = {Proceedings of the National Academy of Sciences}, number = {12}, pages = {6504--6549}, publisher = {Proceedings of the National Academy of Sciences}, title = {{Stochastic activation and bistability in a Rab GTPase regulatory network}}, doi = {10.1073/pnas.1921027117}, volume = {117}, year = {2020}, } @phdthesis{8032, abstract = {Algorithms in computational 3-manifold topology typically take a triangulation as an input and return topological information about the underlying 3-manifold. However, extracting the desired information from a triangulation (e.g., evaluating an invariant) is often computationally very expensive. In recent years this complexity barrier has been successfully tackled in some cases by importing ideas from the theory of parameterized algorithms into the realm of 3-manifolds. Various computationally hard problems were shown to be efficiently solvable for input triangulations that are sufficiently “tree-like.” In this thesis we focus on the key combinatorial parameter in the above context: we consider the treewidth of a compact, orientable 3-manifold, i.e., the smallest treewidth of the dual graph of any triangulation thereof. By building on the work of Scharlemann–Thompson and Scharlemann–Schultens–Saito on generalized Heegaard splittings, and on the work of Jaco–Rubinstein on layered triangulations, we establish quantitative relations between the treewidth and classical topological invariants of a 3-manifold. In particular, among other results, we show that the treewidth of a closed, orientable, irreducible, non-Haken 3-manifold is always within a constant factor of its Heegaard genus.}, author = {Huszár, Kristóf}, isbn = {978-3-99078-006-0}, issn = {2663-337X}, pages = {xviii+120}, publisher = {Institute of Science and Technology Austria}, title = {{Combinatorial width parameters for 3-dimensional manifolds}}, doi = {10.15479/AT:ISTA:8032}, year = {2020}, } @inproceedings{8195, abstract = {This paper presents a foundation for refining concurrent programs with structured control flow. The verification problem is decomposed into subproblems that aid interactive program development, proof reuse, and automation. The formalization in this paper is the basis of a new design and implementation of the Civl verifier.}, author = {Kragl, Bernhard and Qadeer, Shaz and Henzinger, Thomas A}, booktitle = {Computer Aided Verification}, isbn = {9783030532871}, issn = {1611-3349}, pages = {275--298}, publisher = {Springer Nature}, title = {{Refinement for structured concurrent programs}}, doi = {10.1007/978-3-030-53288-8_14}, volume = {12224}, year = {2020}, } @inproceedings{8012, abstract = {Asynchronous programs are notoriously difficult to reason about because they spawn computation tasks which take effect asynchronously in a nondeterministic way. Devising inductive invariants for such programs requires understanding and stating complex relationships between an unbounded number of computation tasks in arbitrarily long executions. In this paper, we introduce inductive sequentialization, a new proof rule that sidesteps this complexity via a sequential reduction, a sequential program that captures every behavior of the original program up to reordering of coarse-grained commutative actions. A sequential reduction of a concurrent program is easy to reason about since it corresponds to a simple execution of the program in an idealized synchronous environment, where processes act in a fixed order and at the same speed. We have implemented and integrated our proof rule in the CIVL verifier, allowing us to provably derive fine-grained implementations of asynchronous programs. We have successfully applied our proof rule to a diverse set of message-passing protocols, including leader election protocols, two-phase commit, and Paxos.}, author = {Kragl, Bernhard and Enea, Constantin and Henzinger, Thomas A and Mutluergil, Suha Orhun and Qadeer, Shaz}, booktitle = {Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation}, isbn = {9781450376136}, location = {London, United Kingdom}, pages = {227--242}, publisher = {Association for Computing Machinery}, title = {{Inductive sequentialization of asynchronous programs}}, doi = {10.1145/3385412.3385980}, year = {2020}, } @phdthesis{8358, abstract = {During bacterial cell division, the tubulin-homolog FtsZ forms a ring-like structure at the center of the cell. This so-called Z-ring acts as a scaffold recruiting several division-related proteins to mid-cell and plays a key role in distributing proteins at the division site, a feature driven by the treadmilling motion of FtsZ filaments around the septum. What regulates the architecture, dynamics and stability of the Z-ring is still poorly understood, but FtsZ-associated proteins (Zaps) are known to play an important role. Advances in fluorescence microscopy and in vitro reconstitution experiments have helped to shed light into some of the dynamic properties of these complex systems, but methods that allow to collect and analyze large quantitative data sets of the underlying polymer dynamics are still missing. Here, using an in vitro reconstitution approach, we studied how different Zaps affect FtsZ filament dynamics and organization into large-scale patterns, giving special emphasis to the role of the well-conserved protein ZapA. For this purpose, we use high-resolution fluorescence microscopy combined with novel image analysis workfows to study pattern organization and polymerization dynamics of active filaments. We quantified the influence of Zaps on FtsZ on three diferent spatial scales: the large-scale organization of the membrane-bound filament network, the underlying polymerization dynamics and the behavior of single molecules. We found that ZapA cooperatively increases the spatial order of the filament network, binds only transiently to FtsZ filaments and has no effect on filament length and treadmilling velocity. Our data provides a model for how FtsZ-associated proteins can increase the precision and stability of the bacterial cell division machinery in a switch-like manner, without compromising filament dynamics. Furthermore, we believe that our automated quantitative methods can be used to analyze a large variety of dynamic cytoskeletal systems, using standard time-lapse movies of homogeneously labeled proteins obtained from experiments in vitro or even inside the living cell. }, author = {Dos Santos Caldas, Paulo R}, isbn = {978-3-99078-009-1}, issn = {2663-337X}, pages = {135}, publisher = {Institute of Science and Technology Austria}, title = {{Organization and dynamics of treadmilling filaments in cytoskeletal networks of FtsZ and its crosslinkers}}, doi = {10.15479/AT:ISTA:8358}, year = {2020}, } @inproceedings{8703, abstract = {Even though Delaunay originally introduced his famous triangulations in the case of infinite point sets with translational periodicity, a software that computes such triangulations in the general case is not yet available, to the best of our knowledge. Combining and generalizing previous work, we present a practical algorithm for computing such triangulations. The algorithm has been implemented and experiments show that its performance is as good as the one of the CGAL package, which is restricted to cubic periodicity. }, author = {Osang, Georg F and Rouxel-Labbé, Mael and Teillaud, Monique}, booktitle = {28th Annual European Symposium on Algorithms}, isbn = {9783959771627}, issn = {18688969}, location = {Virtual, Online; Pisa, Italy}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Generalizing CGAL periodic Delaunay triangulations}}, doi = {10.4230/LIPIcs.ESA.2020.75}, volume = {173}, year = {2020}, } @inproceedings{7481, abstract = {We address the following question: How redundant is the parameterisation of ReLU networks? Specifically, we consider transformations of the weight space which leave the function implemented by the network intact. Two such transformations are known for feed-forward architectures: permutation of neurons within a layer, and positive scaling of all incoming weights of a neuron coupled with inverse scaling of its outgoing weights. In this work, we show for architectures with non-increasing widths that permutation and scaling are in fact the only function-preserving weight transformations. For any eligible architecture we give an explicit construction of a neural network such that any other network that implements the same function can be obtained from the original one by the application of permutations and rescaling. The proof relies on a geometric understanding of boundaries between linear regions of ReLU networks, and we hope the developed mathematical tools are of independent interest.}, author = {Bui Thi Mai, Phuong and Lampert, Christoph}, booktitle = {8th International Conference on Learning Representations}, location = {Online}, title = {{Functional vs. parametric equivalence of ReLU networks}}, year = {2020}, } @article{9781, abstract = {We consider the Pekar functional on a ball in ℝ3. We prove uniqueness of minimizers, and a quadratic lower bound in terms of the distance to the minimizer. The latter follows from nondegeneracy of the Hessian at the minimum.}, author = {Feliciangeli, Dario and Seiringer, Robert}, issn = {1095-7154}, journal = {SIAM Journal on Mathematical Analysis}, keywords = {Applied Mathematics, Computational Mathematics, Analysis}, number = {1}, pages = {605--622}, publisher = {Society for Industrial & Applied Mathematics }, title = {{Uniqueness and nondegeneracy of minimizers of the Pekar functional on a ball}}, doi = {10.1137/19m126284x}, volume = {52}, year = {2020}, } @article{7489, abstract = {In the present work, we consider the evolution of two fluids separated by a sharp interface in the presence of surface tension—like, for example, the evolution of oil bubbles in water. Our main result is a weak–strong uniqueness principle for the corresponding free boundary problem for the incompressible Navier–Stokes equation: as long as a strong solution exists, any varifold solution must coincide with it. In particular, in the absence of physical singularities, the concept of varifold solutions—whose global in time existence has been shown by Abels (Interfaces Free Bound 9(1):31–65, 2007) for general initial data—does not introduce a mechanism for non-uniqueness. The key ingredient of our approach is the construction of a relative entropy functional capable of controlling the interface error. If the viscosities of the two fluids do not coincide, even for classical (strong) solutions the gradient of the velocity field becomes discontinuous at the interface, introducing the need for a careful additional adaption of the relative entropy.}, author = {Fischer, Julian L and Hensel, Sebastian}, issn = {14320673}, journal = {Archive for Rational Mechanics and Analysis}, pages = {967--1087}, publisher = {Springer Nature}, title = {{Weak–strong uniqueness for the Navier–Stokes equation for two fluids with surface tension}}, doi = {10.1007/s00205-019-01486-2}, volume = {236}, year = {2020}, } @unpublished{10012, abstract = {We prove that in the absence of topological changes, the notion of BV solutions to planar multiphase mean curvature flow does not allow for a mechanism for (unphysical) non-uniqueness. Our approach is based on the local structure of the energy landscape near a classical evolution by mean curvature. Mean curvature flow being the gradient flow of the surface energy functional, we develop a gradient-flow analogue of the notion of calibrations. Just like the existence of a calibration guarantees that one has reached a global minimum in the energy landscape, the existence of a "gradient flow calibration" ensures that the route of steepest descent in the energy landscape is unique and stable.}, author = {Fischer, Julian L and Hensel, Sebastian and Laux, Tim and Simon, Thilo}, booktitle = {arXiv}, title = {{The local structure of the energy landscape in multiphase mean curvature flow: weak-strong uniqueness and stability of evolutions}}, year = {2020}, } @article{8755, abstract = {The superconducting circuit community has recently discovered the promising potential of superinductors. These circuit elements have a characteristic impedance exceeding the resistance quantum RQ ≈ 6.45 kΩ which leads to a suppression of ground state charge fluctuations. Applications include the realization of hardware protected qubits for fault tolerant quantum computing, improved coupling to small dipole moment objects and defining a new quantum metrology standard for the ampere. In this work we refute the widespread notion that superinductors can only be implemented based on kinetic inductance, i.e. using disordered superconductors or Josephson junction arrays. We present modeling, fabrication and characterization of 104 planar aluminum coil resonators with a characteristic impedance up to 30.9 kΩ at 5.6 GHz and a capacitance down to ≤ 1 fF, with lowloss and a power handling reaching 108 intra-cavity photons. Geometric superinductors are free of uncontrolled tunneling events and offer high reproducibility, linearity and the ability to couple magnetically - properties that significantly broaden the scope of future quantum circuits. }, author = {Peruzzo, Matilda and Trioni, Andrea and Hassani, Farid and Zemlicka, Martin and Fink, Johannes M}, issn = {23317019}, journal = {Physical Review Applied}, number = {4}, publisher = {American Physical Society}, title = {{Surpassing the resistance quantum with a geometric superinductor}}, doi = {10.1103/PhysRevApplied.14.044055}, volume = {14}, year = {2020}, } @article{7573, abstract = {This paper deals with dynamical optimal transport metrics defined by spatial discretisation of the Benamou–Benamou formula for the Kantorovich metric . Such metrics appear naturally in discretisations of -gradient flow formulations for dissipative PDE. However, it has recently been shown that these metrics do not in general converge to , unless strong geometric constraints are imposed on the discrete mesh. In this paper we prove that, in a 1-dimensional periodic setting, discrete transport metrics converge to a limiting transport metric with a non-trivial effective mobility. This mobility depends sensitively on the geometry of the mesh and on the non-local mobility at the discrete level. Our result quantifies to what extent discrete transport can make use of microstructure in the mesh to reduce the cost of transport.}, author = {Gladbach, Peter and Kopfer, Eva and Maas, Jan and Portinale, Lorenzo}, issn = {00217824}, journal = {Journal de Mathematiques Pures et Appliquees}, number = {7}, pages = {204--234}, publisher = {Elsevier}, title = {{Homogenisation of one-dimensional discrete optimal transport}}, doi = {10.1016/j.matpur.2020.02.008}, volume = {139}, year = {2020}, } @unpublished{10022, abstract = {We consider finite-volume approximations of Fokker-Planck equations on bounded convex domains in R^d and study the corresponding gradient flow structures. We reprove the convergence of the discrete to continuous Fokker-Planck equation via the method of Evolutionary Γ-convergence, i.e., we pass to the limit at the level of the gradient flow structures, generalising the one-dimensional result obtained by Disser and Liero. The proof is of variational nature and relies on a Mosco convergence result for functionals in the discrete-to-continuum limit that is of independent interest. Our results apply to arbitrary regular meshes, even though the associated discrete transport distances may fail to converge to the Wasserstein distance in this generality.}, author = {Forkert, Dominik L and Maas, Jan and Portinale, Lorenzo}, booktitle = {arXiv}, pages = {33}, title = {{Evolutionary Γ-convergence of entropic gradient flow structures for Fokker-Planck equations in multiple dimensions}}, year = {2020}, } @inproceedings{8724, abstract = {We study the problem of learning from multiple untrusted data sources, a scenario of increasing practical relevance given the recent emergence of crowdsourcing and collaborative learning paradigms. Specifically, we analyze the situation in which a learning system obtains datasets from multiple sources, some of which might be biased or even adversarially perturbed. It is known that in the single-source case, an adversary with the power to corrupt a fixed fraction of the training data can prevent PAC-learnability, that is, even in the limit of infinitely much training data, no learning system can approach the optimal test error. In this work we show that, surprisingly, the same is not true in the multi-source setting, where the adversary can arbitrarily corrupt a fixed fraction of the data sources. Our main results are a generalization bound that provides finite-sample guarantees for this learning setting, as well as corresponding lower bounds. Besides establishing PAC-learnability our results also show that in a cooperative learning setting sharing data with other parties has provable benefits, even if some participants are malicious. }, author = {Konstantinov, Nikola H and Frantar, Elias and Alistarh, Dan-Adrian and Lampert, Christoph}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, issn = {2640-3498}, location = {Online}, pages = {5416--5425}, publisher = {ML Research Press}, title = {{On the sample complexity of adversarial multi-source PAC learning}}, volume = {119}, year = {2020}, } @article{8644, abstract = {Determining the phase diagram of systems consisting of smaller subsystems 'connected' via a tunable coupling is a challenging task relevant for a variety of physical settings. A general question is whether new phases, not present in the uncoupled limit, may arise. We use machine learning and a suitable quasidistance between different points of the phase diagram to study layered spin models, in which the spin variables constituting each of the uncoupled systems (to which we refer as layers) are coupled to each other via an interlayer coupling. In such systems, in general, composite order parameters involving spins of different layers may emerge as a consequence of the interlayer coupling. We focus on the layered Ising and Ashkin–Teller models as a paradigmatic case study, determining their phase diagram via the application of a machine learning algorithm to the Monte Carlo data. Remarkably our technique is able to correctly characterize all the system phases also in the case of hidden order parameters, i.e. order parameters whose expression in terms of the microscopic configurations would require additional preprocessing of the data fed to the algorithm. We correctly retrieve the three known phases of the Ashkin–Teller model with ferromagnetic couplings, including the phase described by a composite order parameter. For the bilayer and trilayer Ising models the phases we find are only the ferromagnetic and the paramagnetic ones. Within the approach we introduce, owing to the construction of convolutional neural networks, naturally suitable for layered image-like data with arbitrary number of layers, no preprocessing of the Monte Carlo data is needed, also with regard to its spatial structure. The physical meaning of our results is discussed and compared with analytical data, where available. Yet, the method can be used without any a priori knowledge of the phases one seeks to find and can be applied to other models and structures.}, author = {Rzadkowski, Wojciech and Defenu, N and Chiacchiera, S and Trombettoni, A and Bighin, Giacomo}, issn = {13672630}, journal = {New Journal of Physics}, number = {9}, publisher = {IOP Publishing}, title = {{Detecting composite orders in layered models via machine learning}}, doi = {10.1088/1367-2630/abae44}, volume = {22}, year = {2020}, } @article{8705, abstract = {We consider the quantum mechanical many-body problem of a single impurity particle immersed in a weakly interacting Bose gas. The impurity interacts with the bosons via a two-body potential. We study the Hamiltonian of this system in the mean-field limit and rigorously show that, at low energies, the problem is well described by the Fröhlich polaron model.}, author = {Mysliwy, Krzysztof and Seiringer, Robert}, issn = {1424-0637}, journal = {Annales Henri Poincare}, number = {12}, pages = {4003--4025}, publisher = {Springer Nature}, title = {{Microscopic derivation of the Fröhlich Hamiltonian for the Bose polaron in the mean-field limit}}, doi = {10.1007/s00023-020-00969-3}, volume = {21}, year = {2020}, } @article{14125, abstract = {Motivation: Recent technological advances have led to an increase in the production and availability of single-cell data. The ability to integrate a set of multi-technology measurements would allow the identification of biologically or clinically meaningful observations through the unification of the perspectives afforded by each technology. In most cases, however, profiling technologies consume the used cells and thus pairwise correspondences between datasets are lost. Due to the sheer size single-cell datasets can acquire, scalable algorithms that are able to universally match single-cell measurements carried out in one cell to its corresponding sibling in another technology are needed. Results: We propose Single-Cell data Integration via Matching (SCIM), a scalable approach to recover such correspondences in two or more technologies. SCIM assumes that cells share a common (low-dimensional) underlying structure and that the underlying cell distribution is approximately constant across technologies. It constructs a technology-invariant latent space using an autoencoder framework with an adversarial objective. Multi-modal datasets are integrated by pairing cells across technologies using a bipartite matching scheme that operates on the low-dimensional latent representations. We evaluate SCIM on a simulated cellular branching process and show that the cell-to-cell matches derived by SCIM reflect the same pseudotime on the simulated dataset. Moreover, we apply our method to two real-world scenarios, a melanoma tumor sample and a human bone marrow sample, where we pair cells from a scRNA dataset to their sibling cells in a CyTOF dataset achieving 90% and 78% cell-matching accuracy for each one of the samples, respectively.}, author = {Stark, Stefan G and Ficek, Joanna and Locatello, Francesco and Bonilla, Ximena and Chevrier, Stéphane and Singer, Franziska and Aebersold, Rudolf and Al-Quaddoomi, Faisal S and Albinus, Jonas and Alborelli, Ilaria and Andani, Sonali and Attinger, Per-Olof and Bacac, Marina and Baumhoer, Daniel and Beck-Schimmer, Beatrice and Beerenwinkel, Niko and Beisel, Christian and Bernasconi, Lara and Bertolini, Anne and Bodenmiller, Bernd and Bonilla, Ximena and Casanova, Ruben and Chevrier, Stéphane and Chicherova, Natalia and D'Costa, Maya and Danenberg, Esther and Davidson, Natalie and gan, Monica-Andreea Dră and Dummer, Reinhard and Engler, Stefanie and Erkens, Martin and Eschbach, Katja and Esposito, Cinzia and Fedier, André and Ferreira, Pedro and Ficek, Joanna and Frei, Anja L and Frey, Bruno and Goetze, Sandra and Grob, Linda and Gut, Gabriele and Günther, Detlef and Haberecker, Martina and Haeuptle, Pirmin and Heinzelmann-Schwarz, Viola and Herter, Sylvia and Holtackers, Rene and Huesser, Tamara and Irmisch, Anja and Jacob, Francis and Jacobs, Andrea and Jaeger, Tim M and Jahn, Katharina and James, Alva R and Jermann, Philip M and Kahles, André and Kahraman, Abdullah and Koelzer, Viktor H and Kuebler, Werner and Kuipers, Jack and Kunze, Christian P and Kurzeder, Christian and Lehmann, Kjong-Van and Levesque, Mitchell and Lugert, Sebastian and Maass, Gerd and Manz, Markus and Markolin, Philipp and Mena, Julien and Menzel, Ulrike and Metzler, Julian M and Miglino, Nicola and Milani, Emanuela S and Moch, Holger and Muenst, Simone and Murri, Riccardo and Ng, Charlotte KY and Nicolet, Stefan and Nowak, Marta and Pedrioli, Patrick GA and Pelkmans, Lucas and Piscuoglio, Salvatore and Prummer, Michael and Ritter, Mathilde and Rommel, Christian and Rosano-González, María L and Rätsch, Gunnar and Santacroce, Natascha and Castillo, Jacobo Sarabia del and Schlenker, Ramona and Schwalie, Petra C and Schwan, Severin and Schär, Tobias and Senti, Gabriela and Singer, Franziska and Sivapatham, Sujana and Snijder, Berend and Sobottka, Bettina and Sreedharan, Vipin T and Stark, Stefan and Stekhoven, Daniel J and Theocharides, Alexandre PA and Thomas, Tinu M and Tolnay, Markus and Tosevski, Vinko and Toussaint, Nora C and Tuncel, Mustafa A and Tusup, Marina and Drogen, Audrey Van and Vetter, Marcus and Vlajnic, Tatjana and Weber, Sandra and Weber, Walter P and Wegmann, Rebekka and Weller, Michael and Wendt, Fabian and Wey, Norbert and Wicki, Andreas and Wollscheid, Bernd and Yu, Shuqing and Ziegler, Johanna and Zimmermann, Marc and Zoche, Martin and Zuend, Gregor and Rätsch, Gunnar and Lehmann, Kjong-Van}, issn = {1367-4811}, journal = {Bioinformatics}, keywords = {Computational Mathematics, Computational Theory and Mathematics, Computer Science Applications, Molecular Biology, Biochemistry, Statistics and Probability}, number = {Supplement_2}, pages = {i919--i927}, publisher = {Oxford University Press}, title = {{SCIM: Universal single-cell matching with unpaired feature sets}}, doi = {10.1093/bioinformatics/btaa843}, volume = {36}, year = {2020}, } @inproceedings{14186, abstract = {The goal of the unsupervised learning of disentangled representations is to separate the independent explanatory factors of variation in the data without access to supervision. In this paper, we summarize the results of Locatello et al., 2019, and focus on their implications for practitioners. We discuss the theoretical result showing that the unsupervised learning of disentangled representations is fundamentally impossible without inductive biases and the practical challenges it entails. Finally, we comment on our experimental findings, highlighting the limitations of state-of-the-art approaches and directions for future research.}, author = {Locatello, Francesco and Bauer, Stefan and Lucic, Mario and Rätsch, Gunnar and Gelly, Sylvain and Schölkopf, Bernhard and Bachem, Olivier}, booktitle = {The 34th AAAI Conference on Artificial Intelligence}, isbn = {9781577358350}, issn = {2374-3468}, location = {New York, NY, United States}, number = {9}, pages = {13681--13684}, publisher = {Association for the Advancement of Artificial Intelligence}, title = {{A commentary on the unsupervised learning of disentangled representations}}, doi = {10.1609/aaai.v34i09.7120}, volume = {34}, year = {2020}, } @inproceedings{14188, abstract = {Intelligent agents should be able to learn useful representations by observing changes in their environment. We model such observations as pairs of non-i.i.d. images sharing at least one of the underlying factors of variation. First, we theoretically show that only knowing how many factors have changed, but not which ones, is sufficient to learn disentangled representations. Second, we provide practical algorithms that learn disentangled representations from pairs of images without requiring annotation of groups, individual factors, or the number of factors that have changed. Third, we perform a large-scale empirical study and show that such pairs of observations are sufficient to reliably learn disentangled representations on several benchmark data sets. Finally, we evaluate our learned representations and find that they are simultaneously useful on a diverse suite of tasks, including generalization under covariate shifts, fairness, and abstract reasoning. Overall, our results demonstrate that weak supervision enables learning of useful disentangled representations in realistic scenarios.}, author = {Locatello, Francesco and Poole, Ben and Rätsch, Gunnar and Schölkopf, Bernhard and Bachem, Olivier and Tschannen, Michael}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, location = {Virtual}, pages = {6348–6359}, title = {{Weakly-supervised disentanglement without compromises}}, volume = {119}, year = {2020}, } @inproceedings{14187, abstract = {We propose a novel Stochastic Frank-Wolfe (a.k.a. conditional gradient) algorithm for constrained smooth finite-sum minimization with a generalized linear prediction/structure. This class of problems includes empirical risk minimization with sparse, low-rank, or other structured constraints. The proposed method is simple to implement, does not require step-size tuning, and has a constant per-iteration cost that is independent of the dataset size. Furthermore, as a byproduct of the method we obtain a stochastic estimator of the Frank-Wolfe gap that can be used as a stopping criterion. Depending on the setting, the proposed method matches or improves on the best computational guarantees for Stochastic Frank-Wolfe algorithms. Benchmarks on several datasets highlight different regimes in which the proposed method exhibits a faster empirical convergence than related methods. Finally, we provide an implementation of all considered methods in an open-source package.}, author = {Négiar, Geoffrey and Dresdner, Gideon and Tsai, Alicia and Ghaoui, Laurent El and Locatello, Francesco and Freund, Robert M. and Pedregosa, Fabian}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, location = {Virtual}, pages = {7253--7262}, title = {{Stochastic Frank-Wolfe for constrained finite-sum minimization}}, volume = {119}, year = {2020}, } @article{14195, abstract = {The idea behind the unsupervised learning of disentangled representations is that real-world data is generated by a few explanatory factors of variation which can be recovered by unsupervised learning algorithms. In this paper, we provide a sober look at recent progress in the field and challenge some common assumptions. We first theoretically show that the unsupervised learning of disentangled representations is fundamentally impossible without inductive biases on both the models and the data. Then, we train over 14000 models covering most prominent methods and evaluation metrics in a reproducible large-scale experimental study on eight data sets. We observe that while the different methods successfully enforce properties “encouraged” by the corresponding losses, well-disentangled models seemingly cannot be identified without supervision. Furthermore, different evaluation metrics do not always agree on what should be considered “disentangled” and exhibit systematic differences in the estimation. Finally, increased disentanglement does not seem to necessarily lead to a decreased sample complexity of learning for downstream tasks. Our results suggest that future work on disentanglement learning should be explicit about the role of inductive biases and (implicit) supervision, investigate concrete benefits of enforcing disentanglement of the learned representations, and consider a reproducible experimental setup covering several data sets.}, author = {Locatello, Francesco and Bauer, Stefan and Lucic, Mario and Rätsch, Gunnar and Gelly, Sylvain and Schölkopf, Bernhard and Bachem, Olivier}, journal = {Journal of Machine Learning Research}, publisher = {MIT Press}, title = {{A sober look at the unsupervised learning of disentangled representations and their evaluation}}, volume = {21}, year = {2020}, } @article{7569, abstract = {Genes differ in the frequency at which they are expressed and in the form of regulation used to control their activity. In particular, positive or negative regulation can lead to activation of a gene in response to an external signal. Previous works proposed that the form of regulation of a gene correlates with its frequency of usage: positive regulation when the gene is frequently expressed and negative regulation when infrequently expressed. Such network design means that, in the absence of their regulators, the genes are found in their least required activity state, hence regulatory intervention is often necessary. Due to the multitude of genes and regulators, spurious binding and unbinding events, called “crosstalk”, could occur. To determine how the form of regulation affects the global crosstalk in the network, we used a mathematical model that includes multiple regulators and multiple target genes. We found that crosstalk depends non-monotonically on the availability of regulators. Our analysis showed that excess use of regulation entailed by the formerly suggested network design caused high crosstalk levels in a large part of the parameter space. We therefore considered the opposite ‘idle’ design, where the default unregulated state of genes is their frequently required activity state. We found, that ‘idle’ design minimized the use of regulation and thus minimized crosstalk. In addition, we estimated global crosstalk of S. cerevisiae using transcription factors binding data. We demonstrated that even partial network data could suffice to estimate its global crosstalk, suggesting its applicability to additional organisms. We found that S. cerevisiae estimated crosstalk is lower than that of a random network, suggesting that natural selection reduces crosstalk. In summary, our study highlights a new type of protein production cost which is typically overlooked: that of regulatory interference caused by the presence of excess regulators in the cell. It demonstrates the importance of whole-network descriptions, which could show effects missed by single-gene models.}, author = {Grah, Rok and Friedlander, Tamar}, issn = {1553-7358}, journal = {PLOS Computational Biology}, number = {2}, publisher = {Public Library of Science}, title = {{The relation between crosstalk and gene regulation form revisited}}, doi = {10.1371/journal.pcbi.1007642}, volume = {16}, year = {2020}, } @unpublished{8813, abstract = {In mammals, chromatin marks at imprinted genes are asymmetrically inherited to control parentally-biased gene expression. This control is thought predominantly to involve parent-specific differentially methylated regions (DMR) in genomic DNA. However, neither parent-of-origin-specific transcription nor DMRs have been comprehensively mapped. We here address this by integrating transcriptomic and epigenomic approaches in mouse preimplantation embryos (blastocysts). Transcriptome-analysis identified 71 genes expressed with previously unknown parent-of-origin-specific expression in blastocysts (nBiX: novel blastocyst-imprinted expression). Uniparental expression of nBiX genes disappeared soon after implantation. Micro-whole-genome bisulfite sequencing (μWGBS) of individual uniparental blastocysts detected 859 DMRs. Only 18% of nBiXs were associated with a DMR, whereas 60% were associated with parentally-biased H3K27me3. This suggests a major role for Polycomb-mediated imprinting in blastocysts. Five nBiX-clusters contained at least one known imprinted gene, and five novel clusters contained exclusively nBiX-genes. These data suggest a complex program of stage-specific imprinting involving different tiers of regulation.}, author = {Santini, Laura and Halbritter, Florian and Titz-Teixeira, Fabian and Suzuki, Toru and Asami, Maki and Ramesmayer, Julia and Ma, Xiaoyan and Lackner, Andreas and Warr, Nick and Pauler, Florian and Hippenmeyer, Simon and Laue, Ernest and Farlik, Matthias and Bock, Christoph and Beyer, Andreas and Perry, Anthony C. F. and Leeb, Martin}, booktitle = {bioRxiv}, publisher = {Cold Spring Harbor Laboratory}, title = {{Novel imprints in mouse blastocysts are predominantly DNA methylation independent}}, doi = {10.1101/2020.11.03.366948}, year = {2020}, } @misc{9777, author = {Grah, Rok and Friedlander, Tamar}, publisher = {Public Library of Science}, title = {{Maximizing crosstalk}}, doi = {10.1371/journal.pcbi.1007642.s002}, year = {2020}, } @phdthesis{8332, abstract = {Designing and verifying concurrent programs is a notoriously challenging, time consuming, and error prone task, even for experts. This is due to the sheer number of possible interleavings of a concurrent program, all of which have to be tracked and accounted for in a formal proof. Inventing an inductive invariant that captures all interleavings of a low-level implementation is theoretically possible, but practically intractable. We develop a refinement-based verification framework that provides mechanisms to simplify proof construction by decomposing the verification task into smaller subtasks. In a first line of work, we present a foundation for refinement reasoning over structured concurrent programs. We introduce layered concurrent programs as a compact notation to represent multi-layer refinement proofs. A layered concurrent program specifies a sequence of connected concurrent programs, from most concrete to most abstract, such that common parts of different programs are written exactly once. Each program in this sequence is expressed as structured concurrent program, i.e., a program over (potentially recursive) procedures, imperative control flow, gated atomic actions, structured parallelism, and asynchronous concurrency. This is in contrast to existing refinement-based verifiers, which represent concurrent systems as flat transition relations. We present a powerful refinement proof rule that decomposes refinement checking over structured programs into modular verification conditions. Refinement checking is supported by a new form of modular, parameterized invariants, called yield invariants, and a linear permission system to enhance local reasoning. In a second line of work, we present two new reduction-based program transformations that target asynchronous programs. These transformations reduce the number of interleavings that need to be considered, thus reducing the complexity of invariants. Synchronization simplifies the verification of asynchronous programs by introducing the fiction, for proof purposes, that asynchronous operations complete synchronously. Synchronization summarizes an asynchronous computation as immediate atomic effect. Inductive sequentialization establishes sequential reductions that captures every behavior of the original program up to reordering of coarse-grained commutative actions. A sequential reduction of a concurrent program is easy to reason about since it corresponds to a simple execution of the program in an idealized synchronous environment, where processes act in a fixed order and at the same speed. Our approach is implemented the CIVL verifier, which has been successfully used for the verification of several complex concurrent programs. In our methodology, the overall correctness of a program is established piecemeal by focusing on the invariant required for each refinement step separately. While the programmer does the creative work of specifying the chain of programs and the inductive invariant justifying each link in the chain, the tool automatically constructs the verification conditions underlying each refinement step.}, author = {Kragl, Bernhard}, issn = {2663-337X}, pages = {120}, publisher = {Institute of Science and Technology Austria}, title = {{Verifying concurrent programs: Refinement, synchronization, sequentialization}}, doi = {10.15479/AT:ISTA:8332}, year = {2020}, } @inproceedings{14326, abstract = {Learning object-centric representations of complex scenes is a promising step towards enabling efficient abstract reasoning from low-level perceptual features. Yet, most deep learning approaches learn distributed representations that do not capture the compositional properties of natural scenes. In this paper, we present the Slot Attention module, an architectural component that interfaces with perceptual representations such as the output of a convolutional neural network and produces a set of task-dependent abstract representations which we call slots. These slots are exchangeable and can bind to any object in the input by specializing through a competitive procedure over multiple rounds of attention. We empirically demonstrate that Slot Attention can extract object-centric representations that enable generalization to unseen compositions when trained on unsupervised object discovery and supervised property prediction tasks. }, author = {Locatello, Francesco and Weissenborn, Dirk and Unterthiner, Thomas and Mahendran, Aravindh and Heigold, Georg and Uszkoreit, Jakob and Dosovitskiy, Alexey and Kipf, Thomas}, booktitle = {Advances in Neural Information Processing Systems}, isbn = {9781713829546}, location = {Virtual}, pages = {11525--11538}, publisher = {Curran Associates}, title = {{Object-centric learning with slot attention}}, volume = {33}, year = {2020}, } @article{71, abstract = {We consider dynamical transport metrics for probability measures on discretisations of a bounded convex domain in ℝd. These metrics are natural discrete counterparts to the Kantorovich metric 𝕎2, defined using a Benamou-Brenier type formula. Under mild assumptions we prove an asymptotic upper bound for the discrete transport metric Wt in terms of 𝕎2, as the size of the mesh T tends to 0. However, we show that the corresponding lower bound may fail in general, even on certain one-dimensional and symmetric two-dimensional meshes. In addition, we show that the asymptotic lower bound holds under an isotropy assumption on the mesh, which turns out to be essentially necessary. This assumption is satisfied, e.g., for tilings by convex regular polygons, and it implies Gromov-Hausdorff convergence of the transport metric.}, author = {Gladbach, Peter and Kopfer, Eva and Maas, Jan}, issn = {10957154}, journal = {SIAM Journal on Mathematical Analysis}, number = {3}, pages = {2759--2802}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Scaling limits of discrete optimal transport}}, doi = {10.1137/19M1243440}, volume = {52}, year = {2020}, } @article{5681, abstract = {We introduce dynamically warping grids for adaptive liquid simulation. Our primary contributions are a strategy for dynamically deforming regular grids over the course of a simulation and a method for efficiently utilizing these deforming grids for liquid simulation. Prior work has shown that unstructured grids are very effective for adaptive fluid simulations. However, unstructured grids often lead to complicated implementations and a poor cache hit rate due to inconsistent memory access. Regular grids, on the other hand, provide a fast, fixed memory access pattern and straightforward implementation. Our method combines the advantages of both: we leverage the simplicity of regular grids while still achieving practical and controllable spatial adaptivity. We demonstrate that our method enables adaptive simulations that are fast, flexible, and robust to null-space issues. At the same time, our method is simple to implement and takes advantage of existing highly-tuned algorithms.}, author = {Hikaru, Ibayashi and Wojtan, Christopher J and Thuerey, Nils and Igarashi, Takeo and Ando, Ryoichi}, issn = {19410506}, journal = {IEEE Transactions on Visualization and Computer Graphics}, number = {6}, pages = {2288--2302}, publisher = {IEEE}, title = {{Simulating liquids on dynamically warping grids}}, doi = {10.1109/TVCG.2018.2883628}, volume = {26}, year = {2020}, } @phdthesis{8958, abstract = {The oft-quoted dictum by Arthur Schawlow: ``A diatomic molecule has one atom too many'' has been disavowed. Inspired by the possibility to experimentally manipulate and enhance chemical reactivity in helium nanodroplets, we investigate the rotation of coupled cold molecules in the presence of a many-body environment. In this thesis, we introduce new variational approaches to quantum impurities and apply them to the Fröhlich polaron - a quasiparticle formed out of an electron (or other point-like impurity) in a polar medium, and to the angulon - a quasiparticle formed out of a rotating molecule in a bosonic bath. With this theoretical toolbox, we reveal the self-localization transition for the angulon quasiparticle. We show that, unlike for polarons, self-localization of angulons occurs at finite impurity-bath coupling already at the mean-field level. The transition is accompanied by the spherical-symmetry breaking of the angulon ground state and a discontinuity in the first derivative of the ground-state energy. Moreover, the type of symmetry breaking is dictated by the symmetry of the microscopic impurity-bath interaction, which leads to a number of distinct self-localized states. For the system containing multiple impurities, by analogy with the bipolaron, we introduce the biangulon quasiparticle describing two rotating molecules that align with respect to each other due to the effective attractive interaction mediated by the excitations of the bath. We study this system from the strong-coupling regime to the weak molecule-bath interaction regime. We show that the molecules tend to have a strong alignment in the ground state, the biangulon shows shifted angulon instabilities and an additional spectral instability, where resonant angular momentum transfer between the molecules and the bath takes place. Finally, we introduce a diagonalization scheme that allows us to describe the transition from two separated angulons to a biangulon as a function of the distance between the two molecules.}, author = {Li, Xiang}, issn = {2663-337X}, pages = {125}, publisher = {Institute of Science and Technology Austria}, title = {{Rotation of coupled cold molecules in the presence of a many-body environment}}, doi = {10.15479/AT:ISTA:8958}, year = {2020}, } @phdthesis{8386, abstract = {Form versus function is a long-standing debate in various design-related fields, such as architecture as well as graphic and industrial design. A good design that balances form and function often requires considerable human effort and collaboration among experts from different professional fields. Computational design tools provide a new paradigm for designing functional objects. In computational design, form and function are represented as mathematical quantities, with the help of numerical and combinatorial algorithms, they can assist even novice users in designing versatile models that exhibit their desired functionality. This thesis presents three disparate research studies on the computational design of functional objects: The appearance of 3d print—we optimize the volumetric material distribution for faithfully replicating colored surface texture in 3d printing; the dynamic motion of mechanical structures— our design system helps the novice user to retarget various mechanical templates with different functionality to complex 3d shapes; and a more abstract functionality, multistability—our algorithm automatically generates models that exhibit multiple stable target poses. For each of these cases, our computational design tools not only ensure the functionality of the results but also permit the user aesthetic freedom over the form. Moreover, fabrication constraints were taken into account, which allow for the immediate creation of physical realization via 3D printing or laser cutting.}, author = {Zhang, Ran}, issn = {2663-337X}, pages = {148}, publisher = {Institute of Science and Technology Austria}, title = {{Structure-aware computational design and its application to 3D printable volume scattering, mechanism, and multistability}}, doi = {10.15479/AT:ISTA:8386}, year = {2020}, } @phdthesis{7996, abstract = {Quantum computation enables the execution of algorithms that have exponential complexity. This might open the path towards the synthesis of new materials or medical drugs, optimization of transport or financial strategies etc., intractable on even the fastest classical computers. A quantum computer consists of interconnected two level quantum systems, called qubits, that satisfy DiVincezo’s criteria. Worldwide, there are ongoing efforts to find the qubit architecture which will unite quantum error correction compatible single and two qubit fidelities, long distance qubit to qubit coupling and calability. Superconducting qubits have gone the furthest in this race, demonstrating an algorithm running on 53 coupled qubits, but still the fidelities are not even close to those required for realizing a single logical qubit. emiconductor qubits offer extremely good characteristics, but they are currently investigated across different platforms. Uniting those good characteristics into a single platform might be a big step towards the quantum computer realization. Here we describe the implementation of a hole spin qubit hosted in a Ge hut wire double quantum dot. The high and tunable spin-orbit coupling together with a heavy hole state character is expected to allow fast spin manipulation and long coherence times. Furthermore large lever arms, for hut wire devices, should allow good coupling to superconducting resonators enabling efficient long distance spin to spin coupling and a sensitive gate reflectometry spin readout. The developed cryogenic setup (printed circuit board sample holders, filtering, high-frequency wiring) enabled us to perform low temperature spin dynamics experiments. Indeed, we measured the fastest single spin qubit Rabi frequencies reported so far, reaching 140 MHz, while the dephasing times of 130 ns oppose the long decoherence predictions. In order to further investigate this, a double quantum dot gate was connected directly to a lumped element resonator which enabled gate reflectometry readout. The vanishing inter-dot transition signal, for increasing external magnetic field, revealed the spin nature of the measured quantity.}, author = {Kukucka, Josip}, issn = {2663-337X}, pages = {178}, publisher = {Institute of Science and Technology Austria}, title = {{Implementation of a hole spin qubit in Ge hut wires and dispersive spin sensing}}, doi = {10.15479/AT:ISTA:7996}, year = {2020}, } @inproceedings{8272, abstract = {We study turn-based stochastic zero-sum games with lexicographic preferences over reachability and safety objectives. Stochastic games are standard models in control, verification, and synthesis of stochastic reactive systems that exhibit both randomness as well as angelic and demonic non-determinism. Lexicographic order allows to consider multiple objectives with a strict preference order over the satisfaction of the objectives. To the best of our knowledge, stochastic games with lexicographic objectives have not been studied before. We establish determinacy of such games and present strategy and computational complexity results. For strategy complexity, we show that lexicographically optimal strategies exist that are deterministic and memory is only required to remember the already satisfied and violated objectives. For a constant number of objectives, we show that the relevant decision problem is in NP∩coNP , matching the current known bound for single objectives; and in general the decision problem is PSPACE -hard and can be solved in NEXPTIME∩coNEXPTIME . We present an algorithm that computes the lexicographically optimal strategies via a reduction to computation of optimal strategies in a sequence of single-objectives games. We have implemented our algorithm and report experimental results on various case studies.}, author = {Chatterjee, Krishnendu and Katoen, Joost P and Weininger, Maximilian and Winkler, Tobias}, booktitle = {International Conference on Computer Aided Verification}, isbn = {9783030532901}, issn = {16113349}, pages = {398--420}, publisher = {Springer Nature}, title = {{Stochastic games with lexicographic reachability-safety objectives}}, doi = {10.1007/978-3-030-53291-8_21}, volume = {12225}, year = {2020}, } @inbook{7572, abstract = {The polymerization–depolymerization dynamics of cytoskeletal proteins play essential roles in the self-organization of cytoskeletal structures, in eukaryotic as well as prokaryotic cells. While advances in fluorescence microscopy and in vitro reconstitution experiments have helped to study the dynamic properties of these complex systems, methods that allow to collect and analyze large quantitative datasets of the underlying polymer dynamics are still missing. Here, we present a novel image analysis workflow to study polymerization dynamics of active filaments in a nonbiased, highly automated manner. Using treadmilling filaments of the bacterial tubulin FtsZ as an example, we demonstrate that our method is able to specifically detect, track and analyze growth and shrinkage of polymers, even in dense networks of filaments. We believe that this automated method can facilitate the analysis of a large variety of dynamic cytoskeletal systems, using standard time-lapse movies obtained from experiments in vitro as well as in the living cell. Moreover, we provide scripts implementing this method as supplementary material.}, author = {Dos Santos Caldas, Paulo R and Radler, Philipp and Sommer, Christoph M and Loose, Martin}, booktitle = {Methods in Cell Biology}, editor = {Tran, Phong }, issn = {0091679X}, pages = {145--161}, publisher = {Elsevier}, title = {{Computational analysis of filament polymerization dynamics in cytoskeletal networks}}, doi = {10.1016/bs.mcb.2020.01.006}, volume = {158}, year = {2020}, } @article{7387, abstract = {Most bacteria accomplish cell division with the help of a dynamic protein complex called the divisome, which spans the cell envelope in the plane of division. Assembly and activation of this machinery are coordinated by the tubulin-related GTPase FtsZ, which was found to form treadmilling filaments on supported bilayers in vitro1, as well as in live cells, in which filaments circle around the cell division site2,3. Treadmilling of FtsZ is thought to actively move proteins around the division septum, thereby distributing peptidoglycan synthesis and coordinating the inward growth of the septum to form the new poles of the daughter cells4. However, the molecular mechanisms underlying this function are largely unknown. Here, to study how FtsZ polymerization dynamics are coupled to downstream proteins, we reconstituted part of the bacterial cell division machinery using its purified components FtsZ, FtsA and truncated transmembrane proteins essential for cell division. We found that the membrane-bound cytosolic peptides of FtsN and FtsQ co-migrated with treadmilling FtsZ–FtsA filaments, but despite their directed collective behaviour, individual peptides showed random motion and transient confinement. Our work suggests that divisome proteins follow treadmilling FtsZ filaments by a diffusion-and-capture mechanism, which can give rise to a moving zone of signalling activity at the division site.}, author = {Baranova, Natalia S. and Radler, Philipp and Hernández-Rocamora, Víctor M. and Alfonso, Carlos and Lopez Pelegrin, Maria D and Rivas, Germán and Vollmer, Waldemar and Loose, Martin}, issn = {2058-5276}, journal = {Nature Microbiology}, pages = {407--417}, publisher = {Springer Nature}, title = {{Diffusion and capture permits dynamic coupling between treadmilling FtsZ filaments and cell division proteins}}, doi = {10.1038/s41564-019-0657-5}, volume = {5}, year = {2020}, } @article{8163, abstract = {Fejes Tóth [3] studied approximations of smooth surfaces in three-space by piecewise flat triangular meshes with a given number of vertices on the surface that are optimal with respect to Hausdorff distance. He proves that this Hausdorff distance decreases inversely proportional with the number of vertices of the approximating mesh if the surface is convex. He also claims that this Hausdorff distance is inversely proportional to the square of the number of vertices for a specific non-convex surface, namely a one-sheeted hyperboloid of revolution bounded by two congruent circles. We refute this claim, and show that the asymptotic behavior of the Hausdorff distance is linear, that is the same as for convex surfaces.}, author = {Vegter, Gert and Wintraecken, Mathijs}, issn = {1588-2896}, journal = {Studia Scientiarum Mathematicarum Hungarica}, number = {2}, pages = {193--199}, publisher = {Akadémiai Kiadó}, title = {{Refutation of a claim made by Fejes Tóth on the accuracy of surface meshes}}, doi = {10.1556/012.2020.57.2.1454}, volume = {57}, year = {2020}, } @article{8671, abstract = {We study relations between evidence theory and S-approximation spaces. Both theories have their roots in the analysis of Dempsterchr('39')s multivalued mappings and lower and upper probabilities, and have close relations to rough sets. We show that an S-approximation space, satisfying a monotonicity condition, can induce a natural belief structure which is a fundamental block in evidence theory. We also demonstrate that one can induce a natural belief structure on one set, given a belief structure on another set, if the two sets are related by a partial monotone S-approximation space. }, author = {Shakiba, A. and Goharshady, Amir Kafshdar and Hooshmandasl, M.R. and Alambardar Meybodi, M.}, issn = {2008-9473}, journal = {Iranian Journal of Mathematical Sciences and Informatics}, number = {2}, pages = {117--128}, publisher = {Iranian Academic Center for Education, Culture and Research}, title = {{A note on belief structures and s-approximation spaces}}, doi = {10.29252/ijmsi.15.2.117}, volume = {15}, year = {2020}, } @article{6359, abstract = {The strong rate of convergence of the Euler-Maruyama scheme for nondegenerate SDEs with irregular drift coefficients is considered. In the case of α-Hölder drift in the recent literature the rate α/2 was proved in many related situations. By exploiting the regularising effect of the noise more efficiently, we show that the rate is in fact arbitrarily close to 1/2 for all α>0. The result extends to Dini continuous coefficients, while in d=1 also to all bounded measurable coefficients.}, author = {Dareiotis, Konstantinos and Gerencser, Mate}, issn = {1083-6489}, journal = {Electronic Journal of Probability}, publisher = {Institute of Mathematical Statistics}, title = {{On the regularisation of the noise for the Euler-Maruyama scheme with irregular drift}}, doi = {10.1214/20-EJP479}, volume = {25}, year = {2020}, } @phdthesis{8390, abstract = {Deep neural networks have established a new standard for data-dependent feature extraction pipelines in the Computer Vision literature. Despite their remarkable performance in the standard supervised learning scenario, i.e. when models are trained with labeled data and tested on samples that follow a similar distribution, neural networks have been shown to struggle with more advanced generalization abilities, such as transferring knowledge across visually different domains, or generalizing to new unseen combinations of known concepts. In this thesis we argue that, in contrast to the usual black-box behavior of neural networks, leveraging more structured internal representations is a promising direction for tackling such problems. In particular, we focus on two forms of structure. First, we tackle modularity: We show that (i) compositional architectures are a natural tool for modeling reasoning tasks, in that they efficiently capture their combinatorial nature, which is key for generalizing beyond the compositions seen during training. We investigate how to to learn such models, both formally and experimentally, for the task of abstract visual reasoning. Then, we show that (ii) in some settings, modularity allows us to efficiently break down complex tasks into smaller, easier, modules, thereby improving computational efficiency; We study this behavior in the context of generative models for colorization, as well as for small objects detection. Secondly, we investigate the inherently layered structure of representations learned by neural networks, and analyze its role in the context of transfer learning and domain adaptation across visually dissimilar domains. }, author = {Royer, Amélie}, isbn = {978-3-99078-007-7}, issn = {2663-337X}, pages = {197}, publisher = {Institute of Science and Technology Austria}, title = {{Leveraging structure in Computer Vision tasks for flexible Deep Learning models}}, doi = {10.15479/AT:ISTA:8390}, year = {2020}, } @inproceedings{8186, abstract = {Numerous methods have been proposed for probabilistic generative modelling of 3D objects. However, none of these is able to produce textured objects, which renders them of limited use for practical tasks. In this work, we present the first generative model of textured 3D meshes. Training such a model would traditionally require a large dataset of textured meshes, but unfortunately, existing datasets of meshes lack detailed textures. We instead propose a new training methodology that allows learning from collections of 2D images without any 3D information. To do so, we train our model to explain a distribution of images by modelling each image as a 3D foreground object placed in front of a 2D background. Thus, it learns to generate meshes that when rendered, produce images similar to those in its training set. A well-known problem when generating meshes with deep networks is the emergence of self-intersections, which are problematic for many use-cases. As a second contribution we therefore introduce a new generation process for 3D meshes that guarantees no self-intersections arise, based on the physical intuition that faces should push one another out of the way as they move. We conduct extensive experiments on our approach, reporting quantitative and qualitative results on both synthetic data and natural images. These show our method successfully learns to generate plausible and diverse textured 3D samples for five challenging object classes.}, author = {Henderson, Paul M and Tsiminaki, Vagia and Lampert, Christoph}, booktitle = {Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition}, issn = {2575-7075}, location = {Virtual}, pages = {7498--7507}, publisher = {IEEE}, title = {{Leveraging 2D data to learn textured 3D mesh generation}}, doi = {10.1109/CVPR42600.2020.00752}, year = {2020}, } @article{7416, abstract = {Earlier, we demonstrated that transcript levels of METAL TOLERANCE PROTEIN2 (MTP2) and of HEAVY METAL ATPase2 (HMA2) increase strongly in roots of Arabidopsis upon prolonged zinc (Zn) deficiency and respond to shoot physiological Zn status, and not to the local Zn status in roots. This provided evidence for shoot-to-root communication in the acclimation of plants to Zn deficiency. Zn-deficient soils limit both the yield and quality of agricultural crops and can result in clinically relevant nutritional Zn deficiency in human populations. Implementing Zn deficiency during cultivation of the model plant Arabidopsis thaliana on agar-solidified media is difficult because trace element contaminations are present in almost all commercially available agars. Here, we demonstrate root morphological acclimations to Zn deficiency on agar-solidified medium following the effective removal of contaminants. These advancements allow reproducible phenotyping toward understanding fundamental plant responses to deficiencies of Zn and other essential trace elements.}, author = {Sinclair, Scott A and Krämer, U.}, issn = {1559-2324}, journal = {Plant Signaling & Behavior}, number = {1}, publisher = {Taylor & Francis}, title = {{Generation of effective zinc-deficient agar-solidified media allows identification of root morphology changes in response to zinc limitation}}, doi = {10.1080/15592324.2019.1687175}, volume = {15}, year = {2020}, } @article{7464, abstract = {Retrovirus assembly is driven by the multidomain structural protein Gag. Interactions between the capsid domains (CA) of Gag result in Gag multimerization, leading to an immature virus particle that is formed by a protein lattice based on dimeric, trimeric, and hexameric protein contacts. Among retroviruses the inter- and intra-hexamer contacts differ, especially in the N-terminal sub-domain of CA (CANTD). For HIV-1 the cellular molecule inositol hexakisphosphate (IP6) interacts with and stabilizes the immature hexamer, and is required for production of infectious virus particles. We have used in vitro assembly, cryo-electron tomography and subtomogram averaging, atomistic molecular dynamics simulations and mutational analyses to study the HIV-related lentivirus equine infectious anemia virus (EIAV). In particular, we sought to understand the structural conservation of the immature lentivirus lattice and the role of IP6 in EIAV assembly. Similar to HIV-1, IP6 strongly promoted in vitro assembly of EIAV Gag proteins into virus-like particles (VLPs), which took three morphologically highly distinct forms: narrow tubes, wide tubes, and spheres. Structural characterization of these VLPs to sub-4Å resolution unexpectedly showed that all three morphologies are based on an immature lattice with preserved key structural components, highlighting the structural versatility of CA to form immature assemblies. A direct comparison between EIAV and HIV revealed that both lentiviruses maintain similar immature interfaces, which are established by both conserved and non-conserved residues. In both EIAV and HIV-1, IP6 regulates immature assembly via conserved lysine residues within the CACTD and SP. Lastly, we demonstrate that IP6 stimulates in vitro assembly of immature particles of several other retroviruses in the lentivirus genus, suggesting a conserved role for IP6 in lentiviral assembly.}, author = {Dick, Robert A. and Xu, Chaoyi and Morado, Dustin R. and Kravchuk, Vladyslav and Ricana, Clifton L. and Lyddon, Terri D. and Broad, Arianna M. and Feathers, J. Ryan and Johnson, Marc C. and Vogt, Volker M. and Perilla, Juan R. and Briggs, John A. G. and Schur, Florian KM}, issn = {1553-7374}, journal = {PLOS Pathogens}, number = {1}, publisher = {Public Library of Science}, title = {{Structures of immature EIAV Gag lattices reveal a conserved role for IP6 in lentivirus assembly}}, doi = {10.1371/journal.ppat.1008277}, volume = {16}, year = {2020}, }