@inproceedings{17214, abstract = {Current numerical algorithms for simulating friction fall in one of two camps: smooth solvers sacrifice the stable treatment of static friction in exchange for fast convergence, and non-smooth solvers accurately compute friction at convergence rates that are often prohibitive for large graphics applications. We introduce a novel bridge between these two ideas that computes static and dynamic friction stably and efficiently. Our key idea is to convert the highly constrained non-smooth problem into an unconstrained smooth problem using logarithmic barriers that converges to the exact solution as accuracy increases. We phrase the problem as an interior point primal-dual problem that can be solved efficiently with Newton iteration. We observe quadratic convergence despite the non-smooth nature of the original problem, and our method is well-suited for large systems of tightly packed objects with many contact points. We demonstrate the efficacy of our method with stable piles of grains and stacks of objects, complex granular flows, and robust interlocking assemblies of rigid bodies.}, author = {Chen, Yi-Lu and Ly, Mickaël and Wojtan, Christopher J}, booktitle = {Special Interest Group on Computer Graphics and Interactive Techniques Conference Conference Papers '24}, isbn = {9798400705250}, keywords = {physical simulation, frictional contact, rigid body mechanics, non-smooth dynamics}, location = {Denver, United States}, publisher = {Association for Computing Machinery}, title = {{Primal-dual non-smooth friction for rigid body animation}}, doi = {10.1145/3641519.3657485}, year = {2024}, } @article{17219, abstract = {We introduce a multi-material non-manifold mesh-based surface tracking algorithm that converts self-intersections into topological changes. Our algorithm generalizes prior work on manifold surface tracking with topological changes: it preserves surface features like mesh-based methods, and it robustly handles topological changes like level set methods. Our method also offers improved efficiency and robustness over the state of the art. We demonstrate the effectiveness of the approach on a range of examples, including complex soap film simulations with thousands of interacting bubbles, and boolean unions of non-manifold meshes consisting of millions of triangles.}, author = {Synak, Peter and Kalinov, Aleksei and Strugaru, Irina-Malina and Etemadihaghighi, Arian and Yang, Huidong and Wojtan, Christopher J}, issn = {1557-7368}, journal = {ACM Transactions on Graphics}, keywords = {surface tracking, topology change, non- manifold meshes, multi-material flows, solid modeling}, number = {4}, publisher = {Association for Computing Machinery}, title = {{Multi-material mesh-based surface tracking with implicit topology changes}}, doi = {10.1145/3658223}, volume = {43}, year = {2024}, } @unpublished{17222, abstract = {The quantum approximate optimization algorithm (QAOA) uses a quantum computer to implement a variational method with $2p$ layers of alternating unitary operators, optimized by a classical computer to minimize a cost function. While rigorous performance guarantees exist for the QAOA at small depths $p$, the behavior at large depths remains less clear, though simulations suggest exponentially fast convergence for certain problems. In this work, we gain insights into the deep QAOA using an analytic expansion of the cost function around transition states. Transition states are constructed in a recursive manner: from the local minima of the QAOA with $p$ layers we obtain transition states of the QAOA with $p+1$ layers, which are stationary points characterized by a unique direction of negative curvature. We construct an analytic estimate of the negative curvature and the corresponding direction in parameter space at each transition state. The expansion of the QAOA cost function along the negative direction to the quartic order gives a lower bound of the QAOA cost function improvement. We provide physical intuition behind the analytic expressions for the local curvature and quartic expansion coefficient. Our numerical study confirms the accuracy of our approximations and reveals that the obtained bound and the true value of the QAOA cost function gain have a characteristic exponential decrease with the number of layers $p$, with the bound decreasing more rapidly. Our study establishes an analytical method for recursively studying the QAOA that is applicable in the regime of high circuit depth.}, author = {Medina Ramos, Raimel A and Serbyn, Maksym}, booktitle = {arXiv}, title = {{A recursive lower bound on the energy improvement of the quantum approximate optimization algorithm}}, doi = {10.48550/arXiv.2405.10125}, year = {2024}, } @article{17231, abstract = {In the class of projective billiards, which contains the usual billiards, we exhibit counter-examples to Ivrii's conjecture, which states that in any planar billiard with smooth boundary the set of periodic orbits has zero measure. The counter-examples are polygons admitting a 2-parameters family of n-periodic orbits, with n being either 3 or any even integer greater than 4.}, author = {Fiorebe, Corentin}, issn = {1553-5231}, journal = {Discrete and Continuous Dynamical Systems- Series A}, number = {11}, pages = {3287--3301}, publisher = {American Institute of Mathematical Sciences}, title = {{Examples of projective billiards with open sets of periodic orbits}}, doi = {10.3934/dcds.2024059}, volume = {44}, year = {2024}, } @article{17232, abstract = {The lineage relationship of clonally-related cells offers important insights into the ontogeny and cytoarchitecture of the brain in health and disease. Here, we provide a protocol to concurrently assess cell lineage relationship and cell-type identity among clonally-related cells in situ. We first describe the preparation and screening of acute brain slices containing clonally-related cells labeled using mosaic analysis with double markers (MADM). We then outline steps to collect RNA from individual cells for downstream applications and cell-type identification using RNA sequencing. For complete details on the use and execution of this protocol, please refer to Cheung et al. 1}, author = {Cheung, Giselle T and Pauler, Florian and Koppensteiner, Peter and Hippenmeyer, Simon}, issn = {2666-1667}, journal = {STAR Protocols}, number = {3}, publisher = {Elsevier}, title = {{Protocol for mapping cell lineage and cell-type identity of clonally-related cells in situ using MADM-CloneSeq}}, doi = {10.1016/j.xpro.2024.103168}, volume = {5}, year = {2024}, } @article{17233, abstract = {CRISPR-Cas9 technology has become an essential tool for plant genome editing. Recent advancements have significantly improved the ability to target multiple genes simultaneously within the same genetic background through various strategies. Additionally, there has been significant progress in developing methods for inducible or tissue-specific editing. These advancements offer numerous possibilities for tailored genome modifications. Building upon existing research, we have developed an optimized and modular strategy allowing the targeting of several genes simultaneously in combination with the synchronized expression of the Cas9 endonuclease in the egg cell. This system allows significant editing efficiency while avoiding mosaicism. In addition, the versatile system we propose allows adaptation to inducible and/or tissue-specific edition according to the promoter chosen to drive the expression of the Cas9 gene. Here, we describe a step-by-step protocol for generating the binary vector necessary for establishing Arabidopsis edited lines using a versatile cloning strategy that combines Gateway® and Golden Gate technologies. We describe a versatile system that allows the cloning of as many guides as needed to target DNA, which can be multiplexed into a polycistronic gene and combined in the same construct with sequences for the expression of the Cas9 endonuclease. The expression of Cas9 is controlled by selecting from among a collection of promoters, including constitutive, inducible, ubiquitous, or tissue-specific promoters. Only one vector containing the polycistronic gene (tRNA-sgRNA) needs to be constructed. For that, sgRNA (composed of protospacers chosen to target the gene of interest and sgRNA scaffold) is cloned in tandem with the pre-tRNA sequence. Then, a single recombination reaction is required to assemble the promoter, the zCas9 coding sequence, and the tRNA-gRNA polycistronic gene. Each element is cloned in an entry vector and finally assembled according to the Multisite Gateway® Technology. Here, we detail the process to express zCas9 under the control of egg cell promoter fused to enhancer sequence (EC1.2en-EC1.1p) and to simultaneously target two multiple C2 domains and transmembrane region protein genes (MCTP3 and MCTP4, respectively at3g57880 and at1g51570), using one or two sgRNA per gene.}, author = {Li, Ziqiang and Huard, Jennifer and Bayer, Emmanuelle M. and Wattelet-Boyer, Valérie}, issn = {2331-8325}, journal = {Bio-protocol}, number = {13}, publisher = {Bio-Protocol}, title = {{Versatile cloning strategy for efficient multigene editing in Arabidopsis}}, doi = {10.21769/BioProtoc.5029}, volume = {14}, year = {2024}, } @article{17234, abstract = {The identification of red, apparently massive galaxies at z > 7 in early James Webb Space Telescope (JWST) photometry suggests a strongly accelerated time line compared to standard models of galaxy growth. A major uncertainty in the interpretation is whether the red colors are caused by evolved stellar populations, dust, or other effects such as emission lines or active galactic nuclei (AGNs). Here we show that three of the massive galaxy candidates at z = 6.7–8.4 have prominent Balmer breaks in JWST/NIRSpec spectroscopy from the RUBIES program. The Balmer breaks demonstrate unambiguously that stellar emission dominates at λrest = 0.4 μm and require formation histories extending hundreds of millions of years into the past in galaxies only 600–800 Myr after the big bang. Two of the three galaxies also show broad Balmer lines, with Hβ FWHM > 2500 km s−1, suggesting that dust-reddened AGNs contribute to, or even dominate, the spectral energy distributions of these galaxies at λrest ≳ 0.6 μm. All three galaxies have relatively narrow [O iii] lines, seemingly ruling out a high-mass interpretation if the lines arise in dynamically relaxed, inclined disks. Yet the inferred masses also remain highly uncertain. We model the high-quality spectra using Prospector to decompose the continuum into stellar and AGN components and explore limiting cases in stellar/AGN contribution. This produces a wide range of possible stellar masses, spanning M⋆ ∼ 109−1011M⊙. Nevertheless, all fits suggest a very early and rapid formation, most of which follow with a truncation in star formation. Potential origins and evolutionary tracks for these objects are discussed, from the cores of massive galaxies to low-mass galaxies with overmassive black holes. Intriguingly, we find all of these explanations to be incomplete; deeper and redder data are needed to understand the physics of these systems.}, author = {Wang, Bingjie and Leja, Joel and De Graaff, Anna and Brammer, Gabriel B. and Weibel, Andrea and Van Dokkum, Pieter and Baggen, Josephine F.W. and Suess, Katherine A. and Greene, Jenny E. and Bezanson, Rachel and Cleri, Nikko J. and Hirschmann, Michaela and Labbé, Ivo and Matthee, Jorryt J and Mcconachie, Ian and Naidu, Rohan P. and Nelson, Erica and Oesch, Pascal A. and Setton, David J. and Williams, Christina C.}, issn = {2041-8213}, journal = {Astrophysical Journal Letters}, number = {1}, publisher = {IOP Publishing}, title = {{RUBIES: Evolved stellar populations with extended formation histories at z ∼ 7-8 in candidate massive galaxies identified with JWST/NIRSpec}}, doi = {10.3847/2041-8213/ad55f7}, volume = {969}, year = {2024}, } @article{17235, abstract = {We demonstrate ion irradiation by argon or gallium as a wafer-scale post-processing method to increase disorder in superconducting thin films. We study several widely used superconductors, both single-elements and compounds. We show that ion irradiation increases normal-state resistivity in all our films, which is expected to enable tuning their superconducting properties, for example, toward a higher kinetic inductance. We observe an increase in superconducting transition temperature for Al and MoSi and a decrease for Nb, NbN, and TiN. In MoSi, ion irradiation also improves the mixing of the two materials. We demonstrate the fabrication of an amorphous and homogeneous film of MoSi with uniform thickness, which is promising, for example, for superconducting nanowire single-photon detectors.}, author = {Kohopää, Katja and Ronzani, Alberto and Jabdaraghi, Robab Najafi and Bera, Arijit and Ribeiro, Mário and Hazra, Dibyendu and Senior, Jorden L and Prunnila, Mika and Govenius, Joonas and Lehtinen, Janne S. and Kemppinen, Antti}, issn = {2166-532X}, journal = {APL Materials}, number = {7}, publisher = {AIP Publishing}, title = {{Effect of ion irradiation on superconducting thin films}}, doi = {10.1063/5.0202851}, volume = {12}, year = {2024}, } @inproceedings{17236, abstract = {Currently, the best known tradeoff between approximation ratio and complexity for the Sparsest Cut problem is achieved by the algorithm in [Sherman, FOCS 2009]: it computes O(√(log n)/ε)-approximation using O(nε logO(1) n) maxflows for any ε∈[Θ(1/log n),Θ(1)]. It works by solving the SDP relaxation of [Arora-Rao-Vazirani, STOC 2004] using the Multiplicative Weights Update algorithm (MW) of [Arora-Kale, JACM 2016]. To implement one MW step, Sherman approximately solves a multicommodity flow problem using another application of MW. Nested MW steps are solved via a certain "chaining" algorithm that combines results of multiple calls to the maxflow algorithm. We present an alternative approach that avoids solving the multicommodity flow problem and instead computes "violating paths". This simplifies Sherman's algorithm by removing a need for a nested application of MW, and also allows parallelization: we show how to compute O(√(log n)/ε)-approximation via O(logO(1) n) maxflows using O(nε) processors. We also revisit Sherman's chaining algorithm, and present a simpler version together with a new analysis.}, author = {Kolmogorov, Vladimir}, booktitle = {Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures}, isbn = {9798400704161}, issn = {1548-6109}, location = {Nantes, France}, pages = {403--414}, publisher = {Association for Computing Machinery}, title = {{A simpler and parallelizable O(√log n)-approximation algorithm for sparsest cut}}, doi = {10.1145/3626183.3659969}, year = {2024}, } @article{17237, abstract = {The impact of climate change on populations will be contingent upon their contemporary adaptive evolution. In this study, we investigated the contemporary evolution of 4 populations of the cold-water kelp Laminaria digitata by analyzing their spatial and temporal genomic variations using ddRAD-sequencing. These populations were sampled from the center to the southern margin of its north-eastern Atlantic distribution at 2 time points, spanning at least 2 generations. Through genome scans for local adaptation at a single time point, we identified candidate loci that showed clinal variation correlated with changes in sea surface temperature (SST) along latitudinal gradients. This finding suggests that SST may drive the adaptive response of these kelp populations, although factors such as species’ demographic history should also be considered. Additionally, we performed a simulation approach to distinguish the effect of selection from genetic drift in allele frequency changes over time. This enabled the detection of loci in the southernmost population that exhibited temporal differentiation beyond what would be expected from genetic drift alone: these are candidate loci which could have evolved under selection over time. In contrast, we did not detect any outlier locus based on temporal differentiation in the population from the North Sea, which also displayed low and decreasing levels of genetic diversity. The diverse evolutionary scenarios observed among populations can be attributed to variations in the prevalence of selection relative to genetic drift across different environments. Therefore, our study highlights the potential of temporal genomics to offer valuable insights into the contemporary evolution of marine foundation species facing climate change.}, author = {Reynes, Lauric and Fouqueau, Louise and Aurelle, Didier and Mauger, Stephane and Destombe, Christophe and Valero, Myriam}, issn = {1420-9101}, journal = {Journal of Evolutionary Biology}, number = {6}, pages = {677--692}, publisher = {Oxford University Press}, title = {{Temporal genomics help in deciphering neutral and adaptive patterns in the contemporary evolution of kelp populations}}, doi = {10.1093/jeb/voae048}, volume = {37}, year = {2024}, } @article{17238, abstract = {We know that heritable variation is abundant, and that selection causes all but the smallest populations to rapidly shift beyond their original trait distribution. So then, what limits the range of a species? There are physical constraints and also population genetic limits to the effectiveness of selection, ultimately set by population size. Global adaptation, where the same genotype is favoured over the whole range, is most efficient when based on a multitude of weakly selected alleles and is effective even when local demes are small, provided that there is some gene flow. In contrast, local adaptation is sensitive to gene flow and may require alleles with substantial effect. How can populations combine the advantages of large effective size with the ability to specialise into local niches? To what extent does reproductive isolation help resolve this tension? I address these questions using eco-evolutionary models of polygenic adaptation, contrasting discrete demes with continuousspace.}, author = {Barton, Nicholas H}, issn = {1420-9101}, journal = {Journal of Evolutionary Biology}, number = {6}, pages = {605--615}, publisher = {Oxford University Press}, title = {{Limits to species' range: The tension between local and global adaptation}}, doi = {10.1093/jeb/voae052}, volume = {37}, year = {2024}, } @article{17239, abstract = {Collagen is the most abundant protein in tissue scaffolds in live organisms. Collagen can self-assemble in vitro, which has led to a number of biotechnological and biomedical applications. To understand the dominant factors that participate in the formation of collagen nanostructures, here we study in real time and with nanoscale resolution the disassembly and reassembly of collagens. We implement a high-speed force microscope, which provides in situ high spatiotemporal resolution images of collagen nanostructures under changing pH conditions. The disassembly and reassembly are dominated by the electrostatic interactions among amino-acid residues of different molecules. Acidic conditions favor disassembly by neutralizing negatively charged residues. The process sets a net repulsive force between collagen molecules. A neutral pH favors the presence of negative and positively charged residues along the collagen molecules, which promotes their electrostatic attraction. Molecular dynamics simulations reproduce the experimental behavior and validate the electrostatic-based model of the disassembly and reassembly processes.}, author = {Garcia-Sacristan, Clara and Gisbert, Victor G. and Klein, Kevin and Šarić, Anđela and Garcia, Ricardo}, issn = {1936-086X}, journal = {ACS Nano}, number = {28}, pages = {18485--18492}, publisher = {American Chemical Society}, title = {{In operando imaging electrostatic-driven disassembly and reassembly of collagen nanostructures}}, doi = {10.1021/acsnano.4c03839}, volume = {18}, year = {2024}, } @article{17269, abstract = {The directed migration of epithelial cell collectives through coordinated movements plays a crucial role in various physiological processes and is increasingly understood at the level of large confluent monolayers. However, numerous processes rely on the migration of small groups of polarized epithelial clusters in complex environments, and their responses to external geometries remain poorly understood. To address this, we cultivate primary epithelial keratocyte tissues on adhesive microstripes to create autonomous epithelial clusters with well-defined geometries. We show that their migration efficiency is strongly influenced by the contact geometry and the orientation of cell–cell contacts with respect to the direction of migration. A combination of velocity and polarity alignment with contact regulation of locomotion in an active matter model captures quantitatively the experimental data. Furthermore, we predict that this combination of rules enables efficient navigation in complex geometries, which we confirm experimentally. Altogether, our findings provide a conceptual framework for extracting the interaction rules of active systems from their interaction with physical boundaries, as well as design principles for collective navigation in complex microenvironments.}, author = {Vercruysse, Eléonore and Brückner, David and Gómez-González, Manuel and Remson, Alexandre and Luciano, Marine and Kalukula, Yohalie and Rossetti, Leone and Trepat, Xavier and Hannezo, Edouard B and Gabriele, Sylvain}, issn = {1745-2481}, journal = {Nature Physics}, pages = {1492--1500}, publisher = {Springer Nature}, title = {{Geometry-driven migration efficiency of autonomous epithelial cell clusters}}, doi = {10.1038/s41567-024-02532-x}, volume = {20}, year = {2024}, } @article{17277, abstract = {This paper is devoted to stability results for the Gaussian logarithmic Sobolev inequality, with explicit stability constants. }, author = {Brigati, Giovanni and Dolbeault, Jean and Simonov, Nikita}, issn = {1096-0783}, journal = {Journal of Functional Analysis}, number = {8}, publisher = {Elsevier}, title = {{Stability for the logarithmic Sobolev inequality}}, doi = {10.1016/j.jfa.2024.110562}, volume = {287}, year = {2024}, } @article{17278, abstract = {An azeotrope is a constant boiling point mixture, and its behavior is important for fluid separation processes. Predicting azeotropes from atomistic simulations is difficult due to the complexities and convergence problems of Monte Carlo and free-energy perturbation techniques. Here, we present a methodology for predicting the azeotropes of binary mixtures, which computes the compositional dependence of chemical potentials from molecular dynamics simulations using the S0 method and employs experimental boiling point and vaporization enthalpy data. Using this methodology, we reproduce the azeotropes, or lack thereof, in five case studies, including ethanol/water, ethanol/isooctane, methanol/water, hydrazine/water, and acetone/chloroform mixtures. We find that it is crucial to use the experimental boiling point and vaporization enthalpy for reliable azeotrope predictions, as empirical force fields are not accurate enough for these quantities. Finally, we use regular solution models to rationalize the azeotropes and reveal that they tend to form when the mixture components have similar boiling points and strong interactions.}, author = {Wang, Xiaoyu and Cheng, Bingqing}, issn = {1089-7690}, journal = {Journal of Chemical Physics}, number = {3}, publisher = {AIP Publishing}, title = {{Integrating molecular dynamics simulations and experimental data for azeotrope predictions in binary mixtures}}, doi = {10.1063/5.0217232}, volume = {161}, year = {2024}, } @article{17279, abstract = {In a recent issue of Cell, Zhang et al.1 demonstrate that mechanical features of a solid tumor can drive T cells into dysfunctionality and identify pathways that revert this “exhausted” state.}, author = {Avellaneda Sarrió, Mario and Sixt, Michael K}, issn = {2451-9448}, journal = {Cell Chemical Biology}, number = {7}, pages = {1242--1243}, publisher = {Elsevier}, title = {{Rescuing T cells from stiff tumors}}, doi = {10.1016/j.chembiol.2024.06.011}, volume = {31}, year = {2024}, } @article{17280, abstract = {Adherens junction–associated protein 1 (AJAP1) has been implicated in brain diseases; however, a pathogenic mechanism has not been identified. AJAP1 is widely expressed in neurons and binds to γ-aminobutyric acid type B receptors (GBRs), which inhibit neurotransmitter release at most synapses in the brain. Here, we show that AJAP1 is selectively expressed in dendrites and trans-synaptically recruits GBRs to presynaptic sites of neurons expressing AJAP1. We have identified several monoallelic AJAP1 variants in individuals with epilepsy and/or neurodevelopmental disorders. Specifically, we show that the variant p.(W183C) lacks binding to GBRs, resulting in the inability to recruit them. Ultrastructural analysis revealed significantly decreased presynaptic GBR levels in Ajap1−/− and Ajap1W183C/+ mice. Consequently, these mice exhibited reduced GBR-mediated presynaptic inhibition at excitatory and inhibitory synapses, along with impaired synaptic plasticity. Our study reveals that AJAP1 enables the postsynaptic neuron to regulate the level of presynaptic GBR-mediated inhibition, supporting the clinical relevance of loss-of-function AJAP1 variants.}, author = {Früh, Simon and Boudkkazi, Sami and Koppensteiner, Peter and Sereikaite, Vita and Chen, Li Yuan and Fernandez-Fernandez, Diego and Rem, Pascal D. and Ulrich, Daniel and Schwenk, Jochen and Chen, Ziyang and Monnier, Elodie Le and Fritzius, Thorsten and Innocenti, Sabrina M. and Besseyrias, Valérie and Trovò, Luca and Stawarski, Michal and Argilli, Emanuela and Sherr, Elliott H. and Van Bon, Bregje and Kamsteeg, Erik Jan and Iascone, Maria and Pilotta, Alba and Cutrì, Maria R. and Azamian, Mahshid S. and Hernández-García, Andrés and Lalani, Seema R. and Rosenfeld, Jill A. and Zhao, Xiaonan and Vogel, Tiphanie P. and Ona, Herda and Scott, Daryl A. and Scheiffele, Peter and Strømgaard, Kristian and Tafti, Mehdi and Gassmann, Martin and Fakler, Bernd and Shigemoto, Ryuichi and Bettler, Bernhard}, issn = {2375-2548}, journal = {Science Advances}, number = {28}, publisher = {American Association for the Advancement of Science}, title = {{Monoallelic de novo AJAP1 loss-of- function variants disrupt trans-synaptic control of neurotransmitter release}}, doi = {10.1126/sciadv.adk5462}, volume = {10}, year = {2024}, } @article{17281, abstract = {We extend the free convolution of Brown measures of R-diagonal elements introduced by Kösters and Tikhomirov [ 28] to fractional powers. We then show how this fractional free convolution arises naturally when studying the roots of random polynomials with independent coefficients under repeated differentiation. When the proportion of derivatives to the degree approaches one, we establish central limit theorem-type behavior and discuss stable distributions.}, author = {Campbell, Andrew J and O'Rourke, Sean and Renfrew, David T}, issn = {1687-0247}, journal = {International Mathematics Research Notices}, number = {13}, pages = {10189--10218}, publisher = {Oxford University Press}, title = {{The fractional free convolution of R-diagonal elements and random polynomials under repeated differentiation}}, doi = {10.1093/imrn/rnae062}, volume = {2024}, year = {2024}, } @article{17282, abstract = {Let X be a vector field and Y be a co-vector field on a smooth manifold M. Does there exist a smooth Riemannian metric gαβ on M such that Yβ=gαβXα ? The main result of this note gives necessary and sufficient conditions for this to be true. As an application of this result we show that a finite-dimensional ergodic Lindblad equation admits a gradient flow structure for the von Neumann relative entropy if and only if the condition of BKM-detailed balance holds.}, author = {Brooks, Morris and Maas, Jan}, issn = {1432-0835}, journal = {Calculus of Variations and Partial Differential Equations}, number = {6}, publisher = {Springer Nature}, title = {{Characterisation of gradient flows for a given functional}}, doi = {10.1007/s00526-024-02755-z}, volume = {63}, year = {2024}, } @article{17283, abstract = {We consider the problems of statically refuting equivalence and similarity of output distributions defined by a pair of probabilistic programs. Equivalence and similarity are two fundamental relational properties of probabilistic programs that are essential for their correctness both in implementation and in compilation. In this work, we present a new method for static equivalence and similarity refutation. Our method refutes equivalence and similarity by computing a function over program outputs whose expected value with respect to the output distributions of two programs is different. The function is computed simultaneously with an upper expectation supermartingale and a lower expectation submartingale for the two programs, which we show to together provide a formal certificate for refuting equivalence and similarity. To the best of our knowledge, our method is the first approach to relational program analysis to offer the combination of the following desirable features: (1) it is fully automated, (2) it is applicable to infinite-state probabilistic programs, and (3) it provides formal guarantees on the correctness of its results. We implement a prototype of our method and our experiments demonstrate the effectiveness of our method to refute equivalence and similarity for a number of examples collected from the literature.}, author = {Chatterjee, Krishnendu and Kafshdar Goharshadi, Ehsan and Novotný, Petr and Zikelic, Dorde}, issn = {2475-1421}, journal = {Proceedings of the ACM on Programming Languages}, publisher = {Association for Computing Machinery}, title = {{Equivalence and similarity refutation for probabilistic programs}}, doi = {10.1145/3656462}, volume = {8}, year = {2024}, }