OpenRaiser/Intern-Atlas huggingface dataset:
A $4/3$ Approximation for $2$-Vertex-Connectivity
Venue: arXiv cs.DS 2025
Year: 2025

The 2-Vertex-Connected Spanning Subgraph problem (2VCSS) is among the most basic NP-hard (Survivable) Network Design problems: we are given an (unweighted) undirected graph $G$. Our goal is to find a spanning subgraph $S$ of $G$ with the minimum number of edges which is $2$-vertex-connected, namely $S$ remains connected after the deletion of an arbitrary node. 2VCSS is well-studied in terms of approximation algorithms, and the current best (polynomial-time) approximation factor is $10/7$ by Heeger and Vygen [SIDMA'17] (improving on earlier results by Khuller and Vishkin [STOC'92] and Garg, Vempala and Singla [SODA'93]). Here we present an improved $4/3$ approximation. Our main technical ingredient is an approximation preserving reduction to a conveniently structured subset of instances which are ``almost'' 3-vertex-connected. The latter reduction might be helpful in future work.
A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble
Venue: arXiv cs.IT 2025
Year: 2025

We present an explicit construction of a sequence of rate $1/2$ Wozencraft ensemble codes (over any fixed finite field $\mathbb{F}_q$) that achieve minimum distance $Ω(\sqrt{k})$ where $k$ is the message length. The coefficients of the Wozencraft ensemble codes are constructed using Sidon Sets and the cyclic structure of $\mathbb{F}_{q^{k}}$ where $k+1$ is prime with $q$ a primitive root modulo $k+1$. Assuming Artin's conjecture, there are infinitely many such $k$ for any prime power $q$.
ChatGPT Needs SPADE (Sustainability, PrivAcy, Digital divide, and Ethics) Evaluation: A Review
Venue: arXiv cs.CY 2025
Year: 2025

ChatGPT is another large language model (LLM) vastly available for the consumers on their devices but due to its performance and ability to converse effectively, it has gained a huge popularity amongst research as well as industrial community. Recently, many studies have been published to show the effectiveness, efficiency, integration, and sentiments of chatGPT and other LLMs. In contrast, this study focuses on the important aspects that are mostly overlooked, i.e. sustainability, privacy, digital divide, and ethics and suggests that not only chatGPT but every subsequent entry in the category of conversational bots should undergo Sustainability, PrivAcy, Digital divide, and Ethics (SPADE) evaluation. This paper discusses in detail the issues and concerns raised over chatGPT in line with aforementioned characteristics. We also discuss the recent EU AI Act briefly in accordance with the SPADE evaluation. We support our hypothesis by some preliminary data collection and visualizations along with hypothesized facts. We also suggest mitigations and recommendations for each of the concerns. Furthermore, we also suggest some policies and recommendations for EU AI policy act concerning ethics, digital divide, and sustainability
Tighter Approximation for the Uniform Cost-Distance Steiner Tree Problem
Venue: arXiv cs.DS 2025
Year: 2025

Uniform cost-distance Steiner trees minimize the sum of the total length and weighted path lengths from a dedicated root to the other terminals. They are applied when the tree is intended for signal transmission, e.g. in chip design or telecommunication networks. They are a special case of general cost-distance Steiner trees, where different distance functions are used for total length and path lengths. We improve the best published approximation factor for the uniform cost-distance Steiner tree problem from 2.39 to 2.05. If we can approximate the minimum-length Steiner tree problem arbitrarily well, our algorithm achieves an approximation factor arbitrarily close to $ 1 + \frac{1}{\sqrt{2}} $. This bound is tight in the following sense. We also prove the gap $ 1 + \frac{1}{\sqrt{2}} $ between optimum solutions and the lower bound which we and all previous approximation algorithms for this problem use. Similarly to previous approaches, we start with an approximate minimum-length Steiner tree and split it into subtrees that are later re-connected. To improve the approximation factor, we split it into components more carefully, taking the cost structure into account, and we significantly enhance the analysis.
Next-generation Surgical Navigation: Marker-less Multi-view 6DoF Pose Estimation of Surgical Instruments
Venue: arXiv cs.CV 2025
Year: 2025

State-of-the-art research of traditional computer vision is increasingly leveraged in the surgical domain. A particular focus in computer-assisted surgery is to replace marker-based tracking systems for instrument localization with pure image-based 6DoF pose estimation using deep-learning methods. However, state-of-the-art single-view pose estimation methods do not yet meet the accuracy required for surgical navigation. In this context, we investigate the benefits of multi-view setups for highly accurate and occlusion-robust 6DoF pose estimation of surgical instruments and derive recommendations for an ideal camera system that addresses the challenges in the operating room. The contributions of this work are threefold. First, we present a multi-camera capture setup consisting of static and head-mounted cameras, which allows us to study the performance of pose estimation methods under various camera configurations. Second, we publish a multi-view RGB-D video dataset of ex-vivo spine surgeries, captured in a surgical wet lab and a real operating theatre and including rich annotations for surgeon, instrument, and patient anatomy. Third, we evaluate three state-of-the-art single-view and multi-view methods for the task of 6DoF pose estimation of surgical instruments and analyze the influence of camera configurations, training data, and occlusions on the pose accuracy and generalization ability. The best method utilizes five cameras in a multi-view pose optimization and achieves an average position and orientation error of 1.01 mm and 0.89° for a surgical drill as well as 2.79 mm and 3.33° for a screwdriver under optimal conditions. Our results demonstrate that marker-less tracking of surgical instruments is becoming a feasible alternative to existing marker-based systems.
Approximation by non-symmetric networks for cross-domain learning
Venue: arXiv cs.LG 2025
Year: 2025

For the past 30 years or so, machine learning has stimulated a great deal of research in the study of approximation capabilities (expressive power) of a multitude of processes, such as approximation by shallow or deep neural networks, radial basis function networks, and a variety of kernel based methods. Motivated by applications such as invariant learning, transfer learning, and synthetic aperture radar imaging, we initiate in this paper a general approach to study the approximation capabilities of kernel based networks using non-symmetric kernels. While singular value decomposition is a natural instinct to study such kernels, we consider a more general approach to include the use of a family of kernels, such as generalized translation networks (which include neural networks and translation invariant kernels as special cases) and rotated zonal function kernels. Naturally, unlike traditional kernel based approximation, we cannot require the kernels to be positive definite. In particular, we obtain estimates on the accuracy of uniform approximation of functions in a Sobolev class by ReLU$^r$ networks when $r$ is not necessarily an integer. Our general results apply to the approximation of functions with small smoothness compared to the dimension of the input space.
Heterogeneous Directed Hypergraph Neural Network over abstract syntax tree (AST) for Code Classification
Venue: arXiv cs.SE 2025
Year: 2025

Code classification is a difficult issue in program understanding and automatic coding. Due to the elusive syntax and complicated semantics in programs, most existing studies use techniques based on abstract syntax tree (AST) and graph neural network (GNN) to create code representations for code classification. These techniques utilize the structure and semantic information of the code, but they only take into account pairwise associations and neglect the high-order data correlations that already exist between nodes of the same field or called attribute in the AST, which may result in the loss of code structural information. On the other hand, while a general hypergraph can encode high-order data correlations, it is homogeneous and undirected which will result in a lack of semantic and structural information such as node types, edge types, and directions between child nodes and parent nodes when modeling AST. In this study, we propose a heterogeneous directed hypergraph (HDHG) to represent AST and a heterogeneous directed hypergraph neural network (HDHGN) to process the graph for code classification. Our method improves code understanding and can represent high-order data correlations beyond paired interactions. We assess our heterogeneous directed hypergraph neural network (HDHGN) on public datasets of Python and Java programs. Our method outperforms previous AST-based and GNN-based methods, which demonstrates the capability of our model.
Location Privacy Threats and Protections in 6G Vehicular Networks: A Comprehensive Review
Venue: arXiv cs.CR 2025
Year: 2025

Location privacy is critical in vehicular networks, where drivers' trajectories and personal information can be exposed, allowing adversaries to launch data and physical attacks that threaten drivers' safety and personal security. This survey reviews comprehensively different localization techniques, including widely used ones like sensing infrastructure-based, optical vision-based, and cellular radio-based localization, and identifies inadequately addressed location privacy concerns. We classify Location Privacy Preserving Mechanisms (LPPMs) into user-side, server-side, and user-server-interface-based, and evaluate their effectiveness. Our analysis shows that the user-server-interface-based LPPMs have received insufficient attention in the literature, despite their paramount importance in vehicular networks. Further, we examine methods for balancing data utility and privacy protection for existing LPPMs in vehicular networks and highlight emerging challenges from future upper-layer location privacy attacks, wireless technologies, and network convergences. By providing insights into the relationship between localization techniques and location privacy, and evaluating the effectiveness of different LPPMs, this survey can help inform the development of future LPPMs in vehicular networks.
Fundamental Limits of Distributed Linearly Separable Computation under Cyclic Assignment
Venue: arXiv cs.IT 2025
Year: 2025

This paper studies the master-worker distributed linearly separable computation problem, where the considered computation task, referred to as linearly separable function, is a typical linear transform model widely used in cooperative distributed gradient coding, real-time rendering, linear transformers, etc. %A master asks $\Nsf$ distributed workers to compute a linearly separable function from $\Ksf$ datasets. The computation task on $\Ksf$ datasets can be expressed as $\Ksf_{\rm c}$ linear combinations of $\Ksf$ messages, where each message is the output of an individual function on one dataset. Straggler effect is also considered, such that from the answers of any $\Nsf_{\rm r}$ of the $\Nsf$ distributed workers, the master should accomplish the task. The computation cost is defined as the number of datasets assigned to each worker, while the communication cost is defined as the number of (coded) messages that should be received. The objective is to characterize the optimal tradeoff between the computation and communication costs. The problem has remained so far open, even under the cyclic data assignment.Since in fact various distributed computing schemes were proposed in the literature under the cyclic data assignment, with this paper we close the problem for the cyclic assignment. This paper proposes a new computing scheme with the cyclic assignment based on the concept of interference alignment, by treating each message which cannot be computed by a worker as an interference from this worker. Under the cyclic assignment, the proposed computing scheme is then proved to be optimal when $\Nsf=\Ksf$ and be order optimal within a factor of $2$ otherwise.
Probabilistic detection of GNSS spoofing using opportunistic information
Venue: arXiv cs.CR 2025
Year: 2025

Global Navigation Satellite Systems (GNSS) are integrated into many devices. However, civilian GNSS signals are usually not cryptographically protected. This makes attacks that forge signals relatively easy. Considering modern devices often have network connections and onboard sensors, the proposed here Probabilistic Detection of GNSS Spoofing (PDS) scheme is based on such opportunistic information. PDS has at its core two parts. First, a regression problem with motion model constraints, which equalizes the noise of all locations considering the motion model of the device. Second, a Gaussian process, that analyzes statistical properties of location data to construct uncertainty. Then, a likelihood function, that fuses the two parts, as a basis for a Neyman-Pearson lemma (NPL)-based detection strategy. Our experimental evaluation shows a performance gain over the state-of-the-art, in terms of attack detection effectiveness.
Pavlok-Nudge: A Feedback Mechanism for Atomic Behaviour Modification with Snoring Usecase
Venue: arXiv cs.CV 2025
Year: 2025

This paper proposes an atomic behaviour intervention strategy using the Pavlok wearable device. Pavlok utilises beeps, vibration and shocks as a mode of aversion technique to help individuals with behaviour modification. While the device can be useful in certain periodic daily life situations, like alarms and exercise notifications, it relies on manual operations that limit its usage. To automate behaviour modification, we propose a framework that first detects targeted behaviours through a lightweight deep learning model and subsequently nudges the user. Our proposed solution is implemented and verified in the context of snoring, which captures audio from the environment following a prediction of whether the audio content is a snore or not using a lightweight 1D convolutional neural network. Based on the prediction, we use Pavlok to nudge users for preventive measures, such as a change in sleeping posture. We believe that this simple solution can help people change their atomic habits, which may lead to long-term health benefits. Our proposed lightweight model (99.8% fewer parameters over SOTA; 790,273$\rightarrow$1,337) achieves SOTA test accuracy of 0.99 on a public benchmark. The code and model are publicly available at https://github.com/hasan-rakibul/pavlok-nudge-snore.
Finitely Presentable Higher-Dimensional Automata and the Irrationality of Process Replication
Venue: arXiv cs.FL 2025
Year: 2025

Higher-dimensional automata (HDA) are a formalism to faithfully model the behaviour of concurrent systems. For ordinary automata, there is a correspondence between regular expressions, regular languages and finite automata, which provides a powerful link between algebraic proofs and operational behaviour. It has been shown by Fahrenberg et al. that finite HDA correspond with interfaced interval pomset languages generated by sequential and parallel composition and non-empty iteration, and thereby to a variant of Kleene algebras (KA) with parallel composition. It is known that this correspondence cannot be extended to concurrent KA, which additionally have process replication. An alternative to finite HDA are locally finite HDA, in which every state can only reach finitely many other states, and finitely branching HDA. In this paper, we show that both classes of HDA are closed under process replication and thus models of concurrent KA. To achieve this, we prove that the category of HDA is locally finitely presentable, where the finite HDA generate all other HDA. We then prove that this has the unfortunate side-effect that all HDA are locally finite, which means that the correspondence with concurrent KA trivialises. Similarly, we also show that, even though finitely branching HDA are closed under process replication, the resulting HDA necessarily have infinitely many initial states.
High-Resolution Thermal Simulation Framework for Extrusion-based Additive Manufacturing of Complex Geometries
Venue: arXiv cs.GR 2025
Year: 2025

Accurate simulation of the printing process is essential for improving print quality, reducing waste, and optimizing the printing parameters of extrusion-based additive manufacturing. Traditional additive manufacturing simulations are very compute-intensive and are not scalable to simulate even moderately sized geometries. In this paper, we propose a general framework for creating a digital twin of the dynamic printing process by performing physics simulations with the intermediate print geometries. Our framework takes a general extrusion-based additive manufacturing G-code, generates an analysis-suitable voxelized geometry representation from the print schedule, and performs physics-based (transient thermal) simulations of the printing process. Our approach leverages adaptive octree meshes for both geometry representation as well as for fast simulations to address real-time predictions. We demonstrate the effectiveness of our method by simulating the printing of complex geometries at high voxel resolutions with both sparse and dense infills. Our results show that this approach scales to high voxel resolutions and can predict the transient heat distribution as the print progresses. Because the simulation runs faster than real print time, the same engine could, in principle, feed thermal predictions back to the machine controller (e.g., to adjust fan speed or extrusion rate). The present study establishes the computational foundations for a real-time digital twin, which can be used for closed control loop control in the future.
Breaking the Curse of Knowledge: Towards Effective Multimodal Recommendation using Knowledge Soft Integration
Venue: arXiv cs.IR 2025
Year: 2025

A critical challenge in contemporary recommendation systems lies in effectively leveraging multimodal content to enhance recommendation personalization. Although various solutions have been proposed, most fail to account for discrepancies between knowledge extracted through isolated feature extraction and its application in recommendation tasks. Specifically, multimodal feature extraction does not incorporate task-specific prior knowledge, while downstream recommendation tasks typically use these features as auxiliary information. This misalignment often introduces biases in model fitting and degrades performance, a phenomenon we refer to as the curse of knowledge. To address this challenge, we propose a knowledge soft integration framework designed to balance the utilization of multimodal features with the biases they may introduce. The framework, named Knowledge Soft Integration (KSI), comprises two key components: the Structure Efficient Injection (SEI) module and the Semantic Soft Integration (SSI) module. The SEI module employs a Refined Graph Neural Network (RGNN) to model inter-modal correlations among items while introducing a regularization term to minimize redundancy in user and item representations. In parallel, the SSI module utilizes a self-supervised retrieval task to implicitly integrate multimodal semantic knowledge, thereby enhancing the semantic distinctiveness of item representations. We conduct comprehensive experiments on three benchmark datasets, demonstrating KSI's effectiveness. Furthermore, these results underscore the ability of the SEI and SSI modules to reduce representation redundancy and mitigate the curse of knowledge in multimodal recommendation systems.
Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compression
Venue: arXiv cs.LG 2025
Year: 2025

Communication compression is an essential strategy for alleviating communication overhead by reducing the volume of information exchanged between computing nodes in large-scale distributed stochastic optimization. Although numerous algorithms with convergence guarantees have been obtained, the optimal performance limit under communication compression remains unclear. In this paper, we investigate the performance limit of distributed stochastic optimization algorithms employing communication compression. We focus on two main types of compressors, unbiased and contractive, and address the best-possible convergence rates one can obtain with these compressors. We establish the lower bounds for the convergence rates of distributed stochastic optimization in six different settings, combining strongly-convex, generally-convex, or non-convex functions with unbiased or contractive compressor types. To bridge the gap between lower bounds and existing algorithms' rates, we propose NEOLITHIC, a nearly optimal algorithm with compression that achieves the established lower bounds up to logarithmic factors under mild conditions. Extensive experimental results support our theoretical findings. This work provides insights into the theoretical limitations of existing compressors and motivates further research into fundamentally new compressor properties.
Selective Population Protocols
Venue: arXiv cs.DC 2025
Year: 2025

The model of population protocols provides a universal platform to study distributed processes driven by pairwise interactions of anonymous agents. While population protocols present an elegant and robust model for randomized distributed computation, their efficiency wanes when tackling issues that require more focused communication or the execution of multiple processes. To address this issue, we propose a new, selective variant of population protocols by introducing a partition of the state space and the corresponding conditional selection of responders. We demonstrate on several examples that the new model offers a natural environment, complete with tools and a high-level description, to facilitate more efficient solutions. In particular, we provide fixed-state stable and efficient solutions to two central problems: leader election and majority computation, both with confirmation. This constitutes a separation result, as achieving stable and efficient majority computation requires $Ω(\log n)$ states in standard population protocols, even when the leader is already determined. Additionally, we explore the computation of the median using the comparison model, where the operational state space of agents is fixed, and the transition function determines the order between (arbitrarily large) hidden keys associated with interacting agents. Our findings reveal that the computation of the median of $n$ numbers requires $Ω(n)$ time. Moreover, we demonstrate that the problem can be solved in $O(n\log n)$ time, both in expectation and with high probability, in standard population protocols. In contrast, we establish that a feasible solution in selective population protocols can be achieved in $O(\log^4 n)$ time.
Representing states in iterated belief revision
Venue: arXiv cs.AI 2025
Year: 2025

Iterated belief revision requires information about the current beliefs. This information is represented by mathematical structures called doxastic states. Most literature concentrates on how to revise a doxastic state and neglects that it may exponentially grow. This problem is studied for the most common ways of storing a doxastic state. All four methods are able to store every doxastic state, but some do it in less space than others. In particular, the explicit representation (an enumeration of the current beliefs) is the more wasteful on space. The level representation (a sequence of propositional formulae) and the natural representation (a history of natural revisions) are more compact than it. The lexicographic representation (a history of lexicographic revision) is even more compact than them.