Peer Revenue Past citations are no guarantee of future returns

Papers

Fresh from arXiv, typeset properly. Highlighted words trade on the market.

Mathematics

math Watch Mathematics (sign in to use)

Monday 11 May

Probability · Cross-listed from cs.LG

GRAFT-ATHENA: Self-Improving Agentic Teams for Autonomous Discovery and Evolutionary Numerical Algorithms

Language-model agents plan, execute, and evaluate scientific workflows. However, the problem–method relationships guiding their choices remain implicit, so plausible outputs can violate the assumptions of the scientific problem. We introduce Graph Reduction to Adaptive Factored Trees (GRAFT), which makes this problem-to-method map explicit as an expandable probabilistic structure of admissible problems, methods, and dependencies. Because this structure follows scientific semantics, knowledge from documentation, papers, and domain experts can be encoded, while factorization keeps the structure tractable. Semantic fingerprints of encoded problems measure their similarity, so expertise and experience guide related problems. GRAFT-guided workflows exceeded published expert baselines in physics-informed learning, recovered blood-rheology trends, predicted Apollo Command Module hypersonic loading within 1.8% of experiment, and established machine-checked error bounds for regularized brain-flow reconstruction and a spectral physics-informed architecture. The representation retains evaluated outcomes and incorporates new methods, allowing scientific knowledge and experience to accumulate.
Read the full abstract

Combinatorics

A coarse Menger's Theorem for planar and bounded genus graphs

Menger's Theorem is a fundamental result in graph theory. It states that if in a graph $G$ with distinguished sets of terminal vertices $S$ and $T$ there are no $k$ pairwise vertex-disjoint $S$-$T$ paths, then there is a set of less than $k$ vertices that intersects every $S$-$T$ path. In this work, we give a coarse variant of this result for planar and bounded genus graphs. Precisely, we prove that for every surface $\Sigma$ there is a function $f\colon \mathbb{N}\times \mathbb{N}\to \mathbb{N}$ such that for every pair of integers $d,k\in \mathbb{N}$ and a $\Sigma$-embeddable graph $G$ with distinguished sets of terminal vertices $S$ and $T$, if $G$ does not contain a family of $k$ $S$-$T$ paths that are pairwise at distance larger than $d$, then there is a set $X$ consisting of at most $f(d,k)$ vertices of $G$ such that every $S$-$T$ path is at distance at most $d$ from a vertex of $X$. This partially answers questions of Nguyen, Scott, and Seymour [arXiv:2508.14332], who proved that such a result cannot hold in general graphs. A key ingredient of our proof is a structure theorem from the developing ”colorful” graph minor theory, where the focus is on studying the structure in a graph relative to some fixed subsets of annotated vertices. In our case, these annotated vertices are $S$ and $T$.
Read the full abstract

Differential Geometry

Improvement of flatness in annuli

We present a short and flexible improvement-of-flatness argument adapted to the setting of exterior domains, where one is naturally led to work with annuli instead of balls. As a model application in the classical setting of minimal surfaces, we give an alternative proof of the end-structure and asymptotics for finite Morse index minimal hypersurfaces with Euclidean area growth in low dimensions. The method is largely PDE-based and general in its application. Suitable variants have been employed in Bernoulli and Allen–Cahn settings.
Read the full abstract

Probability

Empirical Convergence of Even-Order Gromov-Wasserstein Functionals

We study the sample complexity of empirical plug-in estimation for the powered even-order Gromov-Wasserstein functional between compactly supported probability measures on $\mathbb{R}^{d_x}$ and $\mathbb{R}^{d_y}$. For every fixed pair of integers $r,k\geq 1$, we prove that the two-sample empirical error is bounded at the rate $n^{-2/\max\{\min\{d_x,d_y\},4\}}$, up to a logarithmic factor in the critical case $\min\{d_x,d_y\}=4$. This extends the known quadratic Euclidean upper rate to the full powered even-order family. The proof uses a polynomial decomposition of the even-order GW functional, a generalized duality formula reducing the coupling-dependent term to a compact family of ordinary optimal transport problems, and entropy estimates for semiconcave dual potentials.
Read the full abstract

Commutative Algebra

Derived complete intersections and polynomial growth of Betti numbers over dg-algebras

A theorem of Gulliksen states that a local ring is a complete intersection if and only if the Betti numbers of its finitely generated modules grow polynomially. We prove a derived version of Gulliksen's Theorem. More precisely, we prove a structure theorem for dg-algebras whose modules exhibit polynomial Betti growth. As a key ingredient in the proof, we establish the existence and uniqueness of minimal models and acyclic closures of morphisms of dg-algebras in a broader setting than was previously known. We also extend to dg-algebras a theorem of Halperin on the vanishing of deviations of local rings, recovering Gulliksen's Theorem as an immediate consequence.
Read the full abstract

Number Theory

Two dimensional arithmetic progressions avoiding squares

We show that any proper symmetric two dimensional arithmetic progression contained in the interval $[-T,T]$ which avoids non-zero perfect squares has at most $O_\varepsilon(T^{20/27+\varepsilon})$ elements. This improves on a result of Croot, Lyall and Rice. We also discuss lower bounds for this problem and their connections to bounds for the least quadratic non-residue modulo a prime.
Read the full abstract

Number Theory

The 2-part of the Bloch-Kato conjecture, and indivisibility results, for $K_2$ of some elliptic curves

For certain integers $u$, we investigate the 2-part of the Bloch-Kato conjecture for $L(E_u,2)$, where $E_u: y^2=x(x+1)(x+u^2)$ is part of a (twisted) Legendre family that is 2-isogenous to a family studied by Boyd. For this, we first work out the corresponding 2-parts of the Tamagawa factors and Galois invariants. Then we give an explicit description of the 2-torsion in the Selmer group $H_f^1(\mathbb{Q},E_u[2^\infty](-1))$. We construct a specific element in the kernel of the tame symbol for $K_2$ on an integral model of $E_u$, with non-vanishing real and 2-adic regulators. Using techniques involving the norm residue isomorphism of Merkur'ev-Suslin, we prove indivisibility of this element by 2 in that kernel, even modulo torsion, even though it is explicitly divisible by 2 in the kernel of the tame symbol for $K_2$ on $E_u$. We also bound the 2-divisibility of the images of these elements under the 2-adic regulator map. Finally, in many cases we investigate numerically the validity of the 2-part of the Bloch-Kato conjecture.
Read the full abstract

All authors Neil Dummigan, Vasily Golyshev, Rob de Jeu, Matt Kerr

Probability · Cross-listed from stat.ML

Uniform Scaling Limits in AdamW-Trained Transformers

We study the large-depth limit of transformers trained with AdamW, by modelling the hidden-state dynamics as an interacting particle system (IPS) coupled through the attention mechanism. Under appropriate scaling of the attention heads, we prove that the joint dynamics of the hidden states and backpropagated variables converge in $L^2$, uniformly over the initial condition, to the solution of a forward–backward system of ODEs at rate $\mathcal O(L^{-1}+L^{-1/3}H^{-1/2})$. Here, $L$ and $H$ denote the depth and number of heads of the transformer, respectively. The limiting system of ODEs can be identified with a McKean–Vlasov ODE (MVODE) when the attention heads do not incorporate causal masking. By using the flow maps associated with this MVODE and applying concentration of measure techniques, we obtain bounds on the difference between the discrete and continuous models that are uniform over compact sets of initial conditions. As this is achieved without resorting to a covering argument, the constants in our bounds are independent of the number of tokens. Furthermore, under a suitable adaptation to AdamW, the bounds become independent of the token embedding dimension.
Read the full abstract

Combinatorics

The Poincaré Series of Coxeter Folding Subgroups

Folding subgroups give a way to realize non-simply-laced Coxeter groups as subgroups of simply-laced Coxeter groups. In this paper, we study how folding subgroups of finite and affine type are distributed length-wise by calculating the length generating function of the subgroup with respect the length of the ambient group. These generating functions have surprisingly nice formulas in terms of $q$-integers and give rise to interesting combinatorial identities on polynomials involving length statistics of both the ambient group and folding subgroup.
Read the full abstract

Combinatorics

Diagonal parity and loop toggling for symmetric matrices over $\mathbb F_2$

For a symmetric matrix $M$ over $\mathbb F_2$, it is known that its diagonal vector belongs to its column space. We prove the parity refinement that every solution of $Mx=\operatorname{diag}(M)$ satisfies $\operatorname{diag}(M)^Tx\equiv\operatorname{rank}(M)\pmod 2$. This extends the parity theorem for odd dominating sets to graph matrices with arbitrary binary diagonal labels. A self-contained rank-one update formula gives the changes caused by a single loop toggle and yields $\operatorname{nul} A(\overline G)=\operatorname{nul}(A(G)+I)+[\operatorname{rank}(A(G)+I)\text{ is odd}]$. For rooted trees, we augment Filmus's three classes of realizable boundary data with an explicit multiplicity recursion. The resulting formula computes the nullity of $A(T)+D_\varepsilon$ in a single traversal and gives a nonsingularity criterion. For complete rooted trees with eventually periodic labels indexed by height above the leaves, we obtain eventual periodicity of the boundary states and nullity formulas affine in powers of the branching degree on each eventual residue class. Constant labels give explicit closed forms.
Read the full abstract

Combinatorics

Paving matroids that are not sparse paving

The Mayhew–Newman–Welsh–Whittle conjecture predicts that asymptotically almost all matroids are sparse paving. We study the gap between paving and sparse paving matroids at the logarithmic scale. Let \(p_n\) be the number of paving matroids on \([n]\), let \(sp_n\) be the number of sparse paving matroids on \([n]\), and let \(sp_{n,r}\) be the number of rank-\(r\) sparse paving matroids on \([n]\). We prove that \[ p_n-sp_n\ge sp_{n,\lfloor n/2\rfloor}^{1-o(1)}. \] Thus the paving matroids that are not sparse paving are themselves logarithmically large. The construction prescribes one hyperplane larger than the rank and then counts stable sets in an induced subgraph of a Johnson graph. We also give amplified versions obtained by varying the large hyperplane and by prescribing distance-six families of large hyperplanes.
Read the full abstract

Combinatorics

A note on the $t$-partite link problem of Füredi

Motivated by the Erdős–Sós bipartite link conjecture, Füredi (Oberwolfach, 2004) asked for the asymptotic maximum edge density $\pi_{\mathrm{link}}(t)$ of $3$-graphs in which the link graph of every vertex is $t$-partite. Goldwasser's recursive blow-up construction based on projective planes gives the lower bound $\pi_{\mathrm{link}}(t)\ge 1-t^{-1}-(2+o_t(1))t^{-2}$ whenever $t-1$ is a prime power. In this note, we prove the upper bound $\pi_{\mathrm{link}}(t)\le 1-t^{-1}-t^{-2}/12$ for every $t \ge 2$. Together with Goldwasser's construction, this determines, up to a constant factor, the correct order of the gap between $\pi_{\mathrm{link}}(t)$ and the trivial averaging upper bound $1-t^{-1}$ for all prime-power values of $t-1$. In fact, our argument applies in the more general setting of $3$-graphs with no generalized daisies, equivalently, $3$-graphs in which the link graph of every vertex is $K_{t+1}$-free. We also establish an analogous upper bound for the positive $(r-1)$-codegree Turán density of generalized daisies.
Read the full abstract

All authors Jianfeng Hou, Xinmin Hou, Xizhi Liu, Jiasheng Zeng, Yixiao Zhang

Information Theory

Survey-Free Radio Map Construction via HMM-Based Coarse-to-Fine Inference

Traditional radio map construction methods mandate labor-intensive data collection and precise location labeling. To address these limitations, we propose a novel survey-free approach for radio map construction that relies solely on unlabeled Received Signal Strength (RSS) measurements, thereby obviating the need for manual site surveys or auxiliary Inertial Measurement Units (IMUs). The key idea involves embedding multiple unlabeled RSS sequences into a known indoor layout, specifically targeting corridor-guided environments with a dominant unidirectional pedestrian flow. However, aligning the embedded coordinates with the RSS collection locations remains challenging due to the random fluctuations inherent in RSS data. To tackle this, we introduce a Hidden Markov Model (HMM)- based Coarse-to-Fine Inference (HCFI) framework. At the coarse level, we employ an HMM-based region label inference algorithm to partition RSS sequences and align the RSS segments with specific physical regions using graph-based inference. At the fine level, we develop an HMM-based location label inference technique to estimate RSS collection coordinates by leveraging RSS propagation principles while incorporating sequential spatio-temporal mobility probability. Empirical results from an office environment demonstrate that the proposed method achieves a radio map construction Mean Absolute Error (MAE) of 8.96 dB. Furthermore, based on the estimated radio map, k-Nearest Neighbor (KNN) localization yields an average positioning error of approximately 3.33 meters, offering a highly viable, survey-free solution for radio map construction under sequential topological assumptions.
Read the full abstract

All authors Zheng Xing, Weibing Zhao, Guanghui Zhang, Guangjin Pan, Xuhui Zhang, Jinke Ren, Henk Wymeersch, Yuan Wu, Shuguang Cui

Information Theory

Annotation-Free Indoor Radio Mapping via Physics-Informed Trajectory Inference

Constructing indoor radio maps traditionally requires extensive site surveys with precise user-location labels, making the calibration process costly and time-consuming. Existing calibration-reduction methods either depend on partial location annotations or exploit inertial measurement units (IMUs) to provide relative motion cues; however, IMU-assisted solutions are constrained by hardware availability, device-level access restrictions, and accumulated sensor drift. In this paper, we study a location-label-free indoor radio mapping problem under known access-point deployment geometry and a known walkable spatial domain. We propose a physics-informed trajectory inference framework that uses only Channel State Information (CSI), without relying on user-location labels or IMU measurements. The key idea is to recover the latent spatial coordinates of CSI measurements by exploiting the local spatial continuity of multipath propagation. To this end, we construct a Power-Angle-Delay Profile (PADP) feature distance from MIMO-OFDM CSI and show that, within a local neighborhood and under quasi-static multipath conditions, this distance provides a physically meaningful proxy for small spatial displacements. We then incorporate the PADP-based continuity constraint into a spatially regularized Bayesian inference model for joint trajectory recovery and propagation-parameter estimation. Experiments on a real-world industrial CSI dataset demonstrate that the proposed framework achieves an average localization error of 0.88 m and a relative beam map construction error of 6.68%, improving upon representative channel-embedding and IMU-assisted baselines.
Read the full abstract

All authors Zheng Xing, Mengru Wu, Yi Zhang, Guanghui Zhang, Jun Gao, Weibing Zhao, Xuhui Zhang, Jinke Ren, Shuguang Cui

Information Theory · Cross-listed from quant-ph

A passive self-correcting quantum memory in three dimensions

We construct a 3D Pauli stabilizer Hamiltonian whose ground state space can encode a qubit for exponential time when coupled to a bath at non-zero temperature. Our construction recursively applies a sequence of transformations to a seed Hamiltonian that increases the memory lifetime of the encoded qubit while maintaining geometric locality in $\mathbb{R}^3$.
Read the full abstract

Metric Geometry

Dimension-free Gaussian tail estimates for linear functionals on convex bodies

Let $K \subset \mathbb{R}^n$ be a centered convex body of volume one. We prove that there exist absolute constants $c,C > 0$ and an orthonormal set of vectors $\Theta \subset S^{n-1}$ with size $\left|\Theta\right| \ge 9n/10$ such that, if $X$ is a random vector uniformly distributed on $K$, then for all $\theta \in \Theta$ one has \[ c\cdot \sqrt{p}\,\left(\mathbb{E} \left|\left\langle X,\theta \right\rangle\right|^2\right)^{1/2} \le \left(\mathbb{E} \left|\left\langle X,\theta \right\rangle\right|^p\right)^{1/p} \le C\cdot \sqrt{p}\,\left(\mathbb{E} \left|\left\langle X,\theta \right\rangle\right|^2\right)^{1/2}, \] where the upper estimate holds for all $p \ge 1$ while the lower bound only holds for $1 \le p \le n$.
Read the full abstract

Analysis of PDEs

Quantifying Concentration Phenomena of Mean-Field Transformers in the Low-Temperature Regime

Transformers with self-attention modules as their core components have become an integral architecture in modern large language and foundation models. In this paper, we study the evolution of tokens in deep encoder-only transformers at inference time which is described in the large-token limit by a mean-field continuity equation. Leveraging ideas from the convergence analysis of interacting multi-particle systems, with particles corresponding to tokens, we prove that the token distribution rapidly concentrates onto the push-forward of the initial distribution under a projection map induced by the key, query, and value matrices, and remains metastable for moderate times. Specifically, we show that the Wasserstein distance of the two distributions scales like $\sqrt{{\log(\beta+1)}/{\beta}}\exp(Ct)+\exp(-ct)$ in terms of the temperature parameter $\beta^{-1}\to 0$ and inference time $t\geq 0$. For the proof, we establish Lyapunov-type estimates for the zero-temperature equation, identify its limit as $t\to\infty$, and employ a stability estimate in Wasserstein space together with a quantitative Laplace principle to couple the two equations. Our result implies that for time scales of order $\log\beta$, which correspond to the early-phase behavior most relevant for practical finite-depth models, the token distribution concentrates at the identified limiting distribution. Numerical experiments confirm this and, beyond that, complement our theory by showing that for finite $\beta$ and large $t$ the dynamics enter a different terminal phase, dominated by the spectrum of the value matrix.
Read the full abstract

All authors Albert Alcalde, Leon Bungert, Konstantin Riedl, Tim Roith

Numerical Analysis

Efficient Admissible Set Projection in Optimization-based Invariant-Domain-Preserving Limiters for Ideal MHD

Preserving the admissible set of the ideal magnetohydrodynamics (MHD) equations is important not only for producing physically meaningful numerical solutions, but more importantly for achieving robust computations. In this paper, we develop an optimization-based limiter to enforce admissibility while preserving global conservation and accuracy. For an easy and efficient projection, we decompose the admissible set into slices parameterized by the magnetic energy, so that the MHD projection reduces to a one-dimensional minimization, which can be solved efficiently by the Brent method. The splitting method can be used to efficiently solve the global minimization problem of the optimization-based limiter, which can be used to enforce cell average admissibility in discontinuous Galerkin (DG) schemes, and pointwise admissibility can be further enforced by the Zhang-Shu positivity-preserving limiter. We apply the limiter to high-order DG schemes and present numerical results for a few representative MHD problems.
Read the full abstract

Combinatorics

Counting Spinal Tree-Child Networks via Word Encodings and Generating Functions

We study the enumeration of spinal tree-child phylogenetic networks, a rigid family of tree-child networks in which all internal vertices lie on a single root–to–leaf path. We provide two complementary combinatorial frameworks. First, we introduce a word model: unlabeled spinal networks correspond to a suitable class of restricted words with fixed multiplicities, taken modulo a simple relabeling equivalence, which yields an explicit closed enumeration. Second, we develop a symbolic-method approach based on a marked version of trees that admits a clean recursive specification; its boxed-product translation leads to a solvable bivariate generating function and a direct derivation of the coefficients.
Read the full abstract

All authors Pau Vives, Anna de Mier, Gabriel Cardona, Joan Carles Pons

Information Theory

Random Access Expectation in DNA Data Storage: Asymptotic Analysis Through Fountain Codes

The expected number of coded symbols drawn from a linear code until a desired information symbol can be decoded is studied. This quantity is of interest in DNA data storage, where it is called the random access expectation. If the generator matrix of the code is binary and fully symmetric, the process of sampling symbols from the code is equivalent to the encoder of an LT code. Based on this observation, the random access expectation of binary fully symmetric codes under a peeling decoder is analyzed in the large blocklength limit. Asymptotically, a random access expectation, normalized by the number of information symbols, of $0.7869$ is achievable, while for a binary fully symmetric code under a peeling decoder it cannot be below $\pi/4\approx 0.7854$. The analysis is extended to the case where a set of information symbols needs to be decoded.
Read the full abstract

Statistics Theory

A Generative High Quantile Homogeneity Test Using Bahadur Representation for Heteroskedastic High Quantile Regression of Tail Dependent Time Series

We consider a high quantile homogeneity test to determine whether a certain set of explanatory variables has homogeneous effects on different high quantiles of the response variable in the tail. To accommodate for situations under both the null and the alternative, the auxiliary process in this case may no longer be treated as stationary, and the problem requires a joint analysis of both homoscedastic and heteroskedastic high quantiles. For this, we develop a novel Bahadur representation result in the high quantile setting for a general class of tail dependent time series under potential heteroskedasticity, which can be of interest by its own. In particular, the Bahadur representation provides a foundation for reducing problems regarding nonlinear high quantile regression estimators to those regarding suitably constructed linear forms with an explicit error bound and can be transformative and useful in many statistical problems. We in the current article apply it to guide the development of a generative high quantile homogeneity test, which is then illustrated through applications to both synthetic and real data.
Read the full abstract

Probability

The stochastic block model has the overlap graph property for modularity

The overlap gap property (OGP) is a statement about the geometry of near-optimal solutions. Exhibiting OGP implies failure of a class of local algorithms; and has been observed to coincide with conjectured algorithmic limits in problems with statistical computational gap. We consider the Stochastic Block Model (SBM), where the graph has a planted partition with $k$ equal-size blocks which form the `communities', and where, for parameters $p>q$, vertices within the same community connect with probability $p$, while vertices in different communities connect with probability $q$, independently across pairs of vertices. Modularity–based clustering algorithms have become ubiquitous in applications. This article studies theoretical limits of local algorithms based on the modularity score on the SBM. We establish that modularity exhibits OGP on the SBM. This rules out a class of local algorithms based on modularity for recovery in the SBM, and shows slow mixing time for a related Markov Chain. Theoretically this is one of the few instances where OGP has been established for a `planted' model, as most such analyses to date consider the `null' model. As part of our analysis, we extend a result by Bickel and Chen 2009, who established that with high probability, the modularity optimal partition of SBM is $o(n)$ local moves away from the planted partition, where $n$ is the graph size. We show that, with high probability, any partition with modularity score sufficiently near the optimal value is close to the planted partition.
Read the full abstract

All authors Shankar Bhamidi, David Gamarnik, Remco van der Hofstad, Nelly Litvak, Pawel Pralat, Fiona Skerman, Yasmin Tousinejad

Probability

On Talagrand's Convexity Conjecture

We prove that any random vector in $\mathbb{R}^n$ which is dominated in convex order by a standard Gaussian vector can be written as the sum of three standard Gaussian vectors. This implies that any $1$-subgaussian random vector in $\mathbb{R}^n$ is the sum of a universal number of Gaussian vectors. It also solves M. Talagrand's convexity problem, which in turn implies a weak version of a combinatorial analogue to the problem.
Read the full abstract

2605.10908 · 11 May · 22 pages, no figures. Comments welcomed! Major changes in v2: Supplied second half of the if and only if in Proposition 3.6. New proof of the main theorem in Section 5 gives explicit constants. Connections with the existing literature in Appendix B expanded on in more detail

Quantum Algebra · Cross-listed from hep-th

Parafermionizing the Monster

We study the parafermionization of the Monster CFT with respect to its $\mathbb{Z}_{pA}$ subgroups, with $p$ an odd prime. Under certain assumptions, we show that the parafermionization is equal to a non-invertible gauging of $\mathcal{P}(p) \times \mathcal{P}(p)^\vee$, where $\mathcal{P}(p)$ is the theory of $\mathbb{Z}_p$-parafermions and $\mathcal{P}(p)^\vee$ is an appropriate dual theory, with global symmetry characterized by the centralizer of $\mathbb{Z}_{pA}$. By tracking the symmetries of $\mathcal{P}(p) \times \mathcal{P}(p)^\vee$ through the non-invertible gauging, we argue that the diagonal Monster CFT has $\mathrm{Rep}(\mathfrak{so}(3)_p) \boxtimes \mathrm{Rep}(\mathfrak{so}(3)_p)^\mathrm{op}$ symmetry, and hence that the holomorphic Monster theory has symmetry $\mathrm{Rep}(\mathfrak{so}(3)_p)$. We then compute the defect McKay-Thompson series associated to these symmetries, and prove that their invariance subgroups are $\Gamma_1(p+2)$.
Read the full abstract

Combinatorics

Chromatic thresholds for pairs of graphs

The chromatic threshold of a graph $H$ is the minimum-degree density above which every $H$-free graph has bounded chromatic number. We study a two-color Ramsey analogue: for graphs $H_1$ and $H_2$, we ask for the minimum-degree density above which every graph that admits a red-blue edge-coloring with no red copy of $H_1$ and no blue copy of $H_2$ has bounded chromatic number. We give a complete answer when both $H_1$ and $H_2$ are 3-chromatic. The threshold takes exactly one of the five values \[ \frac23,\quad \frac57,\quad \frac34,\quad \frac79,\quad \frac45, \] and we characterize precisely which pairs $(H_1,H_2)$ give each value. The classification is determined by the ordinary chromatic thresholds of $H_1$ and $H_2$ and by their embeddability into a hierarchy of $C_5$-type Ramsey configurations.
Read the full abstract

All authors Jun Gao, Hong Liu, Zhuo Wu, Yisai Xue

Probability

Scaling limits for nonlinear functionals of the discrete Gaussian free field with degenerate random conductances

We consider nonlinear functionals of discrete Gaussian free fields with ergodic random conductances on a class of random subgraphs of $\mathbb{Z}^{2}$, including i.i.d. supercritical percolation clusters, where the conductances are possibly unbounded but satisfy an integrability condition. As our main result, we show that, for almost every realisation of the environment, the nonlinear functionals of the rescaled field converge to their continuum counterparts in the Sobolev space $H^{-s}(D)$ for suitable $s > 0$. To obtain the latter, we establish pointwise bounds for the Green's function of the associated random walk among random conductances with Dirichlet boundary conditions, which are valid for all $d \geq 2$.
Read the full abstract

Geometric Topology

Hyperbolic space groups and edge conditions for their domains

Looking to the fundamental domains of space groups we can investigate in which space they can be realized. If this space is hyperbolic, then the corresponding space group is also hyperbolic. In addition to the usual methods for investigating space of realization, the symmetries of the fundamental polyhedron can give new restricted conditions, here called edge conditions. The aim of the research is to find out in which cases simplicial fundamental domains are hyperbolic with vertices out of the absolute. For this reason, edge conditions for simplicial fundamental domains belonging to Family F12 by the notation of E. Molnár et all in 2006, are considered.
Read the full abstract

Information Theory

Private Information Retrieval With Arbitrary Privacy Requirements for Graph-Based Storage

We reformulate the definition of privacy in the private information retrieval (PIR) problem to accommodate flexible privacy requirements. We focus on graph-replicated PIR, with a generalized privacy requirement, instead of requiring all messages to be private from all servers, during retrieval. Towards this, we define a privacy requirement set for each server, which can be an arbitrary subset of all message indices, as long as the stored message indices are in their privacy requirement set. Since both the storage and privacy requirement sets have many possibilities, we focus on two specific storage settings, namely the path and cyclic graphs. We consider several privacy settings for each of them, which are not necessarily the same, to give different examples for privacy sets. Of particular interest are the privacy sets that comprise the indices of messages stored at servers within a neighborhood range. The neighborhood range parameter allows a transition from the recently introduced local PIR [1] to the standard graph-replicated PIR. In these cases, we derive bounds on the capacity or find the exact capacity.
Read the full abstract

Information Theory · Cross-listed from cs.LG

Neural Weight Norm = Kolmogorov Complexity

Why does weight decay work? We prove that, in any fixed-precision regime, the smallest weight norm of a looped neural network outputting a binary string equals the Kolmogorov complexity of that string, up to a logarithmic factor. This implies that weight decay induces a prior matching Solomonoff's universal prior, the optimal prior over computable functions, up to a polynomial factor. The result is norm-agnostic: in fixed precision, every weight norm collapses to the non-zero parameter count up to constants, so the same sandwich bound holds for any norm used as a regulariser. The proof has two short reductions: any program for a universal Turing machine can be encoded into neural weights at unit cost per program bit, and any fixed-precision network can be described by enumerating its non-zero parameters with logarithmic addressing overhead. Both bounds are tight up to constants, with the logarithmic factor realised by permutation encodings: a network whose parameters encode a permutation produces a string whose Kolmogorov complexity is the non-zero parameter count times its logarithm. The fixed-precision assumption is essential: with infinite precision, neural networks can encode non-computable functions and the weight norm loses its relevance.
Read the full abstract

Information Theory

Local Private Information Retrieval: A New Privacy Perspective for Graph-Based Replicated Systems

We rethink the definition of privacy in multi-server, graph-replicated private information retrieval (PIR) systems, and introduce a novel setting where the user's privacy is governed by the servers' storage structure. In particular, while retrieving a message from a server, the user is concerned with hiding their desired message index from the server, only if the server stores the corresponding message. We coin this privacy requirement as local user privacy and the resulting PIR problem as local PIR on the graph. Our goal is to measure the gain in communication efficiency of local PIR, compared to that of canonical PIR, by establishing its capacity, i.e., the maximum number of message symbols retrieved, per downloaded symbol. To this end, we observe a remarkable gain in the local PIR capacity of graphs, that are disjoint union of distinct graphs, which is multiplicative, compared to the PIR capacity, when the individual graphs are identical. For connected graphs, we propose schemes to establish capacity lower bounds for edge-transitive and bipartite graphs, which are greater than the best-known PIR capacity bounds. Finally, we derive the exact local PIR capacity for the cyclic graph, and the path graph with an odd number of vertices.
Read the full abstract