TY - CONF
AB - Markov chains are the de facto finite-state model for stochastic dynamical systems, and Markov decision processes (MDPs) extend Markov chains by incorporating non-deterministic behaviors. Given an MDP and rewards on states, a classical optimization criterion is the maximal expected total reward where the MDP stops after T steps, which can be computed by a simple dynamic programming algorithm. We consider a natural generalization of the problem where the stopping times can be chosen according to a probability distribution, such that the expected stopping time is T, to optimize the expected total reward. Quite surprisingly we establish inter-reducibility of the expected stopping-time problem for Markov chains with the Positivity problem (which is related to the well-known Skolem problem), for which establishing either decidability or undecidability would be a major breakthrough. Given the hardness of the exact problem, we consider the approximate version of the problem: we show that it can be solved in exponential time for Markov chains and in exponential space for MDPs.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
ID - 10004
KW - Computer science
KW - Heuristic algorithms
KW - Memory management
KW - Automata
KW - Markov processes
KW - Probability distribution
KW - Complexity theory
SN - 1043-6871
T2 - Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science
TI - Stochastic processes with expected stopping time
ER -
TY - CONF
AB - In runtime verification, a monitor watches a trace of a system and, if possible, decides after observing each finite prefix whether or not the unknown infinite trace satisfies a given specification. We generalize the theory of runtime verification to monitors that attempt to estimate numerical values of quantitative trace properties (instead of attempting to conclude boolean values of trace specifications), such as maximal or average response time along a trace. Quantitative monitors are approximate: with every finite prefix, they can improve their estimate of the infinite trace's unknown property value. Consequently, quantitative monitors can be compared with regard to a precision-cost trade-off: better approximations of the property value require more monitor resources, such as states (in the case of finite-state monitors) or registers, and additional resources yield better approximations. We introduce a formal framework for quantitative and approximate monitoring, show how it conservatively generalizes the classical boolean setting for monitoring, and give several precision-cost trade-offs for monitors. For example, we prove that there are quantitative properties for which every additional register improves monitoring precision.
AU - Henzinger, Thomas A
AU - Sarac, Naci E
ID - 10003
KW - Computer science
KW - Runtime
KW - Registers
KW - Time factors
KW - Monitoring
SN - 1043-6871
T2 - Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science
TI - Quantitative and approximate monitoring
ER -
TY - JOUR
AB - In this paper, we introduce a random environment for the exclusion process in obtained by assigning a maximal occupancy to each site. This maximal occupancy is allowed to randomly vary among sites, and partial exclusion occurs. Under the assumption of ergodicity under translation and uniform ellipticity of the environment, we derive a quenched hydrodynamic limit in path space by strengthening the mild solution approach initiated in Nagy (2002) and Faggionato (2007). To this purpose, we prove, employing the technology developed for the random conductance model, a homogenization result in the form of an arbitrary starting point quenched invariance principle for a single particle in the same environment, which is a result of independent interest. The self-duality property of the partial exclusion process allows us to transfer this homogenization result to the particle system and, then, apply the tightness criterion in Redig et al. (2020).
AU - Floreani, Simone
AU - Redig, Frank
AU - Sau, Federico
ID - 10024
JF - Stochastic Processes and their Applications
KW - hydrodynamic limit
KW - random environment
KW - random conductance model
KW - arbitrary starting point quenched invariance principle
KW - duality
KW - mild solution
SN - 0304-4149
TI - Hydrodynamics for the partial exclusion process in random environment
VL - 142
ER -
TY - THES
AB - This thesis is the result of the research carried out by the author during his PhD at IST Austria between 2017 and 2021. It mainly focuses on the Fröhlich polaron model, specifically to its regime of strong coupling. This model, which is rigorously introduced and discussed in the introduction, has been of great interest in condensed matter physics and field theory for more than eighty years. It is used to describe an electron interacting with the atoms of a solid material (the strength of this interaction is modeled by the presence of a coupling constant α in the Hamiltonian of the system). The particular regime examined here, which is mathematically described by considering the limit α →∞, displays many interesting features related to the emergence of classical behavior, which allows for a simplified effective description of the system under analysis. The properties, the range of validity and a quantitative analysis of the precision of such classical approximations are the main object of the present work. We specify our investigation to the study of the ground state energy of the system, its dynamics and its effective mass. For each of these problems, we provide in the introduction an overview of the previously known results and a detailed account of the original contributions by the author.
AU - Feliciangeli, Dario
ID - 9733
SN - 2663-337X
TI - The polaron at strong coupling
ER -
TY - JOUR
AB - The developmental strategies used by progenitor cells to endure a safe journey from their induction place towards the site of terminal differentiation are still poorly understood. Here we uncovered a progenitor cell allocation mechanism that stems from an incomplete process of epithelial delamination that allows progenitors to coordinate their movement with adjacent extra-embryonic tissues. Progenitors of the zebrafish laterality organ originate from the surface epithelial enveloping layer by an apical constriction process of cell delamination. During this process, progenitors retain long-term apical contacts that enable the epithelial layer to pull a subset of progenitors along their way towards the vegetal pole. The remaining delaminated progenitors follow apically-attached progenitors’ movement by a co-attraction mechanism, avoiding sequestration by the adjacent endoderm, ensuring their fate and collective allocation at the differentiation site. Thus, we reveal that incomplete delamination serves as a cellular platform for coordinated tissue movements during development. Impact Statement: Incomplete delamination serves as a cellular platform for coordinated tissue movements during development, guiding newly formed progenitor cell groups to the differentiation site.
AU - Pulgar, Eduardo
AU - Schwayer, Cornelia
AU - Guerrero, Néstor
AU - López, Loreto
AU - Márquez, Susana
AU - Härtel, Steffen
AU - Soto, Rodrigo
AU - Heisenberg, Carl Philipp
AU - Concha, Miguel L.
ID - 9999
JF - eLife
KW - cell delamination
KW - apical constriction
KW - dragging
KW - mechanical forces
KW - collective 18 locomotion
KW - dorsal forerunner cells
KW - zebrafish
TI - Apical contacts stemming from incomplete delamination guide progenitor cell allocation through a dragging mechanism
VL - 10
ER -
TY - JOUR
AB - We study the temporal dissipation of variance and relative entropy for ergodic Markov Chains in continuous time, and compute explicitly the corresponding dissipation rates. These are identified, as is well known, in the case of the variance in terms of an appropriate Hilbertian norm; and in the case of the relative entropy, in terms of a Dirichlet form which morphs into a version of the familiar Fisher information under conditions of detailed balance. Here we obtain trajectorial versions of these results, valid along almost every path of the random motion and most transparent in the backwards direction of time. Martingale arguments and time reversal play crucial roles, as in the recent work of Karatzas, Schachermayer and Tschiderer for conservative diffusions. Extensions are developed to general “convex divergences” and to countable state-spaces. The steepest descent and gradient flow properties for the variance, the relative entropy, and appropriate generalizations, are studied along with their respective geometries under conditions of detailed balance, leading to a very direct proof for the HWI inequality of Otto and Villani in the present context.
AU - Karatzas, Ioannis
AU - Maas, Jan
AU - Schachermayer, Walter
ID - 10023
IS - 4
JF - Communications in Information and Systems
KW - Markov Chain
KW - relative entropy
KW - time reversal
KW - steepest descent
KW - gradient flow
SN - 1526-7555
TI - Trajectorial dissipation and gradient flow for the relative entropy in Markov chains
VL - 21
ER -
TY - JOUR
AB - The ⊗*-monoidal structure on the category of sheaves on the Ran space is not pro-nilpotent in the sense of [3]. However, under some connectivity assumptions, we prove that Koszul duality induces an equivalence of categories and that this equivalence behaves nicely with respect to Verdier duality on the Ran space and integrating along the Ran space, i.e. taking factorization homology. Based on ideas sketched in [4], we show that these results also offer a simpler alternative to one of the two main steps in the proof of the Atiyah-Bott formula given in [7] and [5].
AU - Ho, Quoc P
ID - 10033
JF - Advances in Mathematics
KW - Chiral algebras
KW - Chiral homology
KW - Factorization algebras
KW - Koszul duality
KW - Ran space
SN - 0001-8708
TI - The Atiyah-Bott formula and connectivity in chiral Koszul duality
VL - 392
ER -
TY - JOUR
AB - The control of nonequilibrium quantum dynamics in many-body systems is challenging because interactions typically lead to thermalization and a chaotic spreading throughout Hilbert space. We investigate nonequilibrium dynamics after rapid quenches in a many-body system composed of 3 to 200 strongly interacting qubits in one and two spatial dimensions. Using a programmable quantum simulator based on Rydberg atom arrays, we show that coherent revivals associated with so-called quantum many-body scars can be stabilized by periodic driving, which generates a robust subharmonic response akin to discrete time-crystalline order. We map Hilbert space dynamics, geometry dependence, phase diagrams, and system-size dependence of this emergent phenomenon, demonstrating new ways to steer complex dynamics in many-body systems and enabling potential applications in quantum information science.
AU - Bluvstein, D.
AU - Omran, A.
AU - Levine, H.
AU - Keesling, A.
AU - Semeghini, G.
AU - Ebadi, S.
AU - Wang, T. T.
AU - Michailidis, Alexios
AU - Maskara, N.
AU - Ho, W. W.
AU - Choi, S.
AU - Serbyn, Maksym
AU - Greiner, M.
AU - Vuletić, V.
AU - Lukin, M. D.
ID - 9618
IS - 6536
JF - Science
KW - Multidisciplinary
SN - 0036-8075
TI - Controlling quantum many-body dynamics in driven Rydberg atom arrays
VL - 371
ER -
TY - JOUR
AB - SnSe has emerged as one of the most promising materials for thermoelectric energy conversion due to its extraordinary performance in its single-crystal form and its low-cost constituent elements. However, to achieve an economic impact, the polycrystalline counterpart needs to replicate the performance of the single crystal. Herein, we optimize the thermoelectric performance of polycrystalline SnSe produced by consolidating solution-processed and surface-engineered SnSe particles. In particular, the SnSe particles are coated with CdSe molecular complexes that crystallize during the sintering process, forming CdSe nanoparticles. The presence of CdSe nanoparticles inhibits SnSe grain growth during the consolidation step due to Zener pinning, yielding a material with a high density of grain boundaries. Moreover, the resulting SnSe–CdSe nanocomposites present a large number of defects at different length scales, which significantly reduce the thermal conductivity. The produced SnSe–CdSe nanocomposites exhibit thermoelectric figures of merit up to 2.2 at 786 K, which is among the highest reported for solution-processed SnSe.
AU - Liu, Yu
AU - Calcabrini, Mariano
AU - Yu, Yuan
AU - LEE, Seungho
AU - Chang, Cheng
AU - David, Jérémy
AU - Ghosh, Tanmoy
AU - Spadaro, Maria Chiara
AU - Xie, Chenyang
AU - Cojocaru-Mirédin, Oana
AU - Arbiol, Jordi
AU - Ibáñez, Maria
ID - 10042
JF - ACS Nano
KW - tin selenide
KW - nanocomposite
KW - grain growth
KW - Zener pinning
KW - thermoelectricity
KW - annealing
KW - solution processing
SN - 1936-0851
TI - Defect engineering in solution-processed polycrystalline SnSe leads to high thermoelectric performance
ER -
TY - THES
AB - This PhD thesis is primarily focused on the study of discrete transport problems, introduced for the first time in the seminal works of Maas [Maa11] and Mielke [Mie11] on finite state Markov chains and reaction-diffusion equations, respectively. More in detail, my research focuses on the study of transport costs on graphs, in particular the convergence and the stability of such problems in the discrete-to-continuum limit. This thesis also includes some results concerning
non-commutative optimal transport. The first chapter of this thesis consists of a general introduction to the optimal transport problems, both in the discrete, the continuous, and the non-commutative setting. Chapters 2 and 3 present the content of two works, obtained in collaboration with Peter Gladbach, Eva Kopfer, and Jan Maas, where we have been able to show the convergence of discrete transport costs on periodic graphs to suitable continuous ones, which can be described by means of a homogenisation result. We first focus on the particular case of quadratic costs on the real line and then extending the result to more general costs in arbitrary dimension. Our results are the first complete characterisation of limits of transport costs on periodic graphs in arbitrary dimension which do not rely on any additional symmetry. In Chapter 4 we turn our attention to one of the intriguing connection between evolution equations and optimal transport, represented by the theory of gradient flows. We show that discrete gradient flow structures associated to a finite volume approximation of a certain class of diffusive equations (Fokker–Planck) is stable in the limit of vanishing meshes, reproving the convergence of the scheme via the method of evolutionary Γ-convergence and exploiting a more variational point of view on the problem. This is based on a collaboration with Dominik Forkert and Jan Maas. Chapter 5 represents a change of perspective, moving away from the discrete world and reaching the non-commutative one. As in the discrete case, we discuss how classical tools coming from the commutative optimal transport can be translated into the setting of density matrices. In particular, in this final chapter we present a non-commutative version of the Schrödinger problem (or entropic regularised optimal transport problem) and discuss existence and characterisation of minimisers, a duality result, and present a non-commutative version of the well-known Sinkhorn algorithm to compute the above mentioned optimisers. This is based on a joint work with Dario Feliciangeli and Augusto Gerolin. Finally, Appendix A and B contain some additional material and discussions, with particular attention to Harnack inequalities and the regularity of flows on discrete spaces.
AU - Portinale, Lorenzo
ID - 10030
SN - 2663-337X
TI - Discrete-to-continuum limits of transport problems and gradient flows in the space of measures
ER -