Formal Languages and Automata
From k+1 to k heads the descriptive trade-off is non-recursive
Christos Kapoutsis
We prove that no recursive function can upper bound the increase in the size of description when a two-way deterministic finite automaton with k+1 heads is replaced by an equivalent two-way deterministic finite automaton with k heads. This is true for all k, and remains true if the automata are unary and/or nondeterministic.
Read the full abstract ▾
Machine Learning
Stochastic Grouping Conformal Prediction for Effective Subgroup Reliability
Meihui Zhong, Wenxin Tai, Ting Zhong et al. (+1 more)
Conformal prediction offers a distribution-free coverage guarantee, making it especially attractive for clinical applications. Standard conformal prediction, however, provides such guarantees only at the population level, and its prediction sets can exhibit coverage disparities across clinically important subgroups. A natural remedy is to calibrate within predefined groups. However, this can require access to sensitive subgroup attributes and is prone to a worst-group bottleneck: protecting the most difficult subgroup can inflate prediction sets for all, increasing cognitive burden on decision makers. To this end, we propose
Stochastic Grouping Conformal Prediction (SGCP), a conformal framework for subgroup-reliable uncertainty quantification. It learns a
stochastic grouping map that allows each sample to draw calibration information from others with similar calibration behavior, yielding a local score law that boosts reliability across subpopulations. We prove that SGCP retains the standard coverage guarantee. Experiments on synthetic and real-world
benchmarks show that it consistently reduces subgroup coverage gaps while achieving smaller or comparable prediction set sizes relative to existing baselines.
Read the full abstract ▾
All authors Meihui Zhong, Wenxin Tai, Ting Zhong, Fan Zhou
Robotics
Reliability-Aware Future Conditioning for Temporally Robust Robot Manipulation
Mohammad Khoshnazar, Mohammad Dehghani Tezerjani, Zhiyuan Gao et al. (+8 more)
A generated
video of a task the
robot is about to perform is useful guidance only if it depicts the phase the
robot is actually in. We show that temporal misalignment can turn a task-consistent generated future into actively harmful guidance. On CALVIN, a five-frame early shift nearly erases the benefit of generated futures, reducing success from 81.3% to 54.8% against 54.0% without futures; imposed timing shifts reduce it even further to 34.2%, 19.8 points below the future-free policy. We introduce Reliability-Aware Future Conditioning (RAFC), which treats this as a control problem rather than a generation problem. At every step, RAFC estimates how far to trust the received clip and which nearby temporal hypothesis to prefer, falling back toward a static branch when neither fits, and it learns both from task reward alone without shift labels or
alignment supervision. RAFC sits on top of Future-Experience Conditioning (FEC), which builds the clip once from task grounding, a
robot-free digital-twin rollout, and mask-free
video diffusion. Under deliberately off-grid phase shifts and rate mismatch, RAFC substantially improves success under temporal mismatch. Candidate ensembling accounts for most of the recovery near
alignment, while learned reliability adds a further 7.0 percentage points over uniform averaging of the identical candidate bank under off-grid shifts. The gain holds on the evaluated task sets and survives on a Franka under natural timing mismatch nobody imposed, where aggregate success rises from 26.7% to 56.7%. All resources will be made publicly available. https://future-condition.github.io/.
Read the full abstract ▾
All authors Mohammad Khoshnazar, Mohammad Dehghani Tezerjani, Zhiyuan Gao, Deyuan Qu, Max Gandyra, Yanxiang Zhan, Mehreen Naeem, Andrew Melnik, Jeroen Schafer, Qing Yang, Michael Beetz
Distributed Computing
Capturing a Moving Target on Star Graphs by Two Communicating Mobile Agents
Khaled Jawhar and Evangelos Kranakis
We study a problem of searching for a mobile target in an $m$-ray
star graph, a natural generalization of linear search to multiple directions. The target is placed adversarially on one of the rays and may move with constant speed. We investigate a two-
robot setting, where cooperation and communication play a central role. We study two communication models: the Face-to-Face (F2F) model, where
robots communicate only upon meeting, and the Sender-Receiver (S/R) model, where communication is asymmetric. We focus on the away model, in which the target moves away from the origin with speed $v<1$. We design search strategies that minimize the competitive ratio and analyze the problem under three knowledge assumptions: NoDistance, NoSpeed, and NoKnowledge. For each setting, we derive upper bounds on the competitive ratio and for some cases, we derive the lower bound. Our results highlight how the number of rays and the communication model influence the competitive ratio.
Read the full abstract ▾
Computer Vision
Look Where You Can: Active View Selection for CAD Reconstruction under Occlusion
Kartik Bali, Mahish Guru, Yiderigun Borjigin et al. (+3 more)
CAD reconstruction methods assume a luxury reality rarely grants: unrestricted visual access to the object, photographed from any desired angle. Real objects, however, are scene-embedded, bolted against walls, wedged into corners, resting on floors, where the scene renders much of the view sphere unreachable and the remaining views unequally informative. We introduce SightCAD, a framework for parametric CAD reconstruction that treats view feasibility as a first-class constraint. In this work we consider objects from standard CAD
benchmarks embedded in realistic indoor scenes with physically derived visibility constraints over a discrete view sphere. A learned view selector must choose $K$ feasible views for a
vision–
language model (VLM) that generates executable CadQuery code, scored by
geometric fidelity of the executed solid. Because reward arrives only after discrete view selection, autoregressive generation, and CAD-kernel execution, we propose a joint training paradigm in which the view selector and the CAD-generation VLM are trained together against this reward. The learned selection policy departs sharply from random, uniform, and coverage-greedy alternatives, outperforming surface-area maximization (SA-max) by up to $6.4$ Intersection-over-Union (IoU) points across budgets $K\in\{1,\dots,5\}$. The full system surpasses strong external baselines on scene-embedded, occluded multi-view renders of DeepCAD and Fusion360 objects ($+21$ and $+17$ effective-mIoU points over the best baseline, respectively), as well as on test-time domain-canonicalized real images from the industrial T-LESS
benchmark and on both synthetic and real images from the MP6D industrial metal-parts
benchmark, while producing the highest rate of executable programs of any method compared (invalid-code rate ${\leq}1.5\%$).
Read the full abstract ▾
All authors Kartik Bali, Mahish Guru, Yiderigun Borjigin, Alexandra Starostina, Christian J. Cyron, Roland Aydin
Machine Learning
Interval-valued SHAP in Tree-Based Models
Chenrui Zhu, Vu-Linh Nguyen, Marie-Hélène Masson et al. (+1 more)
Shapley values are among the most popular feature-attribution explanations. Efficient approaches for computing/estimating Shapley values for tree-based models, which are state-of-the-art for tabular data sets, have been developed. However, it is known that Shapley values can be (highly) unrobust due to small and realistic changes. In this paper, we propose an imprecise Dirichlet model (IDM) based method to analyze the robustness of Shapley values in decision trees and random forests. Technically, it is done by quantifying and analyzing the interval-valued Shapley values when a few unannotated instances are randomly introduced to the leaves of the trees. The interval-valued Shapley values can be defined following common principles in handling incomplete data: the pessimistic and averaging principles. We derive various theoretical results that lead to efficient computation of the interval-valued Shapley values. We also show that the proposed method can be straightforwardly generalized to the case of Banzhaf values. We then present various case studies and experiments to illustrate the behaviour of the proposed interval-valued Shapley values and their applications in debiasing uninformative features.
Read the full abstract ▾
All authors Chenrui Zhu, Vu-Linh Nguyen, Marie-Hélène Masson, Sébastien Destercke
Robotics
Tell Robot What Not to Do: A Negation Understanding Perspective
Fazeng Li, Gan Sun, Hao Cheng et al. (+2 more)
Instruction following enables
robots to perform diverse tasks specified in natural
language, making it a fundamental capability for human-
robot interaction. Beyond communicating desired outcomes, users also need to specify constraints on what not to do. We investigate how to enable
vision-
language-action models (VLAs) to follow negated instructions, where
robots must accomplish task goals while respecting explicit exclusions. To this end, we propose NegaAlign, a parameter-efficient, plug-and-play framework that extends pretrained VLAs to follow negated instructions through image-
language supervision alone. Specifically, we introduce Negation Transformation Layers into selected layers of the
vision-
language backbone to reshape intermediate instruction representations. Meanwhile, a teacher-guided
alignment mechanism is designed to align instruction-relevant visual
tokens, transferring action-relevant grounding from instructions that satisfy the negated constraint. The training phase uses supervision constructed from existing demonstrations and updates only the inserted layers, keeping all pretrained parameters frozen, including the action generator. We further introduce NegaBench, a simulation
benchmark spanning 10 scenarios across five domains for systematically evaluating manipulation under negated constraints. Experiments across GR00T, $\pi_0$, and $\pi_{0.5}$ demonstrate consistent improvements in negated instruction following. With 11.6M trainable parameters, NegaAlign increases the negated-instruction success rate of $\pi_{0.5}$ from 2.60% to 88.45% on NegaBench and from 12.4% to 88.8% on real-world tasks, while retaining performance on affirmative instructions.
Read the full abstract ▾
All authors Fazeng Li, Gan Sun, Hao Cheng, Weihong Ren, Yang Cong
Human-Computer Interaction
"Hot-Blooded" vs "Cold-Blooded": Simulating the Behavioral Phenotypes of Childhood Aggression via Generative Agents
Liping Fu
This study examines the construct validity of LLM-based generative
agents in simulating reactive, proactive, and co-occurring aggression in children. Four distinct
agents were instantiated using a theory-driven parameterization grounded in the social information processing model. A total of 1,920 simulation runs were conducted across eight social scenarios, employing a hybrid blind-coding pipeline to extract 32 quantitative behavioral indicators. Results demonstrate robust discriminant validity relative to a non-aggressive baseline, with large effect sizes. High cross-seed reliability confirms that behavioral differentiation is driven by underlying psychological parameters rather than model stochasticity. Qualitative narrative analyses further converged with established empirical literature. Overall, these findings indicate that theory-parameterized LLM
agents can accurately reproduce distinct aggression subtypes, offering a scalable, highly controllable framework for hypothesis generation, intervention piloting, and the refinement of psychological measurement tools.
Read the full abstract ▾
Computation and Language
When History Helps and Hurts: Selective History Use across Multimodal Turns
Shuoyang Sun, Kerui Gu, Hao Fang et al. (+2 more)
Reliable
multimodal interaction depends on selective use of conversational history: an earlier question may remain relevant while its previous answer is outdated, whereas a current request may depend on historical evidence despite conflicting new observations. Existing multi-turn evaluations rarely separate these history-use demands from underlying question difficulty. To address this gap, we introduce ReTurn, a
benchmark of 7,000 base tasks spanning visual and audio evidence for evaluating selective history use. For task-carrying history, Reconfirm/Reground require applying a historical question to current media while varying historical agreement; for evidence-carrying history, Retrieve/Rebind require answering a current question using historical media while varying current-media competition. Each pair preserves the target question, media, and answer. Tasks support open-ended and multiple-choice evaluation, with matched single-turn counterparts serving as answerability references. Across 13 omni-modal,
vision-
language, and audio-
language models, median model-level open-ended accuracy falls from 93.7% with direct input to 72.3% in conversation. Behavioral probes show that high question recall can coexist with weaker task application, while competing media can redirect answers away from historical targets. Supervised adaptation yields only partial gains. ReTurn provides a controlled framework for assessing whether
multimodal models select and use the historical information required by each request.
Read the full abstract ▾
All authors Shuoyang Sun, Kerui Gu, Hao Fang, Shaoli Huang, Bin Chen
Machine Learning · Cross-listed from stat.ML
Score-Based Learning of Cluster DAGs from Interventions
Gaetano Tedesco and Alex Markham
Graphical approaches to causal abstraction transform a low-level causal directed acyclic graph (DAG) over many measured variables into a smaller, high-level DAG whose nodes cluster the original variables and whose edges summarize the causal relations between clusters. Such cluster DAGs are easier to interpret, but learning them requires finding the clusters and recovering the edges between them. Madaleno et al. (2026) learn the interventional coarsening (the cluster DAG that merges variables the interventions cannot distinguish) in two constraint-based phases: first the clusters, then the edges. We introduce COARSE, the first score-based method for this task: it keeps the two-phase structure but, under linear Gaussian assumptions, swaps the constraint-based edge phase for a score-based one. We show that the interventions themselves identify a causal order over the clusters, and learning the edges reduces to a single local search per cluster under a cluster-level BIC score. We prove that the procedure runs in
polynomial time and, provided the variables affected by each intervention are correctly identified, that it is consistent. On synthetic and real-world interventional data, COARSE matches state-of-the-art edge recovery given enough samples, with an edge phase up to two orders of magnitude faster, including on dense graphs with hundreds of nodes.
Read the full abstract ▾
Robotics
TACROSS: An Efficient and Low-Cost Scalable Human Touch System Across Heterogeneous Tactile Sensors for Dexterous Robot Learning
Bo Chen, Huanzhang Hu, Junyang Ma et al. (+11 more)
Collecting tactile demonstrations on
robots is costly and slow, motivating the use of lower-cost human tactile gloves for scalable data collection. However, human capacitive/piezoresistive gloves and robotic tactile sensors differ fundamentally in transduction principle, sensor layout, spatial resolution, and dynamic response, making
alignment of raw sensor channels ill-posed. To address this problem, we present TACROSS, a scalable system for learning from human touch and transferring it to
robots that bridges this heterogeneity by aligning tactile streams at the level of contact events rather than raw sensor values. The hardware component of TACROSS integrates a piezoresistive glove with five layers and a cost of USD 10.86 with 285 sensing points. To align contact semantics, we design canonicalizers and residual adapters that map heterogeneous signals into a shared tactile latent with 256 dimensions via a temporal
Transformer with
attention across fingers. We further introduce a
robot-grounded policy learning scheme in which
robot demonstrations provide the sole source of ground-truth action supervision, while human demonstrations support tactile representation learning and provide confidence-weighted auxiliary supervision through valid retargeted hand targets. We evaluate our system on four contact-rich manipulation tasks. Compared to conventional teleoperation, our proposed system achieves a 3.5-fold efficiency improvement while reducing demonstration acquisition equipment cost by 95.7%. We will open-source the TACROSS hardware and software system and publicly release a tactile
dataset comprising over 150 hours of recordings. Project page: https://tacross-touch-project.github.io/.
Read the full abstract ▾
All authors Bo Chen, Huanzhang Hu, Junyang Ma, Bo Yue, Fangdi Yu, Haijier Chen, Xianxin Lai, Shuyu Pan, Zhen Yang, Xiaoquan Sun, Wenze Cui, Zhongliang Jiang, Shaopeng Liu, Jiayu Chen
Data Structures and Algorithms
Faster Planar Graph Algorithms for Connectivity Problems via Meanders
Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista et al. (+1 more)
In this paper, we refine the dynamic programming framework based on the sphere cut decomposition designed by Dorn, Penninkx, Bodlaender, and Fomin (ESA 2005) to obtain faster subexponential
algorithms for connectivity problems on planar graphs. We investigate the relationship between these problems and meanders, which are simple closed planar loops that intersect a fixed line in a given number of points. By combining dynamic programming with techniques from meandric system analysis and the use of fast
matrix multiplication by Dorn (ESA 2006), we obtain improved
algorithms for planar connectivity problems. We show that the number of meanders on $2n$ crossings $M_n$ is $\mathcal O^*(12.806^n)$, which improves the previous upper bound of $\mathcal O^*(12.901^n)$ by Albert and Paterson (FPSAC 2004). This then gives the best-known classical upper bounds on the deterministic time complexity of several planar graph problems with polynomially-bounded weights, namely $\mathcal O(2^{5.543\sqrt n})$ for the Planar Travelling Salesman problem, $\mathcal O(2^{5.796\sqrt n})$ for Planar Longest Cycle/Path, $\mathcal O(2^{8.251\sqrt n})$ for Planar Connected Dominating Set and $\mathcal O(2^{8.037\sqrt n})$ for Planar Steiner Tree. Notably, this leads to the best-known deterministic complexity $\mathcal O(2^{5.543\sqrt{n}})$ for the Planar
Hamiltonian Cycle problem.
Read the full abstract ▾
All authors Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista, Jevgēnijs Vihrovs
Robotics
STAG: A Sparse Traversability-Aware Graph Representation from Grid-Based Costmaps for Robotic Navigation
Gabriel Manuel Garcia, Stéphanie Aravecchia and Miguel Angel Olivares-Mendez
Autonomous rovers navigating large unstructured environments need efficient global planning that accounts for terrain traversability. However, searching dense grid-based costmaps becomes computationally expensive as the mapped area grows. We introduce STAG, a Sparse Traversability-Aware Graph that converts costmaps into compact graphs. STAG combines a medial-axis topological backbone, representative nodes for homogeneous traversability regions, and transition nodes near strong traversability gradients. Edges encode geometry and traversability to account for path length and terrain difficulty. We compare A* on STAG and dense grids using synthetic cave maps, mine maps and the DARPA CERBERUS
dataset. Across five
benchmark categories comprising 203 map instances and 101,200 queries, STAG reduces median planning time by 3.4x to 9.9x and peak query
memory by 2.1x to 15.4x, with median relative path-length differences of -2.9% and +7.6%. STAG offers a compact representation for global planning, trading dense-grid traversability optimality for faster, less
memory-intensive search.
Read the full abstract ▾
Computer Vision
Right Screen, Wrong Transition: World Models as Verifiers for GUI Agents
Jiaming Zhang, Xuan Wang, Fuyao Zhang et al. (+3 more)
A login screen that appears after a tap on Sign in is expected; the same screen after a tap on View order is an attack. For GUI
agents, safety is therefore a property of the transition rather than of the screen, and a monitor that inspects only screens can be defeated by reusing a legitimate one. Judging a transition requires an expectation of what should have followed the action. Existing GUI world models provide one, but they output it as text, code, or images, so checking it against the observed screen requires a second model to judge the two. We argue that a world model meant for verification should instead predict in the space in which observations are encoded, and present LGWM, a decoder-free, action-conditioned world model that predicts the representation of the next screen directly, trained without semantic annotation on 1.85M real GUI transitions. Verification reduces to a vector comparison, and the same signal reveals whether a mismatch is harmful. We evaluate on RSWT-BENCH, a diagnostic where each credential screen appears under both a legitimate and a hijacked transition, so detectors that see only the screen are at chance by construction. The training-free score reaches 0.987 AUC at 17 ms per decision, on par with the strongest closed-source VLMs and about ten AUC points above generative GUI world models at over three orders of magnitude lower latency. The residual direction reaches 0.953 AUC at separating harmful from benign violations, where prompted VLMs are near chance. Further analyses show that the prediction is a usable future state rather than an anomaly score. World models have mostly served as simulators or planners; our results point to a third role, verification, for which predicting in representation space is the natural design.
Read the full abstract ▾
All authors Jiaming Zhang, Xuan Wang, Fuyao Zhang, Yang Cao, Lingjuan Lyu, Wei Yang Bryan Lim
Computer Vision
Does Target Alignment Mean Target Recovery? An Evidence-Ladder Study of Adversarial Claims on Contrastive Encoders
Tao Yang and Jianying Zhou
Adversarial attacks on
vision-
language models optimize an image toward a text target, then cite the attacked model's similarity score as evidence of success. We ask whether that score - victim-space target
alignment (VTS) - predicts recovery of the target by an independent model. We first build a measurement instrument: supervised judges outside the attacked geometry, real-target blend controls, shuffled-target negatives, and a reference level derived from a 50% target-image blend. Two preregistered studies then compare six contrastive encoders under a matched attack at three perturbation budgets. Robustly trained encoders (FARE, TeCoA, PMG, TRADES) transfer substantially more independent evidence than vanilla CLIP or SigLIP; all eight contrasts reject at the bootstrap floor. However, no
cell reaches the blend-derived reference level. The three best
cells fall within its replication band, leaving practical recovery undecided. Within robust encoders, per-sample
alignment gain correlates with evidence gain ($\rho = 0.24-0.51$); within vanilla CLIP the correlation is consistent with zero. Across encoders we find no monotone
alignment-evidence relation. VTS is therefore informative only within a fixed robust encoder, and we provide a reporting protocol in its place.
Read the full abstract ▾
Networking
Digital Twin for Pre-Deployment Validation of AI-Driven Safety-Critical Industrial Edge Control Loops
Sara Cavallero, Federico Tonini, Tony Chahoud et al. (+5 more)
Industrial environments are increasingly characterized by the tight interaction among physical processes, communication infrastructures, and intelligent applications. In this context, Digital Twins (DTs) have emerged as a key technology for system analysis and optimization. However, existing DT solutions typically focus either on industrial processes or communication networks, while lacking an integrated and application-aware perspective. To fill this gap, this paper proposes a modular DT framework for industrial environments that jointly models physical processes, wireless communications, and application logic within a unified architecture. The feasibility of the proposed framework is experimentally validated through a real-world Proof-of-Concept (PoC) implemented in the BI-REX pilot line, involving a 5G-connected Autonomous Mobile
Robot (AMR) transporting hazardous
liquids and remotely controlled by an AI-driven application. The proposed DT is used to reproduce the behaviour of the real deployment and to investigate the impact of different placements of the AI application, including on-premise, edge, and remote cloud execution scenarios. Experimental results demonstrate a close agreement between DT predictions and PoC measurements in terms of both network-level metrics, such as Reference Signal Received Power (RSRP) and latency, and end- to-end application metrics, including application-level Round- Trip-Time (RTT). Moreover, the analysis shows how inaccuracies of network modeling can critically affect the feasibility of latency-sensitive industrial control loops, highlighting the potential of integrated DTs as tools for the pre-deployment design and validation of next-generation industrial systems.
Read the full abstract ▾
All authors Sara Cavallero, Federico Tonini, Tony Chahoud, Giampaolo Cuozzo, Davide Borsatti, Walter Cerroni, Maurizio Fodrini, Riccardo Marini
Cryptography and Security
From Public Posts to AI-Search Citations: Measuring the Fragility of AI Search
Qi Liu, Geng Hong, Xinyang Zhang et al. (+3 more)
As more users ask AI systems for information, AI-search platforms are becoming a common gateway to web information. Unlike traditional search, which maps keywords to ranked pages, AI search retrieves pages, filters sources, selects citations, and generates answers before users see sources. This selection layer may amplify source bias and turn source choice into a security question. If a platform repeatedly cites domains where new users can publish posts easily, ordinary publication on those domains can become an indirect path into AI-search citations and answer text. Measuring this path is hard: platforms reveal little about citation selection, citations change over time, and the web contains so much background content that later answer changes are hard to attribute to our posts. We present a measurement framework for identifying and measuring this low-barrier publication path, combining cross-platform citation mapping, publication-barrier testing, and marker-controlled publication experiments. Across 10 AI-search platforms, we analyze 17,211 citation instances over 6,356 unique source domains and find: (1) citations concentrate in platform-specific sources, with top-20 domains capturing 20.5–70.8% of per-platform citations, and 15 of 22 tested publication platforms tied to cited source domains had low or medium barriers for both account setup and posting; (2) in our experiments, ordinary publication on preferred platforms changed what entered AI-search outputs: 8 of 10 platforms cited a fabricated concept within seven days, and one high-preference-platform article had greater citation impact than over 20 matched low-preference posts; and (3) this path is commercially available: a $14 GEO purchase produced 13 public posts, and one AI-search platform cited GEO-posted content with our designed markers within one hour.
Read the full abstract ▾
All authors Qi Liu, Geng Hong, Xinyang Zhang, Pei Chen, Yutong Li, Min Yang
Numerical Analysis
Data-Driven Free-Energy Learning from Trajectories via Structure-Preserving Exponential Time Differencing
Wenshuai Hu, Guanghua Ji and Xiao Li
Structure-preserving numerical methods for gradient flows have been extensively developed when the governing equations and free energies are known. However, accurately predicting dynamics from observational data while preserving intrinsic physical properties remains challenging. Although neural operators, such as
Fourier neural operators (FNOs), provide powerful data-driven approximations, their predictions do not inherently guarantee physical structure preservation. To address this challenge, we integrate deep learning with structure-preserving exponential time differencing (ETD) methods. Instead of directly learning the
evolution operator, we introduce a *trajectory-inferred free energy* (TIFE), which reconstructs the unknown energy density from observed trajectories through a Duhamel-based learning framework. The learned energy determines the variational force and stabilization parameter, enabling structure-preserving numerical
evolution. We further extend the framework to jointly identify the free energy and
diffusion coefficient. Under suitable assumptions, we establish the maximum-bound principle, unconditional dissipation of the original learned energy, and error estimates incorporating discretization and inference errors. Numerical experiments demonstrate accurate energy recovery and reliable long-time predictions.
Read the full abstract ▾
Computers and Society
Automated Disinformation and Malicious AI Swarms: Risks for Democracy and Development in Africa
Daniel Thilo Schroeder, Philipp M. Lutscher, Samba Dialimpa Badji et al. (+12 more)
Generative artificial intelligence is reshaping how information is produced, accessed, and circulated, while enabling disinformation campaigns of increasing scale and sophistication. There is currently no clear evidence that fully autonomous AI swarms conduct influence operations at scale, but their enabling capabilities are advancing. We define malicious AI swarms as coordinated, persistent, and adaptive multi-
agent systems designed for influence operations, distinguishing them from AI-assisted content production and centrally managed synthetic personas. We examine their implications for hybrid regimes and conflict-affected states in Africa, where institutional constraints and fragile media environments may heighten vulnerability. Drawing on Mali and Ethiopia, we consider how automated influence could infiltrate communities, fabricate consensus, and erode trust in governance and development. The cases illustrate different configurations of state and non-state influence: competing actors in Mali's fragmented information environment, and more organized state-led strategies of narrative management in Ethiopia. African-
language and training-data asymmetries may constrain influence capabilities while weakening defensive responses. Hybrid human-AI operations could combine automated scale and adaptation with local knowledge and credibility. This forward-looking risk analysis develops a scenario of increasingly accessible AI-driven coordination, rather than claiming that autonomous swarms are already operating at scale in Africa. We propose a layered governance approach linking technical safeguards to platform accountability, civic institutions, and regional coordination to protect democratic participation, peacebuilding, and development.
Read the full abstract ▾
All authors Daniel Thilo Schroeder, Philipp M. Lutscher, Samba Dialimpa Badji, Stefan Brenner, Wenchao Dong, Tsehaye Haidemariam, Saheed Bidemi Ibrahim, Amanuel Tesfaye Kebede, Jonas R. Kunst, Johannes Langguth, Pauline Lemaire, Mulatu Alemayehu Moges, Lukasz Olejnik, Kristin Skare Orgeret, Gerald Walulya
Social and Information Networks · Cross-listed from physics.soc-ph
A Gauge-Invariant Clustering Coefficient for Complex-Weighted Bipartite Networks
Anjali Waghmare, Yu Tian and Renaud Lambiotte
Structural measures such as the clustering coefficient and the average shortest-path length characterise how a network is organised. These measures are typically formulated for real, non-negative edge weights. A class of
quantum and photonic architectures has complex edge weights instead, whose phases determine whether alternative routes interfere constructively or destructively. These architectures are also bipartite, so triangles are absent and the smallest closed cycle is a four-node square. Existing measures address complex weights and bipartite structure separately: bipartite clustering coefficients quantify clustering through four-node squares but do not contain phase information, while interferometric coefficients retain phase but are defined on triangles. In this work, we define a clustering coefficient for complex-weighted bipartite networks which reduces to the classical bipartite coefficient when the phases vanish, becomes negative when alternative routes cancel, and can be obtained for all nodes from a single sparse
matrix product. We show that the phase accumulated around a square is the smallest gauge-invariant carrier of structural phase information in a bipartite network. The clustering coefficient factorises into a topological contribution and a phase contribution, making a bipartite Watts–Strogatz ensemble analytically tractable. For phases uniformly distributed on $[-\Delta,\Delta]$, the mean phase contribution is $(\sin\Delta/\Delta)^4$, independent of node, degree, and
topology. We also derive closed-form expressions for the clustering coefficient, open-path visibility, and phase variance. We numerically verify these predictions and further show that phase disorder increases coherent distance.
Read the full abstract ▾
Information Theory · Cross-listed from math.CO
Covering radius of rank-metric codes via covering lifts and clubs
Giuseppe Marino, Alessandro Neri and Alessia Vallefuoco
We introduce a generator-
matrix-based
geometric approach to the covering radius of $\mathbb F_{q^m}$-linear rank-metric codes. Starting from the $q$-system associated with the code, we define the notion of covering lift and show that the covering radius can be recovered from the hyperplane weights of such lifts. This yields an exact criterion, in terms of the length and effective length of the code, for the covering radius to attain its largest possible value, together with the upper bound $\rho(\mathcal{C})\le \min\{m,n\}-1$ in all remaining cases. We then specialize our approach to $1$-dimensional codes, for which the effective length coincides with the minimum rank distance. In this setting, codes attaining $\rho(\mathcal{C})= \min\{m,n\}-1$ are related to covering lifts that are clubs. More generally, we characterize this case through linear maps into suitable quotient spaces, obtaining equivalent interpretations in terms of generalised evasive subspaces and auxiliary
matrix rank-metric codes. These results determine the covering radius for several boundary values of the minimum distance and for all $1$-dimensional codes with extension degree $m\in\{3,4,5\}$. For $m=6$ and every $q$ we provide constructions and, for $q\in\{2,3\}$, computational results showing that $1$-dimensional rank-metric codes with the same length and minimum distance can have different covering radii.
Read the full abstract ▾
Computer Vision
Revisiting Identity and Spectra Dispersion in Media-Bridged Time Series Forecasting: Linking Multivariate Signals and Narrative Flows
Jierui Lei, Wenjian Zhang, Qingyi Yang et al. (+5 more)
Media-bridged time series
forecasting is expanding to encompass traditional "multivariate" and emerging "
multimodal" (e.g., through textual assistance). Existing Time Series
Forecasting (TSF) models still rely on paradigm-specific relation, fusion, and temporal modules, hindering a common
forecasting backbone across numerical and pre-aligned narrative-flow settings. To explore this, we propose the Multimedia Identity-Aware Prism Network (MIDAPN), a unified spatiotemporal
forecasting backbone based on media-general graph adaptation and automatic temporal learning: (1) Following media pre-
alignment, our Multimedia Identity-Aware Graph (MIDAG) revisits identity through static essence, dynamic behavior, and latent commonality, inducing affinities that extend variable-specific dependencies across media. Contextual Identity Modulation (CIM) further refines discriminative aggregation. (2) We develop Spectral Prism Convolution (SPConv) to automatically perform hierarchical temporal analysis, balancing coarse trends and fine-grained details. Meanwhile, its Adaptive Search Guidance configures a scale-efficient architecture for temporal-dimension reconstruction. These decoupled yet synergistic components jointly address media identity disentanglement and temporal-scale mismatch. Comprehensive evaluations involving 16 SOTA TSF models across 13 "multivariate" and 12 "
multimodal"
datasets, alongside targeted long-context comparisons against 14 time series foundation models and fused pretrained
language models, demonstrate MIDAPN's consistent superiority and broad shared backbone compatibility. The code is available at \href{https://github.com/leijieruilq/MIDAPN/tree/main}{https://github.com/MIDAPN}.
Read the full abstract ▾
All authors Jierui Lei, Wenjian Zhang, Qingyi Yang, Yuyang Hong, Fangzheng Chen, Zhengbo Zhang, Haina Tang, Shiming Xiang
Artificial Intelligence · Cross-listed from q-bio.NC
Neural Decoding as Cognitive Inference
Yi Guo, Changhong Jing, Yong Hu et al. (+4 more)
The
brain maintains stable cognition despite continuously changing neural activity. How to extract stable cognitive states from variable neural observations remains a central problem in neural decoding. Existing neural decoding methods map neural observations to predefined external labels based on the stimulus-response principle, often capturing recording-specific spurious correlations. Inspired by how the
brain infers the world, and specifically by
Bayesian brain theory, we recast neural decoding as cognitive inference constrained by
brain-intrinsic priors, yielding high-level meta-neural semantic representations. In decoding experiments spanning five neural recording modalities and three cognitive domains (motor, perception and internal mentation), our cognitive inference method reorganized the geometry of neural observation representations, yielding meta-neural semantic representations that exhibited consistent
geometric relationships across cognitive tasks and enabled the recovery of stable cognitive states from variable neural observations. Our work provides an account of how the
brain maintains relatively stable cognition despite continual changes in the external environment. Cognitive stability is sustained through cognitive inference from changing neural activity, without requiring fixed neural activity patterns.
Read the full abstract ▾
All authors Yi Guo, Changhong Jing, Yong Hu, Yan Liu, Michael K. P. Ng, Shanshan Wang, Shuqiang Wang
Information Retrieval
Project Greenhouse: Progress Toward Fully Open and Sovereign Agentic Search
Jimmy Lin, Sahel Sharifymoghaddam, Lingwei Gu et al. (+1 more)
Project Greenhouse represents our exploration of a simple thesis: We believe that it is possible to build fully open and sovereign models for agentic search with only modest computational resources. As a first milestone, we describe how to build a competitive pointwise decoder-only reranker using a simple two-step recipe comprising pre-training from scratch followed by supervised fine-tuning, starting only from commonly available
datasets. Contrary to the dominant approach in the literature, we do not rely on existing open-weight backbones from third parties, and thus we are fully in control of model training, from end to end. We were able to accomplish the bulk of our experiments using no more than a handful of GPUs. This report articulates the importance and benefits of our approach, and we share artifacts that enable transparent, independent reproduction of all aspects of model training. Beyond data, code, and configurations that capture our efforts, we also release checkpoints for our family of Gaggle models, demonstrating the feasibility of our approach and providing a first step toward validating our broader thesis.
Read the full abstract ▾
All authors Jimmy Lin, Sahel Sharifymoghaddam, Lingwei Gu, Nour Jedidi
Computation and Language
Event-Centric Memory with Query-Aware Graph Augmentation for Long-Term Conversational Agents
Yichen Liu, Chunfeng Yuan, Haowei Liu et al. (+5 more)
For persistent and personalized conversational
agents,
memory systems can enable them to remember, update, and reason over long histories by storing past interactions and retrieving relevant information. Existing
memory systems typically follow two paradigms: flat-structured
memory and graph-based
memory. The former is lightweight but leaves event relations and state updates implicit, while the latter explicitly models
memory structure but incurs additional construction cost and introduces irrelevant relations over long histories. To address these limitations, we propose QGMem, a novel
memory construction and activation framework motivated by human
memory, in which experience is organized into events and query-relevant events are modeled by graph as working
memory. QGMem converts long dialogue histories into event-indexed atomic
memory units that preserve individual experiences and consolidates related units into dynamic
memory traces that retain state trajectories and current states. When a query arrives, hybrid
memory retrieval gathers complementary candidate
memories, and query-aware reranking activates the most relevant units as a compact working
memory. To expose relational dependencies in the working
memory and support conflict-aware
reasoning, QGMem organizes the working
memory as a local graph, which is then encoded as a graph
token and provided to the LLM together with the textual working
memory to improve evidence utilization during answer generation. Experiments across six
benchmarks validate the framework and show consistent gains in
retrieval, multi-hop evidence composition, conflict resolution, and ultra-long dialogue
reasoning with compact contexts and moderate inference cost.
Read the full abstract ▾
All authors Yichen Liu, Chunfeng Yuan, Haowei Liu, Wenjuan Li, Zefeng Lin, Bing Li, Xu Chen, Weiming Hu
Multimedia
From Surface to Depth: Towards Cognitive Appraisal Reasoning in Multimodal Emotion Understanding
Jia Li, Yichao He, Yangchen Yu et al. (+6 more)
Recent
multimodal large
language models (MLLMs) increasingly incorporate explainable
reasoning for
emotion understanding. However,
reasoning based mainly on observable affective cues can reduce
emotion understanding to superficial cue-label associations, giving rise to the Clever Hans effect. Such shortcuts become unreliable when affective cues are implicit, conflicting across modalities, linguistically misleading, or obscured by redundant details. In contrast, human
emotions are shaped by how individuals interpret and evaluate surrounding events beyond observable cues. Inspired by appraisal theories of
emotion, we formulate
multimodal emotion understanding as a progression from perception to cognitive appraisal, and introduce a
dataset, a model, and a
benchmark to support this novel paradigm. CogEmo-40K is a large-scale instruction-tuning
dataset constructed through a perception-to-appraisal pipeline to elicit evidence-grounded
reasoning across six cognitive appraisal dimensions underlying
emotion. CogEmo-MoE is a compact sparse MLLM that introduces interleaved MoE blocks for appraisal-specific adaptation, enabling effective appraisal
reasoning at a substantially smaller scale than typical
emotion MLLMs. CogEmo-Bench introduces an Appraisal Evidence Quality Score (AEQS) to assess cognitive-affective understanding across six complementary appraisal dimensions, addressing the limitation of conventional
emotion metrics that evaluate what
emotion is predicted but not why it arises. Extensive experiments show that our paradigm not only leads CogEmo-Bench, but also exhibits strong cross-domain generalization. Our findings suggest that perception-to-appraisal
reasoning can move beyond surface-level cue-label associations toward more reliable
multimodal emotion understanding and closer cognitive
alignment between MLLMs and humans.
Read the full abstract ▾
All authors Jia Li, Yichao He, Yangchen Yu, Qiankun Li, Xinyi Li, Baiyi Ye, Zhenzhen Hu, Richang Hong, Erik Cambria
Computation and Language
Not Every Change Is Necessary: Recoverable Drift in Large Language Model Unlearning
Xunlei Chen, Qinghui Gong, Jingkun Xue et al. (+3 more)
Machine unlearning in large
language models aims to remove unwanted knowledge while preserving the model's remaining capabilities. Although existing methods use retention objectives or restrict where edits occur, achieving the desired forgetting level can still leave collateral changes that impair non-target behavior. Our recovery comparisons suggest that some of these changes can be reversed while preserving observed forgetting performance. In this work, we present Propose-Then-Project Unlearning (PTP-U), a framework that combines targeted forgetting with the recovery of non-target capabilities. PTP-U first applies local analytic edits to weaken target knowledge associations, then aligns non-target output distributions with those of the original model to recover capabilities while maintaining fixed forgetting constraints. Both stages serve a common goal: satisfying the forgetting requirements while preserving fluent generation and performance on non-target tasks. Across three
benchmarks, PTP-U achieves the strongest forgetting-retention trade-off among evaluated methods, reaching 81.22%-91.03% forgetting while preserving 94.20% non-target utility on average. At matched forgetting, PTP-U consistently retains higher non-target utility.
Read the full abstract ▾
All authors Xunlei Chen, Qinghui Gong, Jingkun Xue, Qihe Liu, Shijie Zhou, Fei Ye
Machine Learning
Puffin: Probabilistic Learning of Spatial Detail From Coarse Observations
Chaitanya Jobanputra, Sebastian Vollmer and Gerrit Großmann
High-resolution socioeconomic variables are important for applications such as urban planning, public health, disaster response, and resource allocation. In practice, however, these variables are often observed only at a coarse spatial resolution. We introduce Puffin, a probabilistic framework for statistical disaggregation that raises the resolution of coarse totals using high-resolution satellite
embeddings as
covariates. Instead of predicting a single value for each fine-resolution subregion, Puffin learns a probability distribution and is trained through an aggregation-aware likelihood. At inference, Puffin conditions these predictions on the observed regional total and splits it among the subregions. The resulting fine-scale estimates are consistent with the observed aggregate and come with calibrated uncertainty, without requiring fine-resolution labels for training. We evaluate Puffin on German and US census, employment, and election data across population, jobs, and other count variables, and study when statistical disaggregation succeeds or fails across regions, countries, and targets.
Read the full abstract ▾
Logic in Computer Science
Formally Certifying the Vertex Set of a Polyhedron Faster than Informal Enumeration
Xavier Allamigeon, Yazid Id-Sahra and Pierre-Yves Strub
The computation of the vertices of a polyhedron described by a system of linear inequalities is a central problem in polyhedral computation. It is a fundamental step in the conversion between H-representations, by linear inequalities, and V-representations, by vertices and extreme rays. This operation plays an important role both in the study of polyhedra and their combinatorics in mathematics and in applications to software and system verification. We present a certificate-based approach for formally verifying the computation of the vertices of a polyhedron. Given an informally computed list of vertices, our method allows to certify in the proof assistant Rocq that the list is complete, or even exact. The cornerstone of the method is a new completeness criterion based on an abstract simplicial complex that generalizes a triangulation of the normal fan of the polyhedron. A significant advantage over previous approaches is that the usually expensive numerical computations are essentially reduced to membership tests to the polyhedron, while the other steps are cheap combinatorial tests. We implement the certification method and prove its correctness in the proof assistant Rocq. We experiment with it on a variety of polyhedra, including Birkhoff polytopes, cross-polytopes, cubes, permutahedra, hypersimplices, and high-dimensional polytopes involved in the disproof of the Hirsch
conjecture. Our experiments show that certification with the Rocq-to-OCaml extracted checker is typically 1.5x to over 5x faster than vertex enumeration by the state-of-the-art informal C implementation lrslib of the reverse search method.
Read the full abstract ▾
Numerical Analysis
Acceleration of Newton's method for nonlinear algebraic systems by preflattening and elimination techniques
Ngoc Do Quyen Dang, Ibtihel Ben Gharbia, Clément Cancès et al. (+1 more)
In this paper, we propose a new approach called preflattening to speed up the resolution of nonlinear algebraic systems by Newton-type methods. Preflattening is meant to be for nonlinear systems what preconditioning is for linear ones. The idea is to transform the system into an equivalent one that is more favorable to Newton's method. To this end, we introduce the notion of flatness, which is intended to play for nonlinear systems a role similar to that of the condition number for linear systems. For a physical model of interest in the geosciences, namely the chemical
equilibrium problem, we combine this strategy with the nonlinear elimination technique and demonstrate the value of the resulting approach through numerical simulations.
Read the full abstract ▾
All authors Ngoc Do Quyen Dang, Ibtihel Ben Gharbia, Clément Cancès, Quang Huy Tran