TY - CONF AB - We study space complexity and time-space trade-offs with a focus not on peak memory usage but on overall memory consumption throughout the computation. Such a cumulative space measure was introduced for the computational model of parallel black pebbling by [Alwen and Serbinenko ’15] as a tool for obtaining results in cryptography. We consider instead the non- deterministic black-white pebble game and prove optimal cumulative space lower bounds and trade-offs, where in order to minimize pebbling time the space has to remain large during a significant fraction of the pebbling. We also initiate the study of cumulative space in proof complexity, an area where other space complexity measures have been extensively studied during the last 10–15 years. Using and extending the connection between proof complexity and pebble games in [Ben-Sasson and Nordström ’08, ’11] we obtain several strong cumulative space results for (even parallel versions of) the resolution proof system, and outline some possible future directions of study of this, in our opinion, natural and interesting space measure. AU - Alwen, Joel F AU - De Rezende, Susanna AU - Nordstrom, Jakob AU - Vinyals, Marc ED - Papadimitriou, Christos ID - 1175 SN - 18688969 TI - Cumulative space in black-white pebbling and resolution VL - 67 ER - TY - JOUR AB - Variation in genotypes may be responsible for differences in dispersal rates, directional biases, and growth rates of individuals. These traits may favor certain genotypes and enhance their spatiotemporal spreading into areas occupied by the less advantageous genotypes. We study how these factors influence the speed of spreading in the case of two competing genotypes under the assumption that spatial variation of the total population is small compared to the spatial variation of the frequencies of the genotypes in the population. In that case, the dynamics of the frequency of one of the genotypes is approximately described by a generalized Fisher–Kolmogorov–Petrovskii–Piskunov (F–KPP) equation. This generalized F–KPP equation with (nonlinear) frequency-dependent diffusion and advection terms admits traveling wave solutions that characterize the invasion of the dominant genotype. Our existence results generalize the classical theory for traveling waves for the F–KPP with constant coefficients. Moreover, in the particular case of the quadratic (monostable) nonlinear growth–decay rate in the generalized F–KPP we study in detail the influence of the variance in diffusion and mean displacement rates of the two genotypes on the minimal wave propagation speed. AU - Kollár, Richard AU - Novak, Sebastian ID - 1191 IS - 3 JF - Bulletin of Mathematical Biology TI - Existence of traveling waves for the generalized F–KPP equation 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 - A drawing of a graph G is radial if the vertices of G are placed on concentric circles C 1 , . . . , C k with common center c , and edges are drawn radially : every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. We show that a graph G is radial planar if G has a radial drawing in which every two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Toth. AU - Fulek, Radoslav AU - Pelsmajer, Michael AU - Schaefer, Marcus ID - 1113 IS - 1 JF - Journal of Graph Algorithms and Applications TI - Hanani-Tutte for radial planarity VL - 21 ER - TY - CHAP AB - Complex I (NADH:ubiquinone oxidoreductase) plays a central role in cellular energy generation, contributing to the proton motive force used to produce ATP. It couples the transfer of two electrons between NADH and quinone to translocation of four protons across the membrane. It is the largest protein assembly of bacterial and mitochondrial respiratory chains, composed, in mammals, of up to 45 subunits with a total molecular weight of ∼1 MDa. Bacterial enzyme is about half the size, providing the important “minimal” model of complex I. The l-shaped complex consists of a hydrophilic arm, where electron transfer occurs, and a membrane arm, where proton translocation takes place. Previously, we have solved the crystal structures of the hydrophilic domain of complex I from Thermus thermophilus and of the membrane domain from Escherichia coli, followed by the atomic structure of intact, entire complex I from T. thermophilus. Recently, we have solved by cryo-EM a first complete atomic structure of mammalian (ovine) mitochondrial complex I. Core subunits are well conserved from the bacterial version, whilst supernumerary subunits form an interlinked, stabilizing shell around the core. Subunits containing additional cofactors, including Zn ion, NADPH and phosphopantetheine, probably have regulatory roles. Dysfunction of mitochondrial complex I is implicated in many human neurodegenerative diseases. The structure of mammalian enzyme provides many insights into complex I mechanism, assembly, maturation and dysfunction, allowing detailed molecular analysis of disease-causing mutations. AU - Sazanov, Leonid A ED - Wikström, Mårten ID - 444 SN - 978-1-78262-865-1 T2 - Mechanisms of primary energy transduction in biology TI - Structure of respiratory complex I: “Minimal” bacterial and “de luxe” mammalian versions ER - TY - JOUR AB - Most kinesin motors move in only one direction along microtubules. Members of the kinesin-5 subfamily were initially described as unidirectional plus-end-directed motors and shown to produce piconewton forces. However, some fungal kinesin-5 motors are bidirectional. The force production of a bidirectional kinesin-5 has not yet been measured. Therefore, it remains unknown whether the mechanism of the unconventional minus-end-directed motility differs fundamentally from that of plus-end-directed stepping. Using force spectroscopy, we have measured here the forces that ensembles of purified budding yeast kinesin-5 Cin8 produce in microtubule gliding assays in both plus- and minus-end direction. Correlation analysis of pause forces demonstrated that individual Cin8 molecules produce additive forces in both directions of movement. In ensembles, Cin8 motors were able to produce single-motor forces up to a magnitude of ∼1.5 pN. Hence, these properties appear to be conserved within the kinesin-5 subfamily. Force production was largely independent of the directionality of movement, indicating similarities between the motility mechanisms for both directions. These results provide constraints for the development of models for the bidirectional motility mechanism of fission yeast kinesin-5 and provide insight into the function of this mitotic motor. AU - Fallesen, Todd AU - Roostalu, Johanna AU - Düllberg, Christian F AU - Pruessner, Gunnar AU - Surrey, Thomas ID - 453 IS - 9 JF - Biophysical Journal TI - Ensembles of bidirectional kinesin Cin8 produce additive forces in both directions of movement VL - 113 ER - TY - JOUR AB - The computation of the winning set for parity objectives and for Streett objectives in graphs as well as in game graphs are central problems in computer-aided verification, with application to the verification of closed systems with strong fairness conditions, the verification of open systems, checking interface compatibility, well-formedness of specifications, and the synthesis of reactive systems. We show how to compute the winning set on n vertices for (1) parity-3 (aka one-pair Streett) objectives in game graphs in time O(n5/2) and for (2) k-pair Streett objectives in graphs in time O(n2+nklogn). For both problems this gives faster algorithms for dense graphs and represents the first improvement in asymptotic running time in 15 years. AU - Chatterjee, Krishnendu AU - Henzinger, Monika H AU - Loitzenbauer, Veronika ID - 464 IS - 3 JF - Logical Methods in Computer Science SN - 1860-5974 TI - Improved algorithms for parity and Streett objectives VL - 13 ER - TY - JOUR AB - This paper presents a method for simulating water surface waves as a displacement field on a 2D domain. Our method relies on Lagrangian particles that carry packets of water wave energy; each packet carries information about an entire group of wave trains, as opposed to only a single wave crest. Our approach is unconditionally stable and can simulate high resolution geometric details. This approach also presents a straightforward interface for artistic control, because it is essentially a particle system with intuitive parameters like wavelength and amplitude. Our implementation parallelizes well and runs in real time for moderately challenging scenarios. AU - Jeschke, Stefan AU - Wojtan, Christopher J ID - 470 IS - 4 JF - ACM Transactions on Graphics SN - 07300301 TI - Water wave packets VL - 36 ER - TY - JOUR AB - We present a new algorithm for the statistical model checking of Markov chains with respect to unbounded temporal properties, including full linear temporal logic. The main idea is that we monitor each simulation run on the fly, in order to detect quickly if a bottom strongly connected component is entered with high probability, in which case the simulation run can be terminated early. As a result, our simulation runs are often much shorter than required by termination bounds that are computed a priori for a desired level of confidence on a large state space. In comparison to previous algorithms for statistical model checking our method is not only faster in many cases but also requires less information about the system, namely, only the minimum transition probability that occurs in the Markov chain. In addition, our method can be generalised to unbounded quantitative properties such as mean-payoff bounds. AU - Daca, Przemyslaw AU - Henzinger, Thomas A AU - Kretinsky, Jan AU - Petrov, Tatjana ID - 471 IS - 2 JF - ACM Transactions on Computational Logic (TOCL) SN - 15293785 TI - Faster statistical model checking for unbounded temporal properties VL - 18 ER - TY - JOUR AB - We introduce planar matchings on directed pseudo-line arrangements, which yield a planar set of pseudo-line segments such that only matching-partners are adjacent. By translating the planar matching problem into a corresponding stable roommates problem we show that such matchings always exist. Using our new framework, we establish, for the first time, a complete, rigorous definition of weighted straight skeletons, which are based on a so-called wavefront propagation process. We present a generalized and unified approach to treat structural changes in the wavefront that focuses on the restoration of weak planarity by finding planar matchings. AU - Biedl, Therese AU - Huber, Stefan AU - Palfrader, Peter ID - 481 IS - 3-4 JF - International Journal of Computational Geometry and Applications TI - Planar matchings for weighted straight skeletons VL - 26 ER -