OpenRaiser/Intern-Atlas huggingface dataset:
Mean-Field Games With Finitely Many Players: Independent Learning and Subjectivity
Venue: arXiv cs.GT 2025
Year: 2025

Independent learners are agents that employ single-agent algorithms in multi-agent systems, intentionally ignoring the effect of other strategic agents. This paper studies mean-field games from a decentralized learning perspective, with two primary objectives: (i) to identify structure that can guide algorithm design, and (ii) to understand the emergent behaviour in systems of independent learners. We study a new model of partially observed mean-field games with finitely many players, local action observability, and a general observation channel for partial observations of the global state. Specific observation channels considered include (a) global observability, (b) local and mean-field observability, (c) local and compressed mean-field observability, and (d) only local observability. We establish conditions under which the control problem of a given agent is equivalent to a fully observed MDP, as well as conditions under which the control problem is equivalent only to a POMDP. Building on the connection to MDPs, we prove the existence of perfect equilibrium among memoryless stationary policies under mean-field observability. Leveraging the connection to POMDPs, we prove convergence of learning iterates obtained by independent learning agents under any of the aforementioned observation channels. We interpret the limiting values as subjective value functions, which an agent believes to be relevant to its control problem. These subjective value functions are then used to propose subjective Q-equilibrium, a new solution concept for partially observed n-player mean-field games, whose existence is proved under mean-field or global observability. We provide a decentralized learning algorithm for partially observed n-player mean-field games, and we show that it drives play to subjective Q-equilibrium by adapting the recently developed theory of satisficing paths to allow for subjectivity.
Optimizing Connectivity through Network Gradients for Restricted Boltzmann Machines
Venue: arXiv cs.LG 2025
Year: 2025

Leveraging sparse networks to connect successive layers in deep neural networks has recently been shown to provide benefits to large-scale state-of-the-art models. However, network connectivity also plays a significant role in the learning performance of shallow networks, such as the classic Restricted Boltzmann Machine (RBM). Efficiently finding sparse connectivity patterns that improve the learning performance of shallow networks is a fundamental problem. While recent principled approaches explicitly include network connections as model parameters that must be optimized, they often rely on explicit penalization or network sparsity as a hyperparameter. This work presents the Network Connectivity Gradients (NCG), an optimization method to find optimal connectivity patterns for RBMs. NCG leverages the idea of network gradients: given a specific connection pattern, it determines the gradient of every possible connection and uses the gradient to drive a continuous connection strength parameter that in turn is used to determine the connection pattern. Thus, learning RBM parameters and learning network connections is truly jointly performed, albeit with different learning rates, and without changes to the model's classic energy-based objective function. The proposed method is applied to the MNIST and other data sets showing that better RBM models are found for the benchmark tasks of sample generation and classification. Results also show that NCG is robust to network initialization and is capable of both adding and removing network connections while learning.
Set Theory in the Foundation of Math; Internal Classes and External Sets
Venue: arXiv cs.LO 2025
Year: 2025

Usual math sets have special types: countable, compact, open, occasionally Borel, rarely projective, etc. Each such set is described by a single Set Theory formula with parameters unrelated to other formulas. Exotic expressions involving sets related to formulas of unlimited quantifiers height appear mostly in esoteric or foundational studies. Recognizing internal to math (formula-specified) and external (based on parameters in those formulas) aspects of math objects greatly simplifies foundations. I postulate external sets (not internally specified, constituting the domain of variables) to be hereditarily countable and independent of formula-defined classes, i.e. with finite algorithmic information about them. This allows to eliminate all non-integer quantifiers in Set Theory sentences. All with seemingly no need to change almost anything in mathematical papers, only to reinterpret some formalities.
STPOTR: Simultaneous Human Trajectory and Pose Prediction Using a Non-Autoregressive Transformer for Robot Following Ahead
Venue: arXiv cs.RO 2025
Year: 2025

In this paper, we develop a neural network model to predict future human motion from an observed human motion history. We propose a non-autoregressive transformer architecture to leverage its parallel nature for easier training and fast, accurate predictions at test time. The proposed architecture divides human motion prediction into two parts: 1) the human trajectory, which is the hip joint 3D position over time and 2) the human pose which is the all other joints 3D positions over time with respect to a fixed hip joint. We propose to make the two predictions simultaneously, as the shared representation can improve the model performance. Therefore, the model consists of two sets of encoders and decoders. First, a multi-head attention module applied to encoder outputs improves human trajectory. Second, another multi-head self-attention module applied to encoder outputs concatenated with decoder outputs facilitates learning of temporal dependencies. Our model is well-suited for robotic applications in terms of test accuracy and speed, and compares favorably with respect to state-of-the-art methods. We demonstrate the real-world applicability of our work via the Robot Follow-Ahead task, a challenging yet practical case study for our proposed model.
On the Generic Capacity of $K$-User Symmetric Linear Computation Broadcast
Venue: arXiv cs.IT 2025
Year: 2025

Linear computation broadcast (LCBC) refers to a setting with $d$ dimensional data stored at a central server, where $K$ users, each with some prior linear side-information, wish to retrieve various linear combinations of the data. For each computation instance, the data is represented as a $d$-dimensional vector with elements in a finite field $\mathbb{F}_{p^n}$ where $p^n$ is a power of a prime. The computation is to be performed many times, and the goal is to determine the minimum amount of information per computation instance that must be broadcast to satisfy all the users. The reciprocal of the optimal broadcast cost is the capacity of LCBC. The capacity is known for up to $K=3$ users. Since LCBC includes index coding as a special case, large $K$ settings of LCBC are at least as hard as the index coding problem. Instead of the general setting (all instances), by focusing on the generic setting (almost all instances) this work shows that the generic capacity of the symmetric LCBC (where every user has $m'$ dimensions of side-information and $m$ dimensions of demand) for large number of users ($K>d$ suffices) is $C_g=1/Δ_g$, where $Δ_g=\min\left\{\max\{0,d-m'\}, \frac{dm}{m+m'}\right\}$, is the broadcast cost that is both achievable and unbeatable asymptotically almost surely for large $n$, among all LCBC instances with the given parameters $p,K,d,m,m'$. Relative to baseline schemes of random coding or separate transmissions, $C_g$ shows an extremal gain by a factor of $K$ as a function of number of users, and by a factor of $\approx d/4$ as a function of data dimensions, when optimized over remaining parameters. For arbitrary number of users, the generic capacity of the symmetric LCBC is characterized within a factor of $2$.
Generative Graphical Inverse Kinematics
Venue: arXiv cs.RO 2025
Year: 2025

Quickly and reliably finding accurate inverse kinematics (IK) solutions remains a challenging problem for many robot manipulators. Existing numerical solvers are broadly applicable but typically only produce a single solution and rely on local search techniques to minimize nonconvex objective functions. More recent learning-based approaches that approximate the entire feasible set of solutions have shown promise as a means to generate multiple fast and accurate IK results in parallel. However, existing learning-based techniques have a significant drawback: each robot of interest requires a specialized model that must be trained from scratch. To address this key shortcoming, we propose a novel distance-geometric robot representation coupled with a graph structure that allows us to leverage the sample efficiency of Euclidean equivariant functions and the generalizability of graph neural networks (GNNs). Our approach is generative graphical inverse kinematics (GGIK), the first learned IK solver able to accurately and efficiently produce a large number of diverse solutions in parallel while also displaying the ability to generalize -- a single learned model can be used to produce IK solutions for a variety of different robots. When compared to several other learned IK methods, GGIK provides more accurate solutions with the same amount of data. GGIK can generalize reasonably well to robot manipulators unseen during training. Additionally, GGIK can learn a constrained distribution that encodes joint limits and scales efficiently to larger robots and a high number of sampled solutions. Finally, GGIK can be used to complement local IK solvers by providing reliable initializations for a local optimization process.
Evaluating Continuous Basic Graph Patterns over Dynamic Link Data Graphs
Venue: arXiv cs.DB 2025
Year: 2025

In this paper, we investigate the problem of evaluating Basic Graph Patterns (BGP, for short, a subclass of SPARQL queries) over dynamic Linked Data graphs; i.e., Linked Data graphs that are continuously updated. We consider a setting where the updates are continuously received through a stream of messages and support both insertions and deletions of triples (updates are straightforwardly handled as a combination of deletions and insertions). In this context, we propose a set of in-memory algorithms minimizing the cached data to efficiently and continuously answer BGP queries. The queries are typically submitted into a system and continuously result in the delta answers while the update messages are processed. To efficiently and continuously evaluate the submitted query over the streaming data, as well as to minimize the amount of cached data, we propose an approach where the submitted query is decomposed into simpler subqueries and the query evaluation is achieved by combining the intermediate answers of the subqueries. Using this approach, the proposed algorithms compute the delta answers of a BGP query in polynomial time and space. Note that for certain subclasses of BGP queries, we show that the evaluation can be achieved in constant or linear time and space. Consolidating all the historical delta answers, the algorithms ensure that the answer to each query is constructed at any given time.
USC: Uncompromising Spatial Constraints for Safety-Oriented 3D Object Detectors in Autonomous Driving
Venue: arXiv cs.CV 2025
Year: 2025

In this work, we consider the safety-oriented performance of 3D object detectors in autonomous driving contexts. Specifically, despite impressive results shown by the mass literature, developers often find it hard to ensure the safe deployment of these learning-based perception models. Attributing the challenge to the lack of safety-oriented metrics, we hereby present uncompromising spatial constraints (USC), which characterize a simple yet important localization requirement demanding the predictions to fully cover the objects when seen from the autonomous vehicle. The constraints, as we formulate using the perspective and bird's-eye views, can be naturally reflected by quantitative measures, such that having an object detector with a higher score implies a lower risk of collision. Finally, beyond model evaluation, we incorporate the quantitative measures into common loss functions to enable safety-oriented fine-tuning for existing models. With experiments using the nuScenes dataset and a closed-loop simulation, our work demonstrates such considerations of safety notions at the perception level not only improve model performances beyond accuracy but also allow for a more direct linkage to actual system safety.
Characterising memory in infinite games
Venue: arXiv cs.FL 2025
Year: 2025

This paper is concerned with games of infinite duration played over potentially infinite graphs. Recently, Ohlmann (LICS 2022) presented a characterisation of objectives admitting optimal positional strategies, by means of universal graphs: an objective is positional if and only if it admits well-ordered monotone universal graphs. We extend Ohlmann's characterisation to encompass (finite or infinite) memory upper bounds. We prove that objectives admitting optimal strategies with $\varepsilon$-memory less than $m$ (a memory that cannot be updated when reading an $\varepsilon$-edge) are exactly those which admit well-founded monotone universal graphs whose antichains have size bounded by $m$. We also give a characterisation of chromatic memory by means of appropriate universal structures. Our results apply to finite as well as infinite memory bounds (for instance, to objectives with finite but unbounded memory, or with countable memory strategies). We illustrate the applicability of our framework by carrying out a few case studies, we provide examples witnessing limitations of our approach, and we discuss general closure properties which follow from our results.
Maker-Breaker is solved in polynomial time on hypergraphs of rank 3
Venue: arXiv cs.DM 2025
Year: 2025

In the Maker-Breaker positional game, Maker and Breaker take turns picking vertices of a hypergraph $H$, and Maker wins if and only if she possesses all the vertices of some edge of $H$. Deciding the outcome (i.e. which player has a winning strategy) is PSPACE-complete even when restricted to 5-uniform hypergraphs (Koepke, 2025). On hypergraphs of rank 3, a structural characterization of the outcome and a polynomial-time algorithm have been obtained for two subcases: one by Kutz (2005), the other by Rahman and Watson (2020) who conjectured that their result should generalize to all hypergraphs of rank 3. We prove this conjecture through a structural characterization of the outcome and a description of both players' optimal strategies, all based on intersections of some key subhypergraph collections, from which we derive a polynomial-time algorithm. Another corollary of our structural result is that, if Maker has a winning strategy on a hypergraph of rank 3, then she can ensure to win the game in a number of rounds that is logarithmic in the number of vertices. Note: This paper provides a counterexample to a similar result which was incorrectly claimed (arXiv:2209.11202, Theorem 22).
A multimodal stress detection dataset with facial expressions and physiological signals
Venue: arXiv cs.MM 2025
Year: 2025

Affective computing has garnered the attention and interest of researchers in recent years, as there is a need for AI systems to better understand and react to human emotions. However, analyzing human emotions, such as mood or stress, is quite complex. While various stress studies use facial expressions and wearables, most existing datasets rely on processing data from a single modality. This paper presents EmpathicSchool, a novel dataset that captures facial expressions and the associated physiological signals, such as heart rate, electrodermal activity, and skin temperature, under different stress levels. The data was collected from 30 participants during different sessions for about ninety minutes each (for a total of 40 hours). The data includes seven different signal types, including both computer vision and physiological features that can be used to detect stress. In addition, various experiments were conducted to validate the signal quality.
EiHi Net: Out-of-Distribution Generalization Paradigm
Venue: arXiv cs.CV 2025
Year: 2025

This paper develops a new EiHi net to solve the out-of-distribution (OoD) generalization problem in deep learning. EiHi net is a model learning paradigm that can be blessed on any visual backbone. This paradigm can change the previous learning method of the deep model, namely find out correlations between inductive sample features and corresponding categories, which suffers from pseudo correlations between indecisive features and labels. We fuse SimCLR and VIC-Reg via explicitly and dynamically establishing the original - positive - negative sample pair as a minimal learning element, the deep model iteratively establishes a relationship close to the causal one between features and labels, while suppressing pseudo correlations. To further validate the proposed model, and strengthen the established causal relationships, we develop a human-in-the-loop strategy, with few guidance samples, to prune the representation space directly. Finally, it is shown that the developed EiHi net makes significant improvements in the most difficult and typical OoD dataset Nico, compared with the current SOTA results, without any domain ($e.g.$ background, irrelevant features) information.
Computing maximal palindromes in non-standard matching models
Venue: arXiv cs.DS 2025
Year: 2025

Palindromes are popular and important objects in textual data processing, bioinformatics, and combinatorics on words. Let $S = XaY$ be a string where $X$ and $Y$ are of the same length, and $a$ is either a single character or the empty string. Then, there exist two alternative definitions for palindromes: $S$ is said to be a palindrome if $S$ is equal to its reversal $S^R$ (Reversal-based definition); or if its right-arm $Y$ is equal to the reversal of its left-arm $X^R$ (Symmetry-based definition). It is clear that if the ``equality'' ($\approx$) used in both definitions is exact character matching ($=$), then the two definitions are the same. However, if we apply other string-equality criteria $\approx$, including the complementary-matching model for biological sequences, the Cartesian-tree model [Park et al., TCS 2020], the parameterized model [Baker, JCSS 1996], the order-preserving model [Kim et al., TCS 2014], and the palindromic-structure model [I et al., TCS 2013], then are the reversal-based palindromes and the symmetry-based palindromes the same? To the best of our knowledge, no previous work has considered or answered this natural question. In this paper, we first provide answers to this question, and then present efficient algorithms for computing all maximal palindromes under the non-standard matching models in a given string. After confirming that Gusfield's offline suffix-tree-based algorithm for computing maximal symmetry-based palindromes can be readily extended to the aforementioned matching models, we show how to extend Manacher's online algorithm for computing maximal reversal-based palindromes in linear time for all the aforementioned matching models.
A Logic for Expressing Log-Precision Transformers
Venue: arXiv cs.LG 2025
Year: 2025

One way to interpret the reasoning power of transformer-based language models is to describe the types of logical rules they can resolve over some input text. Recently, Chiang et al. (2023) showed that finite-precision transformers can be equivalently expressed in a generalization of first-order logic. However, finite-precision transformers are a weak transformer variant because, as we show, a single head can only attend to a constant number of tokens and, in particular, cannot represent uniform attention. Since attending broadly is a core capability for transformers, we ask whether a minimally more expressive model that can attend universally can also be characterized in logic. To this end, we analyze transformers whose forward pass is computed in $\log n$ precision on contexts of length $n$. We prove that any log-precision transformer can be equivalently expressed as a first-order logic sentence that, in addition to standard universal and existential quantifiers, may also contain majority-vote quantifiers. This is the tightest known upper bound and first logical characterization of log-precision transformers.
Oze: Decentralized Graph-based Concurrency Control for Long-running Update Transactions (Extended Version)
Venue: arXiv cs.DB 2025
Year: 2025

This paper proposes Oze, a concurrency control protocol that handles heterogeneous workloads, including long-running update transactions. Oze explores a large scheduling space using a multi-version serialization graph to reduce false positives. Oze manages the graph in a decentralized manner to exploit many cores in modern servers. We further propose an OLTP benchmark, BoMB (Bill of Materials Benchmark), based on a use case in an actual manufacturing company. BoMB consists of one long-running update transaction and five short transactions that conflict with each other. Experiments using BoMB show that Oze can handle the long-running update transaction while achieving four orders of magnitude higher throughput than state-of-the-art optimistic and multi-version protocols and up to five times higher throughput than pessimistic protocols. We also show Oze performs comparably with existing techniques even in a typical OLTP workload, TPC-C, thanks to a protocol switching mechanism.
A policy gradient approach for Finite Horizon Constrained Markov Decision Processes
Venue: arXiv cs.LG 2025
Year: 2025

The infinite horizon setting is widely adopted for problems of reinforcement learning (RL). These invariably result in stationary policies that are optimal. In many situations, finite horizon control problems are of interest and for such problems, the optimal policies are time-varying in general. Another setting that has become popular in recent times is of Constrained Reinforcement Learning, where the agent maximizes its rewards while it also aims to satisfy some given constraint criteria. However, this setting has only been studied in the context of infinite horizon MDPs where stationary policies are optimal. We present an algorithm for constrained RL in the Finite Horizon Setting where the horizon terminates after a fixed (finite) time. We use function approximation in our algorithm which is essential when the state and action spaces are large or continuous and use the policy gradient method to find the optimal policy. The optimal policy that we obtain depends on the stage and so is non-stationary in general. To the best of our knowledge, our paper presents the first policy gradient algorithm for the finite horizon setting with constraints. We show the convergence of our algorithm to a constrained optimal policy. We also compare and analyze the performance of our algorithm through experiments and show that our algorithm performs better than some other well known algorithms.
Algorithms for Weighted Pushdown Automata
Venue: arXiv cs.CL 2025
Year: 2025

Weighted pushdown automata (WPDAs) are at the core of many natural language processing tasks, like syntax-based statistical machine translation and transition-based dependency parsing. As most existing dynamic programming algorithms are designed for context-free grammars (CFGs), algorithms for PDAs often resort to a PDA-to-CFG conversion. In this paper, we develop novel algorithms that operate directly on WPDAs. Our algorithms are inspired by Lang's algorithm, but use a more general definition of pushdown automaton and either reduce the space requirements by a factor of $|Γ|$ (the size of the stack alphabet) or reduce the runtime by a factor of more than $|Q|$ (the number of states). When run on the same class of PDAs as Lang's algorithm, our algorithm is both more space-efficient by a factor of $|Γ|$ and more time-efficient by a factor of $|Q| \cdot |Γ|$.