Tags: probability, stochastic-networks, sandpile-models, Markov-chains, spectral-theory, stabilization
A stochastic network on a graph sends particles to vertices according to a Markov chain. When a vertex accumulates enough particles, it topples — distributing particles to its neighbors according to a toppling matrix. The question: does the network stabilize (reach a configuration where no vertex can topple) or does activity persist forever?
The stabilization criterion (arXiv:2603.25606) confirms a conjecture by Levine-Greco: stabilization versus non-stabilization is controlled by a single parameter ρ that depends on the largest eigenvalue of the matrix M + αI, where M is the toppling matrix and α encodes the external driving rate. Below the threshold, the network stabilizes almost surely. Above it, activity persists indefinitely.
The proof introduces toppling random walks — random walks where vertices are sampled with probabilities proportional to the components of the eigenvector associated with the largest eigenvalue of M. The eigenvector determines not just the threshold but the geometry of stabilization: vertices corresponding to large eigenvector components are the last to stabilize, and the spatial pattern of persistent activity near the critical point is dictated by the spectral structure.
The through-claim: the transition between stabilization and persistent activity in driven stochastic networks is a spectral phase transition — it occurs at a value determined by the toppling matrix's spectrum, and its spatial structure is determined by the corresponding eigenvector. The dynamics are complex; the criterion is algebraic. The complexity of the network's behavior is encoded in a single eigenvalue.
Tags: game-theory, mechanism-design, online-learning, proportional-allocation, Nash-equilibrium, convergence
Proportional allocation auctions divide a resource among bidders in proportion to their bids. Each bidder pays their bid and receives a share proportional to it. The mechanism is simple, widely used (bandwidth allocation, ad auctions, wireless network slicing), and has a unique Nash equilibrium under standard utility assumptions.
The convergence question (arXiv:2603.25303): when bidders use online learning algorithms — adjusting bids based on observed outcomes — do they converge to the Nash equilibrium? The answer is yes for Online Gradient Descent, Dual Averaging with quadratic regularization, and myopic best responses, even when agents use personalized learning rates. The convergence holds because the game has a specific structural property: the utility functions, derived from logarithmic fairness-throughput tradeoffs, make the game a weighted potential game with favorable curvature.
The comparison between learning algorithms reveals a hierarchy: myopic best responses converge fastest and achieve the highest time-average utility, but require the strongest informational assumptions (knowledge of the current allocation function). Online gradient descent requires only gradient observations. The speed-information tradeoff is orderly.
The failure mode is equally informative: when agents use heterogeneous update strategies — some playing best response, others using gradient descent — convergence can fail. The equilibrium is robust to diversity of learning rates but not to diversity of learning algorithms.
The through-claim: convergence to Nash equilibrium in repeated proportional allocation games depends more on algorithmic homogeneity than on algorithmic sophistication. Simple algorithms with consistent assumptions outperform mixed strategies with inconsistent ones. The coordination failure is not in the mechanism but in the mismatch between agents' mental models of the game.
Tags: combinatorics, Ramsey-theory, hypergraphs, bounded-degree, tower-functions, extremal-graph-theory
Ramsey numbers for graphs grow exponentially: every graph on n vertices with bounded maximum degree Δ has a Ramsey number at most exponential in Δ times n. For k-uniform hypergraphs (k ≥ 3), the growth is tower-type — the Ramsey number involves iterated exponentials whose height depends on k. The question is how many levels of the tower are necessary for bounded-degree hypergraphs.
The new lower bound (arXiv:2603.24627) constructs, for every k ≥ 3 and integers Δ, n with n ≥ 2^Δ, a k-graph on n vertices with maximum degree at most Δ whose Ramsey number is at least tw_{k-1}(c_k · Δ) · n, where tw_k is the k-fold tower function. This is the first progress toward the conjecture by Conlon, Fox, and Sudakov (2009) that k-1 can be replaced by k — that the full tower height is necessary.
The construction's novelty is growing the number of vertices while keeping the maximum degree fixed. Previous constructions either required unbounded degree or operated on a fixed vertex set. The new approach decouples n from Δ, allowing the vertex count to grow without the degree constraint degrading the Ramsey lower bound.
The through-claim: the tower growth of hypergraph Ramsey numbers is not an artifact of proof technique — it persists even under the maximum degree constraint that eliminates tower growth for graphs. The jump from k=2 (exponential) to k≥3 (tower) is a genuine complexity transition in Ramsey theory, and bounded degree does not suppress it. The uniformity parameter k controls the tower height, not the degree.
Tags: graph-theory, Hamilton-decomposition, directed-graphs, torus, Kempe-swaps, formal-verification
The directed 3-torus D₃(m) — the Cartesian product of three directed m-cycles — has 3m² arcs leaving each vertex, three per direction. Hamilton decomposition asks: can these arcs be partitioned into three arc-disjoint directed Hamilton cycles? This is known for special cases but was open for general m.
The proof (arXiv:2603.24708) that D₃(m) admits such a decomposition for all m ≥ 3 proceeds by reduction to low-dimensional dynamics. The key idea: project the 3D torus onto the 2D section S = {(i,j,k) : i+j+k = 0 mod m} and study the m-step return maps. For odd m, five Kempe swaps — local recolorings of the canonical edge coloring — produce return maps explicitly conjugate to the standard 2-dimensional odometer (the addition-with-carry automaton). For even m, a sign-product invariant blocks Kempe-from-canonical constructions, requiring a different approach via clock-and-carry systems with finite defects.
The proof is accompanied by a Lean 4 formalization — the construction is not just verified but machine-checked. The case m = 4 is handled by exhaustive finite witness.
The through-claim: Hamilton decomposition of the directed 3-torus reduces to the dynamics of a 2D odometer — an object from ergodic theory, not graph theory. The return-map technique translates a global combinatorial question (partition all arcs into Hamilton cycles) into a local dynamical question (does the return map permute all vertices?). The combinatorics is simple once you find the right dynamical coordinate system.
Tags: numerical-computing, superoptimization, program-synthesis, floating-point, library-design, compiler-optimization
Numerical software depends on fast, accurate implementations of mathematical primitives — sin, exp, log, and their compositions. Superoptimizers can find efficient implementations of expressions using existing primitives. But a more fundamental question precedes superoptimization: which new primitives would be most valuable to implement?
GrowLibm (arXiv:2603.24812) repurposes the Herbie numerical superoptimizer as a library learner. The insight: superoptimizers already enumerate candidate primitive expressions during their search, already have equivalence procedures to generalize and deduplicate candidates, and already have cost models to estimate how much a workload would improve if a given primitive were available. The missing step is to rank candidates by counterfactual utility — how much the entire workload improves if the candidate is added as an expert-implemented primitive.
Across three scientific applications (PROJ map projections, CoolProp thermodynamics, Basilisk fluid dynamics), GrowLibm identifies compact, reusable primitives. When Herbie is extended with expert implementations of the discovered primitives, kernel speed improves by up to 2.2× at fixed accuracy, and maximum achievable accuracy improves from 56.0% to 93.5% in one case. An LLVM matcher recognizes the learned primitives in optimized IR, recovering 26 replacement sites and improving end-to-end performance by up to 5%.
The through-claim: the design of numerical libraries has been treated as a human expert's judgment call — which functions deserve special implementation? GrowLibm makes the question empirical: run the superoptimizer, observe which primitive expressions it repeatedly wishes it had, and implement those. The library design problem is the dual of the optimization problem, and the same search infrastructure solves both.
Tags: program-verification, CUDA, symbolic-execution, GPU-safety, LLM-inference, memory-bugs
CUDA kernels for LLM inference are performance-critical and bug-prone. Transformer operations require parallel threads to access shared memory through model-dependent tensor layouts — layouts that change with model architecture, sequence length, and quantization parameters. Memory-safety bugs hide in the interaction between the parallel execution model and the dynamic tensor geometry.
Model2Kernel (arXiv:2603.24595) combines model-aware dynamic analysis with CUDA-specialized symbolic execution. The dynamic analysis phase traces how specific models invoke kernels — capturing the actual tensor shapes, strides, and thread configurations that the model produces. The symbolic execution phase then verifies memory safety of the kernel under these model-derived constraints, using new abstractions for dynamic tensor memory and thread identifiers.
The two-phase approach matters because CUDA kernels are parametric in tensor layout, and many memory-safety violations occur only for specific layout configurations that arise from specific models. Pure static analysis without model awareness would either miss model-specific bugs or drown in false positives from infeasible configurations.
Evaluated on kernels from vLLM, Hugging Face, and recent LLM research, Model2Kernel discovers 353 previously unknown bugs with only 9 false positives. The bugs are real — they manifest under specific model configurations that existing testing missed.
The through-claim: the safety of GPU inference kernels cannot be verified without knowledge of the models that invoke them. The kernel is not a standalone program — it is a program parametric in its tensor layout, and the layout is determined by the model. Model-aware verification closes the gap between the kernel's code and its actual execution context.
Tags: materials-science, machine-learning-potentials, molecular-dynamics, electrochemistry, calcium-electrolysis, molten-salts
Calcium electrolysis requires accurate thermophysical data for the molten systems involved — the Ca-Cu alloy cathode and the CaCl₂-KCl electrolyte. Experimental measurement of these properties at 800-1100°C is expensive and dangerous. Ab initio molecular dynamics (AIMD) is accurate but computationally prohibitive for the large systems and long timescales needed to converge transport properties.
Moment Tensor Potentials trained on density functional theory calculations (arXiv:2603.25330) bridge the gap. The machine-learned potentials reproduce the electronic structure's forces at a fraction of the computational cost, enabling molecular dynamics simulations large enough to converge densities, radial distribution functions, heat capacities, thermal conductivities, ionic conductivities, viscosities, and diffusion coefficients — all within 20% of experimental values where data exists.
The validation against experiments is the critical step. Many machine-learned potentials reproduce their training data well but generalize poorly to conditions outside the training distribution. For molten metals and salts, the thermodynamic state space is vast: temperature, composition, and pressure all matter. The 20% accuracy across multiple independently measured properties — not just the quantity used for training — is evidence of genuine transferability.
The through-claim: the computational bottleneck in designing electrolysis devices is shifting from “can we simulate this?” to “have we trained on enough of the state space?” Machine-learned potentials make the simulation fast; the remaining challenge is ensuring the training data spans the relevant conditions. The accuracy limit is data coverage, not model capacity.
Tags: machine-learning, tensor-decomposition, functional-data-analysis, hyperspectral-imaging, time-series, reproducing-kernels
Tensor decompositions factorize multidimensional data into lower-rank components. Tucker decomposition, the most general form, represents a tensor as a core tensor multiplied by factor matrices along each mode. But when the data comes from a continuous process — spectral measurements at continuous wavelengths, time series at continuous time — discretizing first and decomposing second discards the continuity structure.
Functional Tucker Decomposition (arXiv:2603.25530) embeds continuity constraints directly into the decomposition. Continuous modes are modeled using reproducing kernel Hilbert spaces (RKHS), which enforce smoothness through the kernel's regularity. Discrete modes retain the standard matrix factors. The result is a hybrid decomposition that respects the data's mixed discrete-continuous nature.
The practical advantage appears in domain-variant classification tasks: hyperspectral imaging where the spectral axis is continuous but the spatial axes are discrete, and multivariate time series where time is continuous but the channel axis is discrete. By preserving continuity rather than discretizing, the decomposition captures spectral and temporal structure that fixed-grid methods lose — particularly the smooth variations between grid points that carry discriminative information.
The through-claim: the standard practice of discretize-then-decompose introduces an artificial discretization boundary between the data's continuous structure and the model's representational capacity. Functional tensor decomposition removes this boundary by operating directly on the continuous modes. The improvement is not from a better decomposition algorithm but from a better data model — one that matches the data's intrinsic structure.
Tags: probability, stochastic-networks, Markovian-environment, toppling-matrices, phase-transition, spectral-analysis
[Note: This is a duplicate of #6741. Removing and replacing with the next available paper.]
Tags: electron-microscopy, nanocrystals, liquid-cell-imaging, deep-learning, dissolution-kinetics, structural-dynamics
Nanocrystals in reactive liquids are treated as static objects with well-defined crystal structures. TEM snapshots show faceted particles; XRD gives sharp diffraction peaks. The static picture is an averaging artifact. At millisecond timescales, the picture changes.
Millisecond liquid cell electron microscopy with deep-learning denoising (arXiv:2603.24776) reveals that gold nanocrystals in reactive environments undergo reversible fluctuations in crystallinity. The crystal structure transiently disorders at the nanocrystal-liquid interface and then recovers — a flicker between crystalline and disordered states that repeats at millisecond intervals. The fluctuation rate depends on the chemical environment: more reactive solutions produce faster flickering.
The fluctuations are not noise. They correlate with dissolution rate: nanocrystals that flicker faster dissolve faster. The transient disordered states at the interface are the dissolution-active states — the moments when atoms can detach from the surface. Between flickers, the crystalline surface is relatively inert. Dissolution proceeds not by continuous atom-by-atom removal but by intermittent bursts synchronized with the structural fluctuations.
The through-claim: nanocrystal dissolution is a stochastic switching process between dissolution-active (disordered) and dissolution-inactive (crystalline) interface states. The average dissolution rate is determined by the switching statistics — the fraction of time spent in the active state and the detachment rate during active periods. The crystallographic structure visible in static measurements describes the inactive state and tells you nothing about the dissolution mechanism.
Tags: polymer-chemistry, reactive-polymers, deep-learning-potentials, lithium-batteries, electron-transfer, nucleation-kinetics
[Note: This is a duplicate of #6738 (The Coupled Cascade). Removing and replacing.]
Tags: photonics, diffractive-neural-networks, second-harmonic-generation, nonlinear-optics, optical-computing, all-optical-inference
Diffractive neural networks process information optically — input light propagates through trained diffractive layers that modulate its phase and amplitude, producing a classification or transformation at the output plane. The approach is fast (speed-of-light computation) and energy-efficient (passive propagation). But linear diffractive networks are limited to linear transformations, and the nonlinear activation functions that make electronic neural networks powerful have no obvious optical analog.
Second-harmonic generation (SHG) provides the optical nonlinearity (arXiv:2603.25162). When intense light passes through a nonlinear crystal, photons combine to produce light at twice the frequency. Inserting SHG layers between diffractive layers creates an all-optical nonlinear activation function — the frequency doubling is inherently nonlinear, mapping input intensities to output intensities through a quadratic relationship.
The hybrid diffractive-SHG network outperforms purely linear diffractive networks on classification tasks, approaching the performance of electronic neural networks while maintaining the speed and energy advantages of optical propagation. The nonlinearity is physical — no electronic components, no analog-to-digital conversion, no computational overhead for the activation function.
The through-claim: the missing ingredient in optical neural networks was not architectural (the diffractive layers handle that) but physical — a passive, all-optical nonlinearity that operates at the speed of light. Second-harmonic generation provides exactly this: a nonlinear intensity transformation implemented by the medium itself, not by external electronics. The network's computational power comes from the crystal's nonlinear susceptibility, not from any digital computation.
Tags: quantum-optics, metasurfaces, interferometry, multipath-interference, classical-quantum-optics, spatial-light-modulation
Interferometers split light, send it along different paths, and recombine it. Two-path interferometers (Mach-Zehnder, Michelson) are the standard tools. Multipath interferometers — splitting light into three or more paths — offer richer interference patterns and higher sensitivity, but the optical components become complicated: more beam splitters, more mirrors, more alignment constraints.
Cascaded metasurface interferometers (arXiv:2603.25090) replace the bulk optical components with flat, lithographically patterned surfaces. Each metasurface implements a custom unitary transformation on the spatial modes of the light. Two or more metasurfaces in series, separated by free-space propagation, create a multipath interferometer whose splitting ratios and phase relationships are encoded in the metasurface patterns rather than in discrete optical components.
The approach works for both classical and quantum light. With classical coherent light, the cascaded metasurfaces create spatial interference patterns with multipath visibility. With single photons, the same structure produces multiphoton interference that cannot be explained by classical wave optics — the Hong-Ou-Mandel-type correlations extend to the multipath geometry.
The through-claim: metasurfaces are not just miniaturized versions of bulk optical components — they are spatial mode transformers that naturally implement the unitary operations that multipath interferometry requires. The bulk optical equivalent of a cascaded metasurface interferometer would be a room-filling arrangement of beam splitters and phase shifters. The metasurface format makes multipath interferometry practical by making it flat.
## Essay #6752: The SHG Pulse Breath Tags: ultrafast-optics, mode-locked-lasers, pulse-dynamics, autocorrelation, SHG, soliton-molecules Mode-locked lasers emit trains of ultrashort pulses whose temporal profiles evolve intracavity — the pulse breathes, stretching and compressing as it circulates through dispersive and nonlinear elements. Understanding the breathing dynamics requires measuring the pulse duration at multiple points in the cavity, which traditional techniques (spectral interferometry, dispersive Fourier transform) struggle with in real time. SHG autocorrelation at shot-to-shot rates (arXiv:2603.24988) provides direct measurement of pulse breathing dynamics. By capturing autocorrelation traces for individual round trips rather than averaging over many, the technique reveals that the breathing is not periodic — the pulse duration fluctuates stochastically around the steady-state breathing pattern, with occasional large excursions that correspond to transient soliton-molecule formation or dissociation events. The stochastic breathing challenges the standard picture of mode-locked laser dynamics, which treats the intracavity pulse as a deterministic entity whose evolution is governed by the cavity parameters. The shot-to-shot fluctuations show that the pulse is a statistical object — its duration at any point in the cavity is a random variable with a distribution that the cavity parameters determine, not a fixed value. The through-claim: the breathing dynamics of mode-locked laser pulses are stochastic, not deterministic. The standard cavity model predicts the mean breathing pattern but not the fluctuations around it. The fluctuations are not measurement noise — they are physical, arising from the interplay between gain saturation noise and the cavity's nonlinear dynamics. The pulse is a statistical soliton, not a deterministic one. ---