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)

Sunday 10 May

Logic

On skew ultralimits and their applications in ultrafilter theory

We define a special version of the ultralimit, called the skewed ultralimit. Using this tool, we show that the set of ultrafilter types in the $C$-equivalence class of a Ramsey ultrafilter $\mathfrak u\in \beta\omega$ with the Rudin-Keisler order is isomorphic to the ultrapower of $(\omega, \leq)$.
Read the full abstract

Probability

A dyadic construction of a three-dimensional attractive point interaction Markov family

We discuss a probabilistic approximation framework for the three-dimensional attractive point interaction on a finite time horizon. By iterating the Doob transforms of the explicit heat kernel associated with the singular Schrödinger operator formally given by \[ \frac12\Delta \,+\, \frac{\beta}{2}\, \delta_0(\cdot), \qquad \beta>0, \] we obtain sub-probability kernels along finite partitions on the punctured domain \[ E_\varepsilon=\{x\in\mathbb R^3:\ |x|>\varepsilon\}, \] which yield a limiting sub-probability kernel via refinement along global dyadic partitions, and we extend this limit to a transition probability kernel on an enlarged space obtained by adjoining a cemetery state. These kernels determine a time-inhomogeneous Markov process on the set of dyadic times, and its step-function interpolations yield càdlàg processes with consistent finite-dimensional distributions and partial tightness properties. The present work may also be viewed as an alternative direct probabilistic approximation scheme for the three-dimensional zero-range homopolymer measure constructed in the work of Cranston, Koralov, Molchanov, and Vainberg, which is constructed as a weak limit of Gibbs measures associated with regularized Schrödinger operators.
Read the full abstract

Numerical Analysis

Neural enrichment finite element method: A hybrid framework for problems with strong oscillations or interface problems

We propose a hybrid method, the Neural Enrichment Finite Element Method (NEFEM), designed for problems involving strong oscillations or interface problems with weak discontinuities. This method is based on the stable generalized finite element method (SGFEM) framework, wherein neural networks (NNs) are introduced as enrichment functions for adaptivity, and the Ritz functional is applied for the training process. This works makes two main contributions. First, the method constructs local subspaces with superior approximation properties, significantly reducing the required number of degrees of freedom (DoFs). Second, minimal a priori knowledge is required to define enrichment functions, as the NNs evolve heuristically during training. Furthermore, for smooth problems, we provide a residual-based error estimator and prove both its reliability and efficiency. For interface problems, a theoretical analysis on the optimal convergence of the SGFEM is studied, notably without imposing additional regularity assumptions. These analytic results guide the network architecture design and training strategies. The performance and effectiveness of the proposed method is validated through several numerical experiments.
Read the full abstract

Combinatorics

Rook theory, normal ordering in the $q$-deformed Ore algebra and the polynomial generalization

For words in the variables $X$ and $Y$ satisfying the commutation relation of the $q$-deformed generalized Ore algebra, $XY-qYX= \mu I + \nu Y$, we show that the corresponding normal ordering coefficients can be given an interpretation in terms of mixed placements of rooks and files. In particular, the associated $q$-deformed Ore-Stirling and Ore-Lah numbers are treated in detail. We show that the $q$-deformed Ore-Stirling numbers (resp., $q$-deformed Ore-Lah numbers) are given as mixed placement numbers of rooks and files on the staircase board (resp., Laguerre board). Using this combinatorial interpretation, their recurrence relations are derived. In addition, the normal ordered form of the binomial $(X+Y)^m$ in the $q$-deformed generalized Ore algebra is determined. These considerations are then extended to the $q$-deformed polynomial Weyl algebra generated by $X$ and $Y$ satisfying $XY-qYX=f(Y)$ for some polynomial $f\in \mathbb{C}[Y]$. In particular, associated $q$-deformed polynomial Stirling and Lah numbers are introduced and their properties studied. The normal ordered form of the binomial is also extended to the $q$-deformed polynomial Weyl algebra.
Read the full abstract

Numerical Analysis

On Enhancing the Dissipative Behavior of Active Flux Advection Schemes

In this work, the traditional third-order Active Flux advection scheme is modified by reformulating the method and introducing four additional parameters R, S, T, and U that allow the numerical dissipation and dispersion of the scheme to be adjusted. The influence of these parameters is studied using Fourier analysis and parameter choices that lead to schemes with improved dissipative properties are identified. These improvements are validated by numerical experiments.
Read the full abstract

General Topology · Cross-listed from cs.FL

Asymptotic Hausdorff and Language Similarity

We introduce the Asymptotic Hausdorff lifting, denoted $\mathbb{AH}_{d}$, a general method for lifting an element-level metric $d$ to a (pseudo-) metric on sets, that captures asymptotic similarity in infinite domains equipped with a notion of size. The construction is designed to be insensitive to finite deviations and to avoid the limitations of classical Hausdorff-based approaches, which are often overly sensitive to outliers and fail to reflect asymptotic behavior. Formal languages provide a central motivating instance of this framework, where elements are words and sets are languages. When applied to normalized edit distances, the Asymptotic Hausdorff lifting yields metric-valued distances between languages that reflect asymptotic edit behavior while preserving metric structure. We study the equivalence classes of regular languages induced by $\mathbb{AH}_{d}$ for normalized edit distances $d$, and characterize their asymptotic essence. Focusing in particular on the normalized edit distance of Marzal and Vidal, $\textsf{ned}$, we investigate the computation of $\mathbb{AH}_{\textsf{ned}}$ for regular languages and for bounded context-free languages.
Read the full abstract

Differential Geometry

Expanders for Mean Curvature Flow and Counterexamples to Ilmanen's Genus-Reduction Conjecture

We construct new expanders for mean curvature flow that are smoothly asymptotic to cones arising from certain shrinkers. For each such cone, we prove the existence of expanders of arbitrarily large genus. Thus, for a fixed incoming shrinker, the genus of the outgoing expander can be chosen much larger than the genus before the singularity, contrary to Ilmanen's genus-reduction conjecture.
Read the full abstract

Information Theory

Geometry of Rényi Entropy on the Majorization Lattice

Majorization is a stochastic ordering relation that compares the relative diversity of probability distributions with numerous applications in econometrics, spectral theory, and ecology. It is well-known that the majorization partial order forms a complete lattice on the set of ordered probability distributions. In this work, we study the properties of Rényi entropy on the majorization lattice. We establish a fundamental relation between the comonotone coupling and the independent coupling associated with a collection of marginal distributions. Consequently, we show that, for every order $\alpha \in [0,\infty]$, the Rényi entropy is subadditive on the majorization lattice. We further characterize the supermodular regime, showing that Rényi entropy is supermodular on the majorization lattice for $\alpha \in \{0\} \,\cup \, [1,\infty]$. For the Tsallis entropy, we show that it also satisfies subadditivity on the majorization lattice, for every order $\alpha \in [0,\infty)$. Finally, we show that, unlike the Rényi entropy, the Tsallis entropy is supermodular on the majorization lattice for every $\alpha \in [0,\infty)$.
Read the full abstract

Numerical Analysis

Kernel Learning of PDE Solution Operators

A kernel-based approach for the learning of the solution operator of general nonhomogeneous partial differential equations (PDEs) is proposed. The method incorporates physical priors, typically encoded through the PDE operator, into a kernel ridge regression framework, and employs a regularization-based formulation to construct an operator learner. This yields a closed-form estimator that is independent of the input functions that determine the underlying PDE. From the perspective of regularization theory, the resulting estimator induces a well-defined operator that links input and output spaces, which contain the functions that define a Dirichlet problem and its solution, respectively. Consequently, it effectively shifts from a PDE solver to an operator-based solver. In contrast to standard supervised learning methods, it does not rely on paired input–output training data and enables systematic extrapolation beyond observed regimes. A full error analysis is conducted, providing convergence rates for the operator-based solver under suitable choices of regularization parameters. Extensive numerical experiments, including Darcy flow and Helmholtz equations, demonstrate that the proposed method achieves high accuracy and efficiency across a range of problem settings, and compares favorably with operator learning approaches in both approximation quality and computational cost.
Read the full abstract

Probability

The Ballot Event for Two-Player Coupon Collection: A Renewal–Catalan Asymptotic

We study the two-player coupon-collector competition in which two independent collectors draw one coupon each per round from a set of $d$ equally likely coupon types. Myers and Wilf gave finite formulae for several two-player events and explicitly left open the ballot-type problem of finding the probability that the ultimate winner was never behind. We prove that this probability satisfies $$ b_d \sim \frac{2}{d}, \qquad d\to\infty .$$ The proof uses a renewal decomposition at the tie boundary. The first one-sided tie-break has an explicit entrance distribution; its level, scaled by $d^{1/2}$, converges to a Rayleigh law; and, after the break, the leader's survival probability is governed by a Catalan, or gambler's-ruin, harmonic. The main estimate shows that the accumulated defect of this comparison harmonic in the exact simultaneous-round chain is negligible.
Read the full abstract

Algebraic Geometry

Plane rectifiable curves: old and new

In this note we recall the classical notion of an algebraically rectifiable plane curve going back to J. A. Serret, E. Laguerre and G. Humbert. We provide new criteria of algebraic rectifiability, relate this notion to quadratic differentials, and generalize it to differentials of higher order.
Read the full abstract

Combinatorics

Symmetric Sudoku-Type Games from Perfect Codes

This paper presents a novel construction method for symmetric Sudoku-type games based on Lee distance perfect codes and diameter perfect codes. The proposed method utilizes the tiling property of these codes to define the structure of the subgrid constraints of Sudoku-type games. In this way, our games inherit the symmetric properties of Sudoku. We provide a detailed analysis of two small cases: a $5 \times 5$ Sudoku in $\mathbb{Z}_5^2$, and an $8 \times 8$ Sudoku in $\mathbb{Z}_8^2$. By defining equivalence relations via rigid motions, we provide a complete enumeration of valid grids, identifying 17 inequivalent solutions for $5\times 5$ Sudoku. For two different types of $8\times 8$ Sudoku, we characterize 232,735 and 304,014 inequivalent solutions, respectively. Furthermore, to verify practical playability, we implement a human-like solver that assesses the difficulty of the generated games. The analysis confirms that our $5\times5$ Sudoku games offer a balanced distribution of difficulty levels, ranging from Easy to Hard, making them a viable alternative to traditional $9 \times 9$ Sudoku.
Read the full abstract

All authors Junmin An, Jae-Hyun Baek, Keon-Hwi Kim, Haeun Lim, Jon-Lark Kim

Numerical Analysis

Discrete positivity and maximum principles for a finite element discretization of the Richards equation

Standard finite element discretizations of the Richards equation may violate the discrete minimum principle, producing unphysical negative saturations. While existing bound-preserving methods typically rely on computationally expensive fully implicit solvers, we propose a novel semi-implicit finite element framework utilizing a bounded continuous auxiliary variable. Our approach treats the gravity-driven advective term using a linearly implicit technique, which improves the time-step restrictions required by explicit gravity methods near the degenerate limit. We provide rigorous mathematical proofs establishing sufficient geometric and algebraic constraints for discrete positivity and the discrete maximum principle, specifically a local Péclet condition and a discrete row-sum condition. When both conditions are satisfied on weakly acute meshes with mass lumping, our framework ensures that numerical solutions strictly respect physical bounds across highly degenerate conditions and initially dry soil regimes. Comprehensive numerical validation demonstrates the method across multiple flow regimes, including cases where algebraic conditions are satisfied, violated, and recovered through mesh refinement.
Read the full abstract

Algebraic Geometry · Cross-listed from cs.LG

Minimal Filling Architectures for Polynomial Neural Networks

Minimal filling architectures describe the smallest hidden-layer widths for which the neurovariety of a polynomial neural network fills its ambient function space. It was conjectured that every such architecture has unimodal hidden widths. We construct counterexamples to this conjecture using a frontier search and certify the main example through finite-field Jacobian computations and recursive dimension bounds. In the opposite direction, we prove that every minimal filling architecture of depth at most three is unimodal. A nonunimodal minimal filling architecture of depth four shows that the depth bound is sharp.
Read the full abstract

Information Theory · Cross-listed from cs.LG

Geometry Conflict: Explaining and Controlling Forgetting in LLM Continual Post-Training

Continual post-training aims to extend large language models (LLMs) with new knowledge, skills, and behaviors, yet it remains unclear when sequential updates enable capability transfer and when they cause catastrophic forgetting. Existing methods mitigate forgetting through sequential fine-tuning, replay, regularization, or model merging, but offer limited criteria for determining when incorporating new updates is beneficial or harmful. In this work, we study LLM continual post-training through three questions: What drives forgetting? When do sequentially acquired capabilities transfer or interfere? How can compatibility be used to control update integration? We address these questions through task geometry: we represent each post-training task by its parameter update and study the covariance geometry induced by the update. Our central finding is that: forgetting can be considered as a state-relative update-integration failure, it arises when the covariance geometries induced by tasks misalign with the geometry of the evolving model state. Sequential updates transfer when they remain compatible with the model state shaped by previous updates, and interfere when state-relative geometry conflict becomes high. Motivated by this finding, we propose Geometry-Conflict Wasserstein Merging (GCWM), a data-free update-integration method that constructs a shared Wasserstein metric via Gaussian Wasserstein barycenters and uses geometry conflict to gate geometry-aware correction. Across Qwen3 0.6B–14B on domain-continual and capability-continual settings, GCWM consistently outperforms data-free baselines, improving retention and final performance without replay data. These results identify geometry conflict as both an explanatory signal for forgetting and a practical control signal for LLM continual post-training.
Read the full abstract

All authors Yuanyi Wang, Yifan Yang, Su Lu, Yanggan Gu, Pengkai Wang, Wenjun Wang, Zhaoyi Yan, Congkai Xie, Jianmin Wu, Jialun Cao, Shing-Chi Cheung, Hongxia Yang

Number Theory

An analogue of a formula of Popov II

Let $r_{k}(n)$ denote the number of representations of the positive integer $n$ as the sum of $k$ squares. We prove a generalization of a summation formula already proved by us [Advances in Applied Mathematics, 175 (2026) 103201], which involves the arithmetical function $r_{k}(n)$ and the Bessel functions of the first kind. We extend the Bessel functions in the aforementioned formula to Whittaker functions, and our proof of this generalization is drastically different from the proof of the particular case presented in [Advances in Applied Mathematics, 175 (2026) 103201].
Read the full abstract

Mathematical Physics

Cocycle Actions on Hidden Quantum Markov Models: Symmetry Protection and Topological Order

We develop a symmetry action framework for hidden quantum Markov models (HQMMs) tailored to one-dimensional quantum spin systems and symmetry-protected topological (SPT) phases. In our setting, a symmetry group $G$ acts projectively on the hidden (virtual) degrees of freedom and linearly on the physical observation space, yielding a global HQMM state that is invariant under the combined action of $G$ for both conventional and causal (input–output) structures. We show that such symmetry actions are naturally classified by a group-cohomology $2$-cocycle $[\omega] \in H^{2}(G,\mathrm{U}(1))$, in direct analogy with the standard cohomological classification of one-dimensional bosonic SPT phases via projective edge representations. As an explicit example, we apply this construction to the Affleck–Kennedy–Lieb–Tasaki (AKLT) chain, where the hidden layer carries a nontrivial class $[\omega] \in H^{2}(\mathrm{SO}(3),\mathrm{U}(1))$ encoding its SPT order. In this case the HQMM formalism reproduces the known SPT properties of the AKLT state while providing a stochastic, Markovian description of the underlying virtual dynamics. Our results establish HQMMs as a natural bridge between quantum stochastic processes, tensor-network descriptions of many-body systems, and symmetry-protected topological order.
Read the full abstract

Combinatorics

Flip of lattices

In this paper, we introduce a new combinatorial operation, called a flip, on arbitrary partially ordered sets. We define a mutation to be a flip that maps a lattice to a lattice. We study properties of flips, and give a necessary and sufficient condition for a flip to be a mutation. We introduce locally mutable lattices and mutable lattices in terms of flips, and prove that mutable lattices are semidistributive. We show that type-A and type-B Cambrian lattices are locally mutable, and those associated with the finite-type Coxeter quivers with different orientations are related also by the sequence of mutations. Finally we introduce a new class of lattices, called Ordovician lattices, as the lattices obtained from Cambrian lattices by iterated mutations. We provide conjectures on the structure of Ordovician lattices and on the compatibility between our mutation and the mutation in the theory of cluster algebras.
Read the full abstract

Number Theory · Cross-listed from cs.DS

Deterministically finding an element of large order in $\mathbb{Z}_N^*$

In this paper, we present an improvement for the problem of deterministically finding an element of large multiplicative order modulo some integer $N$. This problem arises as a key subroutine in current deterministic factoring algorithms, such as those proposed by Harvey and Hittmeir [Mathematics of Computation, 2021]. Specifically, let $D<N$ be positive integers with \begin{equation}\label{eq:abs} D > \exp\left(\sqrt{2\log N \log \log N}\right). \end{equation} We give a deterministic algorithm that does one of the following: Returns an element $a \in \mathbb{Z}_N^*$ with $\operatorname{ord}_N(a) > D$; Returns a non-trivial factor of $N$; Or reports that $N$ is prime. The running time of our algorithm is $O(D^{1/2 + o(1)})$. Similar results were independently and concurrently obtained by Harvey and Hittmeir [arXiv:2601.11131, 2026] in work that appeared while this manuscript was in preparation. Prior to these works, the best known algorithm for finding an element with order larger than $D$ was given by Oznovich and Volk [SODA 2026], requiring $D > N^{\frac{1}{6}}$. We also present a simpler algorithm that applies for any $D < N$ and runs in $O(D^{2.5+o(1)}\operatorname{polylog}(N))$.
Read the full abstract

Quantum Algebra

Affine $\mathrm{i}$quantum groups and Steinberg varieties of type C, II

A geometric realization of the quasi-split affine iquantum group of type $\mathrm{AIII}_{2n-1}^{(\tau)}$ was given by Wang and the second author, in terms of equivariant K-groups of Steinberg varieties of type C. As a completion of that work, this paper focuses on the previously untreated case. We provide a similar construction of the quasi-split affine iquantum group of type $\mathrm{AIII}_{2n}^{(\tau)}$, using the same equivariant K-groups of Steinberg varieties of type C. In the appendix, we employ Steinberg varieties of type D to give a new realization of the quasi-split affine iquantum group of type $\mathrm{AIII}_{2n-1}^{(\tau)}$, thereby avoiding the localization method adopted in the previous work.
Read the full abstract

Differential Geometry

Biharmonic rotational surfaces in the four-dimensional Euclidean space are minimal

In this paper, we show that any biharmonic simple rotational surface in the four-dimensional Euclidean space is minimal. The proof is based on reducing the biharmonic equation to a system of ordinary differential equations for the profile curve and then excluding all possible non-minimal branches. This is a partial affirmative answer to Chen's conjecture.
Read the full abstract

Complex Variables

On entire solutions for a class of product-type nonlinear PDEs in $\mathbb{C}^n$

This paper is mainly devoted to describing the entire solutions of nonlinear partial differential equation $$ u_{z_1}u_{z_2}\cdots u_{z_n}=e^g, $$ with the eikonal equation as a prototype, where $g$ is a polynomial in $\mathbb{C}^n$. Through a novel method, we break through the restriction of finite order condition and present the explicit expressions for the entire solution of the above equation. As an application, we completely resolve two questions of Xu-Liu-Xuan in \cite{Xu}.
Read the full abstract

Rings and Algebras

The comaximal graph of a finite-dimensional Lie algebra

In this paper, we introduce the comaximal graph $\Gamma(L)$ of a finite-dimensional Lie algebra $L$, whose vertices are the nontrivial proper Lie subalgebras of $L$ over a field $\mathbb{F}$, and two vertices $A$ and $B$ are adjacent if and only if $\langle A, B\rangle =L$. We establish general structural properties, including a characterization of isolated vertices via the Frattini subalgebra and a criterion for completeness in terms of $\mu$-algebras. We classify $\Gamma(L)$ for all Lie algebras of dimension at most three over a finite field $\mathbb{F}_q$, providing an explicit description in each case. The resulting graphs exhibit a rich range of behaviors, depending on the structure of the derived algebra and the action of $\operatorname{ad}x$. For $L\cong \mathfrak{sl}_2(\mathbb{F}_q)$, we determine several graph invariants, including the degree sequence, clique number, chromatic number, domination number, diameter, and radius, and show that $\Gamma(L)$ is connected and non-planar. The graph contains a large clique formed by the nonsplit semisimple lines together with the Borel subalgebras, while the nilpotent and split semisimple lines have a more restricted adjacency structure governed by their containment in Borel subalgebras.
Read the full abstract

Logic

Topology and category for singular product spaces

For $\kappa$ a regular uncountable cardinal, the higher Baire and Cantor spaces ${}^\kappa\kappa$ and ${}^\kappa2$ (endowed with the ${<}\kappa$-box topology) have been relatively well-studied, but less is known about the case where $\kappa$ is singular. We will consider several spaces of functions and box topologies that could serve as higher Baire and Cantor spaces for singular cardinals. The ultimate focus of the article lies in studying cardinal characteristics of the ideal of $\kappa$-meagre subsets of these spaces.
Read the full abstract

Probability · Cross-listed from eess.SP

Quadratic Forms in Gaussian Random Variables Theoretical Results and Applications

This manuscript reviews theoretical results and applications related to quadratic forms in Gaussian random variables. It summarizes definitions, canonical representations, exact and approximate distributional results, numerical inversion methods, applications, and selected open problems for real and complex quadratic forms, multiforms, and ratios of quadratic forms.
Read the full abstract

All authors Mohanad Ahmed, Mahmoud Ghazal, Maaz Mahadi, Tareq Y. Al-Naffouri

Complex Variables

On an extremal problem for harmonic maps conformal at a point

Let \(\mathbb D\) denote the unit disc in \(\mathbb C\). For a domain \(D\subset\mathbb C\) and a point \(p\in D\), let \(M_D(p)\) denote the supremum of \(\|df_0\|\) over all harmonic maps \(f:\mathbb D\to D\) with \(f(0)=p\) whose differential \(df_0\) at \(0\in \mathbb D\) is conformal. If \(f:\mathbb D\to D\) is a conformal diffeomorphism onto \(D\) with \(f(0)=p\), then \(\|df_0\|\le M_D(p)\). In a recent paper, the authors proved that equality holds when \(D=\mathbb D\), and they asked whether equality can hold only when \(D\) is a round disc. We give a negative answer by proving that, among bounded convex pointed domains \(p\in D\subset\mathbb C\) and up to translations, rotations, and reflections, equality holds if and only if, after moving \(p\) to the origin, \(D=F(\mathbb D)\) where \(F:\mathbb D\to\mathbb C\) is a holomorphic map with \(F(0)=0\) and \(F'(z)=\frac{c}{1+az+\lambda z^2}\), where \(c>0\), \(|\lambda|<1\), and \(|a-\bar a\lambda|<1-|\lambda|^2\). This family contains strongly convex examples which are not round discs.
Read the full abstract

Statistics Theory

Minimax optimal submatrix detection: Sharp non-asymptotic rates

Given an observation $\mathbf Y \in \mathbb{R}^{d_1\times d_2}$ from the model $\mathbf Y = \mathbf X + \mathbf E$ where $\mathbf X$ is constant and $\mathbf E$ has i.i.d. $N(0,1)$ entries, we consider the problem of detecting a planted submatrix in the mean matrix $\mathbf X$. Specifically, we aim to distinguish the null hypothesis $\mathbf X = 0$ from the alternative hypothesis in which $\mathbf X$ is non-zero only on a submatrix of size $s_1 \times s_2$ with elevated entries bounded below by $\mu>0$. We establish a minimax lower bound characterizing how large $\mu$ must be to ensure that the two hypotheses are distinguishable with high probability. Furthermore, we derive novel minimax-optimal tests achieving the lower bound, and describe extensions of these tests that are adaptive to unknown sparsity levels $s_1$ and $s_2$. In contrast with previous work, which required restrictive assumptions on $s_1,s_2, d_1$ and $d_2$, our non-asymptotic upper and lower bounds match for any configuration of these parameters.
Read the full abstract

Category Theory

Yoshida algebra for groupoids

In this paper, we extend the notion of the Yoshida algebra of a finite group introduced in \cite{Yos83} to finite groupoids and investigate its fundamental properties. Our main results show that the center of the Yoshida algebra of a finite groupoid is isomorphic to the center of the corresponding groupoid algebra, and that there exists a surjective ring homomorphism from the crossed Burnside ring of a finite groupoid, introduced in \cite{Shi26+}, onto the center of the Yoshida algebra of a finite groupoid.
Read the full abstract

Information Theory

Sparse Discrete Laplace and Gaussian Mechanisms under Local Differential Privacy

We study sparse locally private channels of the form $M(y\mid x)\propto w(x,y) 1\{y\in S(x)\},$ where the admissible output set $S(x)$ is allowed to depend on the private input $x$ and is assumed to be small. Here, we consider the sparse discrete-Laplace family with kernel $w(x,y)=e^{-\lambda d(x,y)}$ and the sparse Gaussian family with kernel $w(x,y)=e^{-d(x,y)^2/(2\sigma^2)}$. For both families we give exact characterizations of pure and approximate local differential privacy. For pure $\varepsilon$-local differential privacy, we show that input-dependent sparse supports are obtained when all supports coincide. For $(\varepsilon,\delta)$-local differential privacy, we derive exact formulas for the privacy defect in terms of support leakage and excess privacy loss on the overlap region. We then specialize the analysis to radius-truncated sparse discrete-Laplace and radius-truncated sparse Gaussian mechanisms and obtain explicit privacy-sparsity tradeoffs in terms of the support size $s$. In particular, we show that nontrivial approximate local privacy requires a minimum support size, whereas larger supports reduce support leakage but increase distortion. For the Gaussian family, the overlap term exhibits an additional quadratic dependence on the support radius, which implies a sharper tradeoff between privacy and sparsity. These results identify the support cardinality as the intrinsic complexity parameter of the mechanism and yield an optimal design principle: choose the smallest support size that satisfies the target privacy constraint.
Read the full abstract

All authors Amirreza Zamani, Sajad Daei, Parastoo Sadeghi, Mikael Skoglund

Combinatorics

On $\ell$-weakly cross $t$-intersecting families for sets and vector spaces

Let $[n]$ (resp. $V$) be an $n$-element set (resp. $n$-dimensional vector space over the finite field $\mathbb{F}_{q}$), and $\binom{[n]}{k}$ (resp. $\genfrac{[}{]}{0pt}{}{V}{k}$) denote the set of all $k$-subsets of $[n]$ (resp. $k$-dimensional subspaces of $V$). We say that $\mathcal{F}\subseteq\binom{[n]}{k}$ (resp. $\mathcal{F}\subseteq \genfrac{[}{]}{0pt}{}{V}{k}$) and $\mathcal{G}\subseteq \binom{[n]}{k'}$ (resp. $\mathcal{G}\subseteq \genfrac{[}{]}{0pt}{}{V}{k'}$) are $\ell$-weakly cross $t$-intersecting if $\sum_{1\leq i,j\leq \ell}|F_{i}\cap G_{j}|\geq \ell^{2}t-\ell+1$ (resp. $\sum_{1\leq i,j\leq \ell}\dim(F_{i}\cap G_{j})\geq \ell^{2}t-\ell+1$) for all distinct $F_{1},\ldots,F_{\ell}\in\mathcal{F}$ and $G_{1},\ldots,G_{\ell}\in\mathcal{G}$. In this paper, we provide an alternative proof of the set version of the $\ell$-weakly cross $t$-intersecting theorem and an explicit lower bound for $n$. Moreover, we prove that if $\mathcal{F}$ and $\mathcal{G}$ are $\ell$-weakly cross $t$-intersecting subspace families, then \[ |\mathcal{F}| \cdot |\mathcal{G}| \leq\genfrac{[}{]}{0pt}{}{n-t}{k-t}\genfrac{[}{]}{0pt}{}{n-t}{k'-t} \] holds, provided that $n\geq (2k-t+1)(t+1)+(k-t+1)k'+k+2\ell-1$. This extends the theorem of Cao, Lu, Lv and Wang [J. Combin. Theory Ser. A 193 (2023), 105688], who established the upper bound for the product of the sizes of cross $t$-intersecting subspace families.
Read the full abstract