Computation and Language
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
All of arXiv
Saturday 10 October
Depression is a prevalent mental disorder that affects millions worldwide, with early detection crucial for effective intervention. While exist?ing methods have achieved promising results in automated depression detection, they face two key limitations: (1) noise in post screening: symptom-based semantic screening is easily misled by superficial lexical patterns, thereby introducing false-positive posts; (2) weak op?timization of the post encoder: relying solely on coarse user-level supervision signals pre?vents models from capturing depressive cues within individual posts. To address these limita?tions, we propose PAT, a Personality-driven Augmentation and Transfer learning frame?work. In the first phase, PAT optimizes a post?level encoder via a fine-grained contrastive learning objective, utilizing LLM-based data augmentation driven by classic personality the?ories to alleviate data scarcity. In the second phase, the trained post-level scorer is deployed for high-quality post filtering, while its en?coder parameters are seamlessly transferred for user-level tasks. Extensive experiments demon?strate that PAT significantly outperforms exist?ing methods. Furthermore, PAT delivers multi?granular interpretability by tracing post-level mental-state trajectories and highlighting key symptoms, thereby offering reliable diagnostic evidence for clinical practice.
Machine Learning
Information-Theoretic Foundations of Online Temperature Sampling
Repetitive, degenerate generation is a persistent failure of LLM decoding, and the standard remedies (temperature, nucleus, and top-$k$ sampling) are static heuristics. By Kac's lemma and the AEP, a stationary source takes time exponential in its entropy to repeat a block. We therefore maximize the entropy of the sampling distributions under one cross-entropy budget that keeps the output plausible under the model. Offline, the solution is temperature sampling, with the inverse temperature as the budget's Lagrange multiplier. Our contribution is the online problem: the conditionals $p_1, p_2, \dots$ are revealed one at a time, and the sampling distribution $q_t$ must be chosen causally from $p_1, \dots, p_t$ while the budget couples the entire horizon. The optimal temperature is thus a global shadow price that must be estimated from a prefix. We propose Entropic Online Sampling (EOS), which re-solves for the temperature on each prefix. We prove it loses $O(R\log n)$ entropy against the offline optimum while overshooting the budget by $O(R\log n)$, with $R$ an instance-dependent drift parameter. A budget-tightened variant is exactly feasible at the same rate. Conversely, every exactly feasible online algorithm must lose $\Omega(R)$, so EOS is optimal up to a $\log n$ factor. When the conditionals are drawn from a finite mixture, $R=\tilde{O}(\sqrt{n})$. Experiments confirm that EOS tracks the offline temperature and beats fixed-temperature sampling in entropy.
Read the full abstract
Number Theory
Exact Rank of the Largest Good Lattice Point Matrix
We prove that for every integer $n>2$ the largest good lattice point matrix $U_n=[u_h:h\in H_n]$, whose columns are generated by all integers $h<n$ coprime to $n$, has rank exactly $\varphi(n)/2+1$. The upper bound follows from the pairing identity $u_h+u_{n-h}=(n,\dots,n,2n)^{\top}$. For the lower bound the columns are centered and the resulting orbit under the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^{\times}$ is analysed by means of odd Dirichlet characters; the essential arithmetic input is the non-vanishing of $\sum_{a}a\,\psi(a)$ for odd primitive characters $\psi$, which is equivalent to Dirichlet's theorem $L(1,\psi)\neq 0$.
Read the full abstract
Pattern Formation and Solitons
Extreme Localization via a Singular Edge Mode in an Asymmetric Linkage System
Mechanical localized modes generally retain exponentially decaying tails, whereas confinement to a single structural unit is difficult to achieve without resonators, flat-band lattices or topological design. To address this need, an asymmetric linkage system is introduced in which geometry tunes a boundary mode from finite localization to its extreme limit. Each cell comprises two unequal rigid bars connected by a torsional spring and is described by one generalized coordinate. Linearization and coordinate transformation yield a tridiagonal model and closed-form expressions for the edge mode frequency and spatial decay ratio. The analysis identifies the configurations supporting a singular edge mode at which its decay ratio vanishes, leaving only the boundary cell active in the linear regime. Simulations show near-complete localization under finite-amplitude excitation, and experiments reproduce the configuration-dependent transition from bulk transmission to boundary confinement. These results establish a minimal and analytically tunable platform for mechanical localization
Read the full abstract
Numerical Analysis
Homotopy for Rectangular Multiparameter Eigenvalue Problems
The rectangular multiparameter eigenvalue problem (rMEP) is a recently introduced form of an eigenvalue problem, in which we are looking for the combinations of parameters where the multivariate rectangular matrix loses full column rank. Existing numerical methods for rMEPs typically require substantial memory and are not suitable for problems with a large number of eigenvalues. We propose a novel numerical approach based on the homotopy method that has low memory requirements and can compute all eigenvalues of an rMEP. Moreover, the homotopy method is naturally parallelizable, providing a simple and efficient way to accelerate computations. An implementation, together with a collection of test examples, is available in a public repository.
Read the full abstract
Machine Learning
Sparsity Saves Compute, Not Samples: Oracle Inequalities for Dense and Sparse Mixture of Experts
Mixture-of-Experts (MoE) models combine specialized experts through an input-dependent routing mechanism, and their sparse variants underpin many modern large-scale systems. Yet the statistical cost of adaptive routing remains only partially understood. We study the estimation error of least-squares MoE estimators when both the experts and the gating network are Lipschitz in their parameters. We represent each MoE as a gate–expert pair in a Gated Hilbert Space, whose norm $\|\cdot\|_\Delta$ separates the contributions of routing and expert discrepancies. Using its empirical representation, we derive an oracle inequality with a fast rate of order $\tilde{\mathcal O}\big((Kd_{\mathrm{pr},e}+d_{\mathrm{pr},g})/n\big)$ for dense MoEs with $K$ experts. For sparse Top-$k$ and Top-$p$ routing, the selection map is discontinuous in the gating parameters. We handle this by partitioning the gating class according to the selection patterns it induces on the sample. The resulting bounds match the dense rate up to an additive routing cost governed by the Natarajan dimension of the selector. We show that such a routing-complexity condition cannot be dropped: Lipschitz continuity in the parameters alone does not suffice. For linear softmax gating, the routing cost is of the same order as the gating term. Finally, for linear experts, we establish a matching minimax lower bound of order $Kd_{\mathrm{pr},e}/n$, showing that the rates are optimal up to logarithmic factors.
Read the full abstract
Robotics
Training-Free Multi-Agent Cooperative Embodied Search from Uncertain Vision-Language Priors
Real-world Vision-Language Navigation (VLN) requires agents to act under partial observability, where map structure, semantic cues, and target locations may be incomplete or incorrectly inferred by foundation models. This paper presents a lightweight, training-free, and uncertainty-aware framework for cooperative multi-agent multi-target search in mapless environments. Instead of learning an end-to-end navigation policy, the framework separates high-level semantic reasoning from low-level execution through a scalable graph-optimization backbone. Multimodal Large Language Models (MLLMs) serve only as hypothesis generators, proposing semantic zones, target-location cues, and possible navigable connections. These outputs are treated as uncertain priors and further refined using online observations and graph-context evidence. Cooperative navigation is then formulated as a rolling-horizon multi-agent mixed-integer linear program with a lexicographic objective that first maximizes target-directed reward and then reduces travel distance, uncertain-edge use, and repeated visits. Experiments derived from 100 Matterport3D test cases show that the proposed framework improves target coverage and search efficiency over representative baseline methods, while shared information and joint planning enable more balanced workloads across agents. By operating on an abstract graph without relying on embodiment-specific policy parameters, the framework scales across varying numbers of agents and targets, generalizes to unseen environments, and accommodates different perception modules and low-level controllers without task-specific retraining.
Read the full abstract
Representation Theory
Tate cohomology of unipotent cuspidal representations of finite groups of Lie type
Let $p$ be a prime and $k$ be an algebraic closure of the finite field with $p$ elements. Let $G$ be a connected reductive algebraic group over $k$, and let $F:G\rightarrow G$ be a Frobenius morphism, defining an $\mathbb{F}_q$-rational structure on $G$, where $q$ is a power of $p$. Let $\ell$ be a prime different from $p$ and $\ell\ne 2$. Let $\Pi$ be an $\ell$-adic cuspidal unipotent representation of $G^{F^\ell}$ such that $\Pi\simeq \Pi^\sigma$, where $\sigma$ is a generator the Galois group ${\rm Gal}(\mathbb{F}_{q^\ell}/\mathbb{F}_q)$. In this paper, we prove the irreducibility of the zeroth Tate cohomology group $\widehat{\rm H}^0(\sigma,\mathcal{L})$ and vanishing of the first Tate cohomology group $\widehat{\rm H}^1(\sigma,\mathcal{L})$ for any $G^{F^\ell}\rtimes{\rm Gal}(\mathbb{F}_{q^\ell}/\mathbb{F}_q)$-stable lattice $\mathcal{L}$ in $\Pi$, using the multiplicity-one property of a progenerator constructed via the generalized Gelfand-Graev representations and Harish-Chandra induction.
Read the full abstract
High Energy Physics (Experiment)
Detecting photons in radiative Bhabha interaction with Si-strip and LYSO crystals at future e+e- colliders
Next-generation e+e-colliders have been proposed for the Super Tau Charm Facility covering center-of-mass energies sqrt(s) = 2-7 GeV, and for the Higgs Factories optimized for Z-pole physics and for HZ production. Luminosity can be determined by measuring forward Bhabha scattering. The QED cross-section calculation has reached a precision of better than 10^-3. Detecting radiative photons in Bhabha events provides a tool for validating higher-order corrections in theory. We propose the Forward Detector for detecting Bhabha scattering events at the STCF. The design uses high-resolution silicon detectors and finely segmented LYSO crystals to discriminate radiative photons from closely associated electrons. Bhabha scattering events are simulated with the BHLUMI and BHWIDE programs, and the detector is modeled using GEANT. Systematic uncertainties due to multiple scattering and bremsstrahlung in the beam pipe were evaluated. The potential for achieving precise measurements of radiative processes in Bhabha events is investigated.
Read the full abstract
Computer Vision
What Really Works for Universal Multimodal Embeddings? A Controlled Study of Contrastive Training Strategies
Contrastive learning has become the standard paradigm for multimodal representation learning, aligning semantically matched pairs while separating mismatched ones in a shared embedding space. Although various contrastive training strategies have been proposed across negative selection, batch construction, and gradient modulation, their actual effectiveness under controlled, reproducible conditions remains poorly understood. This motivates a fundamental question: Do sophisticated contrastive strategies consistently bring meaningful downstream gains in multimodal embedding learning? To address this, we systematically evaluate representative strategies under a unified benchmarking framework on MMEB. Surprisingly, direct evaluations reveal that most existing strategies offer marginal gains over a standard aligned baseline, with several even degrading overall performance. To uncover the underlying failure modes, we introduce an MLLM-as-a-Judge diagnostic framework that dissects top-1 retrieval behaviors into labeled positives, false negatives (unlabeled valid matches), and hard/easy negative errors. Our systematic analysis yields three key insights: (1) Gradient distortion: Upweighting gradients from high-similarity negatives consistently hurts downstream generalization; (2) Distribution illusion: Wider separation between positive and negative similarity distributions does not necessarily translate to better retrieval performance; and (3) Synergistic training: While false-negative mitigation or hard-batch construction yields limited gains in isolation, integrating hard-negative mining, false-negative mitigation, and hard-batch construction achieves optimal performance, delivering an average improvement of 6.0% on MMEB with Qwen2-VL-2B. Overall, our findings demystify popular contrastive strategies and provide actionable recipes for training universal multimodal embedding models.
Read the full abstract
Information Retrieval
Faithful Query Resolution for Conversational Search
Conversational query rewriting makes context-dependent requests explicit for retrieval, but additional context can introduce an information need the user did not express. This raises a question about the interaction between query fidelity and retrieval breadth. This paper examines that interaction in behavior-adaptive conversational search, using iKAT SCAI 2026 as the evaluation setting. We compare five query-generation configurations within a behavior-adaptive assistant using BM25 and SPLADE retrieval. A minimal-faithful resolver preserves the user's wording and resolves only context-dependent references; weighted reciprocal rank fusion combines its rankings with those from a learned rewriter and the raw utterance. Offline evaluation shows that adding these formulations recovers recall over the faithful query alone, with a slight reduction in nDCG@10. Across our five iKAT SCAI 2026 submissions, the weighted configuration obtains the highest mean retrieval scores, reaching nDCG@5 of 0.534, a 5.3% relative improvement over the strongest alternative. However, this retrieval advantage does not coincide with the highest conversational satisfaction scores. These findings motivate separating faithful query interpretation from retrieval expansion, while assessing their effects on conversational utility independently.
Read the full abstract
Information Retrieval
What Drives AI Citations? Content, Retrieval and Model Knowledge in Generative Engine Optimization (GEO)
Generative search engines such as ChatGPT, Gemini and Perplexity now decide which Web pages users see as sources, and a growing industry of generative engine optimization advises publishers on how to earn these citations. We study what shapes citation in two 90-day collections of answers to commercial questions in contrasting markets: 158,099 answers with 468,037 citations. Comparing pages of the same website, content matters in one way: pages whose title and paragraphs match the questions people ask are cited more, whereas FAQ blocks, structured data, summary boxes and page speed appear effective only across websites. Page properties nevertheless explain little of the variation between pages of a website. Replaying the questions through the engines' APIs shows why. Every page ChatGPT cites is one its own search retrieved, and which pages that search retrieves, for sub-queries the model rewrites on every answer and that rarely coincide with Google's or Bing's results, explains far more of the variation than page properties (32% against 2.8%). Content acts mainly through this step, by matching the engine's queries in meaning. The model's own knowledge shapes it too: ChatGPT writes brands it knows into its searches, prefers websites it knows, and names brands without any supporting page, and controlled experiments show that brand names reorder its rankings of products with identical facts. Pages are thus cited when searched; brands are also named when remembered. The findings replicate in a market of small B2B vendors. We release data and code.
Read the full abstract
Machine Learning
InCLAD: A Continual Learning Benchmark for Industrial Visual Anomaly Detection
Industrial anomaly detection benchmarks have advanced rapidly, yet they remain largely static and therefore underrepresent deployment settings in which inspection systems must be extended from one industrial component to another over time. In our setting, continual industrial anomaly detection is framed as a task-incremental problem: each component defines a task, while the learning objective remains semi-supervised. The goal extends beyond conventional anomaly detection, since models should preserve their performance on all components as they are sequentially exposed to new components. This framing is especially relevant because many existing industrial pipelines either assume fully supervised defect labels or study only isolated datasets, leaving open the question of how semi-supervised anomaly detectors behave across a sequence of heterogeneous components. We address this gap by organizing the benchmark as a sequence of related component-level tasks and by defining multiple scenarios, including random, easy-to-hard, and hard-to-easy. In addition to single-dataset continual scenarios, we propose challenging scenarios spanning across multiple datasets. We further evaluate continual performance from two complementary perspectives: image-level anomaly detection and pixel-level anomaly localization. By recasting industrial anomaly detection as a continual benchmark rather than a static train/test problem, our work establishes a concrete path toward studying knowledge retention, adaptation, and generalization in evolving industrial environments.
Read the full abstract
Astrophysics of Galaxies
Photometric Identification and Dynamical Purification of Blue Horizontal Branch Stars in DESI MWS DR1
Blue horizontal-branch (BHB) stars are ideal tracers for mapping the structure of the Galactic stellar halo. However, traditional spectroscopic identification is limited by data quality and sample size, while broad-band photometric methods often achieve only moderate completeness and purity. Building upon the color-space BHB identification method of \citet{2025ApJS..278...62H}, we synthesize SkyMapper $(u,v,g,z)$ photometry from DESI MWS DR1 spectroscopy and identify 9,237 BHB candidates in the $(g-z)_0$–$(u-v)_0$ color space using the HDBSCAN clustering algorithm. We then construct a Kernel Density Estimation (KDE) Bayesian probability model with capture-recapture (C-R) prior to assign posterior membership probabilities, achieving a probability-weighted purity of 88.9% and completeness of 94.2%. Applying an escape-velocity cut based on the Galactic gravitational potential, we remove 1,461 contaminants with unphysical kinematic parameters, yielding a clean photometric BHB sample $\mathcal{S}_c$ of 7,776 stars (retention rate $R_{\rm keep} = 84.2\%$). Systematic analysis of the contaminants reveals that they are predominantly faint sources ($g\sim20$~mag) with very low signal-to-noise ratios (median SNR~$<$~5). When the BHB color–luminosity relation is incorrectly applied to these objects, their space velocities are amplified beyond the Galactic escape limit, confirming that the escape-velocity filter essentially acts as a physical detector of low-SNR–driven distance inflation.
Read the full abstract
Computer Vision
Appearance Compensation in Volume Rendering
Can a volume that reproduces every external RGB view still have an incorrect density? We study this question in emission-absorption rendering with an independently parameterized, physically bounded effective source. Appearance compensates a density change by replacing the radiance that it removes from the rest of each ray. We characterize the surviving density information with a shared spatial appearance field. Our first result is an optimal density-only gain after finite-degree spherical-harmonic source refitting. A coupled tensor gauge and physical localized packets identify the sharp limiting nonlinear inverse coefficient as its reciprocal. Our second result realizes positive gain at every fixed finite degree for a residual set of isotropic spatial sources at one fixed density. At the same references, growing angular capacity hides a fixed nonzero density error while retaining physicality and any prescribed finite set of smoothness bounds. Local identifiability and the absence of a capacity-uniform recovery modulus therefore coexist. Our third result constructs an exact physical SH2 ambiguity: central density doubles and relative density $L^2$ error exceeds $14.52\%$, yet every external RGB ray is unchanged. We connect these continuum results to shared finite representations, continuous pixel measurements and density-sensitive acquisition. Complete-class certificates separate SH0, SH1 and SH2 fits at one learned density. Finite-camera results expose the distinct role of spatial capacity, and transmission measurements separate otherwise identical RGB fields. Controlled training tests and captured-smoke profiles supply mechanism evidence with explicit observation scopes. The results show why rendering accuracy alone cannot certify density: recovery also depends on appearance capacity, spatial resolution and measurement design.
Read the full abstract
Computation and Language
Is a 9B Decision Foundation Model Needed for Symptom-to-Disease Classification? Fine-Tuning Clef-Flash Against TF-IDF Baselines
Disease classification from patient-reported symptom descriptions is usually approached with lightweight discriminative models or with autoregressive large language models (LLMs), which understand language broadly but generate text token by token and require output parsing. We study decision foundation models, which score a closed set of candidate labels in a single forward pass without generating text. We adapt Clef-Flash, a 9-billion parameter decision model built on a Qwen3.5 backbone, to the 24-class Symptom2Disease benchmark using 4-bit quantized low-rank adaptation (QLoRA) on a stratified split of 960 training and 240 test cases. The fine-tuned model reaches 95.42% accuracy (95% CI 91.98-97.42%) and a macro F1 of 0.9551, up from 65.00% for the unadapted weights (62.92% through the remote API). However, TF-IDF linear SVM and logistic regression baselines trained on the same split reach 98.75% (95% CI 96.39-99.57%) with sub-millisecond CPU inference, so on this benchmark the fine-tuned model offers no accuracy advantage over a well-tuned linear classifier. A Leave-One-Symptom-Out clause-ablation analysis of four illustrative narratives shows predictions depending on distinguishing clauses: in a psoriasis example, removing the clause describing silvery scales lowers the predicted probability from above 99.99% to 0.12% and shifts the prediction to impetigo, while removing other clauses changes it by less than 0.001 percentage points. Decision architectures deliver structured, single-pass predictions from large language backbones, but short, lexically distinctive benchmarks such as Symptom2Disease cannot show an advantage over simple baselines; validation on longer, real clinical text and clinician review are needed.
Read the full abstract
Computation and Language
UltraBERT: Beyond the Limit of BERT Pre-Training
Recent bidirectional encoders have been modernized with innovations from causal large language models (LLMs). However, the pretraining recipe itself remains inherited from small-scale conventions, leaving encoders underoptimized, with no single model performing competitively across both classification and retrieval tasks. In this work, we investigate how far encoder performance can be pushed by revisiting core design choices in training, revealing three key findings: (1) Encoders saturate on downstream tasks beyond a few trillion tokens, indicating that additional compute past this point does not help. (2) Across model sizes, lower masking ratios benefit classification while higher ones benefit retrieval, contradicting prior work suggesting larger ratios for larger models. (3) Distillation with pruning improves classification at low masking ratios but degrades retrieval at high ones. Guided by these findings, we present UltraBERT, a single encoder that assigns separate LM heads to low and high masking ratios within a batch and restricts the distillation objective to the low ratio. To our knowledge, UltraBERT is the first encoder to achieve state of the art on both classification and retrieval tasks, reaching 91.0 on GLUE and 47.7 on BEIR. Together, these results show how far encoder performance can be pushed and provide a principled basis for compute allocation, masking ratio design, and knowledge transfer in bidirectional models.
Read the full abstract
Statistics Theory
Recurrent Barycenter Encoder: Prediction, Simulation and Applications to Time Series Analysis
This dissertation has two parts. In the first part we theoretically develop a framework that extends the optimal transport barycenter problem from independent data with observed covariates to processes whose relevant covariate is their own history. Given a stationary stochastic process, our framework shows there exists an invertible transport map that extracts from it an iid component whose distribution is the barycenter of the conditional distributions of the input process on its own past. This extracted iid sequence thus captures the innovation or noise component of the process that is not explained by the process's own past. In the second part of this thesis we implement an effective algorithm to solve this problem and test it against synthetic data generated with some well-known models in time series analysis for which the solution is known in closed-form. We then show how this method can be applied to build a predictive sampler for such processes, and assess the accuracy of this predictive sampler both with the aforementioned synthetic data and with real-world time series such as the S&P 500 and Bitcoin 4-hour returns, and the daily records of the North Atlantic Oscillation index from the NOAA Physical Sciences Laboratory. Finally, we demonstrate an application of the sampler to path simulation with a well-known time series model.
Read the full abstract
Human-Computer Interaction
EnRoute: Iterative Design and Evaluation of a Mobile App for Lower-Carbon Fashion and Transportation Choices
EnRoute is an iOS application designed to support more sustainable everyday choices in transportation and fast fashion consumption. We describe three design iterations and the user research and field evaluations that shaped each one. Interviews with 15 people from 12 countries informed Version I, which combined errand route planning with basic fashion guidance. A survey of 1,200 people in five countries found much stronger interest in sustainable shopping (78%) than in switching to lower-carbon transport (46%); respondents most often named limited public transport as the main barrier to lower-carbon travel. We therefore narrowed the focus to fashion. Version II added item-level garment scanning with a manual-entry fallback, a Sustainability Coefficient that rates items, and recommendations of more sustainable alternatives; in a two-week evaluation with 3,021 participants in eight countries, participants randomly assigned to receive a short tutorial and educational prompts viewed more recommended alternatives and reported larger gains in purchase intent than those without it. Version III shifted from "buy better" to "buy less," adding a wardrobe inventory, outfit matching, and a "Real Price" that combines cost per wear with estimated environmental and social costs. In a four-week pre/post pilot with 500 participants, self-reported monthly garment purchases fell from 2.9 to 1.9. We report descriptive results, discuss the substantial limitations of these uncontrolled and self-reported measures, and outline what the iterations suggest about designing for sustainable consumption.
Read the full abstract
Optimization and Control
Mean-Variance Portfolio Selection: Statistical Properties and Distributionally Robust Optimization
We study Markowitz's mean-variance portfolio optimization problem. When practically using this model, the mean vector and the covariance matrix of the assets returns often need to be estimated from the sample data. The sample errors will be propagated to the optimization output. In this paper, we consider three commonly used mean-variance models and build the asymptotic properties for the conventional sample approximations that are widely adopted and studied, by leveraging the stochastic optimization theory. We show that for all three models, under certain conditions the sample approximations have the desired consistency and achieve a convergence rate of square root of sample size, and the asymptotic variance depends on the first four moments of the returns. To address the variability and the uncertainty in the data driven portfolio optimization, we further consider the distributionally robust optimization (DRO) for the mean-variance model. For the ambiguity sets constructed by the $\phi$-divergence and the Wasserstein distance, we build the tractable reformulations for the DRO models. We conduct numerical experiments to test the asymptotic properties for the estimation. We also conduct experiments to illustrate that the asymptotic normality might not hold when the fourth moments of the returns do not exist.
Read the full abstract
Combinatorics
Sharp lower bounds for bisections of graphs with bounded maximum degree
A bisection of a graph is a partition of its vertex set into two parts whose sizes differ by at most one. We prove that every graph with $m$ edges and maximum degree at most $k$ has a bisection of size at least $\frac{k+1}{2k}m$ when $k$ is odd, and at least $\frac{k+2}{2(k+1)}m$ when $k$ is even. Both bounds are sharp, with equality for complete graphs. This establishes the unweighted case of the bisection conjecture of Gerke, Gutin, Yeo and Zhou (arXiv 2024), removes the additive error from the corresponding bounds of Lee, Loh and Sudakov (JCTB 2013), and extends the odd-degree regular case proved by Bollobás and Scott (JGT 2004) to arbitrary graphs of bounded maximum degree. The proof combines the matching-and-pairing method with the Gallai–Edmonds decomposition. Hall's theorem controls the number of uncovered factor-critical components whose internal degrees are all even. A boundary-edge count bounds this obstruction by the total degree deficiency, while the remaining uncovered components supply the required pairing gain.
Read the full abstract
Dynamical Systems
Dynamical Properties of Perturbed Weighted Shifts
In this paper, sufficient conditions are established for diagonal perturbations of weighted shifts to be supercyclic, hypercyclic, and frequently hypercyclic, extending several classical results for weighted shifts to this more general setting. In addition, a complete analytic characterization of the shadowing property for these operators is obtained. Consequently, examples of frequently hypercyclic perturbed weighted shifts with the shadowing property are constructed.
Read the full abstract
Materials Science
Graphene-Confined Growth of Few-Layer PtSe2 via One-Step Selenization
Platinum diselenide (PtSe$_2$), a member of the transition metal dichalcogenide (TMD) family, is a promising material for next-generation electronic and optoelectronic applications due to its thickness-dependent properties, transitioning from semimetallic in bulk to semiconducting behavior at the few-layer limit. However, the scalable fabrication of large-area ultrathin PtSe$_2$ films remains challenging, as conventional selenization of pre-deposited Pt layers often leads to undesired three-dimensional clustered growth. This work explores a novel strategy for promoting two-dimensional growth of PtSe$_2$ by employing a graphene-mediated confinement approach. The method involves coating a Pt layer with graphene oxide (GO), followed by annealing in a selenium atmosphere, which results in the simultaneous formation of PtSe$_2$ and the reduction of GO to graphene. The graphene overlayer acts as a physical confinement layer, suppressing vertical growth and enabling the synthesis of graphene-confined PtSe$_2$ heterostructures on centimetre-scale substrates and promoting lateral connectivity of PtSe$_2$ regions observed by STEM. Scanning transmission electron microscopy (STEM), including temperature-resolved in situ atomic-resolution measurements, was used to investigate the influence of selenization temperature on the growth mechanism and structural evolution of PtSe$_2$ films. The results show that graphene confinement stabilizes lateral growth and promotes the formation of few-layer films with improved structural ordering. Beyond PtSe$_2$, this graphene-assisted approach provides a general strategy for fabricating and stabilizing ultrathin TMD layers, including those prone to environmental degradation, providing a new outlook for enabling detailed studies of their intrinsic properties.
Read the full abstract
Quantum Physics
Entanglement detection in dynamical quantum systems
Quantum science and engineering increasingly target the exploitation and control of large-scale dynamical systems. As system size grows, novel phenomena and quantum advantages emerge, but the resulting many-body dynamics become correspondingly harder to monitor and characterize. In particular, the underlying Hamiltonian often lacks symmetries, and the induced many-body dynamics quickly become hard to track. Focusing on one of the most important quantum features—entanglement—we demonstrate that, for a broad class of common Hamiltonian models, one can design effective witnesses that detect both the presence and structure of entanglement over relatively long evolution times. Inspired by stabilizer-based simulation, we track the evolution of generalized stabilizers of the underlying state and use them to construct linear entanglement witnesses. Through numerical experiments on Heisenberg-type Hamiltonians with up to twelve qubits, we show that the required number of measurement settings can be kept at a modest scale as the system size increases, and entanglement detection remains effective over evolution times that significantly exceed those accessible to naive approaches. The corresponding calculations can be carried out largely symbolically. Furthermore, unlike accurate state simulation, the stabilizer-based design of entanglement witnesses can be performed in a much more coarse-grained, digitized manner. We hope these results will stimulate further exploration of the quantum control of large systems.
Read the full abstract
Machine Learning
PATTERN Can Be Solved from Memory: Generator-Aware Baselines for Synthetic Node Classification
PATTERN, a synthetic node-classification benchmark still used to rank graph networks, plants a random subgraph in a random host graph and asks which nodes belong to it. Its generator draws 100 patterns once and plants the same ones in every split, so each test graph carries a pattern that also appears in 100 training graphs. A matcher that reads these patterns off the training labels and looks them up in each test graph reaches 99.2 class-weighted accuracy with no trained parameters, against 89.8 for the best published model. Inference under the generator without the patterns reaches 86.8. Two published models, CKGConv and GRIT, score lower on patterns they have not seen: on new graphs with fresh patterns both fall below this pattern-blind predictor, and withholding patterns from CKGConv's training lowers its accuracy on the test graphs that carry them. Training CKGConv with a new pattern in every graph raises its accuracy on fresh patterns by about 2 points, to the level of the pattern-blind predictor, at some cost on the reused patterns. The same kind of inference under the generator matches the best published result on CLUSTER and, without any training, scores above every published result we found on Minesweeper's released board. We recommend that synthetic benchmarks report scores on fresh templates beside reused ones, publish baselines built from their generators, and state how their metric is weighted and pooled.
Read the full abstract
Functional Analysis
A counterexample concerning the coefficient formula for de Branges-Rovnyak norms
Let $\mathcal{H}(b)$ be the de Branges-Rovnyak space associated to a non-extreme point $b$ of the unit ball of $H^\infty$, and let $\phi=b/a$, where $a$ is the Pythagorean mate of $b$. In an earlier article, the author showed that, if $\phi\in H^2$, then \[ f\in\mathcal{H}(b) \iff \Bigl(f\in H^2 \text{ and }\sum_{m\ge0}\Bigl|\sum_{n\ge0}\overline{\hat{\phi}(n)}\hat{f}(m+n)\Bigr|^2<\infty\Bigr), \] in which case we have \[ \|f\|_{\mathcal{H}(b)}^2=\sum_{m\ge0}|\hat{f}(m)|^2 +\sum_{m\ge0}\Bigl|\sum_{n\ge0}\overline{\hat{\phi}(n)}\hat{f}(m+n)\Bigr|^2. \] It was also shown that there exists a space $\mathcal{H}(b)$ for which $\phi\in\cap_{p<2}H^p$, yet \[ f\in\mathcal{H}(b)\not\Rightarrow \sum_{m\ge0}\Bigl|\sum_{n\ge0}\overline{\hat{\phi}(n)}\hat{f}(m+n)\Bigr|^2<\infty. \] Here we complete this circle of ideas by showing that there exists a space $\mathcal{H}(b)$ for which $\phi\in\cap_{p<1}H^p$, yet \[ \Bigl(f\in H^2\text{ and } \sum_{m\ge0}\Bigl|\sum_{n\ge0}\overline{\hat{\phi}(n)}\hat{f}(m+n)\Bigr|^2<\infty\Bigr) \not\Rightarrow f\in\mathcal{H}(b). \]
Read the full abstract
Logic
Nonstandard combinatorial ultrafilters and a new local witness model
A central object in the theory of proof complexity generators is Krajicek's local witness model. We construct a new such model as a definable ultrapower using a definable version of a selective ultrafilter over a model of arithmetic. We transfer some set theory of combinatorial ultrafilters to the definable nonstandard setting.
Read the full abstract
Probability
Non-uniqueness for McKean–Vlasov SDEs with Hölder diffusion coefficients
We show that uniqueness may fail for one-dimensional McKean–Vlasov stochastic differential equations with Hölder continuous diffusion coefficients. More precisely, for every \(\alpha\in(1/2,1)\), we construct an equation with a diffusion coefficient that is \(\alpha\)-Hölder continuous in the state variable, Lipschitz continuous in the measure variable, and of linear growth, for which uniqueness in law and pathwise uniqueness fail. The construction relies on a spreading estimate together with a Schauder fixed-point argument.
Read the full abstract
Optimization and Control
An Exact Branch-Price-and-Cut Algorithm for a Truck-as-Hub Vehicle Routing Problem with Drones
Rural last-mile logistics remains challenging because of sparse demand, limited road infrastructure, and long travel distances. We study a Truck-as-Hub Vehicle Routing Problem with Drones in Rural Areas, in which multiple trucks each carry a dedicated fleet of drones. Drone launch and retrieval are restricted to predesignated passive synchronization pads, where a visiting truck temporarily acts as a mobile hub, may dispatch multiple drones simultaneously, and must wait until all launched drones return before continuing its route. We formulate a mixed-integer quadratic programming model that jointly accounts for customer delivery delays, truck return times, and operating costs. To solve the problem exactly, we transform the original truck–drone network so that each feasible route can be represented as a single path and develop a branch-price-and-cut algorithm with tailored pricing, cutting, branching, and parallel-computing procedures. Computational experiments show that the proposed algorithm proves optimality for most large-scale test cases and achieves optimality gaps of no more than 4% for the remaining cases, whereas Gurobi reaches the 1,800-second time limit on all large-scale instances when applied directly to the compact formulation. Sensitivity analyses show that drone operating costs and managerial priorities substantially affect drone utilization and customer delays, providing practical guidance for balancing service quality and operating cost in rural delivery systems.
Read the full abstract
Machine Learning
Algorithmic Fairness Over Time: Advances & Prospects
In the presence of feedback loops, algorithmic decisions at one time step can influence observed data in subsequent steps, potentially introducing selection bias or shifts in data distribution. Research has demonstrated that ignoring these effects can lead to unfairness, which may worsen over time as the model remains deployed within society. This raises important questions of how to measure and ensure fairness of algorithmic decision-making models over time. In this short paper, we present a taxonomy that distinguishes between different types of static and temporal fairness notions in recent advancements. We then suggest prospects for future research by identifying common implicit temporal assumptions, open questions to enhance our temporal understanding of fairness, and other open challenges.