OpenRaiser/Intern-Atlas huggingface dataset:
First Order Logic and Twin-Width in Tournaments and Dense Oriented Graphs
Venue: arXiv cs.LO 2025
Year: 2025

We characterise the classes of tournaments with tractable first-order model checking. For every hereditary class of tournaments $\mathcal T$, first-order model checking is either fixed parameter tractable or $\textrm{AW}[*]$-hard. This dichotomy coincides with the fact that $\mathcal T$ has either bounded or unbounded twin-width, and that the growth of $\mathcal T$ is either at most exponential or at least factorial. From the model-theoretic point of view, we show that NIP classes of tournaments coincide with bounded twin-width. Twin-width is also characterised by three infinite families of obstructions: $\mathcal T$ has bounded twin-width if and only if it excludes at least one tournament from each family. This generalises results of Bonnet et al.\ on ordered graphs. The key for these results is a polynomial time algorithm that takes as input a tournament $T$ and computes a linear order $<$ on $V(T)$ such that the twin-width of the birelation $(T,<)$ is at most some function of the twin-width of $T$. Since approximating twin-width can be done in polynomial time for an ordered structure $(T,<)$, this provides a polynomial time approximation of twin-width for tournaments. Our results extend to oriented graphs with stable sets of bounded size, which may also be augmented by arbitrary binary relations.
Computing Tree Decompositions with Small Independence Number
Venue: arXiv cs.DS 2025
Year: 2025

The independence number of a tree decomposition is the maximum of the independence numbers of the subgraphs induced by its bags. The tree-independence number of a graph is the minimum independence number of a tree decomposition of it. Several NP-hard graph problems, like maximum weight independent set, can be solved in time n^{O(k)} if the input n-vertex graph is given together with a tree decomposition of independence number k. Yolov, in [SODA 2018], gave an algorithm that, given an n-vertex graph G and an integer k, in time n^{O(k^3)} either constructs a tree decomposition of G whose independence number is O(k^3) or correctly reports that the tree-independence number of G is larger than k. In this paper, we first give an algorithm for computing the tree-independence number with a better approximation ratio and running time and then prove that our algorithm is, in some sense, the best one can hope for. More precisely, our algorithm runs in time 2^{O(k^2)} n^{O(k)} and either outputs a tree decomposition of G with independence number at most $8k$, or determines that the tree-independence number of G is larger than k. This implies 2^{O(k^2)} n^{O(k)}-time algorithms for various problems, like maximum weight independent set, parameterized by the tree-independence number k without needing the decomposition as an input. Assuming Gap-ETH, an n^{Ω(k)} factor in the running time is unavoidable for any approximation algorithm for the tree-independence number. Our second result is that the exact computation of the tree-independence number is para-NP-hard: We show that for every constant k \ge 4 it is NP-hard to decide if a given graph has the tree-independence number at most k.
Multi-Step Deductive Reasoning Over Natural Language: An Empirical Study on Out-of-Distribution Generalisation
Venue: arXiv cs.CL 2025
Year: 2025

Combining deep learning with symbolic logic reasoning aims to capitalize on the success of both fields and is drawing increasing attention. Inspired by DeepLogic, an end-to-end model trained to perform inference on logic programs, we introduce IMA-GloVe-GA, an iterative neural inference network for multi-step reasoning expressed in natural language. In our model, reasoning is performed using an iterative memory neural network based on RNN with a gated attention mechanism. We evaluate IMA-GloVe-GA on three datasets: PARARULES, CONCEPTRULES V1 and CONCEPTRULES V2. Experimental results show DeepLogic with gated attention can achieve higher test accuracy than DeepLogic and other RNN baseline models. Our model achieves better out-of-distribution generalisation than RoBERTa-Large when the rules have been shuffled. Furthermore, to address the issue of unbalanced distribution of reasoning depths in the current multi-step reasoning datasets, we develop PARARULE-Plus, a large dataset with more examples that require deeper reasoning steps. Experimental results show that the addition of PARARULE-Plus can increase the model's performance on examples requiring deeper reasoning depths. The source code and data are available at https://github.com/Strong-AI-Lab/Multi-Step-Deductive-Reasoning-Over-Natural-Language.
Uncertainty-Driven Action Quality Assessment
Venue: arXiv cs.CV 2025
Year: 2025

Automatic action quality assessment (AQA) has attracted increasing attention due to its wide applications. However, most existing AQA methods employ deterministic models to predict the final score for each action, while overlooking the subjectivity and diversity among expert judges during the scoring process. In this paper, we propose a novel probabilistic model, named Uncertainty-Driven AQA (UD-AQA), to utilize and capture the diversity among multiple judge scores. Specifically, we design a Conditional Variational Auto-Encoder (CVAE)-based module to encode the uncertainty in expert assessment, where multiple judge scores can be produced by sampling latent features from the learned latent space multiple times. To further utilize the uncertainty, we generate the estimation of uncertainty for each prediction, which is employed to re-weight AQA regression loss, effectively reducing the influence of uncertain samples during training. Moreover, we further design an uncertainty-guided training strategy to dynamically adjust the learning order of the samples from low uncertainty to high uncertainty. The experiments show that our proposed method achieves competitive results on three benchmarks including the Olympic events MTL-AQA and FineDiving, and the surgical skill JIGSAWS datasets.
A point to set principle for finite-state dimension
Venue: arXiv cs.CC 2025
Year: 2025

Effective dimension has proven very useful in geometric measure theory through the point-to-set principle \cite{LuLu18}\ that characterizes Hausdorff dimension by relativized effective dimension. Finite-state dimension is the least demanding effectivization in this context \cite{FSD}\ that among other results can be used to characterize Borel normality \cite{BoHiVi05}. In this paper we prove a characterization of finite-state dimension in terms of information content of a real number at a certain precision. We then use this characterization to give a robust concept of relativized normality and prove a finite-state dimension point-to-set principle. We finish with an open question on the equidistribution properties of relativized normality.
An Approximate Generalization of the Okamura-Seymour Theorem
Venue: arXiv cs.DM 2025
Year: 2025

We consider the problem of multicommodity flows in planar graphs. Okamura and Seymour showed that if all the demands are incident on one face, then the cut-condition is sufficient for routing demands. We consider the following generalization of this setting and prove an approximate max flow-min cut theorem: for every demand edge, there exists a face containing both its end points. We show that the cut-condition is sufficient for routing $Ω(1)$-fraction of all the demands. To prove this, we give a $L_1$-embedding of the planar metric which approximately preserves distance between all pair of points on the same face.
Maintaining Performance with Less Data
Venue: arXiv cs.LG 2025
Year: 2025

We propose a novel method for training a neural network for image classification to reduce input data dynamically, in order to reduce the costs of training a neural network model. As Deep Learning tasks become more popular, their computational complexity increases, leading to more intricate algorithms and models which have longer runtimes and require more input data. The result is a greater cost on time, hardware, and environmental resources. By using data reduction techniques, we reduce the amount of work performed, and therefore the environmental impact of AI techniques, and with dynamic data reduction we show that accuracy may be maintained while reducing runtime by up to 50%, and reducing carbon emission proportionally.
On Brooks' Theorem
Venue: arXiv cs.DM 2025
Year: 2025

In this note we give two proofs of Brooks' Theorem. The first is obtained by modifying an earlier proof and the second by combining two earlier proofs. We believe these proofs are easier to teach in Computer Science courses.
Measuring the Availability and Response Times of Public Encrypted DNS Resolvers
Venue: arXiv cs.CR 2025
Year: 2025

Unencrypted DNS traffic between users and DNS resolvers can lead to privacy and security concerns. In response to these privacy risks, many browser vendors have deployed DNS-over-HTTPS (DoH) to encrypt queries between users and DNS resolvers. Today, many client-side deployments of DoH, particularly in browsers, select between only a few resolvers, despite the fact that many more encrypted DNS resolvers are deployed in practice. Unfortunately, if users only have a few choices of encrypted resolver, and only a few perform well from any particular vantage point, then the privacy problems that DoH was deployed to help address merely shift to a different set of third parties. It is thus important to assess the performance characteristics of more encrypted DNS resolvers, to determine how many options for encrypted DNS resolvers users tend to have in practice. In this paper, we explore the performance of a large group of encrypted DNS resolvers supporting DoH by measuring DNS query response times from global vantage points in North America, Europe, and Asia. Our results show that many non-mainstream resolvers have higher response times than mainstream resolvers, particularly for non-mainstream resolvers that are queried from more distant vantage points -- suggesting that most encrypted DNS resolvers are not replicated or anycast. In some cases, however, certain non-mainstream resolvers perform at least as well as mainstream resolvers, suggesting that users may be able to use a broader set of encrypted DNS resolvers than those that are available in current browser configurations.
Transferable Adversarial Examples with Bayes Approach
Venue: arXiv cs.LG 2025
Year: 2025

The vulnerability of deep neural networks (DNNs) to black-box adversarial attacks is one of the most heated topics in trustworthy AI. In such attacks, the attackers operate without any insider knowledge of the model, making the cross-model transferability of adversarial examples critical. Despite the potential for adversarial examples to be effective across various models, it has been observed that adversarial examples that are specifically crafted for a specific model often exhibit poor transferability. In this paper, we explore the transferability of adversarial examples via the lens of Bayesian approach. Specifically, we leverage Bayesian approach to probe the transferability and then study what constitutes a transferability-promoting prior. Following this, we design two concrete transferability-promoting priors, along with an adaptive dynamic weighting strategy for instances sampled from these priors. Employing these techniques, we present BayAtk. Extensive experiments illustrate the significant effectiveness of BayAtk in crafting more transferable adversarial examples against both undefended and defended black-box models compared to existing state-of-the-art attacks.
Differentiable Inductive Logic Programming in High-Dimensional Space
Venue: arXiv cs.AI 2025
Year: 2025

Synthesizing large logic programs through symbolic Inductive Logic Programming (ILP) typically requires intermediate definitions. However, cluttering the hypothesis space with intensional predicates typically degrades performance. In contrast, gradient descent provides an efficient way to find solutions within such high-dimensional spaces. Neuro-symbolic ILP approaches have not fully exploited this so far. We propose extending the δILP approach to inductive synthesis with large-scale predicate invention, thus allowing us to exploit the efficacy of high-dimensional gradient descent. We show that large-scale predicate invention benefits differentiable inductive synthesis through gradient descent and allows one to learn solutions for tasks beyond the capabilities of existing neuro-symbolic ILP systems. Furthermore, we achieve these results without specifying the precise structure of the solution within the language bias.
Toward Interpretable Sleep Stage Classification Using Cross-Modal Transformers
Venue: arXiv cs.LG 2025
Year: 2025

Accurate sleep stage classification is significant for sleep health assessment. In recent years, several machine-learning based sleep staging algorithms have been developed , and in particular, deep-learning based algorithms have achieved performance on par with human annotation. Despite improved performance, a limitation of most deep-learning based algorithms is their black-box behavior, which have limited their use in clinical settings. Here, we propose a cross-modal transformer, which is a transformer-based method for sleep stage classification. The proposed cross-modal transformer consists of a novel cross-modal transformer encoder architecture along with a multi-scale one-dimensional convolutional neural network for automatic representation learning. Our method outperforms the state-of-the-art methods and eliminates the black-box behavior of deep-learning models by utilizing the interpretability aspect of the attention modules. Furthermore, our method provides considerable reductions in the number of parameters and training time compared to the state-of-the-art methods. Our code is available at https://github.com/Jathurshan0330/Cross-Modal-Transformer. A demo of our work can be found at https://bit.ly/Cross_modal_transformer_demo.
C-Causal Blindness
Venue: arXiv cs.AI 2025
Year: 2025

This text is concerned with a hypothetical flavour of cognitive blindness referred to in this paper as \textit{C-Causal Blindness} or C-CB. A cognitive blindness where the policy to obtain the objective leads to the state to be avoided. A literal example of C-CB would be \textit{Kurt Gödel's} decision to starve for \textit{"fear of being poisoned"} - take this to be premise \textbf{A}. The objective being \textit{"to avoid being poisoned (so as to not die)"}: \textbf{C}, the plan or policy being \textit{"don't eat"}: \textbf{B}, and the actual outcome having been \textit{"dying"}: $\lnot$\textbf{C} - the state that Gödel wanted to avoid to begin with. Gödel pursued a strategy that caused the result he wanted to avoid. An experimental computational framework is proposed to show the isomorphic relationship between C-CB in brain computations, logic, and computer computations using a new proposed algorithm: a Weighted Hidden Markov Model.
Efficient Contextual Preferential Bayesian Optimization with Historical Examples
Venue: arXiv cs.LG 2025
Year: 2025

State-of-the-art multi-objective optimization often assumes a known utility function, learns it interactively, or computes the full Pareto front-each requiring costly expert input.~Real-world problems, however, involve implicit preferences that are hard to formalize. To reduce expert involvement, we propose an offline, interpretable utility learning method that uses expert knowledge, historical examples, and coarse information about the utility space to reduce sample requirements. We model uncertainty via a full Bayesian posterior and propagate it throughout the optimization process. Our method outperforms standard Gaussian processes and BOPE across four domains, showing strong performance even with biased samples, as encountered in the real-world, and limited expert input.
Targeted Advertising on Social Networks Using Online Variational Tensor Regression
Venue: arXiv cs.SI 2025
Year: 2025

This paper is concerned with online targeted advertising on social networks. The main technical task we address is to estimate the activation probability for user pairs, which quantifies the influence one user may have on another towards purchasing decisions. This is a challenging task because one marketing episode typically involves a multitude of marketing campaigns/strategies of different products for highly diverse customers. In this paper, we propose what we believe is the first tensor-based contextual bandit framework for online targeted advertising. The proposed framework is designed to accommodate any number of feature vectors in the form of multi-mode tensor, thereby enabling to capture the heterogeneity that may exist over user preferences, products, and campaign strategies in a unified manner. To handle inter-dependency of tensor modes, we introduce an online variational algorithm with a mean-field approximation. We empirically confirm that the proposed TensorUCB algorithm achieves a significant improvement in influence maximization tasks over the benchmarks, which is attributable to its capability of capturing the user-product heterogeneity.
Historical/temporal necessities/possibilities, and a logical theory of them in branching time
Venue: arXiv cs.CL 2025
Year: 2025

In this paper, we do three kinds of work. First, we recognize four notions of necessity and two notions of possibility related to time flow, namely strong/weak historical/temporal necessities, as well as historical/temporal possibilities, which are motivated more from a linguistic perspective than from a philosophical one. Strong/weak historical necessities and historical possibility typically concern the possible futures of the present world, and strong/weak temporal necessities and temporal possibility concern possible timelines of alternatives of the present world. Second, we provide our approach to the six notions and present a logical theory of them in branching time. Our approach to the six notions is as follows. The agent has a system of ontic rules that determine expected timelines. She treats some ontic rules as undefeatable, determining accepted timelines. The domains of strong/weak historical necessities, respectively, consist of accepted and expected timelines passing through the present moment, and historical possibility is the dual of strong historical necessity. The domains of strong/weak temporal necessities, respectively, consist of accepted and expected timelines, and temporal possibility is the dual of strong temporal necessity. The logical theory has six operators: a last-moment operator, a next-moment operator, and four operators for the four notions of necessity. Formulas' evaluation contexts consist of a tree-like model representing a time flow, a context representing the agent's system of ontic rules, a timeline, and an instant. Third, we offer an axiomatic system for the logical theory and show its soundness and completeness.
Space-efficient Data Structure for Next/Previous Larger/Smaller Value Queries
Venue: arXiv cs.DS 2025
Year: 2025

Given an array of size $n$ from a total order, we consider the problem of constructing a data structure that supports various queries (range minimum/maximum queries with their variants and next/previous larger/smaller queries) efficiently. In the encoding model (i.e., the queries can be answered without the input array), we propose a $(3.701n + o(n))$-bit data structure, which supports all these queries in $O(\log^{(\ell)}n)$ time, for any positive constant integer $\ell$ (here, $\log^{(1)} n = \log n$, and for $\ell > 1$, $\log^{(\ell)} n = \log ({\log^{(\ell-1)}} n)$). The space of our data structure matches the current best upper bound of Tsur (Inf. Process. Lett., 2019), which does not support the queries efficiently. Also, we show that at least $3.16n-Θ(\log n)$ bits are necessary for answering all the queries. Our result is obtained by generalizing Gawrychowski and Nicholson's $(3n - Θ(\log n))$-bit lower bound (ICALP, 15) for answering range minimum and maximum queries on a permutation of size $n$.
Generalized $k$-Center: Distinguishing Doubling and Highway Dimension
Venue: arXiv cs.DS 2025
Year: 2025

We consider generalizations of the $k$-Center problem in graphs of low doubling and highway dimension. For the Capacitated $k$-Supplier with Outliers (CkSwO) problem, we show an efficient parameterized approximation scheme (EPAS) when the parameters are $k$, the number of outliers and the doubling dimension of the supplier set. On the other hand, we show that for the Capacitated $k$-Center problem, which is a special case of CkSwO, obtaining a parameterized approximation scheme (PAS) is $\mathrm{W[1]}$-hard when the parameters are $k$, and the highway dimension. This is the first known example of a problem for which it is hard to obtain a PAS for highway dimension, while simultaneously admitting an EPAS for doubling dimension.
Hierarchical Relational Learning for Few-Shot Knowledge Graph Completion
Venue: arXiv cs.LG 2025
Year: 2025

Knowledge graphs (KGs) are powerful in terms of their inference abilities, but are also notorious for their incompleteness and long-tail distribution of relations. To address these challenges and expand the coverage of KGs, few-shot KG completion aims to make predictions for triplets involving novel relations when only a few training triplets are provided as reference. Previous methods have focused on designing local neighbor aggregators to learn entity-level information and/or imposing a potentially invalid sequential dependency assumption at the triplet level to learn meta relation information. However, pairwise triplet-level interactions and context-level relational information have been largely overlooked for learning meta representations of few-shot relations. In this paper, we propose a hierarchical relational learning method (HiRe) for few-shot KG completion. By jointly capturing three levels of relational information (entity-level, triplet-level and context-level), HiRe can effectively learn and refine meta representations of few-shot relations, and thus generalize well to new unseen relations. Extensive experiments on benchmark datasets validate the superiority of HiRe over state-of-the-art methods. The code can be found in https://github.com/alexhw15/HiRe.git.
RNN(p) for Power Consumption Forecasting
Venue: arXiv cs.LG 2025
Year: 2025

An elementary Recurrent Neural Network that operates on p time lags, called an RNN(p), is the natural generalisation of a linear autoregressive model ARX(p). It is a powerful forecasting tool for variables displaying inherent seasonal patterns across multiple time scales, as is often observed in energy, economic, and financial time series. The architecture of RNN(p) models, characterised by structured feedbacks across time lags, enables the design of efficient training strategies. We conduct a comparative study of learning algorithms for these models, providing a rigorous analysis of their computational complexity and training performance. We present two applications of RNN(p) models in power consumption forecasting, a key domain within the energy sector where accurate forecasts inform both operational and financial decisions. Experimental results show that RNN(p) models achieve excellent forecasting accuracy while maintaining a high degree of interpretability. These features make them well-suited for decision-making in energy markets and other fintech applications where reliable predictions play a significant economic role.