IST Austria: PubRep (Institute of Science and Technology)
Not a member yet
6140 research outputs found
Sort by
Improved differentially private continual observation using group algebra
No full textDifferentially private weighted prefix sum under continual observation is a crucial component in the production-level deployment of private next-word prediction for Gboard, which, according to Google, has over a billion users. More specifically, Google uses a differentially private mechanism to sum weighted gradients in its private follow-the-regularized leader algorithm. Apart from efficiency, the additive error of the private mechanism is crucial as multiplied with the square root of the model’s dimension d (with d ranging up to 10 trillion, for example, Switch Transformers or M6-10T), it determines the accuracy of the learning system. So, any improvement in leading constant matters significantly in practice. In this paper, we show a novel connection between mechanisms for continual weighted prefix sum and a concept in representation theory known as the group matrix introduced in correspondence between Dedekind and Frobenius (Sitzungsber. Preuss. Akad. Wiss. Berlin, 1897) and generalized by Schur (Journal für die reine und angewandte Mathematik, 1904). To the best of our knowledge, this is the first application of group algebra in the analysis of differentially private algorithms. Using this connection, we analyze a class of matrix norms known as factorization norms that give upper and lower bounds for the additive error under general ℓp-norms of the matrix mechanism. This allows us to give 1. the first efficient factorization that matches the best-known non-constructive upper bound on the factorization norm by Mathias (SIAM Journal of Matrix Analysis and Applications, 1993) for the matrix used in Google’s deployment, and also improves on the previous best-known constructive bound of Fichtenberger, Henzinger, and Upadhyay (ICML 2023) and Henzinger, Upadhyay, and Upadhyay (SODA 2023); thereby, partially resolving an open question in operator theory, 2. the first upper bound on the additive error for a large class of weight functions for weighted prefix sum problems, including the sliding window matrix (Bolot, Fawaz, Muthukrishnan, Nikolov, and Taft (ICDT 2013). We also improve the bound on factorizing the striped matrix used for outputting a synthetic graph that approximates all cuts (Fichtenberger, Henzinger, and Upadhyay (ICML 2023)); 3. a general improved upper bound on the factorization norms that depend on algebraic properties of the weighted sum matrices and that applies to a more general class of weighting functions than the ones considered in Henzinger, Upadhyay, and Upadhyay (SODA 2024). Using the known connection between these factorization norms and the ℓp-error of continual weighted sum, we give an upper bound on the ℓp-error for the continual weighted sum problem for p ≥ 2
Deformational rigidity of integrable metrics on the torus
No full textIt is conjectured that the only integrable metrics on the two-dimensional torus are Liouville metrics. In this paper, we study a deformative version of this conjecture: we consider integrable deformations of a non-flat Liouville metric in a conformal class and show that for a fairly large class of such deformations, the deformed metric is again Liouville. The principal idea of the argument is that the preservation of rational invariant tori in the foliation of the phase space forces a linear combination on the Fourier coefficients of the deformation to vanish. Showing that the resulting linear system is non-degenerate will then yield the claim. Since our method of proof immediately carries over to higher dimensional tori, we obtain analogous statements in this more general case. To put our results in perspective, we review existing results about integrable metrics on the torus
LIPIcs
No full textUniquely represented (UR) data structures represent each logical state with a unique storage state. We study the problem of maintaining a dynamic set of n keys from a totally ordered universe in this context. UR structures are also called "strongly history independent" structures in the literature.
We introduce a two-layer data structure called (α,ε)-Randomized Block Search Tree (RBST) that is uniquely represented and suitable for external memory (EM). Though RBSTs naturally generalize the well-known binary Treaps, several new ideas are needed to analyze the expected search, update, and storage efficiency in terms of block-reads, block-writes, and blocks stored. We prove that searches have O(ε^{-1} + log_α n) block-reads, that dynamic updates perform O(ε^{-1} + log_α(n)/α) block-writes and O(ε^{-2}+(1+(ε^{-1}+log n)/α)log_α n) block-reads, and that (α, ε)-RBSTs have an asymptotic load-factor of at least (1-ε) for every ε ∈ (0,1/2].
Thus (α, ε)-RBSTs improve on the known, uniquely represented B-Treap [Golovin; ICALP'09]. Compared with non-UR structures, the RBST is also, to the best of our knowledge, the first external memory structure that is storage-efficient and has a non-amortized, write-efficient update bound
nextGEMS: Entering the era of kilometer-scale Earth system modeling
No full textThe Next Generation of Earth Modeling Systems (nextGEMS) project aimed to produce multidecadal climate simulations, for the first time, with resolved kilometer-scale (km-scale) processes in the ocean, land, and atmosphere. In only 3 years, nextGEMS achieved this milestone with the two km-scale Earth system models, ICOsahedral Non-hydrostatic model (ICON) and Integrated Forecasting System coupled to the Finite-volumE Sea ice-Ocean Model (IFS-FESOM). nextGEMS was based on three cornerstones: (1) developing km-scale Earth system models with small errors in the energy and water balance, (2) performing km-scale climate simulations with a throughput greater than 1 simulated year per day, and (3) facilitating new workflows for an efficient analysis of the large simulations with common data structures and output variables. These cornerstones shaped the timeline of nextGEMS, divided into four cycles. Each cycle marked the release of a new configuration of ICON and IFS-FESOM, which were evaluated at hackathons. The hackathon participants included experts from climate science, software engineering, and high-performance computing as well as users from the energy and agricultural sectors. The continuous efforts over the four cycles allowed us to produce 30-year simulations with ICON and IFS-FESOM, spanning the period 2020–2049 under the SSP3-7.0 scenario. The throughput was about 500 simulated days per day on the Levante supercomputer of the German Climate Computing Center (DKRZ). The simulations employed a horizontal grid of about 5 km resolution in the ocean and 10 km resolution in the atmosphere and land. Aside from this technical achievement, the simulations allowed us to gain new insights into the realism of ICON and IFS-FESOM. Beyond its time frame, nextGEMS builds the foundation of the Climate Change Adaptation Digital Twin developed in the Destination Earth initiative and paves the way for future European research on climate change
Multiplicative rewards in Markovian models
No full textThis paper studies the expected value of multiplicative rewards, where rewards obtained in each step are multiplied (instead of the usual addition), in Markov chains (MCs) and Markov decision processes (MDPs). One of the key differences to additive rewards is that the expected value may diverge to ∞ not only due to recurrent, but also due to transient states.For MCs, computing the value is shown to be possible in polynomial time given an oracle for the comparison of succinctly represented integers (CSRI), which is only known to be solvable in polynomial time subject to number-theoretic conjectures. Interestingly, distinguishing whether the value is ∞ or 0 is at least as hard as CSRI, while determining if it is one of these two can be done in polynomial time. In MDPs, the optimal value can be computed in polynomial space. Further refined complexity results and results on the complexity of optimal schedulers are presented. The techniques developed for MDPs additionally allow to solve the multiplicative variant of the stochastic shortest path problem. Finally, for MCs and MDPs where an absorbing state is reached almost surely, all considered problems are solvable in polynomial time
Machine learning of charges and long-range interactions from energies and forces
No full textAccurate modeling of long-range forces is critical in atomistic simulations, as they play a central role in determining the properties of material and chemical systems. However, standard machine learning interatomic potentials (MLIPs) often rely on short-range approximations, limiting their applicability to systems with significant electrostatics and dispersion forces. We recently introduced the Latent Ewald Summation (LES) method, which captures long-range electrostatics without explicitly learning atomic charges or charge equilibration. We benchmark LES on diverse and challenging systems, including charged molecules, ionic liquids, electrolyte solutions, polar dipeptides, surface adsorption, electrolyte/solid interfaces, and solid-solid interfaces. Here we show that LES can reproduce the exact atomic charges for classical systems with fixed charges and can infer dipole and quadrupole moments, as well as the dipole derivative with respect to atomic positions, for quantum mechanical systems. Moreover, LES can achieve better accuracy in energy and force predictions compared to methods that explicitly learn from charges
GA-NIFS and EIGER: A merging quasar host at z = 7 with an overmassive black hole
No full textThe James Webb Space Telescope is revolutionising our ability to understand the host galaxies and local environments of high-z quasars. Here we obtain a comprehensive understanding of the host galaxy of the z = 7.08 quasar J1120+0641 by combining NIRSpec integral field spectroscopy with NIRCam photometry of the host continuum emission. Our emission-line maps reveal that this quasar host is undergoing a merger with a bright companion galaxy. The quasar host and the companion have similar dynamical masses of ∼1010 M⊙, suggesting that this is a major galaxy interaction. Through detailed quasar subtraction and SED fitting using the NIRCam data, we obtained an estimate of the host stellar mass of M* = (3.0−1.4+2.5) × 109 M⊙, with M∗ = (2.7−0.5+0.5) × 109 M⊙ for the companion galaxy. Using the Hβ Balmer line, we estimated a virial black hole mass of MBH = (1.9−1.1+2.9) × 109 M⊙. Thus, J1120+0641 has an extreme black hole–stellar mass ratio of MBH/M* = 0.63−0.31+0.54, which is ∼3 dex larger than expected by the local scaling relations between black hole and stellar mass. J1120+0641 is powered by an overmassive black hole with the highest reported black hole–stellar mass ratio in a quasar host that is currently undergoing a major merger. These new insights highlight the power of JWST for measuring and understanding these extreme first quasars
Crystal growth engineering for dendrite-free Zinc metal plating
No full textThe practical implementation of aqueous zinc-ion batteries (AZIBs) is limited by uncontrolled zinc (Zn) dendrite growth during anode plating, compromising both safety and cycle life. Typically, Zn plating proceeds via 2D growth along the six equivalent prismatic [1010] directions of the hexagonal close-packed (HCP) Zn lattice, forming hexagonal platelets that promote dendrite formation. Here, an effective electrolyte engineering strategy is presented using rare-earth ions to regulate Zn plating. Combined multiscale experimental analyses and computational modeling reveal that these ions preferentially adsorb onto the prismatic {1010} facets, suppressing lateral epitaxial growth of the basal (0002) planes. This redirects Zn plating toward an apparent screw dislocation-driven growth along the [0001] axis. The resulting growth pathway, together with randomly oriented Zn nucleation, yields dense, uniform, and dendrite-free Zn layers with markedly improved cycling stability and high depth-of-discharge operation, thereby challenging the prevailing assumption that dendrite suppression requires (0002)-oriented growth parallel to the substrate. This work provides new mechanistic insights into Zn plating dynamics and establishes a scalable strategy for stable, dendrite-free Zn anodes in next-generation AZIBs
Observation of analogue dynamic Schwinger effect and non-perturbative light sensing in lead halide perovskites
No full textDielectric breakdown of physical vacuum (Schwinger effect) is the textbook demonstration of compatibility of Relativity and Quantum theory. Although observing this effect is still practically unachievable, its analogue generalizations have been shown to be more readily attainable. This paper demonstrates that a gapped Dirac semiconductor, methylammonium lead-bromide perovskite (MAPbBr3), exhibits analogue dynamic Schwinger effect. Tunneling ionization under deep subgap mid-infrared irradiation leads to intense photoluminescence in the visible range, in full agreement with quasi-adiabatic theory. In addition to revealing a gapped extended system suitable for studying the analogue Schwinger effect, this observation holds great potential for nonperturbative field sensing, i.e., sensing electric fields through nonperturbative light-matter interactions. First, this paper illustrates this by measuring the local deviation from the nominally cubic phase of a perovskite single crystal, which can be interpreted in terms of frozen-in fields. Next, it is shown that analogue dynamic Schwinger effect can be used for nonperturbative amplification of nonparametric upconversion process in perovskites driven simultaneously by multiple optical fields. This discovery demonstrates the potential for material response beyond perturbation theory in the tunneling regime, offering extremely sensitive light detection and amplification across an ultrabroad spectral range not accessible by conventional devices