Papers

Finding a minimum proper vertex coloring is $\NP$-hard and hard to approximate. $B$-coloring is used as a heuristic approach to graph coloring. A b-coloring of a graph $G$ is a proper vertex coloring where each color class contains at least one vertex (a b-vertex) adjacent to a vertex in every other color class. The maximum number of colors in such a coloring is the b-chromatic number, ${\rm b}(G)$. A ${\rm b}^{\ast}$-coloring is a variation in which a b-vertex is adjacent to a b-vertex in every other color class. We employ the ${\rm b}^{\ast}$-coloring to prove that any $n$-vertex graph $G$ with independence number at most $t$ satisfies ${\rm b}(G) \leq [(t-1)n+t\chi(G)]/(2t-1)$. This bound extends the bounds of Kouider and Zaker (2006) and Alkhateeb and Kohl (2011) and significantly improves the bound in terms of the clique partition number. We show that this bound is sharp for all $t\geq 2$ and $\chi(G)\geq 3$. Furthermore, we provide a refined bound based on the maximum number of vertex-disjoint independent sets of size $t$. Finally, we prove ${\rm b}^{\ast}(G) \leq [(t-2)n+(t-1)\chi(G)]/(2t-3)$ for all $K_{1,t}$-free graphs $G$, a significant improvement over the analogous bound for ${\rm b}(G)$.

Spielman-Srivastava spectral sparsification preserves Laplacian quadratic forms to within (1 +/- epsilon), but does not directly control the adjacency spectral radius lambda_1, which governs the NIMFA epidemic threshold and arises in spectral clustering. We prove |lambda_1(A_H) - lambda_1(A_G)| <= epsilon(2 Delta - lambda_1) deterministically, with a sharp epsilon*lambda_1 bound for reweighting sparsifiers via Perron-Frobenius monotonicity. Under effective-resistance sampling, Matrix Bernstein gives O(epsilon Delta / sqrt(c)) with high probability. Combining eigenvector delocalization with resolvent perturbation theory, we establish that for graphs with delocalized Perron eigenvectors and spectral gap = Omega(Delta), the distortion is O(epsilon Delta sqrt(log n) / sqrt(n)) + O(epsilon^2 Delta^2 / delta_gap), with corollaries for Erdos-Renyi graphs, regular expanders, and stochastic block models. Lower bounds establish tightness for regular graphs.

We study two invariants, rate and slant, that describe the extremal behavior of the maximal shifts in the minimal free resolution of the residue field over a standard graded algebra. We provide bounds and computations of these invariants for a variety of rings, including compressed level algebras, rings defined by general forms and rings defined by monomials. We also prove an asymptotic additivity property of the maximal shifts for certain classes of rings, including Golod rings, which allows to interpret slant as a limit.

We study community detection on Markovian random networks outside of the Stochastic Block Model (SBM) framework. Specifically, we consider a random network growth process which generates $K$ separate preferential attachment trees and connects them with Erdős–Rényi edges, so that each tree represents a community and each node inherits the label of the tree to which it belongs. This model is able to produce many features of real world networks that are improbable under SBM, such as power law degree distribution and the existence of chains and hubs. Given only the final graph, without any knowledge of the growth process, we seek to recover the unobserved community membership of the nodes. We first prove that it is impossible for any algorithm to consistently recover the community label of all the nodes. However, we design algorithms which are provably able to recover the community labels of subsets of central nodes, for several different notions of node centrality such as arrival time or degree. Our procedure consists of two stages where, in the first stage, we classify high degree nodes and then, in the second stage, extend the community assignments to the remaining vertices. Numerical experiments and a real data application on a coauthorship network demonstrate the effectiveness of our proposed approach.

We study optimal design of $\varepsilon$-locally differentially private mechanisms for binary hypothesis testing. Each observation is drawn from one of two known distributions $P_0,P_1$ on a finite alphabet of size $k$, privatized by a mechanism $Q$, and then used to infer which distribution generated the data. We measure testing utility using an $f$-divergence, including total variation, KL, and hockey-stick divergences, between the two induced output distributions. Previous work established structural properties of optimal mechanisms, but only yielded exponential-time algorithms. We prove a sharp structure: for every $\varepsilon$ and every $f$-divergence objective, after sorting the alphabet by likelihood ratio, there exists an optimal mechanism that partitions the sorted alphabet into contiguous blocks and applies randomized response to the block label. We call this class Sort-Partition-Randomize (SPR). This characterization yields an exact dynamic program that computes an optimal mechanism in $O(k^3)$ time, and more generally in $O(\ell k^2)$ time with an $\ell$-output budget. Our results make it possible to efficiently compute and characterize the exact optimum across the full privacy range, beyond asymptotic privacy regimes.

We consider local optimization of a weak distance between two compact surfaces embedded in the three-dimensional Euclidean space on its special Euclidean group. Identifying those objects with the associated surface measures, their discrepancy is quantified in terms of the inhomogeneous Sobolev norm of negative order via the Plancherel theorem. Then, applying an isometry to one surface corresponds to pushforwarding its surface measure and the distance can be regarded as a function on the Lie group. For appropriate exponents of the Sobolev norm, the second power of the function acquires sufficient differentiability that allows to search for its local minima in a derivative-based framework, and the gradient of the objective function has a favorable structure for efficient implementations using the nonuniform fast Fourier transform. In numerical experiments, we observe convergence of the SR1 trust-region method applied to a few root-finding problems and discuss its connection to a more geometric quantity.

Given a 3-manifold $M$ with a network of line and point defects in its boundary, we define the skein module of this configuration, generalizing the well-studied case of 3-manifolds which only admit point defects in the boundary. We prove that when all defects are labelled by semisimple data, our skein module is isomorphic to the state space of $\partial M$ in the defect version of the Reshetikhin-Turaev TQFT constructed by Carqueville-Runkel-Schaumann. Our defect skein modules follow naturally by globalizing the graphical calculus of module categories and functors thereof, and generalize the possible defect data considered in the defect TQFT beyond the semisimple case.

We study the spectral properties of Laplacians on the Schreier graphs $\Gamma_n$ of the basilica group, the iterated monodromy group of the polynomial $z^2 - 1$, which is an important example in the theory of self-similar, amenable but not elementarily amenable, automaton groups. Building heavily on results by Brzoska, Jarvis, George, Rogers and Teplyaev about certain subgraphs of the basilica graphs, we develop a new recursive framework for computing the characteristic polynomials of these Laplacians. Our analysis reveals a simple underlying dynamical system and proves approximation results for the Kesten-von Neumann-Serre (KNS) spectral measure.

With $\rho = \frac{13-\sqrt{69}}{10} \approx 0.47$, it was recently established that there exist multiplicative Sidon sets (sets without any non-trivial solutions to $ab = cd$) in $\{1, 2, \ldots, n\}$ with maximal gap size $\ll_{\varepsilon} n^{\rho + \varepsilon}$. Here we improve upon this result and show that one can take $\rho = \frac{10}{33} \approx 0.303$ instead.

We give a general framework for tomography of states that have bounded-extent with respect to a structured class of states. Let $\textsf{C}$ be a family of $n$-qubit states such that: $(i)$ $\textsf{C}$ is succinctly representable and $(ii)$ there is a weak agnostic learner of $\textsf{C}$. We give a tomography protocol for an unknown state $|\psi\rangle$ that is promised to admit a decomposition of the form $|\psi\rangle = \sum_i c_i |\phi_i\rangle$, where $|\phi_i\rangle \in \textsf{C}$ with bounded $\ell_1$-norm of the coefficients (which we call extent). Our main contribution is to show that a weak agnostic learner for $\textsf{C}$ can be boosted into a tomography algorithm for states with bounded extent with respect to $\textsf{C}$. Our reduction is black-box and applies broadly across model classes. As an application, when $\textsf{C}$ is the class of stabilizer states, we obtain tomography algorithms for states with stabilizer extent $\xi$ up to trace distance $\varepsilon$, in time $\textsf{poly}(n,(\xi/\varepsilon)^{\log(\xi/\varepsilon)})$, which is improvable to $ \textsf{poly}(n,\xi,1/\varepsilon)$ assuming the algorithmic polynomial Freiman-Ruzsa conjecture in the high-doubling regime. When the unknown state $|\psi\rangle$ is arbitrary, we give an algorithmic decomposition result in the spirit of a weak regularity lemma for quantum states with respect to $\textsf{C}$ and show that the structure in $|\psi\rangle$ that is explainable by $\textsf{C}$ can be efficiently learned. Our main conceptual message is that agnostic learning of a structured base class automatically yields learnability of its low-complexity linear span.

We investigate the long-time behaviour of a one-dimensional compressible viscous fluid with general capillarity and density dependent viscosity, driven by a stochastic force. In particular, we prove the existence of invariant measures by applying the Krylov-Bogoliubov method in a setting where the dynamics is supported on a non-complete phase space. This analysis is further enhanced by the derivation of a refined stability result determining the continuous dependence with respect to the initial data. The present paper exhibits some properties and results for Korteweg fluids which are not known in absence of the capillarity tensor. In particular, we prove that the Markov semigroup associated with strong solutions is Feller and we can consider ranges of the adiabatic and viscosity exponents $\gamma$ and $\alpha$ larger than those available in the current ergodic literature for compressible fluids. Also the interplay between the choice of the physical domain and the use of a damping term is discussed.

For a Fano manifold $X$, Gamma conjecture II aims to use $\mathcal{D}_{\rm{coh}}^b(X)$ to describe the asymptotic behavior of its Dubrovin connection via $\widehat{\Gamma}$-integral structure. It was proposed by Galkin, Golyshev and Iritani, and can be regarded as a quantitative refinement of Dubrovin's conjecture on Fano manifolds with semisimple big quantum cohomology. As a step toward Gamma conjecture II, we define the Gamma-I property at points satisfying the (SR) condition, arising from the original Gamma conjecture I. We prove that the property holds globally in the following sense: if it holds at one such point, then it holds throughout the connected component of the (SR)-region containing that point. Based on this global Gamma-I property, we establish a strategy-type theorem relating Gamma conjecture II to the Gamma-I property at a possibly non-semisimple point, together with an analysis of small quantum cohomology. We further apply this theorem to prove Gamma conjecture II for del Pezzo surfaces; the proof combines Iritani's Galois action with addtional elementary operations on exceptional collections, and its most technically involved step consists in verifying the required global Gamma-I property.

We study local well-posedness for a class of stochastic reaction-diffusion equations driven by multiplicative, possibly colored, noise. The interaction between rough stochastic forcing and polynomial nonlinearities naturally leads to solutions with low spatial regularity, making the treatment of the nonlinear terms delicate. Our main contribution is a general local existence and uniqueness theory for SPDEs with rough noise and highly irregular initial data. The framework also yields new results in standard noise regimes, including trace-class noise and space-time white noise. We identify the critical initial-data spaces for a wide range of nonlinearities, and we establish instantaneous parabolic regularization, general blow-up criteria, and sufficient conditions for positivity preservation. We apply the abstract theory to several prototypical models, including the stochastic Allen-Cahn, Burgers, Fisher-KPP, and coupled Gray-Scott equations. Finally, in the one-dimensional space-time white-noise setting, we combine our local theory with existing global a priori results in a highly singular regime.

We develop a nine-compartment nonlinear epidemic model incorporating two co-circulating viral strains (ancestral I1 and the Alpha variant B.1.1.7 I2, which is 43-90% more transmissible, c2=1.5), a super-spreader subpopulation, partial vaccine-induced immunity with waning, and explicit hospitalization dynamics with differentiated mortality. Transmission and vaccination rates are treated as time-varying control inputs and identified from Italian COVID-19 data (January-May 2021) via a Piecewise Cubic Hermite Interpolating Polynomial (PCHIP) control-node parameterization, reducing calibration to a fourteen-variable Sequential Quadratic Programming (SQP) problem with monotonicity and box constraints. A parametric bootstrap (n=1000) quantifies parameter uncertainty. The calibrated model achieves R^2=0.966 for active hospitalizations, R^2=0.987 for cumulative fatalities, and R^2=0.999 for cumulative vaccinations. Well-posedness, the basic reproduction number in closed form, and local and global stability of the disease-free equilibrium are established analytically. An L-infinity approximation error bound shows that the PCHIP control-node parameterization converges to the true time-varying parameters at rate O(h^2) as the node spacing vanishes. Local identifiability and a noise stability bound are established via the Fisher information matrix. A sufficient threshold condition proves epidemic decay under time-varying suppression whenever the effective reproduction number remains persistently below one. Sensitivity analyses consistently rank hospital throughput parameters above the transmission rate, providing a mathematical basis for the observation that reactive containment measures cannot prevent a hospitalization peak already driven by the pre-existing latent viral load.

We consider the problem of rate loss - a strict penalty suffered in achievable rates due to the lack of channel state information at the receiver (Rx) of a classical-quantum (CQ) channel. First, we identify non-commutative CQ channels and analytically prove a rate loss. Building on this, we next prove that coset-code-based strategies can strictly outperform conventional unstructured IID-code-based strategies for non-commutative 3-user CQ broadcast channels.

Every (resp. a generic) complex $n \times n$ matrix can be expressed as a product of $2n+5$ (resp. $\lfloor n/2 \rfloor +1$) Toeplitz matrices. Motivated by this result, it is natural to ask the following question: what is the minimum number of Toeplitz matrices required to factor a given matrix? We generalize this question from Toeplitz structure to more general structures. In this paper, we introduce the notion of structured matrix factorization length when the set of matrices with a given structure is an affine variety $X \subseteq \mathbb{C}^{n \times n}$. Then we introduce the $r$-th $X$-factorization variety, defined as the Zariski closure of the set of products of $r$ matrices in $X$, and use it to define the border structured matrix factorization length. In particular, we study the cases in which $X$ is the affine variety of Toeplitz, Hankel, bidiagonal, tridiagonal, skew-symmetric or companion matrices. We calculate the dimension of the $X$-factorization varieties for all these cases, and discuss how numerical algebraic geometry can be used to obtain computational evidence for the degrees of $X$-factorization varieties with an example. In addition, we propose methods for deriving lower and upper bounds for (border) structured matrix factorization length. For lower bounds, we develop a method based on displacement rank, which can also be used to obtain some defining equations of the $r$-th $X$-factorization variety; for upper bounds, we suggest an approach using alternating minimization.

Benders decomposition is a fundamental framework for solving large-scale mixed-integer optimization problems with complicating variables that, when fixed, yield significantly easier subproblems. However, classical Benders decomposition repeatedly solves highly similar subproblems and often exhibits zigzagging behavior across iterations, leading to slow convergence in large-scale settings. Motivated by the repetitive structure and parametric nature of Benders subproblems, this paper introduces the proxy Benders decomposition (Proxy-BD), a new decomposition framework in which subproblem optimization is replaced by certified optimization proxies rather than repeated exact solves. The proposed proxy follows a self-supervised predict-project-and-complete mechanism that produces dual-feasible solutions for generating provably valid Benders cuts. The framework preserves the theoretical validity of the decomposition independently of prediction quality through a projection-and-completion certification layer. A formal characterization of proxy-induced cuts is established, and the framework naturally extends to modern decomposition schemes, including branch-and-Benders-cut algorithms. Computational experiments on large-scale facility location and network design problems demonstrate that Proxy-BD substantially reduces the computational effort of subproblems while maintaining near-optimal solution quality. On large-scale uncapacitated facility location instances up to 2000x2000, Proxy-BD achieves median optimality gaps below 0.5%, yields up to 161x median speedups, and reduces the number of generated cuts by more than 240x on the largest instances. The computational gains consistently increase with recourse complexity, indicating that proxy-based inference scales substantially more favorably than repeated exact subproblem optimization in large-scale decomposition settings.

Icart's encoding is a classical deterministic map from finite fields to elliptic curves and a basic ingredient in early hash-to-curve constructions. We determine the exact one-output distribution of this map in the exceptional \(j=0\) case. More precisely, for \[ E_{0,b}:Y^2=X^3+b,\ q\equiv2\pmod3, \] we compute the complete fibre distribution of \(f_{0,b}:\mathbb F_q\to E_{0,b}(\mathbb F_q)\). This gives closed formulae for the image size, total variation distance from uniform, collision probability, power sums, entropy measures and basic batch statistics. We also derive the exact second moment of all nontrivial character sums of the output distribution. Via the Weil pairing, this becomes an exact energy formula for pairing-character tests on the supersingular \(j=0\) family whose odd prime order subgroups have embedding degree two.

In the demographic framework, mortality payoff function describes the cost of an interaction and fertility payoff function describes its reward. So while mortality cost depends on opponent's strategy, fertility reward can be affected by the density-dependent juvenile recruitment survival. This motivates an analysis of the eco-evolutionary dynamics of the classical Hawk-Dove game. It is shown that the stable and unstable equilibria (determined by the intersections of frequency and density nullclines) are connected by heteroclinic orbits, which attract nearby trajectories. The resulting bundle of trajectories leads to the discovery of the so-called subnullcines (manifolds placed between frequency and density nullcline) before they converge to the stable rest point. The initial isolated system is then extended by adding environmental seasonality (periodic background mortality), which acts as an external factor. This leads to complex cycling behavior and the subnullclines act as barriers to the propagation of the perturbation (resilience/resistance threshold). Thus, in a way, this paper completes, yet extends, previous works on the eco-evolutionary dynamics of games with demographic payoffs.

In a recent article, Cheng, Jiang and Yuan gave an affirmative answer to Klee's convex bodies problem of Banach spaces in the sense of strict convexity and Gâteaux smoothness. In this paper, we continue to study this problem in strong senses, such as local uniform convexity, uniform convexity, Fréchet smoothness and uniform smoothness. As a result, we show (1) Every convex body in a Banach space $X$ is approximated by locally uniformly convex bodies with respect to the Hausdorff metric if and only if $X$ admits an equivalent locally uniformly convex norm; (2) Every convex body in $X$ can be approximated by Fréchet smooth convex bodies if $X$ admits an equivalent norm so that its dual norm is locally uniformly convex on $X^*$; 3. Every convex body in $X$ can be approximated by both locally uniformly convex and Fréchet smooth convex bodies if $X$ is reflexive; 4. If $X$ is separable, then every convex body in $X$ can be approximated by both locally uniformly convex and Fréchet smooth convex bodies if and only if $X$ is an Asplund space; (5) the following statements are equivalent: A. $X$ is super reflexive; B. Every convex body in $X$ can be uniformly approximated by uniformly convex bodies; C. Every convex body in $X$ can be uniformly approximated by uniformly smooth convex bodies; D. Every convex body in $X$ can be uniformly approximated by both uniformly convex and uniformly smooth convex bodies.

We prove Ulam stability of the hyperfinite II$_1$-factor with respect to the trace norm on the operator-norm unit ball. More precisely, every sufficiently additive, multiplicative, unital, $*$-preserving map from the hyperfinite II$_1$-factor-factor into a II$_1$-factor-factor von Neumann algebra is uniformly close, after passing to a small amplification of the target, to a genuine unital $*$-homomorphism. As a key finite-dimensional ingredient, we establish a dimension-free stability theorem for matrix algebras in the same trace-norm setting. As an application, we show that the hyperfinite II$_1$-factor is isolated among II$_1$-factors with respect to sufficiently accurate approximate $*$-isomorphisms.

We study the Dirichlet problem for the fully non-linear elliptic equation of second order traducing the prescription of the scalar curvature of a spacelike hypersurface in Anti-de Sitter space. The problem is solved if the datas are strictly convex.

In this note we present how the almost-orthogonality methods based on $TT^*$ arguments can be employed to study boundedness of discrete operators of Radon type. Almost-orthogonality methods have particular significance when the classical Fourier methods are not available. However here, to avoid technicalities and present the key ideas behind the discrete almost-orthogonality methods, we give a new proof of the $\ell^2(\mathbb{Z}^d)$-boundedness of Bourgain's maximal inequality for Radon polynomial averages.

Let $H$ be a fixed 3-chromatic graph, and let $g \geq 2$ be the smallest integer such that there is no homomorphism $H \rightarrow C_{2 g+1}$. For every $\varepsilon>0$, we prove that there exists a constant $\rho>0$ such that every $H$-free $n$-vertex graph $G$ with $\delta(G) \geq(2 /(2 g+1)+\varepsilon) n$ can be made bipartite by deleting $O\left(n^{2-\rho}\right)$ edges. Thus the sharp qualitative minimum-degree stability theorem for 3-chromatic graphs admits a polynomial strengthening. In particular, this gives an affirmative answer to a question of Illingworth [\textit{Minimum degree stability of $H$-free graphs}, Combinatorica, 43(1):129-147, 2023.] on blow-ups of odd cycles.

Recently studied dependence measures, such as Chatterjee's rank correlation, that characterize both independence and perfect functional dependence, provide a powerful framework for detecting nonlinear dependencies. However, these measures cannot be weakly continuous, which limits the applicability of classical plug-in estimators based on empirical distributions. This obstruction is natural, as such measures are defined via conditional distributions and not through their joint law alone. In this paper, we introduce an optimal transport-based mode of convergence that captures weak convergence of conditional distributions and restores continuity for a broad class of dependence measures. We relate this mode of convergence to the adapted Wasserstein distance, the Knothe-Rosenblatt distance and the d1-metric on copulas. Building on this perspective, we propose a copula estimator based on the adapted empirical measure and compare it with the classical rank-based checkerboard estimator. For both estimators, we derive O(N^{-1/3})-rates of convergence with respect to metrics that capture conditional weak continuity. As a consequence, we obtain the same rates for plug-in estimators of several classes of dependence measures, including rank-based and rearranged dependence measures.

We study the KPZ equation on a circle with an additive spatial perturbation $\partial_t h=\tfrac12\Delta h+\tfrac12|\nabla h|^2+\xi+ V$, where $\xi$ is a spacetime white noise and $V$ is a smooth spatial function. When $V=0$, it is well-known that the unique invariant measure is the Brownian bridge. In the presence of the perturbation, we show that the equation admits a unique invariant measure that is absolutely continuous with respect to the Brownian bridge. We further prove the measure has a finite relative entropy with respect to the law of the bridge and that, for any $p\in(1,\infty)$, the corresponding Radon-Nikodym derivative belongs to $L^p$, provided that $\int V^2$ is sufficiently small. The proof uses the discretization and mollification scheme of \cite{FQ}, together with an application of the log-Sobolev and spectral gap inequalities for the underlying Gaussian measure.

We introduce the syntax and the semantics of intuitionistic modal logics based on a diamond connective à la Prenosil, its dual box connective, a diamond connective à la Wijesekera and its dual box connective. We analyze the modal definability of some elementary classes of frames. We study the complete axiomatizability of the sets of valid formulas determined by these classes of frames. We prove the decidability of the minimal intuitionistic modal logic determined by the class of all frames.

For tasks of likelihood families invariant under the action of a lie group, the quotient is the minimal sufficient invariant representation. On compact homogeneous spaces, this quotient representation admits a harmonic realization through spherical Fourier coefficients; for finite-band harmonic exponential families, the empirical harmonic coefficients are minimal sufficient statistics. The partition function can be expressed algebraically by extracting the trivial representation component through Clebsch-Gordan decomposition.

Momentum-based accelerated gradient methods are widely adopted to expedite convergence in nonconvex optimization, but are prone to overshooting and oscillatory behavior. A class of PID-damped accelerated gradient methods mitigates this issue by augmenting classical momentum methods with a discrete-time derivative damping term. However, the coupling among the step size, momentum, and derivative gain renders the explicit characterization of their convergence regions analytically intractable, leaving explicit theoretical convergence boundaries unexplored. In this paper, we model this class of algorithms as a third-order nonlinear feedback dynamical system and establish explicit three-dimensional convergence regions for the step size, momentum, and derivative gain via a robust control-theoretic analysis based on the Kalman-Yakubovich-Popov (KYP) lemma, formally guaranteeing linear convergence under the Regularity Condition. Furthermore, we reveal a strict geometric upper bound on the derivative gain dictated by the nonconvex curvature, beyond which over-damping severely contracts the feasible step-size region, providing a rigorous theoretical explanation for the overdamped stagnation phenomenon. Numerical experiments corroborate the theoretical boundaries and illustrate practical parameter selection guidelines for the derivative gain.

We compute the twisted first and second moments of the shifted central values of the Rankin-Selberg $L$-functions given by $L\left(\frac12+\omega, f\otimes g\right)$ as $f$ varies over primitive forms of prime power level $p^\nu$ with $\nu \geq 3$. Here $\omega$ is a bounded shift and $g$ is a fixed primitive form of level relatively prime to $p$.