@article{20457, abstract = {Patch-clamp recording of miniature postsynaptic currents (mPSCs, or ‘minis’) is used extensively to investigate the functional properties of synapses. With this approach, spontaneous synaptic transmission events are recorded in an attempt to determine quantal synaptic parameters or the effect of synaptic manipulations. However, at the majority of brain synapses these events are small, with many undetectable due to recording noise. The effects of incomplete detection were well appreciated in the early years of synaptic physiology analysis, but appear to be increasingly forgotten. Here we sought to characterise the consequences of incomplete detection on the interpretability of mini analysis, using simulated mPSC data to give full control over event parameters. We demonstrate that commonly reported measures such as mean event amplitude and frequency, are misrepresented by the loss of undetected events. Probabilistic loss of small events results in detected event amplitude distributions that appear biologically complete, yet do not reflect the underlying synaptic properties. With both simulated and experimental datasets, we demonstrate that specific changes in event amplitude are primarily detected as changes in frequency, compromising classical biological interpretations. To facilitate more robust data analysis and interpretation, we detail a means for experimental estimation of the event detection limit and provide practical recommendations for data analysis. Together, our study highlights how mini analysis is prone to falsely reporting synaptic changes, raising awareness of these considerations, and provides a framework for more robust data analysis and interpretation.}, author = {Greger, Ingo H. and Watson, Jake}, issn = {1469-7793}, journal = {Journal of Physiology}, number = {22}, pages = {7189--7205}, publisher = {Wiley}, title = {{‘Mini analysis’ misrepresents changes in synaptic properties due to incomplete event detection}}, doi = {10.1113/JP288183}, volume = {603}, year = {2025}, } @article{20477, abstract = {An electric double-layer capacitor (EDLC) stores energy by modulating the spatial distribution of ions in the electrolytic solution that it contains. We determine the mean-field timescales for planar EDLC relaxation to equilibrium after a potential difference is applied. We tackle first the fully symmetric case, where positive and negative ionic species have the same valence and diffusivity, and then the general, more complex, asymmetric case. Depending on the applied voltage and salt concentration, different regimes appear, revealing a remarkably rich phenomenology relevant for nanocapacitors.}, author = {Palaia, Ivan and Asta, Adelchi J. and Dutta, Megh and Warren, Patrick B. and Rotenberg, Benjamin and Trizac, Emmanuel}, issn = {1079-7114}, journal = {Physical Review Letters}, number = {14}, publisher = {American Physical Society}, title = {{Charging dynamics of electric double-layer nanocapacitors in mean field}}, doi = {10.1103/72b9-c8cq}, volume = {135}, year = {2025}, } @article{20478, abstract = {We consider the Wigner minor process, i.e. the eigenvalues of an N\times N Wigner matrix H^{(N)} together with the eigenvalues of all its n\times n minors, H^{(n)}, n\le N. The top eigenvalues of H^{(N)} and those of its immediate minor H^{(N-1)} are very strongly correlated, but this correlation becomes weaker for smaller minors H^{(N-k)} as k increases. For the GUE minor process the critical transition regime around k\sim N^{2/3} was analyzed by Forrester and Nagao (J. Stat. Mech.: Theory and Experiment, 2011) providing an explicit formula for the nontrivial joint correlation function. We prove that this formula is universal, i.e. it holds for the Wigner minor process. Moreover, we give a complete analysis of the sub- and supercritical regimes both for eigenvalues and for the corresponding eigenvector overlaps, thus we prove the decorrelation transition in full generality.}, author = {Bao, Zhigang and Cipolloni, Giorgio and Erdös, László and Henheik, Sven Joscha and Kolupaiev, Oleksii}, issn = {1432-2064}, journal = {Probability Theory and Related Fields}, publisher = {Springer Nature}, title = {{Decorrelation transition in the Wigner minor process}}, doi = {10.1007/s00440-025-01422-4}, year = {2025}, } @article{20479, abstract = {Genetic variation is generally regarded as a prerequisite for evolution. In principle, epigenetic information inherited independently of DNA sequence can also enable evolution, but whether this occurs in natural populations is unknown. Here we show that single-nucleotide and epigenetic gene body DNA methylation (gbM) polymorphisms explain comparable amounts of expression variance in Arabidopsis thaliana populations. We genetically demonstrate that gbM regulates transcription, and we identify and genetically validate many associations between gbM polymorphism and the variation of complex traits: fitness under heat and drought, flowering time and accumulation of diverse minerals. Epigenome-wide association studies pinpoint trait-relevant genes with greater precision than genetic association analyses, probably due to reduced linkage disequilibrium between gbM variants. Finally, we identify numerous associations between gbM epialleles and diverse environmental conditions in native habitats, suggesting that gbM facilitates adaptation. Overall, our results indicate that epigenetic methylation variation fundamentally shapes phenotypic diversity in a natural population.}, author = {Shahzad, Zaigham and Hollwey, Elizabeth and Moore, Jonathan D. and Choi, Jaemyung and Cassin-Ross, Gaëlle and Rouached, Hatem and Robinson, Matthew Richard and Zilberman, Daniel}, issn = {2055-0278}, journal = {Nature Plants}, pages = {2084--2099}, publisher = {Springer Nature}, title = {{Gene body methylation regulates gene expression and mediates phenotypic diversity in natural Arabidopsis populations}}, doi = {10.1038/s41477-025-02108-4}, volume = {11}, year = {2025}, } @article{20480, abstract = {Recent studies have argued that air temperatures over many mountain glaciers are decoupled from their surroundings, leading to a local cooling which could slow down melting. Here we use a compilation of on-glacier meteorological observations to assess the extent to which this relationship changes under warming. Statistical modelling of the potential temperature decoupling of the world’s mountain glaciers indicates that currently glacier boundary layers warm ~0.83 °C on average for every degree of ambient temperature rise. Future projections under shared socioeconomic pathway (SSP) climate scenarios SSP 2-4.5 and SSP 5-8.5 indicate that decoupling, and thus relative cooling over glaciers, is maximized during the 2020s and 2030s, before widespread glacier retreat acts to recouple above-glacier air temperatures with its surroundings. This nonlinear feedback will lead to an increased sensitivity to warming from midcentury, with glaciers losing their capacity to affect the local climate and cool themselves.}, author = {Shaw, Thomas and Miles, Evan S. and McCarthy, Michael and Buri, Pascal and Guyennon, Nicolas and Salerno, Franco and Carturan, Luca and Brock, Benjamin and Pellicciotti, Francesca}, issn = {1758-6798}, journal = {Nature Climate Change}, pages = {1212--1218}, publisher = {Springer Nature}, title = {{Mountain glaciers recouple to atmospheric warming over the twenty-first century}}, doi = {10.1038/s41558-025-02449-0}, volume = {15}, year = {2025}, } @article{20483, abstract = {A parallel plate capacitor containing an electrolytic solution is the simplest model of a supercapacitor or electric double-layer capacitor. Using both analytical and numerical techniques, we solve the Poisson-Nernst-Planck equations for such a system, describing the mean-field charging dynamics of the capacitor, when a constant potential difference is abruptly applied to its plates. Working at constant total number of ions, we focus on the physical processes involved in the relaxation and, whenever possible, give its functional shape and exact time constants. We first review and study the case of a symmetric binary electrolyte, where we assume the two ionic species to have the same charges and diffusivities. We then relax these assumptions and present results for a generic strong (i.e fully dissociated) binary electrolyte. At low electrolyte concentration, the relaxation is simple to understand, as the dynamics of positive and negative ions appear decoupled. At higher electrolyte concentration, we distinguish several regimes. In the linear regime (low voltages), relaxation is multiexponential, it starts by the buildup of the equilibrium charge profile and continues with neutral mass diffusion, and the relevant timescales feature both the average and the Nernst-Hartley diffusion coefficients. In the purely nonlinear regime (intermediate voltages), the initial relaxation is slowed down exponentially due to increased capacitance, while bulk effects become more and more evident. In the fully nonlinear regime (high voltages), the dynamics of charge and mass are completely entangled and, asymptotically, the relaxation is linear in time. We finally discuss nonideal behavior in real capacitors and provide conditions for which mean-field is expected to hold.}, author = {Palaia, Ivan and Asta, Adelchi J. and Dutta, Megh and Warren, Patrick B. and Rotenberg, Benjamin and Trizac, Emmanuel}, issn = {2470-0053}, journal = {Physical Review E}, number = {3}, publisher = {American Physical Society}, title = {{Poisson-Nernst-Planck charging dynamics of an electric double-layer capacitor: Symmetric and asymmetric binary electrolytes}}, doi = {10.1103/p4dg-snqf}, volume = {112}, year = {2025}, } @article{20491, abstract = {Global fibre production has expanded rapidly, with polyester and cotton dominating, significantly contributing to textile waste and increasing demand for sustainable solutions. This study presents innovative method to recycle polyester/cotton (PET/CO) blends using hydrophobic deep eutectic solvents (DESs), eliminating the need for toxic chemicals while achieving high dissolution yields. PET was completely dissolved within 5 min, substantially outperforming state-of-the-art methods and facilitating the efficient and selective recovery of both components, PET (97%) and CO (100%). SEM imaging confirmed no morphological changes in cotton fibres after treatment. The thermal stability of the recovered materials was validated using DSC and TGA analyses, while ATR-FTIR spectroscopy indicated no chemical changes. Mechanical testing confirmed recovered cotton’s tenacity and elongation are within expected ranges despite showing a decrease of 28% in tenacity and 34% in elongation. Hence, the proposed process provides an efficient and sustainable recycling solution for PET/CO blends, retaining both polymers in a condition similar to virgin materials used in textile manufacturing with minimal processing time.}, author = {Depope, Nika and Depope, Al and Archodoulaki, Vasiliki Maria and Ipsmiller, Wolfgang and Bartl, Andreas}, issn = {1879-2456}, journal = {Waste Management}, publisher = {Elsevier}, title = {{Deep eutectic solvent as a solution for polyester/cotton textile recycling}}, doi = {10.1016/j.wasman.2025.115177}, volume = {208}, year = {2025}, } @article{20493, abstract = {We propose a formation pathway linking black holes (BHs) observed in gravitational-wave (GW) mergers, wide BH–stellar systems uncovered by Gaia, and accreting low-mass X-ray binaries (LMXBs). In this scenario, a stellar-mass BH binary undergoes isolated binary evolution and merges while hosting a distant, dynamically unimportant tertiary stellar companion. The tertiary becomes relevant only after the merger, when the remnant BH receives a GW recoil kick. Depending on the kick velocity and system configuration, the outcome can be: (1) a bright electromagnetic (EM) counterpart to the GW merger; (2) an LMXB; (3) a wide BH–stellar companion system resembling the Gaia BH population; or (4) an unbound isolated BH. Modeling the three-body dynamics, we find that ∼0.02% of LIGO–Virgo–KAGRA (LVK) mergers may be followed by an EM counterpart within ∼10 days, produced by tidal disruption of the star by the BH. The flare is likely brightest in the optical–UV and lasts for days to weeks; in some cases, partial disruption causes recurring flares with a period of ∼2 months. We further estimate that this channel can produce ∼1%–10% of Gaia BH systems in the Milky Way. This scenario provides the first physically motivated link between GW sources, Gaia BHs, and some X-ray binaries, and predicts a rare but robust pathway for EM counterparts to binary BH mergers, potentially detectable in LVK’s O5 run.}, author = {Naoz, Smadar and Haiman, Zoltán and Quataert, Eliot and Holzknecht, Liz}, issn = {2041-8213}, journal = {The Astrophysical Journal Letters}, number = {1}, publisher = {IOP Publishing}, title = {{Triples as links between binary Black Hole mergers, their electromagnetic counterparts, and galactic Black Holes}}, doi = {10.3847/2041-8213/ae0a20}, volume = {992}, year = {2025}, } @article{20494, abstract = {The 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.}, author = {Marshall, Madeline A. and Yue, Minghao and Eilers, Anna Christina and Scholtz, Jan and Perna, Michele and Willott, Chris J. and Maiolino, Roberto and Übler, Hannah and Arribas, Santiago and Bunker, Andrew J. and Charlot, Stephane and Rodríguez Del Pino, Bruno and Böker, Torsten and Carniani, Stefano and Circosta, Chiara and Cresci, Giovanni and D'Eugenio, Francesco and Jones, Gareth C. and Venturi, Giacomo and Bordoloi, Rongmon and Kashino, Daichi and Mackenzie, Ruari and Matthee, Jorryt J and Naidu, Rohan and Simcoe, Robert A.}, issn = {1432-0746}, journal = {Astronomy & Astrophysics}, publisher = {EDP Sciences}, title = {{GA-NIFS and EIGER: A merging quasar host at z = 7 with an overmassive black hole}}, doi = {10.1051/0004-6361/202452650}, volume = {702}, year = {2025}, } @article{20495, abstract = {We consider a tracer particle coupled to a Bose scalar field and study the regime where the field’s propagation speed approaches infinity. For initial states devoid of field excitations, we introduce an effective approximation of the time-evolved wave function and prove its validity in Hilbert space norm. In this approximation, the field remains in the vacuum state, while the tracer particle propagates with a modified dispersion relation. Physically, the new dispersion relation can be understood as the effect of radiative corrections due to interactions with virtual bosons. Mathematically, it is defined as the solution of a self-consistent nonlinear equation, whose form depends on the relevant time scale.}, author = {Cárdenas, Esteban and Mitrouskas, David Johannes}, issn = {1424-0637}, journal = {Annales Henri Poincare}, publisher = {Springer Nature}, title = {{Radiative corrections to the dynamics of a tracer particle coupled to a Bose ccalar field}}, doi = {10.1007/s00023-025-01626-3}, year = {2025}, } @article{20496, abstract = {The 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.}, author = {Zeng, Guifang and Horta, Sharona and Sun, Qing and Khan, Malik Dilshad and Ibáñez, Maria and Han, Yuhang and Wang, Shang and Li, Longqiu and Ci, Lijie and Tian, Yanhong and Cabot, Andreu}, issn = {1521-4095}, journal = {Advanced Materials}, publisher = {Wiley}, title = {{Crystal growth engineering for dendrite-free Zinc metal plating}}, doi = {10.1002/adma.202510906}, year = {2025}, } @article{20503, abstract = {We introduce a class of interacting fermionic quantum models in d dimensions with nodal interactions that exhibit superdiffusive transport. We establish nonperturbatively that the nodal structure of the interactions gives rise to long-lived quasiparticle excitations that result in a diverging diffusion constant, even though the system is fully chaotic. Using a Boltzmann equation approach, we find that the charge mode acquires an anomalous dispersion relation at long wavelength ωðqÞ ∼ qz with dynamical exponent z ¼ min½ð2n þ dÞ=2n; 2, where n is the order of the nodal point in momentum space. We verify our predictions in one-dimensional systems using tensor-network techniques.}, author = {Wang, Yupeng and Ren, Jie and Gopalakrishnan, Sarang and Vasseur, Romain}, issn = {1079-7114}, journal = {Physical Review Letters}, number = {16}, publisher = {American Physical Society}, title = {{Superdiffusive transport in chaotic quantum systems with nodal interactions}}, doi = {10.1103/xx9z-4j6c}, volume = {135}, year = {2025}, } @article{20504, abstract = {Let r, k, be integers such that 0 ≤ ≤ (k/r). Given a large r-uniform hypergraph G, we consider the fraction of k-vertex subsets that span exactly edges. If is 0 or (k/r), this fraction can be exactly 1 (by taking G to be empty or complete), but for all other values of , one might suspect that this fraction is always significantly smaller than 1. In this paper we prove an essentially optimal result along these lines: if is not 0 or (k/r), then this fraction is at most (1/e) + ε, assuming k is sufficiently large in terms of r and ε > 0, and G is sufficiently large in terms of k. Previously, this was only known for a very limited range of values of r, k, (due to Kwan–Sudakov–Tran, Fox–Sauermann, and Martinsson–Mousset–Noever–Trujic). Our result answers a question of Alon–Hefetz–Krivelevich–Tyomkyn, who suggested this as a hypergraph generalization of their edge-statistics conjecture. We also prove a much stronger bound when is far from 0 and (k/r).}, author = {Jain, Vishesh and Kwan, Matthew Alan and Mubayi, Dhruv and Tran, Tuan}, issn = {1687-0247}, journal = {International Mathematics Research Notices}, number = {18}, publisher = {Oxford University Press}, title = {{The edge-statistics conjecture for hypergraphs}}, doi = {10.1093/imrn/rnaf273}, volume = {2025}, year = {2025}, } @misc{20523, abstract = {Includes all data and Python code needed to reproduce figures for the publication: No Time for Surface Charge: How Bulk Conductivity Hides Charge Patterns from Kelvin Probe Force Microscopy in Contact-Electrified Surfaces.}, author = {Pertl, Felix}, publisher = {Zenodo}, title = {{No Time for Surface Charge: How Bulk Conductivity Hides Charge Patterns from Kelvin Probe Force Microscopy in Contact-Electrified Surfaces}}, doi = {10.5281/ZENODO.14888054}, year = {2025}, } @article{20530, abstract = {Cells must coordinate DNA segregation with cytokinesis to ensure that each daughter cell inherits a complete genome. Here, we explore how DNA segregation and division are mechanistically coupled in archaeal relatives of eukaryotes, which lack Cyclin-dependent kinase (CDK)/Cyclins. Using live cell imaging, we first describe the series of sequential changes in DNA organization that accompany cell division in Sulfolobus, which computational modeling shows likely aid genome segregation. Through a perturbation analysis we identify a regulatory checkpoint which ensures that the compaction of the genome into two spatially segregated nucleoids only occurs once cells have assembled a division ring—which also defines the axis of DNA segregation. Finally, we show that DNA compaction and segregation depend, in part, on a ParA homologue, SegA, and its partner SegB, whose absence leads to bridging DNA. Taken together, these data show how regulatory checkpoints like those operating in eukaryotes aid high-fidelity division in an archaeon.}, author = {Parham, Joe and Sorichetti, Valerio and Cezanne, Alice and Foo, Sherman and Kuo, Yin Wei and Hoogenberg, Baukje and Radoux-Mergault, Arthur and Mawdesley, Eloise and Gatward, Lydia Daniels and Boulanger, Jerome and Schulze, Ulrike and Šarić, Anđela and Baum, Buzz}, issn = {1091-6490}, journal = {Proceedings of the National Academy of Sciences}, number = {42}, pages = {e2513939122}, publisher = {National Academy of Sciences}, title = {{Temporal and spatial coordination of DNA segregation and cell division in an archaeon}}, doi = {10.1073/pnas.2513939122}, volume = {122}, year = {2025}, } @article{20531, abstract = {Genetic drift is potentially an important component of selection for sex, as it is a source of statistical associations between alleles at selected loci. By increasing local drift, population structure may thus amplify the evolutionary advantage of sex. However, most previous models have focused either on haploid populations or on diploid populations without spatial structure. In this article, we use two- and three-locus analytical models and multilocus simulations to explore selection for sex in a diploid population structured according to the island model, in the presence of recurrent deleterious mutations. Our results show that selection generally favors an intermediate rate of sex that decreases as the direct cost of sex increases and increases moderately as the degree of population structure increases. Selection for sex is generated by multiple effects involving genetic associations within and between loci. When selection occurs at many loci, it is generally dominated by interference effects involving deleterious alleles at different loci, captured by our three-locus model. In our multilocus simulations, we observed an irreversible spread of asexual mutants under strong costs of sex, and when deleterious mutations are partially recessive. However, population structure may prevent this spread of asexual mutants when dispersal rates are sufficiently small.}, author = {Fouqueau, Louise and Roze, Denis}, issn = {1558-5646}, journal = {Evolution}, number = {10}, pages = {2167--2180}, publisher = {Oxford University Press}, title = {{Deleterious mutations and selection for sex in spatially structured, diploid populations}}, doi = {10.1093/evolut/qpaf143}, volume = {79}, year = {2025}, } @article{20532, abstract = {A unified mechanism directs synaptic vesicle release}, author = {Lichter, Katharina}, issn = {1095-9203}, journal = {Science}, number = {6770}, pages = {236--237}, publisher = {AAAS}, title = {{Kiss, shrink, run}}, doi = {10.1126/science.aec0091}, volume = {390}, year = {2025}, } @inproceedings{20533, abstract = {We give an introduction into differential privacy in the dynamic setting, called the continual observation setting.}, author = {Henzinger, Monika H and Safavi Hemami, Roodabeh}, booktitle = {33rd Annual European Symposium on Algorithms}, isbn = {9783959773959}, issn = {1868-8969}, location = {Warsaw, Poland}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Securing dynamic data: A primer on differentially private data structures}}, doi = {10.4230/LIPIcs.ESA.2025.2}, volume = {351}, year = {2025}, } @inproceedings{20534, abstract = {A non-trivial minimum cut (NMC) sparsifier is a multigraph Ĝ that preserves all non-trivial minimum cuts of a given undirected graph G. We introduce a flexible data structure for fully dynamic graphs that can efficiently provide an NMC sparsifier upon request at any point during the sequence of updates. We employ simple dynamic forest data structures to achieve a fast from-scratch construction of the sparsifier at query time. Based on the strength of the adversary and desired type of time bounds, the data structure comes with different guarantees. Specifically, let G be a fully dynamic simple graph with n vertices and minimum degree δ. Then our data structure supports an insertion/deletion of an edge to/from G in n^o(1) worst-case time. Furthermore, upon request, it can return w.h.p. an NMC sparsifier of G that has O(n/δ) vertices and O(n) edges, in Ô(n) time. The probabilistic guarantees hold against an adaptive adversary. Alternatively, the update and query times can be improved to Õ(1) and Õ(n) respectively, if amortized-time guarantees are sufficient, or if the adversary is oblivious. Throughout the paper, we use Õ to hide polylogarithmic factors and Ô to hide subpolynomial (i.e., n^o(1)) factors. We discuss two applications of our new data structure. First, it can be used to efficiently report a cactus representation of all minimum cuts of a fully dynamic simple graph. Building this cactus for the NMC sparsifier instead of the original graph allows for a construction time that is sublinear in the number of edges. Against an adaptive adversary, we can with high probability output the cactus representation in worst-case Ô(n) time. Second, our data structure allows us to efficiently compute the maximal k-edge-connected subgraphs of undirected simple graphs, by repeatedly applying a minimum cut algorithm on the NMC sparsifier. Specifically, we can compute with high probability the maximal k-edge-connected subgraphs of a simple graph with n vertices and m edges in Õ(m+n²/k) time. This improves the best known time bounds for k = Ω(n^{1/8}) and naturally extends to the case of fully dynamic graphs.}, author = {Henzinger, Monika H and Kosinas, Evangelos and Münk, Robin and Räcke, Harald}, booktitle = {33rd Annual European Symposium on Algorithms}, isbn = {9783959773959}, issn = {1868-8969}, location = {Warsaw, Poland}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Efficient contractions of dynamic graphs - with applications}}, doi = {10.4230/LIPIcs.ESA.2025.36}, volume = {351}, year = {2025}, } @inproceedings{20535, abstract = {Many differentially private and classical non-private graph algorithms rely crucially on determining whether some property of each vertex meets a threshold. For example, for the k-core decomposition problem, the classic peeling algorithm iteratively removes a vertex if its induced degree falls below a threshold. The sparse vector technique (SVT) is generally used to transform non-private threshold queries into private ones with only a small additive loss in accuracy. However, a naive application of SVT in the graph setting leads to an amplification of the error by a factor of n due to composition, as SVT is applied to every vertex. In this paper, we resolve this problem by formulating a novel generalized sparse vector technique which we call the Multidimensional AboveThreshold (MAT) Mechanism which generalizes SVT (applied to vectors with one dimension) to vectors with multiple dimensions. When applied to vectors with n dimensions, we solve a number of important graph problems with better bounds than previous work. Specifically, we apply our MAT mechanism to obtain a set of improved bounds for a variety of problems including k-core decomposition, densest subgraph, low out-degree ordering, and vertex coloring. We give a tight local edge differentially private (LEDP) algorithm for k-core decomposition that results in an approximation with O(ε^{-1} log n) additive error and no multiplicative error in O(n) rounds. We also give a new (2+η)-factor multiplicative, O(ε^{-1} log n) additive error algorithm in O(log² n) rounds for any constant η > 0. Both of these results are asymptotically tight against our new lower bound of Ω(log n) for any constant-factor approximation algorithm for k-core decomposition. Our new algorithms for k-core decomposition also directly lead to new algorithms for the related problems of densest subgraph and low out-degree ordering. Finally, we give novel LEDP differentially private defective coloring algorithms that use number of colors given in terms of the arboricity of the graph.}, author = {Dhulipala, Laxman and Henzinger, Monika H and Li, George Z. and Liu, Quanquan C. and Sricharan, A. R. and Zhu, Leqi}, booktitle = {33rd Annual European Symposium on Algorithms}, isbn = {9783959773959}, issn = {1868-8969}, location = {Warsaw, Poland}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism}}, doi = {10.4230/LIPIcs.ESA.2025.91}, volume = {351}, year = {2025}, }