TY - CONF
AB - The main result of this paper is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even Δ-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec. Knowing that edge CSP is tractable for even Δ-matroid constraints allows us to extend the tractability result to a larger class of Δ-matroids that includes many classes that were known to be tractable before, namely co-independent, compact, local and binary.
AU - Kazda, Alexandr
AU - Kolmogorov, Vladimir
AU - Rolinek, Michal
ID - 1192
SN - 978-161197478-2
TI - Even delta-matroids and the complexity of planar Boolean CSPs
ER -
TY - CONF
AB - Termination is one of the basic liveness properties, and we study the termination problem for probabilistic programs with real-valued variables. Previous works focused on the qualitative problem that asks whether an input program terminates with probability~1 (almost-sure termination). A powerful approach for this qualitative problem is the notion of ranking supermartingales with respect to a given set of invariants. The quantitative problem (probabilistic termination) asks for bounds on the termination probability. A fundamental and conceptual drawback of the existing approaches to address probabilistic termination is that even though the supermartingales consider the probabilistic behavior of the programs, the invariants are obtained completely ignoring the probabilistic aspect. In this work we address the probabilistic termination problem for linear-arithmetic probabilistic programs with nondeterminism. We define the notion of {\em stochastic invariants}, which are constraints along with a probability bound that the constraints hold. We introduce a concept of {\em repulsing supermartingales}. First, we show that repulsing supermartingales can be used to obtain bounds on the probability of the stochastic invariants. Second, we show the effectiveness of repulsing supermartingales in the following three ways: (1)~With a combination of ranking and repulsing supermartingales we can compute lower bounds on the probability of termination; (2)~repulsing supermartingales provide witnesses for refutation of almost-sure termination; and (3)~with a combination of ranking and repulsing supermartingales we can establish persistence properties of probabilistic programs. We also present results on related computational problems and an experimental evaluation of our approach on academic examples.
AU - Chatterjee, Krishnendu
AU - Novotny, Petr
AU - Zikelic, Djordje
ID - 1194
IS - 1
SN - 07308566
TI - Stochastic invariants for probabilistic termination
VL - 52
ER -
TY - JOUR
AB - We define the . model-measuring problem: given a model . M and specification . ϕ, what is the maximal distance . ρ such that all models . M' within distance . ρ from . M satisfy (or violate) . ϕ. The model-measuring problem presupposes a distance function on models. We concentrate on . automatic distance functions, which are defined by weighted automata. The model-measuring problem subsumes several generalizations of the classical model-checking problem, in particular, quantitative model-checking problems that measure the degree of satisfaction of a specification; robustness problems that measure how much a model can be perturbed without violating the specification; and parameter synthesis for hybrid systems. We show that for automatic distance functions, and (a) . ω-regular linear-time, (b) . ω-regular branching-time, and (c) hybrid specifications, the model-measuring problem can be solved.We use automata-theoretic model-checking methods for model measuring, replacing the emptiness question for word, tree, and hybrid automata by the . optimal-value question for the weighted versions of these automata. For automata over words and trees, we consider weighted automata that accumulate weights by maximizing, summing, discounting, and limit averaging. For hybrid automata, we consider monotonic (parametric) hybrid automata, a hybrid counterpart of (discrete) weighted automata.We give several examples of using the model-measuring problem to compute various notions of robustness and quantitative satisfaction for temporal specifications. Further, we propose the modeling framework for model measuring to ease the specification and reduce the likelihood of errors in modeling.Finally, we present a variant of the model-measuring problem, called the . model-repair problem. The model-repair problem applies to models that do not satisfy the specification; it can be used to derive restrictions, under which the model satisfies the specification, i.e., to repair the model.
AU - Henzinger, Thomas A
AU - Otop, Jan
ID - 1196
JF - Nonlinear Analysis: Hybrid Systems
TI - Model measuring for discrete and hybrid systems
VL - 23
ER -
TY - JOUR
AB - We consider a model of fermions interacting via point interactions, defined via a certain weighted Dirichlet form. While for two particles the interaction corresponds to infinite scattering length, the presence of further particles effectively decreases the interaction strength. We show that the model becomes trivial in the thermodynamic limit, in the sense that the free energy density at any given particle density and temperature agrees with the corresponding expression for non-interacting particles.
AU - Moser, Thomas
AU - Seiringer, Robert
ID - 1198
IS - 3
JF - Letters in Mathematical Physics
SN - 03779017
TI - Triviality of a model of particles with point interactions in the thermodynamic limit
VL - 107
ER -
TY - JOUR
AB - Much of quantitative genetics is based on the ‘infinitesimal model’, under which selection has a negligible effect on the genetic variance. This is typically justified by assuming a very large number of loci with additive effects. However, it applies even when genes interact, provided that the number of loci is large enough that selection on each of them is weak relative to random drift. In the long term, directional selection will change allele frequencies, but even then, the effects of epistasis on the ultimate change in trait mean due to selection may be modest. Stabilising selection can maintain many traits close to their optima, even when the underlying alleles are weakly selected. However, the number of traits that can be optimised is apparently limited to ~4Ne by the ‘drift load’, and this is hard to reconcile with the apparent complexity of many organisms. Just as for the mutation load, this limit can be evaded by a particular form of negative epistasis. A more robust limit is set by the variance in reproductive success. This suggests that selection accumulates information most efficiently in the infinitesimal regime, when selection on individual alleles is weak, and comparable with random drift. A review of evidence on selection strength suggests that although most variance in fitness may be because of alleles with large Nes, substantial amounts of adaptation may be because of alleles in the infinitesimal regime, in which epistasis has modest effects.
AU - Barton, Nicholas H
ID - 1199
JF - Heredity
TI - How does epistasis influence the response to selection?
VL - 118
ER -
TY - JOUR
AB - The eigenvalue distribution of the sum of two large Hermitian matrices, when one of them is conjugated by a Haar distributed unitary matrix, is asymptotically given by the free convolution of their spectral distributions. We prove that this convergence also holds locally in the bulk of the spectrum, down to the optimal scales larger than the eigenvalue spacing. The corresponding eigenvectors are fully delocalized. Similar results hold for the sum of two real symmetric matrices, when one is conjugated by Haar orthogonal matrix.
AU - Bao, Zhigang
AU - Erdös, László
AU - Schnelli, Kevin
ID - 1207
IS - 3
JF - Communications in Mathematical Physics
SN - 00103616
TI - Local law of addition of random matrices on optimal scale
VL - 349
ER -
TY - JOUR
AB - We study parameter estimation in linear Gaussian covariance models, which are p-dimensional Gaussian models with linear constraints on the covariance matrix. Maximum likelihood estimation for this class of models leads to a non-convex optimization problem which typically has many local maxima. Using recent results on the asymptotic distribution of extreme eigenvalues of the Wishart distribution, we provide sufficient conditions for any hill climbing method to converge to the global maximum. Although we are primarily interested in the case in which n≫p, the proofs of our results utilize large sample asymptotic theory under the scheme n/p→γ>1. Remarkably, our numerical simulations indicate that our results remain valid for p as small as 2. An important consequence of this analysis is that, for sample sizes n≃14p, maximum likelihood estimation for linear Gaussian covariance models behaves as if it were a convex optimization problem. © 2016 The Royal Statistical Society and Blackwell Publishing Ltd.
AU - Zwiernik, Piotr
AU - Uhler, Caroline
AU - Richards, Donald
ID - 1208
IS - 4
JF - Journal of the Royal Statistical Society. Series B: Statistical Methodology
SN - 13697412
TI - Maximum likelihood estimation for linear Gaussian covariance models
VL - 79
ER -
TY - JOUR
AB - Systems such as fluid flows in channels and pipes or the complex Ginzburg–Landau system, defined over periodic domains, exhibit both continuous symmetries, translational and rotational, as well as discrete symmetries under spatial reflections or complex conjugation. The simplest, and very common symmetry of this type is the equivariance of the defining equations under the orthogonal group O(2). We formulate a novel symmetry reduction scheme for such systems by combining the method of slices with invariant polynomial methods, and show how it works by applying it to the Kuramoto–Sivashinsky system in one spatial dimension. As an example, we track a relative periodic orbit through a sequence of bifurcations to the onset of chaos. Within the symmetry-reduced state space we are able to compute and visualize the unstable manifolds of relative periodic orbits, their torus bifurcations, a transition to chaos via torus breakdown, and heteroclinic connections between various relative periodic orbits. It would be very hard to carry through such analysis in the full state space, without a symmetry reduction such as the one we present here.
AU - Budanur, Nazmi B
AU - Cvitanović, Predrag
ID - 1211
IS - 3-4
JF - Journal of Statistical Physics
TI - Unstable manifolds of relative periodic orbits in the symmetry reduced state space of the Kuramoto–Sivashinsky system
VL - 167
ER -
TY - JOUR
AB - Bacterial cytokinesis is commonly initiated by the Z-ring, a dynamic cytoskeletal structure that assembles at the site of division. Its primary component is FtsZ, a tubulin-like GTPase, that like its eukaryotic relative forms protein filaments in the presence of GTP. Since the discovery of the Z-ring 25 years ago, various models for the role of FtsZ have been suggested. However, important information about the architecture and dynamics of FtsZ filaments during cytokinesis is still missing. One reason for this lack of knowledge has been the small size of bacteria, which has made it difficult to resolve the orientation and dynamics of individual FtsZ filaments in the Z-ring. While superresolution microscopy experiments have helped to gain more information about the organization of the Z-ring in the dividing cell, they were not yet able to elucidate a mechanism of how FtsZ filaments reorganize during assembly and disassembly of the Z-ring. In this chapter, we explain how to use an in vitro reconstitution approach to investigate the self-organization of FtsZ filaments recruited to a biomimetic lipid bilayer by its membrane anchor FtsA. We show how to perform single-molecule experiments to study the behavior of individual FtsZ monomers during the constant reorganization of the FtsZ-FtsA filament network. We describe how to analyze the dynamics of single molecules and explain why this information can help to shed light onto possible mechanism of Z-ring constriction. We believe that similar experimental approaches will be useful to study the mechanism of membrane-based polymerization of other cytoskeletal systems, not only from prokaryotic but also eukaryotic origin.
AU - Baranova, Natalia
AU - Loose, Martin
ID - 1213
JF - Methods in Cell Biology
SN - 0091679X
TI - Single-molecule measurements to study polymerization dynamics of FtsZ-FtsA copolymers
VL - 137
ER -
TY - JOUR
AB - Since 2006, reprogrammed cells have increasingly been used as a biomedical research technique in addition to neuro-psychiatric methods. These rapidly evolving techniques allow for the generation of neuronal sub-populations, and have sparked interest not only in monogenetic neuro-psychiatric diseases, but also in poly-genetic and poly-aetiological disorders such as schizophrenia (SCZ) and bipolar disorder (BPD). This review provides a summary of 19 publications on reprogrammed adult somatic cells derived from patients with SCZ, and five publications using this technique in patients with BPD. As both disorders are complex and heterogeneous, there is a plurality of hypotheses to be tested in vitro. In SCZ, data on alterations of dopaminergic transmission in vitro are sparse, despite the great explanatory power of the so-called DA hypothesis of SCZ. Some findings correspond to perturbations of cell energy metabolism, and observations in reprogrammed cells suggest neuro-developmental alterations. Some studies also report on the efficacy of medicinal compounds to revert alterations observed in cellular models. However, due to the paucity of replication studies, no comprehensive conclusions can be drawn from studies using reprogrammed cells at the present time. In the future, findings from cell culture methods need to be integrated with clinical, epidemiological, pharmacological and imaging data in order to generate a more comprehensive picture of SCZ and BPD.
AU - Sauerzopf, Ulrich
AU - Sacco, Roberto
AU - Novarino, Gaia
AU - Niello, Marco
AU - Weidenauer, Ana
AU - Praschak Rieder, Nicole
AU - Sitte, Harald
AU - Willeit, Matthaeus
ID - 1228
IS - 1
JF - European Journal of Neuroscience
TI - Are reprogrammed cells a useful tool for studying dopamine dysfunction in psychotic disorders? A review of the current evidence
VL - 45
ER -
TY - JOUR
AB - We study the lengths of curves passing through a fixed number of points on the boundary of a convex shape in the plane. We show that, for any convex shape K, there exist four points on the boundary of K such that the length of any curve passing through these points is at least half of the perimeter of K. It is also shown that the same statement does not remain valid with the additional constraint that the points are extreme points of K. Moreover, the factor ½ cannot be achieved with any fixed number of extreme points. We conclude the paper with a few other inequalities related to the perimeter of a convex shape.
AU - Akopyan, Arseniy
AU - Vysotsky, Vladislav
ID - 909
IS - 7
JF - The American Mathematical Monthly
SN - 00029890
TI - On the lengths of curves passing through boundary points of a planar convex shape
VL - 124
ER -
TY - JOUR
AB - Frequency-independent selection is generally considered as a force that acts to reduce the genetic variation in evolving populations, yet rigorous arguments for this idea are scarce. When selection fluctuates in time, it is unclear whether frequency-independent selection may maintain genetic polymorphism without invoking additional mechanisms. We show that constant frequency-independent selection with arbitrary epistasis on a well-mixed haploid population eliminates genetic variation if we assume linkage equilibrium between alleles. To this end, we introduce the notion of frequency-independent selection at the level of alleles, which is sufficient to prove our claim and contains the notion of frequency-independent selection on haploids. When selection and recombination are weak but of the same order, there may be strong linkage disequilibrium; numerical calculations show that stable equilibria are highly unlikely. Using the example of a diallelic two-locus model, we then demonstrate that frequency-independent selection that fluctuates in time can maintain stable polymorphism if linkage disequilibrium changes its sign periodically. We put our findings in the context of results from the existing literature and point out those scenarios in which the possible role of frequency-independent selection in maintaining genetic variation remains unclear.
AU - Novak, Sebastian
AU - Barton, Nicholas H
ID - 910
IS - 2
JF - Genetics
TI - When does frequency-independent selection maintain genetic variation?
VL - 207
ER -
TY - CONF
AB - We develop a probabilistic technique for colorizing grayscale natural images. In light of the intrinsic uncertainty of this task, the proposed probabilistic framework has numerous desirable properties. In particular, our model is able to produce multiple plausible and vivid colorizations for a given grayscale image and is one of the first colorization models to provide a proper stochastic sampling scheme. Moreover, our training procedure is supported by a rigorous theoretical framework that does not require any ad hoc heuristics and allows for efficient modeling and learning of the joint pixel color distribution.We demonstrate strong quantitative and qualitative experimental results on the CIFAR-10 dataset and the challenging ILSVRC 2012 dataset.
AU - Royer, Amélie
AU - Kolesnikov, Alexander
AU - Lampert, Christoph
ID - 911
TI - Probabilistic image colorization
ER -
TY - JOUR
AB - We consider a many-body system of fermionic atoms interacting via a local pair potential and subject to an external potential within the framework of Bardeen-Cooper-Schrieffer (BCS) theory. We measure the free energy of the whole sample with respect to the free energy of a reference state which allows us to define a BCS functional with boundary conditions at infinity. Our main result is a lower bound for this energy functional in terms of expressions that typically appear in Ginzburg-Landau functionals.
AU - Deuchert, Andreas
ID - 912
IS - 8
JF - Journal of Mathematical Physics
SN - 00222488
TI - A lower bound for the BCS functional with boundary conditions at infinity
VL - 58
ER -
TY - JOUR
AB - Infections with potentially lethal pathogens may negatively affect an individual’s lifespan and decrease its reproductive value. The terminal investment hypothesis predicts that individuals faced with a reduced survival should invest more into reproduction instead of maintenance and growth. Several studies suggest that individuals are indeed able to estimate their body condition and to increase their reproductive effort with approaching death, while other studies gave ambiguous results. We investigate whether queens of a perennial social insect (ant) are able to boost their reproduction following infection with an obligate killing pathogen. Social insect queens are special with regard to reproduction and aging, as they outlive conspecific non-reproductive workers. Moreover, in the ant Cardiocondyla obscurior, fecundity increases with queen age. However, it remained unclear whether this reflects negative reproductive senescence or terminal investment in response to approaching death. Here, we test whether queens of C. obscurior react to infection with the entomopathogenic fungus Metarhizium brunneum by an increased egg-laying rate. We show that a fungal infection triggers a reinforced investment in reproduction in queens. This adjustment of the reproductive rate by ant queens is consistent with predictions of the terminal investment hypothesis and is reported for the first time in a social insect.
AU - Giehr, Julia
AU - Grasse, Anna V
AU - Cremer, Sylvia
AU - Heinze, Jürgen
AU - Schrempf, Alexandra
ID - 914
IS - 7
JF - Royal Society Open Science
SN - 20545703
TI - Ant queens increase their reproductive efforts after pathogen infection
VL - 4
ER -
TY - CONF
AB - We propose a dual decomposition and linear program relaxation of the NP-hard minimum cost multicut problem. Unlike other polyhedral relaxations of the multicut polytope, it is amenable to efficient optimization by message passing. Like other polyhedral relaxations, it can be tightened efficiently by cutting planes. We define an algorithm that alternates between message passing and efficient separation of cycle- and odd-wheel inequalities. This algorithm is more efficient than state-of-the-art algorithms based on linear programming, including algorithms written in the framework of leading commercial software, as we show in experiments with large instances of the problem from applications in computer vision, biomedical image analysis and data mining.
AU - Swoboda, Paul
AU - Andres, Bjoern
ID - 915
SN - 978-153860457-1
TI - A message passing algorithm for the minimum cost multicut problem
VL - 2017
ER -
TY - CONF
AB - We study the quadratic assignment problem, in computer vision also known as graph matching. Two leading solvers for this problem optimize the Lagrange decomposition duals with sub-gradient and dual ascent (also known as message passing) updates. We explore this direction further and propose several additional Lagrangean relaxations of the graph matching problem along with corresponding algorithms, which are all based on a common dual ascent framework. Our extensive empirical evaluation gives several theoretical insights and suggests a new state-of-the-art anytime solver for the considered problem. Our improvement over state-of-the-art is particularly visible on a new dataset with large-scale sparse problem instances containing more than 500 graph nodes each.
AU - Swoboda, Paul
AU - Rother, Carsten
AU - Abu Alhaija, Carsten
AU - Kainmueller, Dagmar
AU - Savchynskyy, Bogdan
ID - 916
SN - 978-153860457-1
TI - A study of lagrangean decompositions and dual ascent solvers for graph matching
VL - 2017
ER -
TY - CONF
AB - We propose a general dual ascent framework for Lagrangean decomposition of combinatorial problems. Although methods of this type have shown their efficiency for a number of problems, so far there was no general algorithm applicable to multiple problem types. In this work, we propose such a general algorithm. It depends on several parameters, which can be used to optimize its performance in each particular setting. We demonstrate efficacy of our method on graph matching and multicut problems, where it outperforms state-of-the-art solvers including those based on subgradient optimization and off-the-shelf linear programming solvers.
AU - Swoboda, Paul
AU - Kuske, Jan
AU - Savchynskyy, Bogdan
ID - 917
SN - 978-153860457-1
TI - A dual ascent framework for Lagrangean decomposition of combinatorial problems
VL - 2017
ER -
TY - THES
AB - The thesis encompasses several topics of plant cell biology which were studied in the model plant Arabidopsis thaliana. Chapter 1 concerns the plant hormone auxin and its polar transport through cells and tissues. The highly controlled, directional transport of auxin is facilitated by plasma membrane-localized transporters. Transporters from the PIN family direct auxin transport due to their polarized localizations at cell membranes. Substantial effort has been put into research on cellular trafficking of PIN proteins, which is thought to underlie their polar distribution. I participated in a forward genetic screen aimed at identifying novel regulators of PIN polarity. The screen yielded several genes which may be involved in PIN polarity regulation or participate in polar auxin transport by other means. Chapter 2 focuses on the endomembrane system, with particular attention to clathrin-mediated endocytosis. The project started with identification of several proteins that interact with clathrin light chains. Among them, I focused on two putative homologues of auxilin, which in non-plant systems is an endocytotic factor known for uncoating clathrin-coated vesicles in the final step of endocytosis. The body of my work consisted of an in-depth characterization of transgenic A. thaliana lines overexpressing these putative auxilins in an inducible manner. Overexpression of these proteins leads to an inhibition of endocytosis, as documented by imaging of cargoes and clathrin-related endocytic machinery. An extension of this work is an investigation into a concept of homeostatic regulation acting between distinct transport processes in the endomembrane system. With auxilin overexpressing lines, where endocytosis is blocked specifically, I made observations on the mutual relationship between two opposite trafficking processes of secretion and endocytosis. In Chapter 3, I analyze cortical microtubule arrays and their relationship to auxin signaling and polarized growth in elongating cells. In plants, microtubules are organized into arrays just below the plasma membrane, and it is thought that their function is to guide membrane-docked cellulose synthase complexes. These, in turn, influence cell wall structure and cell shape by directed deposition of cellulose fibres. In elongating cells, cortical microtubule arrays are able to reorient in relation to long cell axis, and these reorientations have been linked to cell growth and to signaling of growth-regulating factors such as auxin or light. In this chapter, I am addressing the causal relationship between microtubule array reorientation, growth, and auxin signaling. I arrive at a model where array reorientation is not guided by auxin directly, but instead is only controlled by growth, which, in turn, is regulated by auxin.
AU - Adamowski, Maciek
ID - 938
TI - Investigations into cell polarity and trafficking in the plant model Arabidopsis thaliana
ER -
TY - JOUR
AB - We reveal the existence of continuous families of guided single-mode solitons in planar waveguides with weakly nonlinear active core and absorbing boundaries. Stable propagation of TE and TM-polarized solitons is accompanied by attenuation of all other modes, i.e., the waveguide features properties of conservative and dissipative systems. If the linear spectrum of the waveguide possesses exceptional points, which occurs in the case of TM polarization, an originally focusing (defocusing) material nonlinearity may become effectively defocusing (focusing). This occurs due to the geometric phase of the carried eigenmode when the surface impedance encircles the exceptional point. In its turn, the change of the effective nonlinearity ensures the existence of dark (bright) solitons in spite of focusing (defocusing) Kerr nonlinearity of the core. The existence of an exceptional point can also result in anomalous enhancement of the effective nonlinearity. In terms of practical applications, the nonlinearity of the reported waveguide can be manipulated by controlling the properties of the absorbing cladding.
AU - Midya, Bikashkali
AU - Konotop, Vladimir
ID - 939
IS - 3
JF - Physical Review Letters
SN - 00319007
TI - Waveguides with absorbing boundaries: Nonlinearity controlled by an exceptional point and solitons
VL - 119
ER -