OpenRaiser/Intern-Atlas huggingface dataset:
A Discussion to Qualify Intelligence
Venue: arXiv cs.AI 2025
Year: 2025

Our understanding of intelligence is directed primarily at the human level. This paper attempts to give a more unifying definition that can be applied to the natural world in general and then Artificial Intelligence. The definition would be used more to qualify than quantify it and might help when making judgements on the matter. While correct behaviour is the preferred definition, a metric that is grounded in Kolmogorov's Complexity Theory is suggested, which leads to a measurement about entropy. A version of an accepted AI test is then put forward as the 'acid test' and might be what a free-thinking program would try to achieve. Recent work by the author has been more from a direction of mechanical processes, or ones that might operate automatically. This paper agrees that intelligence is a pro-active event, but also notes a second aspect to it that is in the background and mechanical. The paper suggests looking at intelligence and the conscious as being slightly different, where the conscious is this more mechanical aspect. In fact, a surprising conclusion can be a passive but intelligent brain being invoked by active and less intelligent senses.
RankMerging: A supervised learning-to-rank framework to predict links in large social network
Venue: arXiv cs.SI 2025
Year: 2025

Uncovering unknown or missing links in social networks is a difficult task because of their sparsity and because links may represent different types of relationships, characterized by different structural patterns. In this paper, we define a simple yet efficient supervised learning-to-rank framework, called RankMerging, which aims at combining information provided by various unsupervised rankings. We illustrate our method on three different kinds of social networks and show that it substantially improves the performances of unsupervised metrics of ranking. We also compare it to other combination strategies based on standard methods. Finally, we explore various aspects of RankMerging, such as feature selection and parameter estimation and discuss its area of relevance: the prediction of an adjustable number of links on large networks.
Building a Balanced k-d Tree in O(kn log n) Time
Venue: arXiv cs.DS 2025
Year: 2025

The original description of the k-d tree recognized that rebalancing techniques, such as are used to build an AVL tree or a red-black tree, are not applicable to a k-d tree. Hence, in order to build a balanced k-d tree, it is necessary to find the median of the data for each recursive subdivision of those data. The sort or selection that is used to find the median for each subdivision strongly influences the computational complexity of building a k-d tree. This paper discusses an alternative algorithm that builds a balanced k-d tree by presorting the data in each of k dimensions prior to building the tree. It then preserves the order of these k sorts during tree construction and thereby avoids the requirement for any further sorting. Moreover, this algorithm is amenable to parallel execution via multiple threads. Compared to an algorithm that finds the median for each recursive subdivision, this presorting algorithm has equivalent performance for four dimensions and better performance for three or fewer dimensions.
A multistep segmentation algorithm for vessel extraction in medical imaging
Venue: arXiv cs.CV 2025
Year: 2025

The main contribution of this paper is to propose an iterative procedure for tubular structure segmentation of 2D images, which combines tight frame of Curvelet transforms with a SURE technique thresholding which is based on principle obtained by minimizing Stein Unbiased Risk Estimate for denoising. This proposed algorithm is mainly based on the TFA proposal presented in [1, 9], which we use eigenvectors of Hessian matrix of image for improving this iterative part in segmenting unclear and narrow vessels and filling the gap between separate pieces of detected vessels. The experimental results are presented to demonstrate the effectiveness of the proposed model.
Algebras of Information. An Axiomatic Foundation
Venue: arXiv cs.IT 2025
Year: 2025

The basic idea behind information algebras is that information comes in pieces, each referring to a certain question, that these pieces can be combined or aggregated and that the part relating to a given question can be extracted. This algebraic structure can be given different forms. Questions were originally represented by subsets of variables. Pieces of information were then represented by valuations associated with the domains of variables. This leads to an algebraic structure called valuation algebras. The basic axiomatics of this algebraic structure was in essence proposed by Shenoy and Shafer. Here a much more general view of systems of questions is proposed and pieces of information are related to the elements of this system of questions. This leads to a new and extended system of axioms for information algebras. Classical valuation algebras are essentially a special case of this new system. A full discussion of the algebraic theory of this new information algebras is given, including local computation, duality between labeled and domain-free versions of the algebras, order of information, finiteness of information and approximation, compact and continuous information algebras. Finally a rather complete discussion of uncertain information, based on random maps into information algebras is presented. This is shown to represent a generalisation of classical Dempster-Shafer theory.
Exponent Function for Stationary Memoryless Channels with Input Cost at Rates above the Capacity
Venue: arXiv cs.IT 2025
Year: 2025

We consider the stationaly memoryless channels with input cost. We prove that for transmission rates above the capacity the correct probability of decoding tends to zero exponentially as the block length $n$ of codes tends to infinity. In the case where both of channel input and output sets are finite, we determine the optimal exponent function on the above exponential decay of the correct probability. To derive this result we use a new technique called the recuresive method, which is based on the information spectrum approach. The recursive method utilize a certain recursive structure on the information spectrum quantities.
Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations
Venue: arXiv cs.CG 2025
Year: 2025

Let $P$ be a set of $n$ points in the plane. We compute the value of $θ\in [0,2π)$ for which the rectilinear convex hull of $P$, denoted by $\mathcal{RH}_θ(P)$, has minimum (or maximum) area in optimal $O(n\log n)$ time and $O(n)$ space, improving the previous $O(n^2)$ bound. Let $\mathcal{O}$ be a set of $k$ lines through the origin sorted by slope and let $α_i$ be the sizes of the $2k$ angles defined by pairs of two consecutive lines, $i=1, \ldots , 2k$. Let $Θ_{i}=π-α_i$ and $Θ=\min\{Θ_i \colon i=1,\ldots,2k\}$. We obtain: (1) Given a set $\mathcal{O}$ such that $Θ\ge\fracπ{2}$, we provide an algorithm to compute the $\mathcal{O}$-convex hull of $P$ in optimal $O(n\log n)$ time and $O(n)$ space; If $Θ< \fracπ{2}$, the time and space complexities are $O(\frac{n}Θ\log n)$ and $O(\frac{n}Θ)$ respectively. (2) Given a set $\mathcal{O}$ such that $Θ\ge\fracπ{2}$, we compute and maintain the boundary of the ${\mathcal{O}}_θ$-convex hull of $P$ for $θ\in [0,2π)$ in $O(kn\log n)$ time and $O(kn)$ space, or if $Θ< \fracπ{2}$, in $O(k\frac{n}Θ\log n)$ time and $O(k\frac{n}Θ)$ space. (3) Finally, given a set $\mathcal{O}$ such that $Θ\ge\fracπ{2}$, we compute, in $O(kn\log n)$ time and $O(kn)$ space, the angle $θ\in [0,2π)$ such that the $\mathcal{O}_θ$-convex hull of $P$ has minimum (or maximum) area over all $θ\in [0,2π)$.
Quantile Markov Decision Process
Venue: arXiv cs.AI 2025
Year: 2025

The goal of a traditional Markov decision process (MDP) is to maximize expected cumulative reward over a defined horizon (possibly infinite). In many applications, however, a decision maker may be interested in optimizing a specific quantile of the cumulative reward instead of its expectation. In this paper we consider the problem of optimizing the quantiles of the cumulative rewards of a Markov decision process (MDP), which we refer to as a quantile Markov decision process (QMDP). We provide analytical results characterizing the optimal QMDP value function and present a dynamic programming-based algorithm to solve for the optimal policy. The algorithm also extends to the MDP problem with a conditional value-at-risk (CVaR) objective. We illustrate the practical relevance of our model by evaluating it on an HIV treatment initiation problem, where patients aim to balance the potential benefits and risks of the treatment.
A Promising Future: Omission Failures in Choreographic Programming
Venue: arXiv cs.PL 2025
Year: 2025

Choreographic programming promises a simple approach to the coding of concurrent and distributed systems: write the collective communication behaviour of a system of processes as a choreography, and then the programs for these processes are automatically compiled by a provably-correct procedure known as endpoint projection. While this promise prompted substantial research, a theory that can deal with realistic communication failures in a distributed network remains elusive. In this work, we provide the first theory of choreographic programming that addresses realistic communication failures taken from the literature of distributed systems: processes can send or receive fewer messages than they should (send and receive omission), and the network can fail at transporting messages (omission failure). Our theory supports the programming of strategies for failure recovery, and a novel static analysis (called robustness) to check for delivery guarantees (at-most-once and exactly-once). Our key technical innovation is a deconstruction of the usual communication primitive in choreographies to allow for independent implementations of the send and receive actions of a communication, while still retaining the static guarantee that these actions will correlate correctly (the essence of choreographic programming). This has two main benefits. First, each side of a communication can adopt its own failure recovery strategy, as in realistic protocols. Second, initiating new communications does not require any (unrealistic) synchronisation over unreliable channels: senders and receivers agree by construction on how each message should be identified. We validate our design via a series of examples -- including two-phase commit, which so far eluded choreographic programming -- and an implementation of our ideas in the choreographic programming language Choral.
A Maximum Linear Arrangement Problem on Directed Graphs
Venue: arXiv cs.DS 2025
Year: 2025

We propose a new arrangement problem on directed graphs, Maximum Directed Linear Arrangement (MaxDLA). This is a directed variant of a similar problem for undirected graphs, in which however one seeks maximum and not minimum; this problem known as the Minimum Linear Arrangement Problem (MinLA) has been much studied in the literature. We establish a number of theorems illustrating the behavior and complexity of MaxDLA. First, we relate MaxDLA to Maximum Directed Cut (MaxDiCut) by proving that every simple digraph $D$ on $n$ vertices satisfies $\frac{n}{2}$$maxDiCut(D) \leq MaxDLA(D) \leq (n-1)MaxDiCut(D)$. Next, we prove that MaxDiCut is NP-Hard for planar digraphs (even with the added restriction of maximum degree 15); it follows from the above bounds that MaxDLA is also NP-Hard for planar digraphs. In contrast, Hadlock (1975) and Dorfman and Orlova (1972) showed that the undirected Maximum Cut problem is solvable in polynomial time on planar graphs. On the positive side, we present a polynomial-time algorithm for solving MaxDLA on orientations of trees with degree bounded by a constant, which translates to a polynomial-time algorithm for solving MinLA on the complements of those trees. This pairs with results by Goldberg and Klipker (1976), Shiloach (1979) and Chung (1984) solving MinLA in polynomial time on trees. Finally, analogues of Harper's famous isoperimetric inequality for the hypercube, in the setting of MaxDLA, are shown for tournaments, orientations of graphs with degree at most two, and transitive acyclic digraphs.
A biconvex optimization for solving semidefinite programs via bilinear factorization
Venue: arXiv cs.LG 2025
Year: 2025

Many problems in machine learning can be reduced to learning a low-rank positive semidefinite matrix (denoted as $Z$), which encounters semidefinite program (SDP). Existing SDP solvers by classical convex optimization are expensive to solve large-scale problems. Employing the low rank of solution, Burer-Monteiro's method reformulated SDP as a nonconvex problem via the {\emph{quadratic}} factorization ($Z$ as $XX^\top$). However, this would lose the structure of problem in optimization. In this paper, we propose to convert SDP into a biconvex problem via the {\emph{bilinear}} factorization ($Z$ as $XY^\top$), and while adding the term $\frac{\g}{2}\normfs{X-Y}$ to penalize the difference of $X$ and $Y$. Thus, the biconvex structure (w.r.t. $X$ and $Y$) can be exploited naturally in optimization. As a theoretical result, we provide a bound to the penalty parameter $\g$ under the assumption of $L$-Lipschitz smoothness and $σ$-strongly biconvexity, such that, at stationary points, the proposed bilinear factorization is equivalent to Burer-Monteiro's factorization when the bound is arrived, that is $\g>\frac{1}{4}(L-σ)_+$. Our proposal opens up a new way to surrogate SDP by biconvex program. Experiments on two SDP-related applications demonstrate that the proposed method is effective as the state-of-the-art.
Small Hazard-free Transducers
Venue: arXiv cs.DS 2025
Year: 2025

Ikenmeyer et al. (JACM'19) proved an unconditional exponential separation between the hazard-free complexity and (standard) circuit complexity of explicit functions. This raises the question: which classes of functions permit efficient hazard-free circuits? In this work, we prove that circuit implementations of transducers with small state space are such a class. A transducer is a finite state machine that transcribes, symbol by symbol, an input string of length $n$ into an output string of length $n$. We present a construction that transforms any function arising from a transducer into an efficient circuit of size $\mathcal{O}(n)$ computing the hazard-free extension of the function. More precisely, given a transducer with $s$ states, receiving $n$ input symbols encoded by $l$ bits, and computing $n$ output symbols encoded by $m$ bits, the transducer has a hazard-free circuit of size $2^{\mathcal{O}(s+\ell)} m n$ and depth $\mathcal{O}(s\log n + \ell)$; in particular, if $s, \ell,m\in \mathcal{O}(1)$, size and depth are asymptotically optimal. In light of the strong hardness results by Ikenmeyer et al. (JACM'19), we consider this a surprising result.
Ranked Enumeration of Conjunctive Query Results
Venue: arXiv cs.DB 2025
Year: 2025

We study the problem of enumerating answers of Conjunctive Queries ranked according to a given ranking function. Our main contribution is a novel algorithm with small preprocessing time, logarithmic delay, and non-trivial space usage during execution. To allow for efficient enumeration, we exploit certain properties of ranking functions that frequently occur in practice. To this end, we introduce the notions of {\em decomposable} and {\em compatible} (w.r.t. a query decomposition) ranking functions, which allow for partial aggregation of tuple scores in order to efficiently enumerate the output. We complement the algorithmic results with lower bounds that justify why restrictions on the structure of ranking functions are necessary. Our results extend and improve upon a long line of work that has studied ranked enumeration from both a theoretical and practical perspective.
STEFANN: Scene Text Editor using Font Adaptive Neural Network
Venue: arXiv cs.CV 2025
Year: 2025

Textual information in a captured scene plays an important role in scene interpretation and decision making. Though there exist methods that can successfully detect and interpret complex text regions present in a scene, to the best of our knowledge, there is no significant prior work that aims to modify the textual information in an image. The ability to edit text directly on images has several advantages including error correction, text restoration and image reusability. In this paper, we propose a method to modify text in an image at character-level. We approach the problem in two stages. At first, the unobserved character (target) is generated from an observed character (source) being modified. We propose two different neural network architectures - (a) FANnet to achieve structural consistency with source font and (b) Colornet to preserve source color. Next, we replace the source character with the generated character maintaining both geometric and visual consistency with neighboring characters. Our method works as a unified platform for modifying text in images. We present the effectiveness of our method on COCO-Text and ICDAR datasets both qualitatively and quantitatively.
Naive Feature Selection: a Nearly Tight Convex Relaxation for Sparse Naive Bayes
Venue: arXiv cs.LG 2025
Year: 2025

Due to its linear complexity, naive Bayes classification remains an attractive supervised learning method, especially in very large-scale settings. We propose a sparse version of naive Bayes, which can be used for feature selection. This leads to a combinatorial maximum-likelihood problem, for which we provide an exact solution in the case of binary data, or a bound in the multinomial case. We prove that our convex relaxation bounds becomes tight as the marginal contribution of additional features decreases, using a priori duality gap bounds dervied from the Shapley-Folkman theorem. We show how to produce primal solutions satisfying these bounds. Both binary and multinomial sparse models are solvable in time almost linear in problem size, representing a very small extra relative cost compared to the classical naive Bayes. Numerical experiments on text data show that the naive Bayes feature selection method is as statistically effective as state-of-the-art feature selection methods such as recursive feature elimination, $l_1$-penalized logistic regression and LASSO, while being orders of magnitude faster.
The Competitive Ratio of Threshold Policies for Online Unit-density Knapsack Problems
Venue: arXiv cs.DS 2025
Year: 2025

We study a wholesale supply chain ordering problem. In this problem, the supplier has an initial stock, and faces an unpredictable stream of incoming orders, making real-time decisions on whether to accept or reject each order. What makes this wholesale supply chain ordering problem special is its ``knapsack constraint,'' that is, we do not allow partially accepting an order or splitting an order. The objective is to maximize the utilized stock. We model this wholesale supply chain ordering problem as an online unit-density knapsack problem. We study randomized threshold algorithms that accept an item as long as its size exceeds the threshold. We derive two optimal threshold distributions, the first is 0.4324-competitive relative to the optimal offline integral packing, and the second is 0.4285-competitive relative to the optimal offline fractional packing. Both results require optimizing the cumulative distribution function of the random threshold, which are challenging infinite-dimensional optimization problems. We also consider the generalization to multiple knapsacks, where an arriving item has a different size in each knapsack. We derive a 0.2142-competitive algorithm for this problem. We also show that any randomized algorithm for this problem cannot be more than 0.4605-competitive. This is the first upper bound strictly less than 0.5, which implies the intrinsic challenge of knapsack constraint. We show how to naturally implement our optimal threshold distributions in the warehouses of a Latin American chain department store. We run simulations on their order data, which demonstrate the efficacy of our proposed algorithms.
AutoGMM: Automatic Gaussian Mixture Modeling in Python
Venue: arXiv cs.LG 2025
Year: 2025

The exponential growth of complex data demands fully automatic clustering. Gaussian mixture models (GMMs) provide uncertainty-aware grouping but often require expertise to specify hyperparameters, e.g., component count and covariance structure. While mclust (R) automates this via Bayesian Information Criterion (BIC), Python lacks a comparable tool. We introduce AutoGMM, an open-source Python package automating GMM via strategic initialization using an agglomerative Mahalanobis heuristic, and parallelized model selection by information criteria. AutoGMM is a drop-in tool that yields strong out-of-the-box performance on classic benchmarks, targeted stress tests, and two real datasets, with favorable runtime scaling. The code is available at https://github.com/neurodata/AutoGMM with tests and reproducible workflows.
Conditional Hierarchical Bayesian Tucker Decomposition for Genetic Data Analysis
Venue: arXiv cs.LG 2025
Year: 2025

We analyze large, multi-dimensional, sparse counting data sets, finding unsupervised groups to provide unique insights into genetic data. We create gene and biological pathway groups based on patients' variants to find common risk factors for four common types of cancer (breast, lung, prostate, and colorectal) and autism spectrum disorder. To accomplish this, we extend latent Dirichlet allocation to multiple dimensions and design distinct methods for hierarchical topic modeling. We find that our conditional hierarchical Bayesian Tucker decomposition models are more coherent than baseline models.
Fair Division with Bounded Sharing: Binary and Non-Degenerate Valuations
Venue: arXiv cs.GT 2025
Year: 2025

A set of objects is to be divided fairly among agents with different tastes, modeled by additive utility-functions. If we consider the objects as indivisible, many instances of the decision problem: ``Is there a fair division of the objects among the agents'' are negative. In addition, this question is hard to solve even for most of the special cases. The latter reasons give us a good motivation to relax the problem for which the running time complexity is better, and the number of positive instances (admitting a fair division) will significantly grow. Whereas many works relax the fairness criteria, this paper introduces another relaxation: an agent is allowed to share a \emph{bounded} number of objects between two or more agents in order to attain fairness. The paper studies various notions of fairness, such as proportionality, envy-freeness, equitability, and consensus. We analyze the run-time complexity of finding a fair allocation with a given number of sharings under several restrictions on the agents' valuations, such as: binary, generalized-binary, and non-degenerate.