OpenRaiser/Intern-Atlas huggingface dataset:
On Computing the Dollo-1 phylogeny in polynomial time
Venue: arXiv cs.DS 2025
Year: 2025

The Dollo model for reconstructing evolutionary trees from binary characters has been proposed as a generalization of the infinite sites model, also known as the Perfect Phylogeny. In particular, the Dollo model is considered more realistic than the Perfect Phylogeny for inferring the evolution of tumor mutations. In the case of binary matrices, the Dollo-$k$ model requires an evolutionary tree in which each character, corresponding to a column in the input matrix, may change from $0$ to $1$ at most once, and from $1$ to $0$ at most $k$ times throughout the entire tree. Given a binary matrix, the problem of deciding whether there exists a Dollo-$k$ tree compatible with the matrix is NP-complete for any fixed $k \geq 2$, while computing a Dollo-$0$ tree corresponds to the Perfect Phylogeny decision problem, which admits a simple linear-time algorithm. The Dollo-$1$ tree problem corresponds to the Persistent Phylogeny problem, whose computational complexity, albeit under an equivalent formulation, was posed as an open question 20 years ago. We solve this problem by presenting a polynomial-time algorithm for the Persistent Phylogeny problem. Our solution relies on efficiently solving a specific class of binary matrices, represented as bipartite graphs called \emph{skeleton graphs}, or simply skeletons. In these graphs, characters are \emph{maximal}, that is their corresponding sets of species are not related by inclusion.
Proportional Justified Representation
Venue: arXiv cs.GT 2025
Year: 2025

The goal of multi-winner elections is to choose a fixed-size committee based on voters' preferences. An important concern in this setting is representation: large groups of voters with cohesive preferences should be adequately represented by the election winners. In an influential paper, Aziz et al. proposed two axioms that aim to capture this idea: justified representation (JR) and its strengthening extended justified representation (EJR). We observe that EJR is incompatible with the highly desirable Perfect Representation (PR) criterion, and propose a relaxation of EJR, which we call Proportional Justified Representation (PJR). PJR is more demanding than JR, but, unlike EJR, it is compatible with PR, as well as with a stronger variant of this axiom, which we term Fractional Perfect Representation (FPR). Moreover, just like EJR, PJR can be used to characterise the classic Proportional Approval Voting (PAV) rule in the class of weighted PAV rules. On the other hand, we show that EJR provides stronger guarantees with respect to average voter satisfaction than PJR does.
Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph
Venue: arXiv cs.LG 2025
Year: 2025

Approximate nearest neighbor search (ANNS) is a fundamental problem in databases and data mining. A scalable ANNS algorithm should be both memory-efficient and fast. Some early graph-based approaches have shown attractive theoretical guarantees on search time complexity, but they all suffer from the problem of high indexing time complexity. Recently, some graph-based methods have been proposed to reduce indexing complexity by approximating the traditional graphs; these methods have achieved revolutionary performance on million-scale datasets. Yet, they still can not scale to billion-node databases. In this paper, to further improve the search-efficiency and scalability of graph-based methods, we start by introducing four aspects: (1) ensuring the connectivity of the graph; (2) lowering the average out-degree of the graph for fast traversal; (3) shortening the search path; and (4) reducing the index size. Then, we propose a novel graph structure called Monotonic Relative Neighborhood Graph (MRNG) which guarantees very low search complexity (close to logarithmic time). To further lower the indexing complexity and make it practical for billion-node ANNS problems, we propose a novel graph structure named Navigating Spreading-out Graph (NSG) by approximating the MRNG. The NSG takes the four aspects into account simultaneously. Extensive experiments show that NSG outperforms all the existing algorithms significantly. In addition, NSG shows superior performance in the E-commercial search scenario of Taobao (Alibaba Group) and has been integrated into their search engine at billion-node scale.
The Feeling of Success: Does Touch Sensing Help Predict Grasp Outcomes?
Venue: arXiv cs.RO 2025
Year: 2025

A successful grasp requires careful balancing of the contact forces. Deducing whether a particular grasp will be successful from indirect measurements, such as vision, is therefore quite challenging, and direct sensing of contacts through touch sensing provides an appealing avenue toward more successful and consistent robotic grasping. However, in order to fully evaluate the value of touch sensing for grasp outcome prediction, we must understand how touch sensing can influence outcome prediction accuracy when combined with other modalities. Doing so using conventional model-based techniques is exceptionally difficult. In this work, we investigate the question of whether touch sensing aids in predicting grasp outcomes within a multimodal sensing framework that combines vision and touch. To that end, we collected more than 9,000 grasping trials using a two-finger gripper equipped with GelSight high-resolution tactile sensors on each finger, and evaluated visuo-tactile deep neural network models to directly predict grasp outcomes from either modality individually, and from both modalities together. Our experimental results indicate that incorporating tactile readings substantially improve grasping performance.
Multiple-Instance, Cascaded Classification for Keyword Spotting in Narrow-Band Audio
Venue: arXiv cs.LG 2025
Year: 2025

We propose using cascaded classifiers for a keyword spotting (KWS) task on narrow-band (NB), 8kHz audio acquired in non-IID environments -- a more challenging task than most state-of-the-art KWS systems face. We present a model that incorporates Deep Neural Networks (DNNs), cascading, multiple-feature representations, and multiple-instance learning. The cascaded classifiers handle the task's class imbalance and reduce power consumption on computationally-constrained devices via early termination. The KWS system achieves a false negative rate of 6% at an hourly false positive rate of 0.75
A Generic Model for Swarm Intelligence and Its Validations
Venue: arXiv cs.AI 2025
Year: 2025

The modeling of emergent swarm intelligence constitutes a major challenge and it has been tackled in a number of different ways. However, existing approaches fail to capture the nature of swarm intelligence and they are either too abstract for practical application or not generic enough to describe the various types of emergence phenomena. In this paper, a contradiction-centric model for swarm intelligence is proposed, in which individu-als determine their behaviors based on their internal contradictions whilst they associate and interact to update their contradictions. The model hypothesizes that 1) the emergence of swarm intelligence is rooted in the de-velopment of individuals' internal contradictions and the interactions taking place between individuals and the environment, and 2) swarm intelligence is essentially a combinative reflection of the configurations of individuals' internal contradictions and the distributions of these contradictions across individuals. The model is formally described and five swarm intelligence systems are studied to illustrate its broad applicability. The studies confirm the generic character of the model and its effectiveness for describing the emergence of various kinds of swarm intelligence; and they also demonstrate that the model is straightforward to apply, without the need for complicated computations.
Deterministic Scheduling of Periodic Messages for Low Latency in Cloud RAN
Venue: arXiv cs.NI 2025
Year: 2025

Cloud-RAN (C-RAN) is a cellular network architecture where processing units, previously attached to antennas, are centralized in data centers. The main challenge in meeting protocol time constraints is minimizing the latency of periodic messages exchanged between antennas and processing units. We demonstrate that statistical multiplexing introduces significant logical latency due to buffering at network nodes to prevent collisions. To address this, we propose a deterministic scheme for periodic message transmission without collisions, eliminating latency caused by buffering. We develop several algorithms to compute such schemes for star-routed networks, a common topology where all antennas share a single link. First, we show that deterministic transmission is possible without buffering when routes are short or network load is low. Under high load, we allow buffering at processing units and introduce the Periodic Minimal Latency Scheduling (PMLS) algorithm, adapted from classical scheduling methods. Experimental results indicate that even at full load, PMLS finds deterministic transmission schemes with negligible logical latency, whereas statistical multiplexing incurs substantial delays. Moreover, PMLS runs in polynomial time and scales efficiently to hundreds of antennas. Building on this approach, we also derive low-latency periodic transmission schemes that coexist with additional random network traffic. This article extends previous work presented at ICT.
The Strange Attractor Model of Bipedal Locomotion and its Consequences on Motor Control
Venue: arXiv cs.RO 2025
Year: 2025

Despite decades of study, many unknowns exist about the mechanisms governing human locomotion. Current models and motor control theories can only partially capture the phenomenon. This may be a major cause of the reduced efficacy of lower limb rehabilitation therapies. Recently, it has been proposed that human locomotion can be planned in the task-space by taking advantage of the gravitational pull acting on the Centre of Mass (CoM) by modelling the attractor dynamics. The model proposed represents the CoM transversal trajectory as a harmonic oscillator propagating on the attractor manifold. However, the vertical trajectory of the CoM, controlled through ankle strategies, has not been accurately captured yet. Research Questions: Is it possible to improve the model accuracy by introducing a mathematical model of the ankle strategies by coordinating the heel-strike and toe-off strategies with the CoM movement? Our solution consists of closed-form equations that plan human-like trajectories for the CoM, the foot swing, and the ankle strategies. We have tested our model by extracting the biomechanics data and postural during locomotion from the motion capture trajectories of 12 healthy subjects at 3 self-selected speeds to generate a virtual subject using our model. Our virtual subject has been based on the average of the collected data. The model output shows our virtual subject has walking trajectories that have their features consistent with our motion capture data. Additionally, it emerged from the data analysis that our model regulates the stance phase of the foot as humans do. The model proves that locomotion can be modelled as an attractor dynamics, proving the existence of a nonlinear map that our nervous system learns. It can support a deeper investigation of locomotion motor control, potentially improving locomotion rehabilitation and assistive technologies.
Compact Formulation of the First Evolution Equation for Optimal Control Computation
Venue: arXiv cs.SY 2025
Year: 2025

The first evolution equation is derived under the Variation Evolving Method (VEM) that seeks optimal solutions with the variation evolution principle. To improve the performance, its compact form is developed. By replacing the states and costates variation evolution with that of the controls, the dimension-reduced Evolution Partial Differential Equation (EPDE) only solves the control variables along the variation time to get the optimal solution, and its definite conditions may be arbitrary. With this equation, the scale of the resulting Initial-value Problem (IVP), transformed via the semi-discrete method, is significantly reduced. Illustrative examples are solved and it is shown that the compact form evolution equation outperforms the primary form in the precision, and the efficiency may be higher for the dense discretization. Moreover, in discussing the connections to the classic iteration methods, it is uncovered that the computation scheme of the gradient method is the discrete implementation of the third evolution equation, and the compact form of the first evolution equation is a continuous realization of the Newton type iteration mechanism.
Minmax-Regret $k$-Sink Location on a Dynamic Tree Network with Uniform Capacities
Venue: arXiv cs.DS 2025
Year: 2025

A dynamic flow network $G$ with uniform capacity $c$ is a graph in which at most $c$ units of flow can enter an edge in one time unit. If flow enters a vertex faster than it can leave, congestion occurs. The evacuation problem is to evacuate all flow to sinks assuming that all flow is confluent, i.e., all flow passing through a particular vertex must follow the same exit edge. The $k$-sink location problem is to place $k$-sinks so as to minimize this evacuation time. Although the $k$-sink location problem is NP-Hard on a general graph it can be solved in $\tilde O(k^2 n)$ time on trees. The concept of minmax-regret arises from robust optimization. For each source, a range of possible flow values is provided and any scenario with flow values in those ranges might occur. The goal is to find a sink placement that minimizes, over all possible scenarios, the difference between the evacuation time to those sinks and the minimal evacuation time of that scenario. The Minmax-Regret $k$-Sink Location on a Dynamic Path Networks with uniform capacities is polynomial solvable in $n$ and $k$. Similarly, the Minmax-Regret $k$-center problem on trees is polynomial solvable in $n$ and $k$. Prior to this work, polynomial time solutions to the Minmax-Regret $k$-Sink Location on Dynamic Tree Networks with uniform capacities were only known for $k=1$. This paper solves this problem, for general $k,$ in time $$O\Bigl( \max(k^2 \log^2 k,\log ^2n)\, k^4 n^2 \log^5 n\Bigr)$$
Polyline Simplification has Cubic Complexity
Venue: arXiv cs.CG 2025
Year: 2025

In the classic polyline simplification problem we want to replace a given polygonal curve $P$, consisting of $n$ vertices, by a subsequence $P'$ of $k$ vertices from $P$ such that the polygonal curves $P$ and $P'$ are as close as possible. Closeness is usually measured using the Hausdorff or Fréchet distance. These distance measures can be applied "globally", i.e., to the whole curves $P$ and $P'$, or "locally", i.e., to each simplified subcurve and the line segment that it was replaced with separately (and then taking the maximum). This gives rise to four problem variants: Global-Hausdorff (known to be NP-hard), Local-Hausdorff (in time $O(n^3)$), Global-Fréchet (in time $O(k n^5)$), and Local-Fréchet (in time $O(n^3)$). Our contribution is as follows. - Cubic time for all variants: For Global-Fréchet we design an algorithm running in time $O(n^3)$. This shows that all three problems (Local-Hausdorff, Local-Fréchet, and Global-Fréchet) can be solved in cubic time. All these algorithms work over a general metric space such as $(\mathbb{R}^d,L_p)$, but the hidden constant depends on $p$ and (linearly) on $d$. - Cubic conditional lower bound: We provide evidence that in high dimensions cubic time is essentially optimal for all three problems (Local-Hausdorff, Local-Fréchet, and Global-Fréchet). Specifically, improving the cubic time to $O(n^{3-ε} \textrm{poly}(d))$ for polyline simplification over $(\mathbb{R}^d,L_p)$ for $p = 1$ would violate plausible conjectures. We obtain similar results for all $p \in [1,\infty), p \ne 2$. In total, in high dimensions and over general $L_p$-norms we resolve the complexity of polyline simplification with respect to Local-Hausdorff, Local-Fréchet, and Global-Fréchet, by providing new algorithms and conditional lower bounds.
Evolutionarily Stable Preferences Against Multiple Mutations in Multi-player Games
Venue: arXiv cs.GT 2025
Year: 2025

We use the indirect evolutionary approach to study evolutionarily stable preferences against multiple mutations in single- and multi-population matching settings, respectively. Players choose strategies to maximize their subjective preferences, which may be inconsistent with the material payoff function giving them the actual fitness values. In each of the two settings, $n$-player games are played, and we provide necessary and sufficient conditions for multi-mutation stability. These results definitely reveal the connection between the order of stability and the level of efficiency.
Integrating Project Spatial Coordinates into Pavement Management Prioritization
Venue: arXiv cs.CY 2025
Year: 2025

To date, pavement management software products and studies on optimizing the prioritization of pavement maintenance and rehabilitation (M&R) have been mainly focused on three parameters; the pre-treatment pavement condition, the rehabilitation cost, and the available budget. Yet, the role of the candidate projects' spatial characteristics in the decision-making process has not been deeply considered. Such a limitation, predominately, allows the recommended M&R projects' schedule to involve simultaneously running but spatially scattered construction sites, which are very challenging to monitor and manage. This study introduces a novel approach to integrate pavement segments' spatial coordinates into the M&R prioritization analysis. The introduced approach aims at combining the pavement segments with converged spatial coordinates to be repaired in the same timeframe without compromising the allocated budget levels or the overall target Pavement Condition Index (PCI). Such a combination would result in minimizing the routing of crews, materials and other equipment among the construction sites and would provide better collaborations and communications between the pavement maintenance teams. Proposed herein is a novel spatial clustering algorithm that automatically finds the projects within a certain budget and spatial constrains. The developed algorithm was successfully validated using 1,800 pavement maintenance projects from two real-life examples of the City of Milton, GA and the City of Tyler, TX.
The Multi-Agent Reinforcement Learning in MalmÖ (MARLÖ) Competition
Venue: arXiv cs.AI 2025
Year: 2025

Learning in multi-agent scenarios is a fruitful research direction, but current approaches still show scalability problems in multiple games with general reward settings and different opponent types. The Multi-Agent Reinforcement Learning in MalmÖ (MARLÖ) competition is a new challenge that proposes research in this domain using multiple 3D games. The goal of this contest is to foster research in general agents that can learn across different games and opponent types, proposing a challenge as a milestone in the direction of Artificial General Intelligence.
Double-Target Collaborative Spectrum Sharing for 6G Hybrid Satellite-Terrestrial Networks with User-Centric Channel Pools
Venue: arXiv cs.IT 2025
Year: 2025

Satellite and terrestrial cellular networks can be integrated together for extended broadband coverage in e.g., maritime communication scenarios, in the upcoming sixth-generation (6G) era. To counter spectrum scarcity, collaborative spectrum sharing is considered for a hybrid satellite-terrestrial network (HSTN) in this paper. With only slowly-varying large-scale channel state information (CSI), joint power and channel allocation is implemented for terrestrial mobile terminals (MTs) which share the same frequency band with the satellite MTs opportunistically. Specially, strict quality service assurance is adopted for terrestrial MTs under the constraint of leakage interference to satellite MTs. With the target of maximizing both the number of served terrestrial MTs and the average sum transmission rate, a double-target spectrum sharing problem is formulated. To solve the complicated mixed integer programming (MIP) problem efficiently, user-centric channel pools are introduced. Simulations demonstrate that the proposed spectrum sharing scheme could achieve a significant performance gain for the HSTN.
Learning from the Past: How Previous Technological Transformations Can Guide AI Development
Venue: arXiv cs.AI 2025
Year: 2025

Artificial Intelligence (AI) is rapidly changing many areas of society. While this transformation has tremendous potential, there are several challenges as well. Using the history of computing and the world-wide web as a guide, in this paper we identify pitfalls and solutions that suggest how AI can be developed to its full potential. If done right, AI will be instrumental in achieving the goals we set for the economy, the society, and the world in general.
Between the deterministic and non-deterministic query complexity
Venue: arXiv cs.CC 2025
Year: 2025

We consider problems that can be solved by asking certain queries. The deterministic query complexity $D(P,n)$ of a problem $P$ is the smallest number of queries needed to ask in order to find the solution with an input of size $n$ (in the worst case), while the non-deterministic query complexity $D_0(P,n)$ is the smallest number of queries needed to ask, in case we know the solution, to prove that it is indeed the solution (in the worst case). Equivalently, $D(P,n)$ is the largest number of queries needed to find the solution in case an Adversary is answering the queries, while $D_0(P)$ is the largest number of queries needed to find the solution in case an Adversary chooses the input. We define a series of quantities between these two values, $D_k(P,n)$ is the largest number of queries needed to find the solution in case an Adversary chooses the input, and answers the queries, but he can change the input at most $k$ times. We give bounds on $D_k(P,n)$ for various problems $P$.
Taming Unbalanced Training Workloads in Deep Learning with Partial Collective Operations
Venue: arXiv cs.DC 2025
Year: 2025

Load imbalance pervasively exists in distributed deep learning training systems, either caused by the inherent imbalance in learned tasks or by the system itself. Traditional synchronous Stochastic Gradient Descent (SGD) achieves good accuracy for a wide variety of tasks, but relies on global synchronization to accumulate the gradients at every training step. In this paper, we propose eager-SGD, which relaxes the global synchronization for decentralized accumulation. To implement eager-SGD, we propose to use two partial collectives: solo and majority. With solo allreduce, the faster processes contribute their gradients eagerly without waiting for the slower processes, whereas with majority allreduce, at least half of the participants must contribute gradients before continuing, all without using a central parameter server. We theoretically prove the convergence of the algorithms and describe the partial collectives in detail. Experimental results on load-imbalanced environments (CIFAR-10, ImageNet, and UCF101 datasets) show that eager-SGD achieves 1.27x speedup over the state-of-the-art synchronous SGD, without losing accuracy.
Guided Random Forest and its application to data approximation
Venue: arXiv cs.LG 2025
Year: 2025

We present a new way of constructing an ensemble classifier, named the Guided Random Forest (GRAF) in the sequel. GRAF extends the idea of building oblique decision trees with localized partitioning to obtain a global partitioning. We show that global partitioning bridges the gap between decision trees and boosting algorithms. We empirically demonstrate that global partitioning reduces the generalization error bound. Results on 115 benchmark datasets show that GRAF yields comparable or better results on a majority of datasets. We also present a new way of approximating the datasets in the framework of random forests.