OpenRaiser/Intern-Atlas huggingface dataset:
An efficient, provably optimal algorithm for the 0-1 loss linear classification problem
Venue: arXiv cs.LG 2026
Year: 2026

Algorithms for solving the linear classification problem have a long history, dating back at least to 1936 with linear discriminant analysis. For linearly separable data, many algorithms can obtain the exact solution to the corresponding 0-1 loss classification problem efficiently, but for data which is not linearly separable, it has been shown that this problem, in full generality, is NP-hard. Alternative approaches all involve approximations of some kind, such as the use of surrogates for the 0-1 loss (for example, the hinge or logistic loss), none of which can be guaranteed to solve the problem exactly. Finding an efficient, rigorously proven algorithm for obtaining an exact (i.e., globally optimal) solution to the 0-1 loss linear classification problem remains an open problem. By analyzing the combinatorial and incidence relations between hyperplanes and data points, we derive a rigorous construction algorithm, incremental cell enumeration (ICE), that can solve the 0-1 loss classification problem exactly in $O(N^{D+1})$. To the best of our knowledge, this is the first standalone algorithm-one that does not rely on general-purpose solvers-with rigorously proven guarantees for this problem. Moreover, we further generalize ICE to address the polynomial hypersurface classification problem in $O(N^{G+1})$ time, where $G$ is determined by both the data dimension and the polynomial hypersurface degree. The correctness of our algorithm is proved by the use of tools from the theory of hyperplane arrangements and oriented matroids. We demonstrate the effectiveness of our algorithm on real-world datasets, achieving optimal training accuracy for small-scale datasets and higher test accuracy on most datasets. Furthermore, our complexity analysis shows that the ICE algorithm offers superior computational efficiency compared with state-of-the-art branch-and-bound algorithm.
MCQUIC - A Multicast Extension for QUIC
Venue: arXiv cs.NI 2026
Year: 2026

Mass live content, such as world cups, the Superbowl or the Olympics, attract audiences of hundreds of millions of viewers. While such events were predominantly consumed on TV, more and more viewers follow big events on the Internet, which poses a scalability challenge: current unicast delivery over the web comes with large overheads and is inefficient. An attractive alternative are multicast-based transmissions, however, current solutions have several drawbacks, mostly related to security and privacy, which prevent them from being implemented in browsers. In this paper we introduce a multicast extension to QUIC, a widely popular transport protocol standardized by the IETF, that solves several of these problems. It enables multicast delivery by offering encryption as well as integrity verification of packets distributed over multicast and automatic unicast fallback, which solves one of multicasts major obstacles to large scale deployment. It is transparent to applications and can be easily utilized by simply enabling an option in QUIC. This extension is soley focused on the transport layer and uses already existing multicast mechanisms on the network layer.
Analyzing the Performance of ChatGPT in Cardiology and Vascular Pathologies
Venue: arXiv cs.CL 2026
Year: 2026

The article aims to analyze the performance of ChatGPT, a large language model developed by OpenAI, in the context of cardiology and vascular pathologies. The study evaluated the accuracy of ChatGPT in answering challenging multiple-choice questions (QCM) using a dataset of 190 questions from the Siamois-QCM platform. The goal was to assess ChatGPT potential as a valuable tool in medical education compared to two well-ranked students of medicine. The results showed that ChatGPT outperformed the students, scoring 175 out of 190 correct answers with a percentage of 92.10\%, while the two students achieved scores of 163 and 159 with percentages of 85.78\% and 82.63\%, respectively. These results showcase how ChatGPT has the potential to be highly effective in the fields of cardiology and vascular pathologies by providing accurate answers to relevant questions.
Cloud and AI Infrastructure Cost Optimization: A Comprehensive Review of Strategies and Case Studies
Venue: arXiv cs.DC 2026
Year: 2026

Cloud computing has revolutionized the way organizations manage their IT infrastructure, but it has also introduced new challenges, such as managing cloud costs. The rapid adoption of artificial intelligence (AI) and machine learning (ML) workloads has further amplified these challenges, with GPU compute now representing 40-60\% of technical budgets for AI-focused organizations. This paper provides a comprehensive review of cloud and AI infrastructure cost optimization techniques, covering traditional cloud pricing models, resource allocation strategies, and emerging approaches for managing AI/ML workloads. We examine the dramatic cost reductions in large language model (LLM) inference which has decreased by approximately 10x annually since 2021 and explore techniques such as model quantization, GPU instance selection, and inference optimization. Real-world case studies from Amazon Prime Video, Pinterest, Cloudflare, and Netflix showcase practical application of these techniques. Our analysis reveals that organizations can achieve 50-90% cost savings through strategic optimization approaches. Future research directions in automated optimization, sustainability, and AI-specific cost management are proposed to advance the state of the art in this rapidly evolving field.
Dynamic Deep-Reinforcement-Learning Algorithm in Partially Observable Markov Decision Processes
Venue: arXiv cs.LG 2026
Year: 2026

Recent studies have greatly improved reinforcement learning, and an increased interest in real-world implementation has emerged. In many cases, the implementation is challenged by time-varying disturbances as it introduces hidden states, which makes the problem best described with Partially Observable Markov Decision Processes. An effective approach to address this problem is to introduce a Recurrent Neural Network (RNN) in place of a state estimator. However, only a few studies have investigated the types of information to be supplied to the RNN and the network architecture to handle them. This study discusses the effectiveness of the inclusion of action along with observation and the impact of network architecture to handle them by providing interpretations of how the trajectories are summarized at LSTM networks. Specifically, three novel approaches with different architectures are introduced. All algorithms demonstrated the effectiveness of the inclusion of the action trajectories in simulation environments. In particular, one of the developed algorithms, H-TD3, differs from the typical actor and critic network as the critic network is trained by utilizing the hidden states generated by the actor network as the summarized trajectory information. This novel approach exhibited the potential improvement of the computational time while maintaining the performance.
BOPIM: Bayesian Optimization for influence maximization on temporal networks
Venue: arXiv cs.SI 2026
Year: 2026

The goal of influence maximization (IM) is to select a small set of seed nodes which maximizes the spread of influence on a network. In this work, we propose BOPIM, a Bayesian Optimization (BO) algorithm for IM on temporal networks. The IM task is well-suited for a BO solution due to its expensive and complicated objective function. There are at least two key challenges, however, that must be overcome, primarily due to the inputs coming from a cardinality-constrained, non-Euclidean, combinatorial space. The first is constructing the kernel function for the Gaussian Process regression. We propose two kernels, one based on the Hamming distance between seed sets and the other leveraging the Jaccard coefficient between node's neighbors. The second challenge is the acquisition function. For this, we use the Expected Improvement function, suitably adjusting for noise in the observations, and optimize it using a greedy algorithm to account for the cardinality constraint. In numerical experiments on real-world networks, we prove that BOPIM outperforms competing methods and yields comparable influence spreads to a gold-standard greedy algorithm while being as much as ten times faster. In addition, we find that the Hamming kernel performs favorably compared to the Jaccard kernel in nearly all settings, a somewhat surprising result as the former does not explicitly account for the graph structure. Finally, we demonstrate two ways that the proposed method can quantify uncertainty in optimal seed sets. To our knowledge, this is the first attempt to look at uncertainty in the seed sets for IM.
Partially Observable Multi-Agent Reinforcement Learning with Information Sharing
Venue: arXiv cs.LG 2026
Year: 2026

We study provable multi-agent reinforcement learning (RL) in the general framework of partially observable stochastic games (POSGs). To circumvent the known hardness results and the use of computationally intractable oracles, we advocate leveraging the potential \emph{information-sharing} among agents, a common practice in empirical multi-agent RL, and a standard model for multi-agent control systems with communication. We first establish several computational complexity results to justify the necessity of information-sharing, as well as the observability assumption that has enabled quasi-polynomial time and sample single-agent RL with partial observations, for tractably solving POSGs. Inspired by the inefficiency of planning in the ground-truth model, we then propose to further \emph{approximate} the shared common information to construct an approximate model of the POSG, in which an approximate \emph{equilibrium} (of the original POSG) can be found in quasi-polynomial-time, under the aforementioned assumptions. Furthermore, we develop a partially observable multi-agent RL algorithm whose time and sample complexities are \emph{both} quasi-polynomial. Finally, beyond equilibrium learning, we extend our algorithmic framework to finding the \emph{team-optimal solution} in cooperative POSGs, i.e., decentralized partially observable Markov decision processes, a more challenging goal. We establish concrete computational and sample complexities under several structural assumptions of the model. We hope our study could open up the possibilities of leveraging and even designing different \emph{information structures}, a well-studied notion in control theory, for developing both sample- and computation-efficient partially observable multi-agent RL.
Finding Small Complete Subgraphs Efficiently
Venue: arXiv cs.DS 2026
Year: 2026

(I) We revisit the algorithmic problem of finding all triangles in a graph $G=(V,E)$ with $n$ vertices and $m$ edges. According to a result of Chiba and Nishizeki (1985), this task can be achieved by a combinatorial algorithm running in $O(m α) = O(m^{3/2})$ time, where $α= α(G)$ is the graph arboricity. We provide a new very simple combinatorial algorithm for finding all triangles in a graph and show that is amenable to the same running time analysis. We derive these worst-case bounds from first principles and with very simple proofs that do not rely on classic results due to Nash-Williams from the 1960s. Our experimental results show that our simple algorithm for triangle listing is substantially faster in practice than that of Chiba and Nishizeki on all examples of real-world graphs we tried. (II) We extend our arguments to the problem of finding all small complete subgraphs of a given fixed size. We show that the dependency on $m$ and $α$ in the running time $O(α^{\ell-2} \cdot m)$ of the algorithm of Chiba and Nishizeki for listing all copies of $K_\ell$, where $\ell \geq 3$, is asymptotically tight. (III) We give improved arboricity-sensitive running times for counting and/or detection of copies of $K_\ell$, for small $\ell \geq 4$. A key ingredient in our algorithms is, once again, the algorithm of Chiba and Nishizeki. Our new algorithms are faster than all previous algorithms in certain high-range arboricity intervals for every $\ell \geq 7$.
Hidden-Role Games: Equilibrium Concepts and Computation
Venue: arXiv cs.GT 2026
Year: 2026

In this paper, we study the class of games known as hidden-role games in which players are assigned privately to teams and are faced with the challenge of recognizing and cooperating with teammates. This model includes both popular recreational games such as the Mafia/Werewolf family and The Resistance (Avalon) and many real-world settings, such as distributed systems where nodes need to work together to accomplish a goal in the face of possible corruptions. There has been little to no formal mathematical grounding of such settings in the literature, and it was previously not even clear what the right solution concepts (notions of equilibria) should be. A suitable notion of equilibrium should take into account the communication channels available to the players (e.g., can they communicate? Can they communicate in private?). Defining such suitable notions turns out to be a nontrivial task with several surprising consequences. In this paper, we provide the first rigorous definition of equilibrium for hidden-role games, which overcomes serious limitations of other solution concepts not designed for hidden-role games. We then show that in certain cases, including the above recreational games, optimal equilibria can be computed efficiently. In most other cases, we show that computing an optimal equilibrium is at least NP-hard or coNP-hard. Lastly, we experimentally validate our approach by computing exact equilibria for complete 5- and 6-player Avalon instances whose size in terms of number of information sets is larger than $10^{56}$.
On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints
Venue: arXiv cs.DM 2026
Year: 2026

We study the SHORTEST PATH problem with positive disjunctive constraints from the perspective of parameterized complexity. For positive disjunctive constraints, there are certain pair of edges such that any feasible solution must contain at least one edge from every such pair. In this paper, we initiate the study of SHORTEST PATH problem subject to some positive disjunctive constraints the classical version is known to be NP-Complete. Formally, given an undirected graph G = (V, E) with a forcing graph H = (E, F) such that the vertex set of H is same as the edge set of G. The goal is to find a set S of at most k edges from G such that S forms a vertex cover in H and there is a path from s to t in the subgraph of G induced by the edge set S. In this paper, we consider two natural parameterizations for this problem. One natural parameter is the solution size, i.e. k for which we provide a kernel with O(k^5) vertices when both G and H are general graphs. Additionally, when either G or H (but not both) belongs to some special graph classes, we provied kernelization results with O(k^3) vertices . The other natural parameter we consider is structural properties of H, i.e. the size of a vertex deletion set of H to some special graph classes. We provide some fixed-parameter tractability results for those structural parameterizations.
A Multi-Token Coordinate Descent Method for Semi-Decentralized Vertical Federated Learning
Venue: arXiv cs.LG 2026
Year: 2026

Most federated learning (FL) methods use a client-server scheme, where clients communicate only with a central server. However, this scheme is prone to bandwidth bottlenecks at the server and has a single point of failure. In contrast, in a (fully) decentralized approach, clients communicate directly with each other, dispensing with the server and mitigating these issues. Yet, as the client network grows larger and sparser, the convergence of decentralized methods slows down, even failing to converge if the network is disconnected. This work addresses this gap between client-server and decentralized schemes, focusing on the vertical FL setup, where clients hold different features of the same samples. We propose multi-token coordinate descent (MTCD), a flexible semi-decentralized method for vertical FL that can exploit both client-server and client-client links. By selecting appropriate hyperparameters, MTCD recovers the client-sever and decentralized schemes as special cases. In fact, its decentralized instance is itself a novel method of independent interest. Yet, by controlling the degree of dependency on client-server links, MTCD can also explore a spectrum of schemes ranging from client-server to decentralized. We prove that, for sufficiently large batch sizes, MTCD converges at an $\mathcal{O}(1/T)$ rate for nonconvex objectives when the tokens roam across disjoint subsets of clients. To capture the aforementioned drawbacks of the client-server scheme succinctly, we model the relative impact of using client-server versus client-client links as the ratio of their "costs", which depends on the application. This allows us to demonstrate, both analytically and empirically, that by tuning the degree of dependency on the server, the semi-decentralized instances of MTCD can outperform both client-server and decentralized approaches across a range of applications.
Harmony and Duality: An introduction to Music Theory
Venue: arXiv cs.SD 2026
Year: 2026

We develop aspects of music theory related to harmony, such as scales, chord formation and improvisation from a combinatorial perspective. The goal is to provide a foundation for this subject by deriving the basic structure from a few assumptions, rather than writing down long lists of chords/scales to memorize without an underlying principle. Our approach involves introducing constraints that limit the possible scales we can consider. For example, we may impose the constraint that two voices cannot be only a semitone apart as this is too dissonant. We can then study scales that do not contain notes that are a semitone apart. A more refined constraint avoids three voices colliding by studying scales that do not have three notes separated only by semitones. Additionally, we require that our scales are complete, which roughly means that they are the maximal sets of tones that satisfy these constraints. As it turns out, completeness as applied to these simple two/three voice constraints characterizes the types of scales that are commonly used in music composition. Surprisingly, there is a correspondence between scales subject to the two-voice constraint and those subject to the three-voice constraint. We formulate this correspondence as a duality statement that provides a way to understand scales subject to one type of constraint in terms of scales subject to the other. Finally, we combine these constraint ideas to provide a classification of chords.
Expert-Aided Causal Discovery of Ancestral Graphs
Venue: arXiv cs.LG 2026
Year: 2026

Causal discovery (CD) is an important component of many scientific applications, yet most techniques produce unreliable point estimates that often contradict expert knowledge. To mitigate this, recent research has focused on ex-ante incorporation of background knowledge into the CD process, typically under an unrealistic causal sufficiency assumption. When probing experts is costly (e.g., hidden behind expensive LLM APIs), however, ex-post model refinement that maximizes query utility is preferable. Also, when independent experts provide conflicting but better-than-random feedback, a principled aggregation method is required. In this context, we introduce the first CD algorithm that enables (i) distributional inference over ancestral graphs (AGs), which represent causal systems under latent confounding, and (ii) integration of both ex-ante and uncertain ex-post expert knowledge. Briefly, our method is a diversity-seeking reinforcement learning algorithm, termed Ancestral GFlowNet (AGFN), whose policy we iteratively refine based on a Bayesian model of the noisy expert feedback. Importantly, we prove convergence to the true AG given sufficiently accurate responses. Through validation on synthetic and realistic datasets using simulated humans and LLMs, we show AGFN is competitive with or superior to strong baselines in terms of structural Hamming distance and Bayesian Information Criterion.
ELIP: Efficient Discriminative Language-Image Pre-training with Fewer Vision Tokens
Venue: arXiv cs.CV 2026
Year: 2026

Learning a versatile language-image model is computationally prohibitive under a limited computing budget. This paper delves into the \emph{efficient language-image pre-training}, an area that has received relatively little attention despite its importance in reducing computational cost and footprint. To that end, we propose a vision token pruning and merging method ELIP, to remove less influential tokens based on the supervision of language outputs. Our method is designed with several strengths, such as being computation-efficient, memory-efficient, and trainable-parameter-free, and is distinguished from previous vision-only token pruning approaches by its alignment with task objectives. We implement this method in a progressively pruning manner using several sequential blocks. To evaluate its generalization performance, we apply ELIP to three commonly used language-image pre-training models and utilize public image-caption pairs with 4M images for pre-training. Our experiments demonstrate that with the removal of ~30$\%$ vision tokens across 12 ViT layers, ELIP maintains significantly comparable performance with baselines ($\sim$0.32 accuracy drop on average) over various downstream tasks including cross-modal retrieval, VQA, image captioning, \emph{etc}. In addition, the spared GPU resources by our ELIP allow us to scale up with larger batch sizes, thereby accelerating model pre-training and even sometimes enhancing downstream model performance.
Seal2Real: Prompt Prior Learning on Diffusion Model for Unsupervised Document Seal Data Generation and Realisation
Venue: arXiv cs.CV 2026
Year: 2026

Seal-related tasks in document processing-such as seal segmentation, authenticity verification, seal removal, and text recognition under seals-hold substantial commercial importance. However, progress in these areas has been hindered by the scarcity of labeled document seal datasets, which are essential for supervised learning. To address this limitation, we propose Seal2Real, a novel generative framework designed to synthesize large-scale labeled document seal data. As part of this work, we also present Seal-DB, a comprehensive dataset containing 20,000 labeled images to support seal-related research. Seal2Real introduces a prompt prior learning architecture built upon a pre-trained Stable Diffusion model, effectively transferring its generative capability to the unsupervised domain of seal image synthesis. By producing highly realistic synthetic seal images, Seal2Real significantly enhances the performance of downstream seal-related tasks on real-world data. Experimental evaluations on the Seal-DB dataset demonstrate the effectiveness and practical value of the proposed framework. The dataset is available at https://github.com/liuyifan6613/DocBank-Document-Enhancement-Dataset.
Online Dispatching and Routing for Automated Guided Vehicles in Pickup and Delivery Systems on Loop-Based Graphs
Venue: arXiv cs.CE 2026
Year: 2026

Automated guided vehicles (AGVs) are widely used in various industries, and scheduling and routing them in a conflict-free manner is crucial to their efficient operation. We propose a loop-based algorithm that solves the online, conflict-free scheduling and routing problem for AGVs with any capacity and ordered jobs in loop-based graphs. The proposed algorithm is compared against an exact method, a greedy heuristic and a metaheuristic. We experimentally show, using theoretical and real instances on a model representing a real manufacturing plant, that this algorithm either outperforms the other algorithms or gets an equally good solution in less computing time.