Peer Revenue Publish or profit

Papers

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

All of arXiv

Monday 7 September

Computation and Language

LLM Agents as Computational Typologists

Linguistic typology relies on expert analysis of reference grammars across languages, making large-scale crosslinguistic comparison labor-intensive and unscalable. We introduce AUTOTYPOLOGIST, an LLM agent for evidence-grounded typological analysis over reference grammars. The agent is capable of retrieving relevant grammar sections, analyzing interlinear glossed text (IGT), and iteratively reasoning over typological hypotheses using a ReAct-style workflow. We evaluate the system on TYPOLOGICAL FEATURE CODING against expert annotations and TYPOLOGICAL HYPOTHESIS TESTING with typological universals using 25 open-source reference grammars. Operating under different information constraints in TYPOLOGICAL FEATURE CODING, the agent can synthesize information from reference grammar prose but still faces challenges with only IGTs in the target language. In TYPOLOGICAL HYPOTHESIS TESTING, the agent can synthesize crosslinguistic evidence and identify both supporting cases and counterexamples. These findings suggest that LLM agents can support scalable and inspectable typological analysis, while still requiring expert validation.
Read the full abstract

All authors Changbing Yang, Christopher Hammerly, Freda Shi, Jian Zhu

Metric Geometry

Extension properties of planar subsets supporting a weak $(1,1)$-Poincaré inequality

We study Sobolev and $BV$-extension properties of planar subsets. In particular, we prove that fat Sierpiński carpets that support a weak $(1,1)$-Poincaré inequality are $W^{1,1}$-extension sets, and we provide an explicit linear extension operator for them. We also show that for planar domains satisfying a weak $(1,1)$-Poincaré inequality the $W^{1,1}$-extension property and the $BV$-extension property are equivalent. Finally, as a consequence of the previous result, we show that if a simply-connected planar domain is Ahlfors regular and supports a weak $(1,1)$-Poincaré inequality, then it is a (linear) $W^{1,1}$-extension domain.
Read the full abstract

Probability

Discrete Approximation to Time-changed Brownian Motions

We develop a general discrete approximation scheme for time-changed Brownian motions on $\mathbb{R}^d$. Our approximation scheme works for any smooth measure with full quasi-support on $\mathbb{R}^d$ with suitable initial distributions. Under some mild conditions on the smooth measure, the discrete approximation scheme works for every starting point. Our results in particular give a discrete approximation scheme for Liouville Brownian motions.
Read the full abstract

High Energy Physics (Theory)

Eikonal Scattering of Two D0-branes with Graviton Emission

We study the emission of a massless closed-string state in the scattering of two D0-branes using the boundary-state formalism. We compute the corresponding five-point amplitudes for graviton and dilaton emission in bosonic string theory and in type II superstring theory, and analyze their field-theory limit. For nonzero impact parameter, the resulting amplitudes are reproduced by an independent calculation in the worldline formulation of the corresponding low-energy theory.
Read the full abstract

Optimization and Control

The Price of Feasibility: Greedy Approximation Bounds for String Supermodular Optimization over Oracle-Conditioned Greedoids

Greedy algorithms efficiently approximate combinatorial optimization problems, but their guarantees weaken when feasibility couples combinatorial structure with global physical constraints. We study monotone nondecreasing supermodular minimization over the bases of a graphic greedoid under physics-induced constraints. We model physics-informed selection using a look-ahead oracle that identifies candidates extendable to a feasible basis, yielding the Conditioned Sequential Greedy Algorithm. We derive a closed-form approximation bound, which we call the price of feasibility, based on the variability of oracle-restricted candidate sets and a probabilistic correction for unobserved elements. As a case study, we show that FORWARD, an algorithm for multi-source radial network reconfiguration, instantiates this framework. Numerical results demonstrate the tightness of the bound and quantify the feasibility-optimality trade-off.
Read the full abstract

Computation and Language

Signed Rescue Routing: Harm-Aware Cascades for Efficient LLM Inference

Large language model (LLM) cascades answer easy requests with a small model and escalate selected requests to a larger model. Most routers prioritize examples on which the small model appears uncertain or likely to be wrong. This proxy ignores a decisive fact: escalation is useful only when the large model corrects the small model, and it is harmful when the large model replaces a correct answer with an incorrect one. We introduce Signed Rescue Routing (SRR), a budgeted routing method that predicts these two events separately and ranks requests by their difference. We show that this signed conditional gain is the Bayes-optimal routing score under a fixed escalation budget. SRR requires only the small model's output statistics at deployment and adds a lightweight two-head router. We evaluate SRR with Qwen3-4B and Qwen3-8B on TBD examples from MMLU, HellaSwag, and ARC-Challenge. Across the accuracy-compute curve, SRR reaches an area of TBD, compared with TBD for a learned small-model error predictor and TBD for entropy routing. These results show that predicting incremental value, rather than model uncertainty, is a simple and effective objective for efficient LLM cascades.
Read the full abstract

All authors Zheyuan Wang, Siyu Li, Peiqiao Song, Sijia Chen, Qianqian Song, Qian Liu

Artificial Intelligence

What Does an LLM-Agent Leaderboard Rank Actually Compare?

An LLM-agent leaderboard invites a familiar inference: an agent ranked above another is the better agent. Public evaluation logs may not support that conclusion when systems differ in task mixture, label source, release detail, or cost rule. We study what leaderboard scores estimate and when they justify pairwise superiority conclusions. Our estimand-aware pairwise procedure states the comparison target and measurement source, checks common support, and evaluates the supported difference using a stated uncertainty rule and practical margin. Controlled checks evaluate the decision labels under known finite-sample conditions and show why uncertainty must be included when judging sensitivity to target reweighting. Across SWE-bench, AgentRewardBench, and tau2-bench, close rank differences are often unresolved; proxy labels and utility rules can also change which system is selected. DataAgentBench and Open Agent show what remains estimable from coarser public records. A leaderboard score summarizes a released evaluation, whereas a fine-grained superiority claim additionally depends on the estimand and uncertainty rule used to interpret the difference.
Read the full abstract

Artificial Intelligence

xDailyBench: Benchmarking LLMs on Professional Consultation for Real-Life Problems

Large language models (LLMs) are increasingly used for everyday assistance, yet existing benchmarks only partially reflect the requests users naturally make in practice. Real-world requests are often open-ended, casually specified, and context-dependent, requiring models not only to follow explicit instructions but also to infer unstated needs from user background and situational context. We introduce xDailyBench, a benchmark of 248 carefully curated tasks spanning 51 scenarios across personal life, white-collar work, learning and research, and cross-domain activities. The tasks are grounded in requests that users have actually completed or genuinely intended to accomplish with AI, and are evaluated with fine-grained binary rubrics covering both explicit and implicit requirements. We evaluate 11 frontier models under standardized agentic settings. The best models achieve a task-level score of 75.6%, while all models perform substantially worse on implicit than explicit requirements, with gaps no less than 9 percentage points. These results reveal implicit requirement inference as a persistent bottleneck for reliably satisfying real-world everyday user needs.
Read the full abstract

All authors Yongchang Peng, Qingshui Gu, Liya Zhu, Ge Zhang, Duo Wang, Haodong Wang, Jingzhe Ding, Tianhao Yu, Letian Gao, Yongjie Zhong, Chaoxin Li, Zixin Su, Jinchao Tao, Xingyu Ma, Xin'ao Guo, Feng Tian, Shiyuan Dong, Xiaoyan He, Sen Liu, Xin Chen, Jiajun Li, Zejia Zhang, Xi Lin, Wen Zhang, Yi Zhu, Duju Zeng, Xiang Gao, Yunyang Wang, Jiahao Wang, Yujia Qin, Jiaheng Liu, Shen Yan, Xiaolong Chang, Wenhao Huang

Cryptography and Security

Grid Trouble in Paradise: Uncovering Vulnerable Distributed Energy Resources and Their Grid-Level Risks

Grid-connected solar distributed energy resources (DERs), such as solar inverters and monitoring platforms, have been deployed at unprecedented scale over the past few years, with global solar capacity more than doubling since 2022. To support monitoring and control, many of these systems are Internet-connected and configured by installers or end users, yet the real-world scale of their Internet exposure and the implications for power grid operation remain poorly understood. In this paper, we present an Internet-scale evaluation of exposed and vulnerable solar DER infrastructure, and assess the risk that compromised DERs can pose to energy grids. We develop a method for accurately identifying solar DERs from Internet scanning data, and discover a diverse population of over 66,000 Internet-exposed solar DERs. We detect that at least 10,000 of these DERs may have known CVEs, such as unauthenticated monitoring and control endpoints. To assess the risk that these vulnerable DERs pose to a power grid, we use an electric grid network for Oahu, Hawaii, established and used by the power system research community, and conduct a power system analysis. Our evaluation shows that by compromising exposed DERs, attackers can cause voltage and line flow violations across multiple locations in the Oahu network, resulting in a range of consequences from degraded power quality to damaged power system components to power outages. Ultimately, our work brings to light the emerging threat of grid-connected DERs, and provides directions for improving energy security.
Read the full abstract

All authors Anna Raymaker, Samuel Talkington, Zeezoo Ryu, Richard Asiamah, Emad Abukhousa, Betelihem Ashebo, Animesh Chhotaray, Daniel K. Molzahn, Frank Li, Saman Zonouz, Raheem Beyah

Databases

TrajectoryDB: A New Database for Agent Trajectories

AI agents generate rich execution trajectories that capture their interactions with large language models, tools, and external environments. These trajectories are increasingly valuable for downstream tasks such as memory extraction, model fine-tuning, runtime optimization, and security and cost monitoring. Yet trajectory data today is fragmented across files, databases, and observability systems, with no persistent data management system designed around its unique structure and access patterns. We argue that trajectories should be treated as a distinct data type. A trajectory combines hierarchical execution structure, large volumes of text whose analysis often requires semantic reasoning, and rich dependencies and lineage among events, intermediate states, and derived artifacts. These properties introduce new requirements throughout the data lifecycle. Ingestion must reconstruct and preserve execution structure and lineage; storage must efficiently organize large but highly redundant contexts while maintaining relationships among records; and query processing must jointly reason over structure, temporal order, semantics, and lineage. We therefore envision TrajectoryDB, a trajectory-native data management system that co-designs ingestion, storage, and query processing to efficiently manage and analyze agent execution trajectories.
Read the full abstract

Lattice Field Theory

Sector-Resolved Flow Sampling for Topologically Frozen Lattice Gauge Theories

Topological fluctuations are essential to nonperturbative gauge theories but become increasingly difficult to sample toward the continuum limit, where Markov chains can freeze in sectors of fixed topological charge. We introduce a generative sampler, a mixture of sector-resolved samplers (MSRS) that explicitly resolves these sectors and exploits a key advantage of generative models, the ability to directly evaluate the domain-restricted partition function and thereby determine the relative weights of disconnected sectors. We train a generative model in a reference topological sector combined with a bijective topological shift that deterministically maps its samples to other sectors. We demonstrate the method in two-dimensional compact U (1) lattice gauge theory, where it reproduces the topological-charge distribution and yields an unbiased susceptibility in a regime where hybrid Monte Carlo is frozen and overrelaxation gives inaccurate estimates. Our approach also outperforms existing flow-based samplers by orders of magnitude. These results demonstrate that explicit sector resolution provides a promising route to overcoming topological barriers in lattice gauge theory.
Read the full abstract

All authors Ankur Singha, Jacob Kauffmann, Karl Jansen, Jacob Finkenrath, Vipul Arora, Shinichi Nakajima

Computer Vision

DroneGround: Open-Vocabulary Drone Payload Characterization Using Synthetic Data and Grounded Vision-Language Models

Automated drone surveillance has become increasingly important for public safety, critical infrastructure protection,and restricted airspace monitoring. While existing vision-based systems achieve strong performance for drone detection and tracking, reliable payload characterization remains highly challenging under long-range imaging conditions due to limited availability of annotated real-world datasets, and substantial distribution shifts encountered during deployment. Existing approaches formulate payload characterization as a closed-set object detection problem, limiting their ability to recognize previously unseen payloads and generalize beyond the training distribution. To address these challenges, we generate a photorealistic synthetic drone-payload dataset using Unreal Engine 5 and Cosys-AirSim and propose DroneGround: Grounded Vision-Language Payload Characterization, a two-stage framework for robust open-vocabulary payload analysis. DroneGround first employs a YOLO26s detector to localize drones and extract drone-centric image crops, followed by a LoRA-fine-tuned PaliGemma vision-language model that generates seman- tic descriptions of the detected drones and their attached payloads, enabling open-vocabulary payload characterization beyond predefined categories. An occlusion-based grounding module further provides interpretable payload localization by identifying image regions responsible for the generated descriptions. Extensive experiments on both synthetic and real-world drone imagery demonstrate that DroneGround substantially improves robustness under synthetic-to-real distribution shifts, outperforming a conventional closed-set payload detector by improving the F1-score from 82.5% to 96.3%, while achieving significantly better generalization to previously unseen payload categories (80.4%versus 42.7% F1). Dataset and code will be released upon request.
Read the full abstract

All authors Ami Pandat, Rajasekhar Punna, Gopika Vinod, Rohit Shukla

Software Engineering

CodeTD: Topology of Attention Detects Hallucinations in Code LLMs

As AI-code assistant tools become widespread, automatic assessment of the correctness of generated code becomes a significant challenge. Code LLMs are prone to hallucinations, which may lead to code that does not solve the required problem, or even to code with severe security vulnerabilities. In this paper, we introduce CodeTD – the first approach to pre-execution assessment of code correctness based on topological data analysis (TDA) of Code LLMs' attention maps. Our method quantifies prompt-generation mismatch using topological patterns of attention maps. We carry out experiments with common benchmarks (HumanEval, MBPP, BigCodeBench, MultiPL-E), 5 programming languages and 10 Code LLMs of size up to 34B parameters. The experimental results show that the proposed method outperforms recent baselines. Moreover, CodeTD is transferable between coding benchmarks.
Read the full abstract

All authors Daria Voronkova, Ilya Trofimov, Anton Dmitriev, Eduard Tulchinskii, Evgeny Burnaev, Serguei Barannikov

Metric Geometry

Gromov-Hausdorff Distances Between Spheres: Asymptotics and Vietoris-Rips Coindex Bounds

For $1\le m<n$, let $c_{m,n}$ be the infimum of the scales $r$ at which the Vietoris-Rips simplicial complex of the unit round sphere $\mathbb{S}^m$, equipped with its geodesic metric, admits a continuous odd map from $\mathbb{S}^n$. Previous work established the lower bound $\frac{1}{2}c_{m,n}\le d_{\mathrm{GH}}(\mathbb{S}^m,\mathbb{S}^n)$ through a quantitative Borsuk-Ulam theorem and raised the question of whether it is always sharp. We show that this bound can underestimate the distance by a factor arbitrarily close to two, the largest possible factor. Combining projective-code upper bounds for $c_{m,n}$ with lower bounds for $d_{\mathrm{GH}}$ obtained from obstructions to homomorphisms between Borsuk graphs, we obtain explicit finite-dimensional bounds. Along sequences of pairs $1\le m<n$, we have $c_{m,n}\to\frac{\pi}{2}$ whenever $\log n/m\to0$, while $d_{\mathrm{GH}}(\mathbb{S}^m,\mathbb{S}^n)\to\frac{\pi}{2}$ whenever $m/n\to0$. When both conditions hold (for example when $n=m^2$) the ratio of the distance to $\frac{1}{2}c_{m,n}$ tends to two. For each fixed $m\ge3$, the inequality is strict for all sufficiently large $n$.
Read the full abstract

Systems and Control

Distributed Droop-Free Control of Grid-Forming Inverters with Dynamic Line and Load Modeling

Droop-free distributed control has emerged as a promising alternative to conventional linear droop control for coordinating inverter-based resources in AC microgrids. However, existing droop-free methods typically rely on quasi-steady state network models that neglect fast electromagnetic transients and assume a decoupled dependence of active and reactive power on frequency and voltage, respectively. In this paper, we propose a transient-aware droop-free distributed primary/secondary control framework for grid-forming (GFM) inverters. The control objective is to achieve proportional active and reactive power sharing, frequency regulation, and voltage regulation within prescribed bounds. The proposed approach incorporates dynamic models of network lines and loads into the control design, enabling accurate representation of transient behavior while capturing the coupled nature of power flow interactions. A gradient-based distributed control update is derived from an optimization formulation, in which voltage magnitude constraints are enforced through a projection operator. To validate the performance of the proposed control, real-time simulation studies are conducted on a four-inverter microgrid under load changes in both strong and weak grid conditions. The results demonstrate that the proposed method improves transient performance, particularly in weak grids, while preserving the same steady state operating conditions as existing QSS-based droop-free approaches.
Read the full abstract

Quantum Physics

QROB: Quantifying Realization Overhead in Quantum Compilation via Reverse Construction

Quantum compilation reconciles a program's idealized interaction topology with hardware locality constraints, yet evaluations at scale lack calibrated references for realization overhead. We present QROB, a scalable reverse-construction methodology that generates compilation instances backward from directly realizable configurations, retaining the inverse paths as feasible, compiler-independent references. QROB provides a common evaluation substrate for NISQ SWAP routing and fault-tolerant lattice-surgery scheduling, while extending its reference-preserving principle to capacity-constrained quantum memory-access scheduling. Across systems ranging from 9 to 156 qubits, evaluations highlight QROB's utility as both a diagnostic benchmark and a data source. First, for compiler characterization, QROB reveals substantial realization gaps in existing tools, with NISQ compilers incurring up to 24.1x the reference SWAP cost and fault-tolerant compilers requiring up to 7.0x the reference makespan. Second, as a supervision source for data-driven compilation, a router trained on QROB references outperforms Qiskit SABRE on 84.8% of real-world application circuits. Finally, on real hardware, QROB reference realizations achieve a median mirror-circuit survival rate 1.65x that of full Qiskit O3 compilations across three 156-qubit IBM Heron-r2 processors, demonstrating that closing algorithmic compilation gaps translates directly into physical fidelity gains.
Read the full abstract

All authors Jintao Li, Kaiqi Li, Rui Wang, Yilun Zhao, Kaixuan Huang, Ying Wang, Jialin Zhang, Zheng-An Wang, Xiaoming Sun, Heng Fan

Mesoscale and Nanoscale Physics

Simple invariants for band topology

Despite the exhaustive understanding gathered around non-interacting topological states of matter, there is no single method capable of systematically delivering simple, numerically efficient topological invariants that is applicable to all crystalline and non-crystalline systems alike. Here we revisit the spectral localizer operator, constructed from the Hamiltonian and position operators, and show how it can be treated it as an auxiliary zero-dimensional Hamiltonian whose topology encodes the higher dimensional phases of the parent Hamiltonian. Its classification reduces every topological invariant to a matrix signature or the sign of a Pfaffian for an appropriate localizer, both of which are simple to interpret and efficient to compute in real space. We validate this approach by deriving simple real-space invariants for weak and rotationally invariant crystalline phases that were previously beyond the grasp of the spectral localizer formalism, atomic limits that escape scattering invariants, phases that evade symmetry-based indicator methods, as well as phases that had no previously known invariant. Our work provides a systematic way to construct any non-interacting topological invariant for a crystalline or non-crystalline systems, opening avenues to classify and predict the topology of previously unexplored classes of materials.
Read the full abstract

Instrumentation and Methods for Astrophysics

Search for Long-Transient Gravitational Waves from Supernova SN2023ixf using GFH-v2 Pipeline

We present a directed search for long-transient gravitational waves from the possible newborn magnetar remnant of SN2023ixf, a nearby Type II core-collapse supernova in the M101 galaxy. The analysis uses LIGO Hanford and Livingston data from Engineering Run 15, using coincident data lying within the on-source window associated with the supernova. We target signals from a rapidly rotating, non-axisymmetric neutron star whose spin-down is dominated by gravitational-wave emission, producing a power-law decrease in frequency and a corresponding decrease in strain amplitude. The search is performed with the GFH-v2 pipeline, based on the Generalized Frequency Hough transform. No candidate survives the coincidence and follow-up analysis. We therefore set upper limits on the maximum detectable distance as a function of initial frequency and ellipticity. For the highest ellipticity interval, the 90% upper limits reach distances of about 1-2.5~Mpc across most of the analysed band. Although these limits are below the distance to M101, the search provides the first application of GFH-v2 to a nearby core-collapse supernova and characterizes its performance on real detector data.
Read the full abstract

All authors Sandhya Sajith Menon, Lorenzo Pierini, Pia Astone, Cristiano Palomba, Francesco Safai Tehrani, Lorenzo Silvestri, Ornella Juliana Piccinni, Simone Dall'Osso, Stefano Dal Pra, Sabrina D'Antonio, Sergio Frasca, Dafne Guetta, Paola Leaci, Michal Bejger, Alicia Calafat, Evan Goetz, Rafel Jaume Amengual, Ian Jones, David Keitel, Andrzej Krolak, Iuri La Rosa, Andrew Melatos, Joan-Rene Merou, Lorenzo Mirasola, Claudio Salvadore, Alicia M. Sintes, Karl Wette

Materials Science

High-Field Electron Transport in AlGaN alloys: A Full-Band Monte Carlo Study Based on Ab Initio Supercell Calculations

AlGaN alloys are promising wide and ultra-wide-bandgap semiconductors for next-generation power and RF electronics applications. To realize the full potential of AlGaN based devices, it is important to understand the electron transport to accurately predict device performance and identify material limits under various operating conditions. In this work, the high-field electron transport properties of AlxGa1-xN are investigated using a supercell based full band Monte Carlo method. The supercell approach is employed to explicitly capture the true disorder of the alloy system, enabling a more realistic description of carrier transport. The velocity field characteristics are calculated across a range of Al compositions to evaluate key transport metrics, including peak velocity, saturation velocity, and critical electric field. The role of different scattering mechanisms is studied in detail to understand the high field transport mechanism in the AlGaN alloy system. In addition to steady state transport, transient electron dynamics are examined for various Al fractions to study velocity-overshoot behavior, which is especially important for improving the performance of scaled RF devices. Finally, the temperature dependence of the velocity field characteristics in ultra-wide-bandgap Al0.75Ga0.25N is investigated to assess its transport performance under high temperature conditions. These results provide a detailed understanding of high-field transport in AlGaN alloys and offer guidance for the design of AlGaN-based RF and power electronic devices.
Read the full abstract

Analysis of PDEs

On the effective sharp stability of the Faber-Krahn inequality

We prove the sharp quantitative Faber–Krahn inequality with a computable dimensional constant, resolving a problem posed by Brasco and De Philippis~\cite[Open Problem~2]{brasco2017spectral}. In contrast with the known proof of the sharp estimate, our argument avoids indirect compactness arguments and selection principles. It runs through a new level-set proof of the Saint–Venant inequality, using that the torsional deficit controls both the average isoperimetric deficit and the oscillation of the gradient magnitude along the boundaries of level sets. An effective local strong isoperimetric estimate for confined sets then yields the result.
Read the full abstract

Probability

Efficient computation of the asymptotics of extensive-rank HCIZ integrals

We study the high-dimensional asymptotics of Harish-Chandra-Itzykson-Zuber (HCIZ) integrals in the extensive-rank regime. The limit of these integrals is governed by a one-dimensional boundary-value hydrodynamical problem originally derived by Matytsin (1994) and rigorously proved by Guionnet and Zeitouni (2002). Despite its wide-ranging applications, explicit solutions to this problem are known only in a few specific cases. In this work, we introduce an efficient numerical scheme based on a particle discretization and prove its convergence to the continuous boundary-value problem for generic boundary densities. We validate our approach against known analytical solutions and apply it to generic densities, uncovering interesting dynamical phenomena. The high-dimensional limit of HCIZ integrals appears in various contexts, from the large deviations of random matrix spectra to the limiting free energy of disordered systems, high-dimensional statistics, and machine learning. As such, our contribution opens the way towards the numerical exploration of a wide range of high-dimensional models that were previously intractable.
Read the full abstract

Analysis of PDEs

The Dirichlet problem for a non-commutative elliptic operator in the ball

In this paper we establish a necessary and sufficient condition for the solvability of the Dirichlet problem in the unit ball $\mathbb{B}$ for the second order system $\partial_{\underline{x}} f\partial_{\underline{x}}=0$, where $\partial_{\underline{x}}$ stands for the Clifford-algebra valued Dirac operator in $\mathbb{R}^m$. We prove that the problem admits a solution whenever the boundary data belong to $C^1(\partial\mathbb{B})$. Conversely, we construct explicit counterexamples showing that solvability may fail if this smoothness assumption on the boundary is not satisfied. Moreover, in contrast with the standard commutative setting, we show how that solutions exhibit a regularity one order less than the boundary data, when the latter belong to $C^{k,\nu}(\partial\mathbb{B})$.
Read the full abstract

Information Theory

A Note on Binary Quadratic Systems and their relation to complexity theory

Deciding whether a system of multivariate quadratic equations over $\mathbb F_2$ has a solution is a classical NP-complete problem, and remains so for square systems, with as many equations as variables. The hardness of this problem is one of the cornerstones of nowadays post-quantum cryptography. Let $\MQ_0(n)$ and $\MQ_1(n)$ denote the sets of square quadratic systems in $n$ variables having respectively no solutions and exactly one solution. $\cup_{n\geq 2} \MQ_0(n)$ is a coNP-complete language, while $\cup_{n\geq 2} \MQ_1(n)$ lies in DP. It is known that $\lim_{n\to \infty} |\MQ_1(n)|/|\MQ_0(n)|=1$. Here we prove the explicit finite-$n$ bounds \[ |\MQ_0(n)|<|\MQ_1(n)| \le \left(1+\frac{1}{2^n-1}\right)|\MQ_0(n)|, \] More generally, let $Q_d$ be the space of polynomial functions $(\FF_2)^n\to\mathbb F_2$ of degree at most $d$, and let $\alpha_k$ count square systems in $(Q_d)^n$ having exactly $k$ solutions. Then \[ \alpha_0<\alpha_1 \le \left(1+\frac{1}{2^n-1}\right)\alpha_0\,, \qquad 2\le d\le n \,. \] The proof combines matroid and coding-theoretic methods. We interpret $(\FF_2)^n$ as the ground set of the evaluation matroid of $Q_d$, express $\alpha_0$ and $\alpha_1$ through characteristic polynomials, and use a Whitney-type sign-reversing involution to show that the only terms that can push $\alpha_1-\alpha_0$ below $\alpha_1/2^n$ come from the elements of a matroid port. These are identified with minimal-support words of the Reed–Muller code $\RM(n-d-1,n)=\RM(d,n)^\perp$; the required estimate then follows from the MacWilliams identity, the minimum-distance bound $2^{d+1}$, and the even-weight structure of the code.
Read the full abstract

Probability

Weighted isoperimetry implies percolation

Consider an infinite edge-weighted graph satisfying an isoperimetric inequality of the type $\|\partial A\|\geq C|A|^\alpha$ for some $\alpha,C>0$, where $\|\partial A\|$ denotes the weighted size of the edge boundary of $A$. We prove that, for $C$ large enough depending on $\alpha$, if each edge is open independently with probability given by its weight, then any vertex is connected to infinity with positive probability. The result also holds under weaker isoperimetric assumptions and on finite graphs. The proof brings a new perspective on the recent proof of the Benjamini–Schramm conjecture concerning the same problem with homogeneous weights. The crucial novelty in our proof is that, rather than simply counting cutsets, we introduce a new Peierls argument which takes into account internal and external connectivity costs in addition to the cost of the blocking surface. We provide two applications for the above result. First, we show that every non-summable long-range percolation on $\mathbb{Z}^d$, $d\geq 2$, admits a percolating truncation, solving a conjecture of Sidoravicius, Surgailis and Vares and its generalization by Friedli and de Lima. Secondly, we show that there exists a universal constant $C < \infty$ such that $p_{\mathrm{c}} \leq C/\Delta$ for every transitive graph of superlinear growth and vertex degree $\Delta$, thus proving a conjecture of Easo and Hutchcroft.
Read the full abstract

Optimization and Control

Submodular Welfare under Routing Coupling: A Hierarchical Decomposition with Perturbation Guarantees

This paper studies joint submodular welfare maximization and routing over graphs, where agents select items under diminishing returns and transport them through a network with congestion-dependent costs. Although welfare maximization admits matroid-based approximations and routing reduces to shortest paths under modular costs, their coupling creates supermodular interactions that break separability. We show that, for fixed routing, the objective remains submodular in the allocation variable, enabling a principled decomposition. Building on this property, we propose the Welfare-based Hierarchical Routing Algorithm (WHIRL), which alternates between tractable routing and allocation updates. Routing is initialized through its modular counterpart, while supermodular effects are modeled as bounded perturbations. The method has finite convergence guarantees and approximation bounds that depend explicitly on the deviation from modular routing. Numerical results illustrate the impact of routing-induced coupling and show that WHIRL achieves a favorable tradeoff between solution quality and computational cost.
Read the full abstract

All authors Joan Vendrell Gallart, Nhat-Minh Tang-Nguyen, Alan Kuhnle, Solmaz Kia

Computation and Language

Bag of Tricks or Bag of Myths? Reducing Modeling Complexity with Task Knowledge in Explainable Suicide Risk Assessment

Assessing suicide risk from social media text is a small-data, high-stakes setting requiring not only severity prediction but also supporting evidence and clinically relevant risk and protective factors. Yet common NLP techniques, including model scaling, synthetic data, loss reweighting, ensembling, and threshold tuning, are often applied without testing whether their gains hold up under severe class imbalance, coupled outputs, and limited author-level data. We study 1,635 clinician-annotated posts and audit 31 pre-specified techniques from 7 methodological families through roughly 300 controlled experiments on author-disjoint partitions. We found no prior audit of this playbook in this regime. The findings guide a task-grounded system for three outputs: 4-level suicide risk, evidence spans, and 24 clinical risk and protective factors. Only 5 of 31 comparisons produced reliable gains. We reformulate factor prediction as entailment between each post and its codebook definitions, using an architecturally diverse ensemble with class-balanced training and score rescaling. Risk predictions condition a 7-model evidence tagger ensemble; evidence restricts symbolic risk rules; and a difficult risk class is routed separately. The factor predictor remains independent because risk evidence provides no additional factor signal. We also correct a mismatch between validation scores used for threshold fitting and test-time ensemble scores through deployment-consistent calibration, yielding the largest improvement to the factor system. The final system achieves 0.8203 for risk, 0.7953 for evidence, and 0.7045 macro-F1 for factors, with a 0.7781 composite, ranking third among 53 teams. We call the underlying principle task-conditioned technique selection: retain techniques only when task-specific knowledge, structure, or empirical evidence justifies them.
Read the full abstract

All authors Shlok Shelat, Shrey Salvi, Souvik Roy, Manas Gaur, Amit Sheth

2609.07766 · 7 Sep · This work was shaped by the IEEE Big Data Cup, where our team, NIDHI, ranked 3rd overall. NIDHI (Neurosymbolic Intelligent Diagnostics for Holistic Trauma-Informed Care) is an effort from IAIRO.ai . 21 pages, 6 Tables, 4 Figures

High Energy Physics (Theory)

(Anti-)De Sitter null strings and Carroll-Weyl symmetry

We construct a $dS_d$ null string in a novel way by lifting the standard tensionless string to $R^{1,d}$. Gauging worldsheet scale symmetry introduces terms in the action breaking translation invariance, but preserving the $dS_d$ symmetry $SO(1,d)$. Choosing a De Sitter symmetric gauge fixing of the scale symmetry yields a $d$ dimensional theory which we show has all the expected properties of $dS_d$ tensionless strings. The action happens to be the intriguing Carrol-Weyl symmetric string action in $R^{1,d}$, now with a clear target space interpretation in $d$ dimensions. That it does not, as recently claimed, represent a ($d+1$)-dimensional string in flat ($d+1$)-dimensional Minkowski space settles an apparent issue with the Carrol-Weyl string model. Furthermore, while there are clear obstacles for similar formulations of tensile strings in (A)dS backgrounds, our new insights are easily modified to the formulation of Anti-De Sitter tensionless strings. That our construction generates a curved geometry purely algebraically may have even wider applications.
Read the full abstract

Statistical Mechanics

Directional memory of early spectral selection during spinodal decomposition in finite systems

Cahn-Hilliard phase separation turns small composition fluctuations into coarsening domains. In Fourier space, the pattern forms a ring whose angular intensity favors an axis. We ask whether the axis favored early in an evolution remains related to the axis favored later in the same evolution. We analyze two-dimensional simulations with isotropic initial fluctuations and no imposed direction. We introduce $Q_2$, a normalized angular average over the Fourier spectrum, as a measure of the strength and direction of spectral anisotropy. Linear growth amplifies different wave numbers at different rates, selecting an early axis from the angular imbalances in the initial spectrum. This axis remains correlated with the late axis during coarsening. At a fixed time, shallow quenches show stronger early-late alignment. This advantage disappears when the quenches are compared at similar stages of domain growth. Adding the early $Q_2$ to a prediction based on quench depth, mean composition, and box size reduces the mean absolute error for late $Q_2$ by $3.53\%$. This reduction disappears when only the magnitude of the early $Q_2$ is retained, or when its direction is replaced by the direction from another evolution. The early Fourier intensity therefore carries information about the later state of the same evolving field.
Read the full abstract

Statistical Mechanics

Topographic Disorder, Wind Coupling, and Directional Fire Spread: Critical Behavior in a Terrain-Weighted Forest Fire Model

We introduce the Terrain-Weighted Forest Fire Model (TFFM), a lattice model in which fire spreads on a spatially correlated Gaussian height field with the asymmetric bond probability $p_{i\to j}=\mathrm{clip}[e^{-\beta+\gamma(h_j-h_i)},0,1]$, plus an additive wind bias. Simulations on lattices up to $L=8192$ reveal a sharp active-to-inactive transition whose critical suppression threshold $\beta_c$ is even in $\gamma$, decreases with $|\gamma|$, and decreases as the terrain correlation length $\sigma_h$ is reduced: slope asymmetry acts as a suppressant because downhill bonds are penalized and fire stalls at local elevation maxima. For rough terrain and low tree density the fire fails to percolate even at zero suppression. Finite-size scaling on a fine $\beta$ grid at $L=2048$–$8192$ gives a correlation-length exponent $\nu=1.8\pm0.17$ from both the susceptibility peak and the width of the transition, and a front-velocity exponent $\delta=0.34\pm0.03$, identical for smooth and rough terrain; neither matches directed percolation ($\nu_\perp=0.73$, $\nu_\parallel-\nu_\perp\approx0.56$) or isotropic percolation ($\nu=4/3$, $\approx0.18$). The single-seed survival probability at $\beta_c$ is independent of $L$ and decays extremely slowly, with a running exponent falling from $\approx0.09$ to $\approx0.04$, excluding directed percolation and pointing to a survival probability that remains finite at criticality, consistent with the $L$-independent value $P^*\approx0.5$ at which $P_{\rm surv}$ drops to zero. Wind raises $\beta_c$ by a factor of $2$–$4$, produces a sharp onset of downwind fire-scar drift at weak coupling, and, at high terrain coupling, decreases the burned fraction at boundary crossing—a terrain-wind competition effect absent from isotropic bond-disorder models. The model yields fire-risk thresholds and fire-scar signatures comparable to satellite burn-scar data.
Read the full abstract

All authors Juan M. Florez, Eric Suárez Morell, Cristian Millan, J. Restrepo

Signal Processing

Pre-Whitening and BCJR Posterior Distillation for Bi-LSTM Detection in Faster-than-Nyquist Signaling

Recurrent detectors such as bidirectional long short-term memory (Bi-LSTM) networks are low-complexity alternatives to the optimal Bahl-Cocke-Jelinek-Raviv (BCJR) detector for faster-than-Nyquist (FTN) signaling. Motivated by convolutional detectors that build the intersymbol interference (ISI) structure into their architecture, we ask whether processing nested ISI windows in separate recurrent branches improves the bit error rate (BER) of a Bi-LSTM. Across roughly 260 controlled trainings it does not: at a matched parameter budget and a matched readout, the multi-window architecture never significantly beats a plain Bi-LSTM. Nested windowing is an invertible rearrangement that adds no information, extra branches only add bottlenecks, and a distillation diagnostic shows the network is already near optimal for its window. The limitation is therefore the observation model, not the architecture. Keeping the architecture fixed, we pre-whiten the input, restoring the conditional independence that colored matched-filter noise violates, and distill the BCJR soft posterior into the network. With 3.4% more parameters this reaches 1.05 times the BCJR BER at a compression factor of 0.8 and 1.89 times at 0.7, improving to 1.47 times when the whitened window is widened. The 23.7% BER reduction at 0.8 requires an ill-conditioned ISI matrix but is not monotone in the conditioning, and it holds across five independent noise realizations and a symbol-level McNemar test.
Read the full abstract