@phdthesis{18681, author = {Tavakoli, Mojtaba}, isbn = {978-3-99078-048-0}, issn = {2663-337X}, pages = {230}, publisher = {Institute of Science and Technology Austria}, title = {{Developing molecular and structural tools for studying brain architecture with super resolution expansion microscopy. LICONN: Molecularly-informed connectomics reconstruction with light microscopy}}, doi = {10.15479/at:ista:18681}, year = {2024}, } @phdthesis{17133, abstract = {An ideal quantum computer relies on qubits capable of performing fast gate operations and maintaining strong interconnections while preserving their quantum coherence. Since the inception of experimental eforts toward building a quantum computer, the community has faced challenges in engineering such a system. Among the various methods of implementing a quantum computer, superconducting qubits have shown fast gates close to tens of nanoseconds, with the state-of-the-art reaching a coherence of a few milliseconds. However, achieving simultaneously long lifetimes with fast qubit operations poses an inherent paradox. Qubits with high coherence require isolation from the environment, while fast operation necessitates strong coupling of the qubit. This thesis approaches this issue by proposing the idea of engineering superconducting qubits capable of transitioning between operating in a protected regime, where the qubit is completely isolated from the environment, and coupling to the communication channels as needed. In this direction, we use the geometric superinductor to scan the parameter space of rf-SQUID devices, searching for a regime where we can take the qubit protection to its extreme. This leads us to the inductively shunted transmon (IST) regime, characterized by EJ /EC ≫ 1 and EJ /EL ≫ 1, where the circuit potential exhibits a double well with a large barrier separating the local ground states of each quantum well. In this regime, although it is anticipated that the two quantum wells would be isolated from each other, we observe single fuxon tunneling between them. The interplay of the cavity photons and the fuxon transition forms a rich physical system, containing resonance conditions that allow the preparation of the fuxon ground or excited states. This enables us to study the relaxation rate of such transition and show that it can be as large as 3.6 hours. Dynamically controlling the barrier height between the two quantum wells allows for controllable coupling, which scales exponentially, for a qubit encoded in two fuxon states. The 0-π qubit is one of the very few known superconducting circuit types that ofers exponential protection from both relaxation and dephasing simultaneously. However, this qubit is not exempt from the fact that such protection comes at the expense of complex readout and control. In this thesis, we propose a way to controllably break the circuit symmetry, the key reason for the protection, to momentarily restore the ability to control and manipulate the qubit. An asymmetry in capacitances and inductances in the 0-π circuit is detrimental since they lead to coupling of the protected state to the thermally occupied parasitic mode of the circuit. However, here we try to exploit a controlled asymmetry in Josephson energies and show that this can be used as a tunable coupler between the protected states. In the future, this should allow to perform gate operations by dynamically controlling the asymmetry instead of driving the protected transition with microwave pulses. Therefore, we believe that the proposed method can make the use of protected qubits more practical in experimental realizations of quantum computing.}, author = {Hassani, Farid}, isbn = {978-3-99078-040-4}, issn = {2663-337X}, keywords = {Quantum information, Qubits, Superconducting devices}, pages = {161}, publisher = {Institute of Science and Technology Austria}, title = {{Superconducting qubits capable of dynamic switching between protected and high-speed control regimes}}, doi = {10.15479/at:ista:17133}, year = {2024}, } @article{14852, abstract = {The physical conditions giving rise to high escape fractions of ionizing radiation (LyC fesc) in star-forming galaxies – most likely protagonists of cosmic reionization – are not yet fully understood. Using the VLT/MUSE observations of ∼1400 Ly α emitters at 2.9 < z < 6.7, we compare stacked rest-frame UV spectra of candidates for LyC leakers and non-leakers selected based on their Ly α profiles. We find that the stacks of potential LyC leakers, i.e. galaxies with narrow, symmetric Ly α profiles with small peak separation, generally show (i) strong nebular O iii]λ1666, [Si iii]λ1883, and [C iii]λ1907 +C iii]λ1909 emission, indicating a high-ionization state of the interstellar medium (ISM); (ii) high equivalent widths of He iiλ1640 (∼1 − 3 Å), suggesting the presence of hard ionizing radiation fields; (iii) Si ii*λ1533 emission, revealing substantial amounts of neutral hydrogen off the line of sight; (iv) high C ivλλ1548,1550 to [C iii]λ1907 +C iii]λ1909 ratios (C iv/C iii] ≳0.75) , signalling the presence of low column density channels in the ISM. In contrast, the stacks with broad, asymmetric Ly α profiles with large peak separation show weak nebular emission lines, low He iiλ1640 equivalent widths (≲1 Å), and low C iv/C iii] (≲0.25), implying low-ionization states and high-neutral hydrogen column densities. Our results suggest that C iv/C iii] might be sensitive to the physical conditions that govern LyC photon escape, providing a promising tool for identification of ionizing sources among star-forming galaxies in the epoch of reionization.}, author = {Kramarenko, Ivan and Kerutt, J and Verhamme, A and Oesch, P A and Barrufet, L and Matthee, Jorryt J and Kusakabe, H and Goovaerts, I and Thai, T T}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics}, number = {4}, pages = {9853--9871}, publisher = {Oxford University Press}, title = {{Linking UV spectral properties of MUSE Ly α emitters at z ≳ 3 to Lyman continuum escape}}, doi = {10.1093/mnras/stad3853}, volume = {527}, year = {2024}, } @article{18266, abstract = {Matrix games are the most basic model in game theory, and yet robustness with respect to small perturbations of the matrix entries is not fully understood. In this paper, we introduce value positivity and uniform value positivity, two properties that refine the notion of optimality in the context of polynomially perturbed matrix games. The first concept captures how the value depends on the perturbation parameter, and the second consists of the existence of a fixed strategy that guarantees the value of the unperturbed matrix game for every sufficiently small positive parameter. We provide polynomial-time algorithms to check whether a polynomially perturbed matrix game satisfies these properties. We further provide the functional form for a parameterized optimal strategy and the value function. Finally, we translate our results to linear programming and stochastic games, where value positivity is related to the existence of robust solutions.}, author = {Chatterjee, Krishnendu and Oliu-Barton, Miquel and Saona Urmeneta, Raimundo J}, issn = {1526-5471}, journal = {Mathematics of Operations Research}, number = {4}, pages = {2433--3282}, publisher = {Institute for Operations Research and the Management Sciences}, title = {{Value-positivity for matrix games}}, doi = {10.1287/moor.2022.0332}, volume = {50}, year = {2024}, } @article{17047, abstract = {We provide a dynamical study of a model of multiplicative perturbation of a unitary matrix introduced by Fyodorov. In particular, we identify a flow of deterministic domains that bound the spectrum with high probability, separating the outlier from the typical eigenvalues at all sub-critical timescales. These results are obtained under generic assumptions on U that hold for a variety of unitary random matrix models.}, author = {Dubach, Guillaume and Reker, Jana}, issn = {2010-3271}, journal = {Random Matrices: Theory and Applications}, number = {2}, publisher = {World Scientific Publishing}, title = {{Dynamics of a rank-one multiplicative perturbation of a unitary matrix}}, doi = {10.1142/s2010326324500072}, volume = {13}, year = {2024}, } @inproceedings{18891, abstract = {Deep neural networks (DNNs) exhibit a surprising structure in their final layer known as neural collapse (NC), and a growing body of works has currently investigated the propagation of neural collapse to earlier layers of DNNs – a phenomenon called deep neural collapse (DNC). However, existing theoretical results are restricted to special cases: linear models, only two layers or binary classification. In contrast, we focus on non-linear models of arbitrary depth in multi-class classification and reveal a surprising qualitative shift. As soon as we go beyond two layers or two classes, DNC stops being optimal for the deep unconstrained features model (DUFM) – the standard theoretical framework for the analysis of collapse. The main culprit is a low-rank bias of multi-layer regularization schemes: this bias leads to optimal solutions of even lower rank than the neural collapse. We support our theoretical findings with experiments on both DUFM and real data, which show the emergence of the low-rank structure in the solution found by gradient descent.}, author = {Súkeník, Peter and Lampert, Christoph and Mondelli, Marco}, booktitle = {38th Annual Conference on Neural Information Processing Systems}, location = {Vancouver, Canada}, publisher = {Neural Information Processing Systems Foundation}, title = {{Neural collapse versus low-rank bias: Is deep neural collapse really optimal?}}, volume = {37}, year = {2024}, } @phdthesis{18515, abstract = {Understanding the role of evolutionary processes in shaping genetic variation has been a primary goal in evolutionary genetics. In this regard, a key question is how genetically distinct populations evolve in the face of gene flow, thereby generating genetic and phenotypic divergence and reproductive isolation (RI). This requires quantifying the role and relative contributions of prezygotic and postzygotic isolating mechanisms on the reduction of gene exchange between populations, and identifying regions in the genome that mediate RI, which is often polygenic. Further, this needs distinguishing neutral and selected regions in the genome, and discerning how selection influences patterns of neutral divergence. Population structure, defined as any deviation from panmixia, such as geographic distribution, movement and mating patterns of individuals, influences how genetic variation is structured in space and shapes the neutral null model. Availability of large scale spatial genomic datasets now enables us to detect signatures of population structure in genetic data and infer population genetic parameters. Such inferences are crucial and have wide applications in biodiversity, conservation genetics, population management and medical genetics. However, inferences are based on assumptions that do not always match the complex reality, thus leading to erroneous conclusions. Moreover, the role and interaction of heterogeneous population density and dispersal, which are ubiquitous in nature, has been challenging to study owing to their mathematical complexity. In such scenarios, feedback between theory, data and simulations can prove to be useful. In this thesis, I examine the effect of population structure on neutral genetic variation and barriers to gene exchange in hybridising populations, thereby bridging together the fields of spatial population genetics and speciation. Despite being a key concept in speciation, reproductive isolation (RI) lacks a quantitative definition and has been used and measured differently across different fields. Chapter 2 gives a quantitative definition of RI, in terms of the effect of genetic differences on gene flow. We give analytical predictions for RI in a range of scenarios, in terms of effective migration rates for discrete populations and barrier strength for continuous populations. In addition to this, we discuss current measures of RI and their limitations, and propose the need for new measures that combine organismal and genetic perspectives of RI. In chapter 3, I examine the combined effect of assortative mating, sexual selection and viability selection on RI. For this, we consider a polygenic ‘magic’ trait under a mainland-island model. We obtain novel theoretical predictions for molecular divergence in terms of effective migration rates, which bears a simple relationship to measurable fitness components of migrants and various early generation hybrids. We explore the conditions under which local adaptation can be maintained despite maladaptive gene flow and quantify the relative contributions of viability and sexual selection to genome-wide barriers to gene flow. The next two chapters of the thesis focus on a hybrid zone of Antirrhinum majus that consist of two subspecies- the magenta flowered A. m. pseudomajus and the yellow flowered A.m. striatum. Previous studies have suggested that flower colour is target of pollinator mediated selection and is influenced only by few genes. While these regions show high genetic differentiation between the subspecies, the rest of the genome is seen to be well mixed. Chapter 4 examines the effects of heterogeneous population density and leptokurtic dispersal on isolation by distance and the distribution of heterozygosity by focusing on non-flower colour markers. Chapter 5 analyses cline shapes and associations among 6 focal flower colour markers to understand how selection and dispersal maintain this hybrid zone. We see sharp coincident stepped clines at all loci and positive associations throughout the hybrid zone, contrary to the expected patterns from diffusive gene flow. With a novel scheme of inferring dispersal combined with multilocus simulations, we show that stepped clines do not reflect genetic barriers to gene flow, but are rather a result of long-distance migration. This framework allows us to get realistic estimates gene flow and selection and shows how traditional cline analysis may lead to inaccurate conclusions when assumptions of the theory are not met. Overall, this thesis investigates how different features of population structure leave detectable signatures in genetic variation, namely in patterns of isolation by distance, linkage disequilibrium and genetic divergence. It also highlights how effective migration rates provide useful way of analysing polygenic architectures and shed new light into hybrid zones. In doing so, I identify scenarios when simple models become insufficient and suggest possibe directions by combining genetic data with simulations.}, author = {Surendranadh, Parvathy}, issn = {2663-337X}, pages = {219}, publisher = {Institute of Science and Technology Austria}, title = {{Effect of population structure on neutral genetic variation and barriers to gene exchange}}, doi = {10.15479/at:ista:18515}, year = {2024}, } @article{18087, abstract = {We present a theory describing the interaction of structured light, such as light carrying orbital angular momentum, with molecules. The light-matter interaction Hamiltonian we derive is expressed through couplings between spherical gradients of the electric field and the (transition) electric multipole moments of a particle of any nontrivial rotation point group. Our model can therefore accommodate an arbitrary complexity of the molecular and electric field structure, and it can be straightforwardly extended to atoms or nanostructures. Applying this framework to rovibrational spectroscopy of molecules, we uncover the general mechanism of angular momentum exchange between the spin and orbital angular momenta of light, molecular rotation, and its center-of-mass motion. We show that the nonzero vorticity of Laguerre-Gaussian beams can strongly enhance certain rovibrational transitions that are considered forbidden in the case of nonhelical light. We discuss the experimental requirements for the observation of these forbidden transitions in state-of-the-art spatially resolved spectroscopy measurements.}, author = {Maslov, Mikhail and Koutentakis, Georgios and Hrast, Mateja and Heckl, Oliver H. and Lemeshko, Mikhail}, issn = {2643-1564}, journal = {Physical Review Research}, number = {3}, publisher = {American Physical Society}, title = {{Theory of angular momentum transfer from light to molecules}}, doi = {10.1103/physrevresearch.6.033277}, volume = {6}, year = {2024}, } @phdthesis{15020, abstract = {This thesis consists of four distinct pieces of work within theoretical biology, with two themes in common: the concept of optimization in biological systems, and the use of information-theoretic tools to quantify biological stochasticity and statistical uncertainty. Chapter 2 develops a statistical framework for studying biological systems which we believe to be optimized for a particular utility function, such as retinal neurons conveying information about visual stimuli. We formalize such beliefs as maximum-entropy Bayesian priors, constrained by the expected utility. We explore how such priors aid inference of system parameters with limited data and enable optimality hypothesis testing: is the utility higher than by chance? Chapter 3 examines the ultimate biological optimization process: evolution by natural selection. As some individuals survive and reproduce more successfully than others, populations evolve towards fitter genotypes and phenotypes. We formalize this as accumulation of genetic information, and use population genetics theory to study how much such information can be accumulated per generation and maintained in the face of random mutation and genetic drift. We identify the population size and fitness variance as the key quantities that control information accumulation and maintenance. Chapter 4 reuses the concept of genetic information from Chapter 3, but from a different perspective: we ask how much genetic information organisms actually need, in particular in the context of gene regulation. For example, how much information is needed to bind transcription factors at correct locations within the genome? Population genetics provides us with a refined answer: with an increasing population size, populations achieve higher fitness by maintaining more genetic information. Moreover, regulatory parameters experience selection pressure to optimize the fitness-information trade-off, i.e. minimize the information needed for a given fitness. This provides an evolutionary derivation of the optimization priors introduced in Chapter 2. Chapter 5 proves an upper bound on mutual information between a signal and a communication channel output (such as neural activity). Mutual information is an important utility measure for biological systems, but its practical use can be difficult due to the large dimensionality of many biological channels. Sometimes, a lower bound on mutual information is computed by replacing the high-dimensional channel outputs with decodes (signal estimates). Our result provides a corresponding upper bound, provided that the decodes are the maximum posterior estimates of the signal.}, author = {Hledik, Michal}, issn = {2663-337X}, keywords = {Theoretical biology, Optimality, Evolution, Information}, pages = {158}, publisher = {Institute of Science and Technology Austria}, title = {{Genetic information and biological optimization}}, doi = {10.15479/at:ista:15020}, year = {2024}, } @phdthesis{17225, abstract = {This thesis describes the development of an atom interferometer designed to exploit the advantages of utilizing quantum entanglement for enhanced precision measurements beyond the standard quantum limit. While the project remains ongoing, significant progress has been made. A key contribution of this work is the development of Quantrol, an experimental control system leveraging the ARTIQ framework. This software enables precise timing and control without requiring prior knowledge of ARTIQ’s implementation details or coding experience. The interface offers user friendly visual comprehension of the experimental sequence and extended capabilities, allowing researchers to scan variables with a simple click of a mouse. The main proposed project is to implement atom interferometric sequence with squeezed input states inside of a dipole trap generated by a high finesse cavity. The presence of the dipole trap allows one dimensional atomic cloud split while maintaining relatively strong confinement in other directions. We are currently able to trap and cool 87Rb atoms to few micro kelvin temperatures, load them into the dipole trap and state prepare them to be used for squeezing and interferometric sequence.}, author = {Li, Vyacheslav}, issn = {2663-337X}, pages = {79}, publisher = {Institute of Science and Technology Austria}, title = {{Towards a quantum entanglement enhanced atom interferomter}}, doi = {10.15479/at:ista:17225}, year = {2024}, } @article{14542, abstract = {It is a remarkable property of BCS theory that the ratio of the energy gap at zero temperature Ξ and the critical temperature Tc is (approximately) given by a universal constant, independent of the microscopic details of the fermionic interaction. This universality has rigorously been proven quite recently in three spatial dimensions and three different limiting regimes: weak coupling, low density and high density. The goal of this short note is to extend the universal behavior to lower dimensions d=1,2 and give an exemplary proof in the weak coupling limit.}, author = {Henheik, Sven Joscha and Lauritsen, Asbjørn Bækgaard and Roos, Barbara}, issn = {1793-6659}, journal = {Reviews in Mathematical Physics}, number = {9}, publisher = {World Scientific Publishing}, title = {{Universality in low-dimensional BCS theory}}, doi = {10.1142/s0129055x2360005x}, volume = {36}, year = {2024}, } @article{18107, abstract = {We consider a dilute fully spin-polarized Fermi gas at positive temperature in dimensions d∈{1,2,3} . We show that the pressure of the interacting gas is bounded from below by that of the free gas plus, to leading order, an explicit term of order adρ2+2/d, where a is the p-wave scattering length of the repulsive interaction and ρ is the particle density. The results are valid for a wide range of repulsive interactions, including that of a hard core, and uniform in temperatures at most of the order of the Fermi temperature. A central ingredient in the proof is a rigorous implementation of the fermionic cluster expansion of Gaudin, Gillespie and Ripka (Nucl. Phys. A, 176.2 (1971), pp. 237–260).}, author = {Lauritsen, Asbjørn Bækgaard and Seiringer, Robert}, issn = {2050-5094}, journal = {Forum of Mathematics, Sigma}, publisher = {Cambridge University Press}, title = {{Pressure of a dilute spin-polarized Fermi gas: Lower bound}}, doi = {10.1017/fms.2024.56}, volume = {12}, year = {2024}, } @phdthesis{18443, abstract = {In [KW06] Kapustin and Witten conjectured that there is a mirror symmetry relation between the hyperkähler structures on certain Higgs bundle moduli spaces. As a consequence, they conjecture an equivalence between categories of BBB and BAA-branes. At the classical level, this mirror symmetry is given by T-duality between semi-flat hyperkähler structures on algebraic integrable systems. In this thesis, we investigate the T-duality relation between hyperkähler structures and the corresponding branes on affine torus bundles. We use the techniques of generalized geometry to show that semi-flat hyperkähler structures are T-dual on algebraic integrable systems. We also describe T-duality for generalized branes. Motivated by Fourier-Mukai transform we upgrade the T-duality between generalized branes to T-duality of submanifolds endowed with U(1)-bundles and connections. This T-duality in the appropriate context specializes to T-duality between BBB and BAA-branes. }, author = {Sisak, Maria A}, issn = {2663-337X}, keywords = {hyperkaehler geometry, branes, mirror symmetry, T-duality}, pages = {178}, publisher = {Institute of Science and Technology Austria}, title = {{T-dual branes on hyperkähler manifolds}}, doi = {10.15479/at:ista:18443}, year = {2024}, } @inproceedings{17634, abstract = {System behaviors are traditionally evaluated through binary classifications of correctness, which do not suffice for properties involving quantitative aspects of systems and executions. Quantitative automata offer a more nuanced approach, mapping each execution to a real number by incorporating weighted transitions and value functions generalizing acceptance conditions. In this paper, we introduce QuAK, the first tool designed to automate the analysis of quantitative automata. QuAK currently supports a variety of quantitative automaton types, including Inf, Sup, LimInf, LimSup, LimInfAvg, and LimSupAvg automata, and implements decision procedures for problems such as emptiness, universality, inclusion, equivalence, as well as for checking whether an automaton is safe, live, or constant. Additionally, QuAK is able to compute extremal values when possible, construct safety-liveness decompositions, and monitor system behaviors. We demonstrate the effectiveness of QuAK through experiments focusing on the inclusion, constant-function check, and monitoring problems.}, author = {Chalupa, Marek and Henzinger, Thomas A and Mazzocchi, Nicolas Adrien and Sarac, Naci E}, booktitle = {12th International Symposium on Leveraging Applications of Formal Methods, Verification and Validation}, isbn = {9783031753862}, issn = {1611-3349}, location = {Crete, Greece}, pages = {3--20}, publisher = {Springer Nature}, title = {{QuAK: Quantitative Automata Kit}}, doi = {10.1007/978-3-031-75387-9_1}, volume = {15222}, year = {2024}, } @phdthesis{18667, abstract = {Many chemical and physical properties of materials are determined by the material’s shape, for example the size of its pores and the width of its tunnels. This makes materials science a prime application area for geometrical and topological methods. Nevertheless many methods in topological data analysis have not been satisfyingly extended to the needs of materials science. This thesis provides new methods and new mathematical theorems targeted at those specific needs by answering four different research questions. While the motivation for each of the research questions arises from materials science, the methods are versatile and can be applied in different areas as well. The first research question is concerned with image data, for example a three-dimensional computed tomography (CT) scan of a material, like sand or stone. There are two commonly used topologies for digital images and depending on the application either of them might be required. However, software for computing the topological data analysis method persistence homology, usually supports only one of the two topologies. We answer the question how to compute persistent homology of an image with respect to one of the two topologies using software that is intended for the other topology. The second research question is concerned with image data as well, and asks how much of the topological information of an image is lost when the resolution is coarsened. As computer tomography scanners are more expensive the higher the resolution, it is an important question in materials science to know which resolution is enough to get satisfying persistent homology. We give theoretical bounds on the information loss based on different geometrical properties of the object to be scanned. In addition, we conduct experiments on sand and stone CT image data. The third research question is motivated by comparing crystalline materials efficiently. As the atoms within a crystal repeat periodically, crystalline materials are either modeled by unmanageable infinite periodic point sets, or by one of their fundamental domains, which is unstable under perturbation. Therefore a fingerprint of crystalline materials is needed, with appropriate properties such that comparing the crystals can be eased by comparing the fingerprints instead. We define the density fingerprint and prove the necessary properties. The fourth research question is motivated by studying the hole-structure or connectedness, i.e. persistent homology or merge trees, of crystalline materials. A common way to deal with periodicity is to take a fundamental domain and identify opposite boundaries to form a torus. However, computing persistent homology or merge trees on that torus loses some of the information materials scientists are interested in and is additionally not stable under certain noise. We therefore decorate the merge tree stemming from the torus with additional information describing the density and growth rate of the periodic copies of a component within a growing spherical window. We prove all desired properties, like stability and efficient computability.}, author = {Heiss, Teresa}, isbn = {978-3-99078-052-7}, issn = {2663-337X}, keywords = {persistent homology, topological data analysis, periodic, crystalline materials, images, fingerprint}, pages = {111}, publisher = {Institute of Science and Technology Austria}, title = {{New methods for applying topological data analysis to materials science}}, doi = {10.15479/at:ista:18667}, year = {2024}, } @phdthesis{15094, abstract = {Point sets, geometric networks, and arrangements of hyperplanes are fundamental objects in discrete geometry that have captivated mathematicians for centuries, if not millennia. This thesis seeks to cast new light on these structures by illustrating specific instances where a topological perspective, specifically through discrete Morse theory and persistent homology, provides valuable insights. At first glance, the topology of these geometric objects might seem uneventful: point sets essentially lack of topology, arrangements of hyperplanes are a decomposition of Rd, which is a contractible space, and the topology of a network primarily involves the enumeration of connected components and cycles within the network. However, beneath this apparent simplicity, there lies an array of intriguing structures, a small subset of which will be uncovered in this thesis. Focused on three case studies, each addressing one of the mentioned objects, this work will showcase connections that intertwine topology with diverse fields such as combinatorial geometry, algorithms and data structures, and emerging applications like spatial biology. }, author = {Cultrera di Montesano, Sebastiano}, issn = {2663-337X}, pages = {108}, publisher = {Institute of Science and Technology Austria}, title = {{Persistence and Morse theory for discrete geometric structures}}, doi = {10.15479/at:ista:15094}, year = {2024}, } @phdthesis{17336, abstract = {This thesis deals with the study of stochastic processes and their ergodicity properties. The variety of problems encountered calls for a set of different approaches, ranging from classical to modern ones: a special place is held by probabilistic methods based on couplings, by functional inequalities, and by the theory of gradient flows in the space of measures. The material is organized as follows. Chapter 1 contains the introduction to this thesis, starting with a general presentation of some of the relevant topics. Section 1.1 is dedicated to the theory of gradient flows in metric spaces, and introduces the first contribution of this thesis [DSMP24], which is presented in detail in Chapter 2. Section 1.2 moves to the topic of curvature of Markov chains, concluding with a brief description of our second contribution [Ped23], which is included in Chapter 3. Section 1.3 discusses applications of stochastic processes to the theory of sampling, in particular the recent framework of score-based diffusion models, and our contribution [PMM24], which is contained in Chapter 4. Section 1.4 discusses some related problems, concerning the regularization properties of the heat flow. It serves as a motivation for the work [BP24], which we report in Chapter 5. Finally, Section 1.5 discusses the last contribution of this thesis, which can be found in Chapter 6. It deals with the convergence to equilibrium of a particular stochastic model from quantitative genetics: this is established via some functional inequalities, which we prove with probabilistic arguments based on couplings. }, author = {Pedrotti, Francesco}, issn = {2663-337X}, pages = {183}, publisher = {Institute of Science and Technology Austria}, title = {{Functional inequalities and convergence of stochastic processes}}, doi = {10.15479/at:ista:17336}, year = {2024}, } @inproceedings{18890, abstract = {Deep Neural Collapse (DNC) refers to the surprisingly rigid structure of the data representations in the final layers of Deep Neural Networks (DNNs). Though the phenomenon has been measured in a variety of settings, its emergence is typically explained via data-agnostic approaches, such as the unconstrained features model. In this work, we introduce a data-dependent setting where DNC forms due to feature learning through the average gradient outer product (AGOP). The AGOP is defined with respect to a learned predictor and is equal to the uncentered covariance matrix of its input-output gradients averaged over the training dataset. The Deep Recursive Feature Machine (Deep RFM) is a method that constructs a neural network by iteratively mapping the data with the AGOP and applying an untrained random feature map. We demonstrate empirically that DNC occurs in Deep RFM across standard settings as a consequence of the projection with the AGOP matrix computed at each layer. Further, we theoretically explain DNC in Deep RFM in an asymptotic setting and as a result of kernel learning. We then provide evidence that this mechanism holds for neural networks more generally. In particular, we show that the right singular vectors and values of the weights can be responsible for the majority of within-class variability collapse for DNNs trained in the feature learning regime. As observed in recent work, this singular structure is highly correlated with that of the AGOP.}, author = {Beaglehole, Daniel and Súkeník, Peter and Mondelli, Marco and Belkin, Mikhail}, booktitle = {38th Annual Conference on Neural Information Processing Systems}, issn = {1049-5258}, location = {Vancouver, Canada}, publisher = {Neural Information Processing Systems Foundation}, title = {{Average gradient outer product as a mechanism for deep neural collapse}}, doi = {10.52202/079017-4156}, volume = {37}, year = {2024}, } @inproceedings{18875, abstract = {Current state-of-the-art methods for differentially private model training are based on matrix factorization techniques. However, these methods suffer from high computational overhead because they require numerically solving a demanding optimization problem to determine an approximately optimal factorization prior to the actual model training. In this work, we present a new matrix factorization approach, BSR, which overcomes this computational bottleneck. By exploiting properties of the standard matrix square root, BSR allows to efficiently handle also large-scale problems. For the key scenario of stochastic gradient descent with momentum and weight decay, we even derive analytical expressions for BSR that render the computational overhead negligible. We prove bounds on the approximation quality that hold both in the centralized and in the federated learning setting. Our numerical experiments demonstrate that models trained using BSR perform on par with the best existing methods, while completely avoiding their computational overhead.}, author = {Kalinin, Nikita and Lampert, Christoph}, booktitle = {38th Annual Conference on Neural Information Processing Systems}, issn = {1049-5258}, location = {Vancouver, Canada}, publisher = {Neural Information Processing Systems Foundation}, title = {{Banded square root matrix factorization for differentially private model training}}, doi = {10.52202/079017-0560}, volume = {37}, 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}, }