TY - CONF AB - We study the Hamilton cycle problem with input a random graph G ~ G(n,p) in two different settings. In the first one, G is given to us in the form of randomly ordered adjacency lists while in the second one, we are given the adjacency matrix of G. In each of the two settings we derive a deterministic algorithm that w.h.p. either finds a Hamilton cycle or returns a certificate that such a cycle does not exist for p = p(n) ≥ 0. The running times of our algorithms are O(n) and respectively, each being best possible in its own setting. AU - Anastos, Michael ID - 14344 SN - 9781611977554 T2 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms TI - Fast algorithms for solving the Hamilton cycle problem with high probability VL - 2023 ER - TY - JOUR AB - Surface curvature both emerges from, and influences the behavior of, living objects at length scales ranging from cell membranes to single cells to tissues and organs. The relevance of surface curvature in biology is supported by numerous experimental and theoretical investigations in recent years. In this review, first, a brief introduction to the key ideas of surface curvature in the context of biological systems is given and the challenges that arise when measuring surface curvature are discussed. Giving an overview of the emergence of curvature in biological systems, its significance at different length scales becomes apparent. On the other hand, summarizing current findings also shows that both single cells and entire cell sheets, tissues or organisms respond to curvature by modulating their shape and their migration behavior. Finally, the interplay between the distribution of morphogens or micro-organisms and the emergence of curvature across length scales is addressed with examples demonstrating these key mechanistic principles of morphogenesis. Overall, this review highlights that curved interfaces are not merely a passive by-product of the chemical, biological, and mechanical processes but that curvature acts also as a signal that co-determines these processes. AU - Schamberger, Barbara AU - Ziege, Ricardo AU - Anselme, Karine AU - Ben Amar, Martine AU - Bykowski, Michał AU - Castro, André P.G. AU - Cipitria, Amaia AU - Coles, Rhoslyn A. AU - Dimova, Rumiana AU - Eder, Michaela AU - Ehrig, Sebastian AU - Escudero, Luis M. AU - Evans, Myfanwy E. AU - Fernandes, Paulo R. AU - Fratzl, Peter AU - Geris, Liesbet AU - Gierlinger, Notburga AU - Hannezo, Edouard B AU - Iglič, Aleš AU - Kirkensgaard, Jacob J.K. AU - Kollmannsberger, Philip AU - Kowalewska, Łucja AU - Kurniawan, Nicholas A. AU - Papantoniou, Ioannis AU - Pieuchot, Laurent AU - Pires, Tiago H.V. AU - Renner, Lars D. AU - Sageman-Furnas, Andrew O. AU - Schröder-Turk, Gerd E. AU - Sengupta, Anupam AU - Sharma, Vikas R. AU - Tagua, Antonio AU - Tomba, Caterina AU - Trepat, Xavier AU - Waters, Sarah L. AU - Yeo, Edwina F. AU - Roschger, Andreas AU - Bidan, Cécile M. AU - Dunlop, John W.C. ID - 12710 IS - 13 JF - Advanced Materials SN - 0935-9648 TI - Curvature in biological systems: Its quantification, emergence, and implications across the scales VL - 35 ER - TY - JOUR AB - Photoisomerization of azobenzenes from their stable E isomer to the metastable Z state is the basis of numerous applications of these molecules. However, this reaction typically requires ultraviolet light, which limits applicability. In this study, we introduce disequilibration by sensitization under confinement (DESC), a supramolecular approach to induce the E-to-Z isomerization by using light of a desired color, including red. DESC relies on a combination of a macrocyclic host and a photosensitizer, which act together to selectively bind and sensitize E-azobenzenes for isomerization. The Z isomer lacks strong affinity for and is expelled from the host, which can then convert additional E-azobenzenes to the Z state. In this way, the host–photosensitizer complex converts photon energy into chemical energy in the form of out-of-equilibrium photostationary states, including ones that cannot be accessed through direct photoexcitation. AU - Gemen, Julius AU - Church, Jonathan R. AU - Ruoko, Tero-Petri AU - Durandin, Nikita AU - Białek, Michał J. AU - Weissenfels, Maren AU - Feller, Moran AU - Kazes, Miri AU - Borin, Veniamin A. AU - Odaybat, Magdalena AU - Kalepu, Rishir AU - Diskin-Posner, Yael AU - Oron, Dan AU - Fuchter, Matthew J. AU - Priimagi, Arri AU - Schapiro, Igor AU - Klajn, Rafal ID - 13340 IS - 6664 JF - Science TI - Disequilibrating azoarenes by visible-light sensitization under confinement VL - 381 ER - TY - JOUR AB - The elasticity of disordered and polydisperse polymer networks is a fundamental problem of soft matter physics that is still open. Here, we self-assemble polymer networks via simulations of a mixture of bivalent and tri- or tetravalent patchy particles, which result in an exponential strand length distribution analogous to that of experimental randomly cross-linked systems. After assembly, the network connectivity and topology are frozen and the resulting system is characterized. We find that the fractal structure of the network depends on the number density at which the assembly has been carried out, but that systems with the same mean valence and same assembly density have the same structural properties. Moreover, we compute the long-time limit of the mean-squared displacement, also known as the (squared) localization length, of the cross-links and of the middle monomers of the strands, showing that the dynamics of long strands is well described by the tube model. Finally, we find a relation connecting these two localization lengths at high density and connect the cross-link localization length to the shear modulus of the system. AU - Sorichetti, Valerio AU - Ninarello, Andrea AU - Ruiz-Franco, José AU - Hugouvieux, Virginie AU - Zaccarelli, Emanuela AU - Micheletti, Cristian AU - Kob, Walter AU - Rovigatti, Lorenzo ID - 12705 IS - 7 JF - Journal of Chemical Physics SN - 0021-9606 TI - Structure and elasticity of model disordered, polydisperse, and defect-free polymer networks VL - 158 ER - TY - JOUR AB - We study turn-based stochastic zero-sum games with lexicographic preferences over objectives. Stochastic games are standard models in control, verification, and synthesis of stochastic reactive systems that exhibit both randomness as well as controllable and adversarial non-determinism. Lexicographic order allows one to consider multiple objectives with a strict preference order. To the best of our knowledge, stochastic games with lexicographic objectives have not been studied before. For a mixture of reachability and safety objectives, we show that deterministic lexicographically optimal strategies exist 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 the computation of optimal strategies in a sequence of single-objectives games. For omega-regular objectives, we restrict our analysis to one-player games, also known as Markov decision processes. We show that lexicographically optimal strategies exist and need either randomization or finite memory. We present an algorithm that solves the relevant decision problem in polynomial time. We have implemented our algorithms and report experimental results on various case studies. AU - Chatterjee, Krishnendu AU - Katoen, Joost P AU - Mohr, Stefanie AU - Weininger, Maximilian AU - Winkler, Tobias ID - 12738 JF - Formal Methods in System Design TI - Stochastic games with lexicographic objectives ER -