OpenRaiser/Intern-Atlas huggingface dataset:
A faster algorithm for Vertex Cover parameterized by solution size
Venue: arXiv cs.DS 2025
Year: 2025

We describe a new algorithm for vertex cover with runtime $O^*(1.25284^k)$, where $k$ is the size of the desired solution and $O^*$ hides polynomial factors in the input size. This improves over previous runtime of $O^*(1.2738^k)$ due to Chen, Kanj, & Xia (2010) standing for more than a decade. The key to our algorithm is to use a potential function which simultaneously tracks $k$ as well as the optimal value $λ$ of the vertex cover LP relaxation. This approach also allows us to make use of prior algorithms for Maximum Independent Set in bounded-degree graphs and Above-Guarantee Vertex Cover. The main step in the algorithm is to branch on high-degree vertices, while ensuring that both $k$ and $μ= k - λ$ are decreased at each step. There can be local obstructions in the graph that prevent $μ$ from decreasing in this process; we develop a number of novel branching steps to handle these situations.
On the Distortion of Multi-winner Election Using Single-Candidate Ballots
Venue: arXiv cs.GT 2025
Year: 2025

In this paper, we study the distortion bounds for voting mechanisms in multi-winner elections in general metric spaces. Our study pertains to the case in which each voter only reports her favorite candidate amongst $m$ possible choices. Given that candidates' locations are undisclosed to the mechanism, the mechanism has to form a $w-$winner committee based solely on the number of votes received by candidates. We establish distortion bounds for both truthful and non-truthful mechanisms. Our research highlights the significance of the $σ$ parameter, which represents the ratio between maximum and minimum distances among all candidate pairs. We show that the distortion is linear in $σ$. First, we demonstrate that all mechanisms possess a distortion greater than $1+\frac{w-1}{w+1}(σ-1)$. To give an upper bound, we study the Single Non-Transferable Vote (SNTV) mechanism, whose distortion is at most $1+2σ$. Second, we retrieve the upper bounds for strategyproof mechanisms. In particular, we infer an upper bound by examining the Random Sequential Dictator mechanism that achieves a distortion less than $1+4σ$ when $w=2$.
Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player
Venue: arXiv cs.DS 2025
Year: 2025

A $(ϕ,ε)$-expander-decomposition of a graph $G$ (with $n$ vertices and $m$ edges) is a partition of $V$ into clusters $V_1,\ldots,V_k$ with conductance $Φ(G[V_i]) \ge ϕ$, such that there are at most $εm$ inter-cluster edges. Such a decomposition plays a crucial role in many graph algorithms. We give a randomized $\tilde{O}(m/ϕ)$ time algorithm for computing a $(ϕ, ϕ\log^2 {n})$-expander decomposition. This improves upon the $(ϕ, ϕ\log^3 {n})$-expander decomposition also obtained in $\tilde{O}(m/ϕ)$ time by [Saranurak and Wang, SODA 2019] (SW) and brings the number of inter-cluster edges within logarithmic factor of optimal. One crucial component of SW's algorithm is non-stop version of the cut-matching game of [Khandekar, Rao, Vazirani, JACM 2009] (KRV): The cut player does not stop when it gets from the matching player an unbalanced sparse cut, but continues to play on a trimmed part of the large side. The crux of our improvement is the design of a non-stop version of the cleverer cut player of [Orecchia, Schulman, Vazirani, Vishnoi, STOC 2008] (OSVV). The cut player of OSSV uses a more sophisticated random walk, a subtle potential function, and spectral arguments. Designing and analysing a non-stop version of this game was an explicit open question asked by SW.
Automated machine learning: AI-driven decision making in business analytics
Venue: arXiv cs.LG 2025
Year: 2025

The realization that AI-driven decision-making is indispensable in today's fast-paced and ultra-competitive marketplace has raised interest in industrial machine learning (ML) applications significantly. The current demand for analytics experts vastly exceeds the supply. One solution to this problem is to increase the user-friendliness of ML frameworks to make them more accessible for the non-expert. Automated machine learning (AutoML) is an attempt to solve the problem of expertise by providing fully automated off-the-shelf solutions for model choice and hyperparameter tuning. This paper analyzed the potential of AutoML for applications within business analytics, which could help to increase the adoption rate of ML across all industries. The H2O AutoML framework was benchmarked against a manually tuned stacked ML model on three real-world datasets. The manually tuned ML model could reach a performance advantage in all three case studies used in the experiment. Nevertheless, the H2O AutoML package proved to be quite potent. It is fast, easy to use, and delivers reliable results, which come close to a professionally tuned ML model. The H2O AutoML framework in its current capacity is a valuable tool to support fast prototyping with the potential to shorten development and deployment cycles. It can also bridge the existing gap between supply and demand for ML experts and is a big step towards automated decisions in business analytics. Finally, AutoML has the potential to foster human empowerment in a world that is rapidly becoming more automated and digital.
Embedding Principle in Depth for the Loss Landscape Analysis of Deep Neural Networks
Venue: arXiv cs.LG 2025
Year: 2025

Understanding the relation between deep and shallow neural networks is extremely important for the theoretical study of deep learning. In this work, we discover an embedding principle in depth that loss landscape of an NN "contains" all critical points of the loss landscapes for shallower NNs. The key tool for our discovery is the critical lifting operator proposed in this work that maps any critical point of a network to critical manifolds of any deeper network while preserving the outputs. This principle provides new insights to many widely observed behaviors of DNNs. Regarding the easy training of deep networks, we show that local minimum of an NN can be lifted to strict saddle points of a deeper NN. Regarding the acceleration effect of batch normalization, we demonstrate that batch normalization helps avoid the critical manifolds lifted from shallower NNs by suppressing layer linearization. We also prove that increasing training data shrinks the lifted critical manifolds, which can result in acceleration of training as demonstrated in experiments. Overall, our discovery of the embedding principle in depth uncovers the depth-wise hierarchical structure of deep learning loss landscape, which serves as a solid foundation for the further study about the role of depth for DNNs.
Thread and Data Mapping in Software Transactional Memory: An Overview
Venue: arXiv cs.DC 2025
Year: 2025

In current microarchitectures, due to the complex memory hierarchies and different latencies on memory accesses, thread and data mapping are important issues to improve application performance. Software transactional memory (STM) is an abstraction used for thread synchronization, replacing the use of locks in parallel programming. Regarding thread and data mapping, STM presents new challenges and mapping opportunities, since (1) STM can use different conflict detection and resolution strategies, making the behavior of the application less predictable and; (2) the STM runtime has precise information about shared data and the intensity with each thread accesses them. These unique characteristics provide many opportunities for low-overhead, but precise statistics to guide mapping strategies for STM applications. The main objective of this paper is to survey the existing work about thread and data mapping that uses solely information gathered from the STM runtime to guide thread and data mapping decisions. We also discuss future research directions within this research area.
New Fairness Concepts for Allocating Indivisible Items
Venue: arXiv cs.GT 2025
Year: 2025

For the fundamental problem of fairly dividing a set of indivisible items among agents, envy-freeness up to any item (EFX) and maximin fairness (MMS) are arguably the most compelling fairness concepts proposed until now. Unfortunately, despite significant efforts over the past few years, whether EFX allocations always exist is still an enigmatic open problem, let alone their efficient computation. Furthermore, today we know that MMS allocations are not always guaranteed to exist. These facts weaken the usefulness of both EFX and MMS, albeit their appealing conceptual characteristics. We propose two alternative fairness concepts, called epistemic EFX (EEFX) and minimum EFX share fairness (MXS), inspired by EFX and MMS. For both, we explore their relationships to well-studied fairness notions and, more importantly, prove that EEFX and MXS allocations always exist and can be computed efficiently for additive valuations. Our results justify that the new fairness concepts can be excellent alternatives to EFX and MMS.
On the horizontal compression of dag-derivations in minimal purely implicational logic
Venue: arXiv cs.LO 2025
Year: 2025

This report defines (plain) Dag-like derivations in the purely implicational fragment of minimal logic $M_{\supset}$. Introduce the horizontal collapsing set of rules and the algorithm {\bf HC}. Explain why {\bf HC} can transform any polynomial height-bounded tree-like proof of a $M_{\supset}$ tautology into a smaller dag-like proof. Sketch a proof that {\bf HC} preserves the soundness of any tree-like ND in $M_{\supset}$ in its dag-like version after the horizontal collapsing application. We show some experimental results about applying the compression method to a class of (huge) propositional proofs and an example, with non-hamiltonian graphs, for qualitative analysis. The contributions include the comprehensive presentation of the set of horizontal compression (HC), the (sketch) of the proof that HC rules preserve soundness and the demonstration that the compressed dag-like proofs are polynomially upper-bounded when the submitted tree-like proof is height and foundation poly-bounded. Finally, in the appendix, we outline an algorithm that verifies in polynomial time on the size of the dag-like proofs whether they are valid proofs of their conclusions.In the conclusion we discuss what part of the formal results on the HC-compressed dag-like proofs have been proved with the use of Interactive Theorem Prover assistance.
Sports Re-ID: Improving Re-Identification Of Players In Broadcast Videos Of Team Sports
Venue: arXiv cs.CV 2025
Year: 2025

This work focuses on player re-identification in broadcast videos of team sports. Specifically, we focus on identifying the same player in images captured from different camera viewpoints during any given moment of a match. This task differs from traditional applications of person re-id in a few important ways. Firstly, players from the same team wear highly similar clothes, thereby making it harder to tell them apart. Secondly, there are only a few number of samples for each identity, which makes it harder to train a re-id system. Thirdly, the resolutions of the images are often quite low and vary a lot. This combined with heavy occlusions and fast movements of players greatly increase the challenges for re-id. In this paper, we propose a simple but effective hierarchical data sampling procedure and a centroid loss function that, when used together, increase the mean average precision (mAP) by 7 - 11.5 and the rank-1 (R1) by 8.8 - 14.9 without any change in the network or hyper-parameters used. Our data sampling procedure improves the similarity of the training and test distributions, and thereby aids in creating better estimates of the centroids of the embeddings (or feature vectors). Surprisingly, our study shows that in the presence of severely limited data, as is the case for our application, a simple centroid loss function based on euclidean distances significantly outperforms the popular triplet-centroid loss function. We show comparable improvements for both convolutional networks and vision transformers. Our approach is among the top ranked methods in the SoccerNet Re-Identification Challenge 2022 leaderboard (test-split) with a mAP of 86.0 and a R1 of 81.5. On the sequestered challenge split, we achieve an mAP of 84.9 and a R1 of 80.1. Research on re-id for sports-related applications is very limited and our work presents one of the first discussions in the literature on this.
Decentralized Online Regularized Learning Over Random Time-Varying Graphs
Venue: arXiv cs.LG 2025
Year: 2025

We study the decentralized online regularized linear regression algorithm over random time-varying graphs. At each time step, every node runs an online estimation algorithm consisting of an innovation term processing its own new measurement, a consensus term taking a weighted sum of estimations of its own and its neighbors with additive and multiplicative communication noises and a regularization term preventing over-fitting. It is not required that the regression matrices and graphs satisfy special statistical assumptions such as mutual independence, spatio-temporal independence or stationarity. We develop the nonnegative supermartingale inequality of the estimation error, and prove that the estimations of all nodes converge to the unknown true parameter vector almost surely if the algorithm gains, graphs and regression matrices jointly satisfy the sample path spatio-temporal persistence of excitation condition. Especially, this condition holds by choosing appropriate algorithm gains if the graphs are uniformly conditionally jointly connected and conditionally balanced, and the regression models of all nodes are uniformly conditionally spatio-temporally jointly observable, under which the algorithm converges in mean square and almost surely. In addition, we prove that the regret upper bound is $O(T^{1-τ}\ln T)$, where $τ\in (0.5,1)$ is a constant depending on the algorithm gains.
Overcoming Annotation Bottlenecks in Underwater Fish Segmentation: A Robust Self-Supervised Learning Approach
Venue: arXiv cs.CV 2025
Year: 2025

Accurate fish segmentation in underwater videos is challenging due to low visibility, variable lighting, and dynamic backgrounds, making fully-supervised methods that require manual annotation impractical for many applications. This paper introduces a novel self-supervised learning approach for fish segmentation using Deep Learning. Our model, trained without manual annotation, learns robust and generalizable representations by aligning features across augmented views and enforcing spatial-temporal consistency. We demonstrate its effectiveness on three challenging underwater video datasets: DeepFish, Seagrass, and YouTube-VOS, surpassing existing self-supervised methods and achieving segmentation accuracy comparable to fully-supervised methods without the need for costly annotations. Trained on DeepFish, our model exhibits strong generalization, achieving high segmentation accuracy on the unseen Seagrass and YouTube-VOS datasets. Furthermore, our model is computationally efficient due to its parallel processing and efficient anchor sampling technique, making it suitable for real-time applications and potential deployment on edge devices. We present quantitative results using Jaccard Index and Dice coefficient, as well as qualitative comparisons, showcasing the accuracy, robustness, and efficiency of our approach for advancing underwater video analysis
A Spatio-Temporal Neural Network Forecasting Approach for Emulation of Firefront Models
Venue: arXiv cs.LG 2025
Year: 2025

Computational simulations of wildfire spread typically employ empirical rate-of-spread calculations under various conditions (such as terrain, fuel type, weather). Small perturbations in conditions can often lead to significant changes in fire spread (such as speed and direction), necessitating a computationally expensive large set of simulations to quantify uncertainty. Model emulation seeks alternative representations of physical models using machine learning, aiming to provide more efficient and/or simplified surrogate models. We propose a dedicated spatio-temporal neural network based framework for model emulation, able to capture the complex behaviour of fire spread models. The proposed approach can approximate forecasts at fine spatial and temporal resolutions that are often challenging for neural network based approaches. Furthermore, the proposed approach is robust even with small training sets, due to novel data augmentation methods. Empirical experiments show good agreement between simulated and emulated firefronts, with an average Jaccard score of 0.76.
Using a cognitive architecture to consider antiBlackness in design and development of AI systems
Venue: arXiv cs.CY 2025
Year: 2025

How might we use cognitive modeling to consider the ways in which antiblackness, and racism more broadly, impact the design and development of AI systems? We provide a discussion and an example towards an answer to this question. We use the ACT-R/Φ cognitive architecture and an existing knowledge graph system, ConceptNet, to consider this question not only from a cognitive and sociocultural perspective, but also from a physiological perspective. In addition to using a cognitive modeling as a means to explore how antiblackness may manifest in the design and development of AI systems (particularly from a software engineering perspective), we also introduce connections between antiblackness, the Human, and computational cognitive modeling. We argue that the typical eschewing of sociocultural processes and knowledge structures in cognitive architectures and cognitive modeling implicitly furthers a colorblind approach to cognitive modeling and hides sociocultural context that is always present in human behavior and affects cognitive processes.
Sanitization of Multimedia Content: A Survey of Techniques, Attacks, and Future Directions
Venue: arXiv cs.CR 2025
Year: 2025

The exploding rate of data publishing in our networked society has magnified the risk of sensitive information leakage and misuse, pushing the need to secure multimedia content from unintended exposure to potentially untrusted third parties. Data sanitization -- the process of securing multimedia by removing or obfuscating sensitive information such as personally identifiable or confidential data -- helps to mitigate the severe impact of security risks and privacy violations related to the published data. In this paper, we make several contributions. First, we classify data sanitization methods along two main dimensions: the media type (images, audio, text, and video) and the techniques used to sanitize sensitive regions, which we group into obfuscation-based (e.g., distortion, replacement) and removal-based approaches. Building on this categorization, we present a comprehensive review of technologies designed to protect multimedia content. We then broaden the scope by introducing the attacks that specifically target these technologies, followed by a discussion of potential countermeasures. Each aspect is complemented with critical discussions and lessons learned. Finally, we identify and elaborate on open research challenges in the crucial domain of multimodal multimedia sanitization. We argue that the systematization provided in this work -- together with the highlighted challenges and research directions -- offers a valuable blueprint for practitioners, industry, and academia alike, while paving the way for novel research avenues in the field.
Towards the Use of Saliency Maps for Explaining Low-Quality Electrocardiograms to End Users
Venue: arXiv cs.LG 2025
Year: 2025

When using medical images for diagnosis, either by clinicians or artificial intelligence (AI) systems, it is important that the images are of high quality. When an image is of low quality, the medical exam that produced the image often needs to be redone. In telemedicine, a common problem is that the quality issue is only flagged once the patient has left the clinic, meaning they must return in order to have the exam redone. This can be especially difficult for people living in remote regions, who make up a substantial portion of the patients at Portal Telemedicina, a digital healthcare organization based in Brazil. In this paper, we report on ongoing work regarding (i) the development of an AI system for flagging and explaining low-quality medical images in real-time, (ii) an interview study to understand the explanation needs of stakeholders using the AI system at OurCompany, and, (iii) a longitudinal user study design to examine the effect of including explanations on the workflow of the technicians in our clinics. To the best of our knowledge, this would be the first longitudinal study on evaluating the effects of XAI methods on end-users -- stakeholders that use AI systems but do not have AI-specific expertise. We welcome feedback and suggestions on our experimental setup.
On the Relationship Between Adversarial Robustness and Decision Region in Deep Neural Networks
Venue: arXiv cs.LG 2025
Year: 2025

In general, Deep Neural Networks (DNNs) are evaluated by the generalization performance measured on unseen data excluded from the training phase. Along with the development of DNNs, the generalization performance converges to the state-of-the-art and it becomes difficult to evaluate DNNs solely based on this metric. The robustness against adversarial attack has been used as an additional metric to evaluate DNNs by measuring their vulnerability. However, few studies have been performed to analyze the adversarial robustness in terms of the geometry in DNNs. In this work, we perform an empirical study to analyze the internal properties of DNNs that affect model robustness under adversarial attacks. In particular, we propose the novel concept of the Populated Region Set (PRS), where training samples are populated more frequently, to represent the internal properties of DNNs in a practical setting. From systematic experiments with the proposed concept, we provide empirical evidence to validate that a low PRS ratio has a strong relationship with the adversarial robustness of DNNs. We also devise PRS regularizer leveraging the characteristics of PRS to improve the adversarial robustness without adversarial training.
A Tutorial on Event Detection using Social Media Data Analysis: Applications, Challenges, and Open Problems
Venue: arXiv cs.SI 2025
Year: 2025

In recent years, social media has become one of the most popular platforms for communication. These platforms allow users to report real-world incidents that might swiftly and widely circulate throughout the whole social network. A social event is a real-world incident that is documented on social media. Social gatherings could contain vital documentation of crisis scenarios. Monitoring and analyzing this rich content can produce information that is extraordinarily valuable and help people and organizations learn how to take action. In this paper, a survey on the potential benefits and applications of event detection with social media data analysis will be presented. Moreover, the critical challenges and the fundamental tradeoffs in event detection will be methodically investigated by monitoring social media stream. Then, fundamental open questions and possible research directions will be introduced.