OpenRaiser/Intern-Atlas huggingface dataset:
$k$-times bin packing and its application to fair electricity distribution
Venue: arXiv cs.DS 2025
Year: 2025

Given items of different sizes and a fixed bin capacity, the bin-packing problem is to pack these items into a minimum number of bins such that the sum of item sizes in a bin does not exceed the capacity. We define a new variant called \emph{$k$-times bin-packing ($k$BP)}, where the goal is to pack the items such that each item appears exactly $k$ times, in $k$ different bins. We generalize some existing approximation algorithms for bin-packing to solve $k$BP, and analyze their performance ratio. The study of $k$BP is motivated by the problem of \emph{fair electricity distribution}. In many developing countries, the total electricity demand is higher than the supply capacity. We prove that every electricity division problem can be solved by $k$-times bin-packing for some finite $k$. We also show that $k$-times bin-packing can be used to distribute the electricity in a fair and efficient way. Particularly, we implement generalizations of the First-Fit and First-Fit Decreasing bin-packing algorithms to solve $k$BP, and apply the generalizations to real electricity demand data. We show that our generalizations outperform existing heuristic solutions to the same problem in terms of the egalitarian allocation of connection time.
Continuous optimization methods for the graph isomorphism problem
Venue: arXiv cs.DM 2025
Year: 2025

The graph isomorphism problem looks deceptively simple, but although polynomial-time algorithms exist for certain types of graphs such as planar graphs and graphs with bounded degree or eigenvalue multiplicity, its complexity class is still unknown. Information about potential isomorphisms between two graphs is contained in the eigenvalues and eigenvectors of their adjacency matrices. However, symmetries of graphs often lead to repeated eigenvalues so that associated eigenvectors are determined only up to basis rotations, which complicates graph isomorphism testing. We consider orthogonal and doubly stochastic relaxations of the graph isomorphism problem, analyze the geometric properties of the resulting solution spaces, and show that their complexity increases significantly if repeated eigenvalues exist. By restricting the search space to suitable subspaces, we derive an efficient Frank-Wolfe based continuous optimization approach for detecting isomorphisms. We illustrate the efficacy of the algorithm with the aid of various highly symmetric graphs.
Codiscovering graphical structure and functional relationships within data: A Gaussian Process framework for connecting the dots
Venue: arXiv cs.LG 2025
Year: 2025

Most problems within and beyond the scientific domain can be framed into one of the following three levels of complexity of function approximation. Type 1: Approximate an unknown function given input/output data. Type 2: Consider a collection of variables and functions, some of which are unknown, indexed by the nodes and hyperedges of a hypergraph (a generalized graph where edges can connect more than two vertices). Given partial observations of the variables of the hypergraph (satisfying the functional dependencies imposed by its structure), approximate all the unobserved variables and unknown functions. Type 3: Expanding on Type 2, if the hypergraph structure itself is unknown, use partial observations of the variables of the hypergraph to discover its structure and approximate its unknown functions. These hypergraphs offer a natural platform for organizing, communicating, and processing computational knowledge. While most scientific problems can be framed as the data-driven discovery of unknown functions in a computational hypergraph whose structure is known (Type 2), many require the data-driven discovery of the structure (connectivity) of the hypergraph itself (Type 3). We introduce an interpretable Gaussian Process (GP) framework for such (Type 3) problems that does not require randomization of the data, access to or control over its sampling, or sparsity of the unknown functions in a known or learned basis. Its polynomial complexity, which contrasts sharply with the super-exponential complexity of causal inference methods, is enabled by the nonlinear ANOVA capabilities of GPs used as a sensing mechanism.
Critical Influence of Overparameterization on Sharpness-aware Minimization
Venue: arXiv cs.LG 2025
Year: 2025

Sharpness-Aware Minimization (SAM) has attracted considerable attention for its effectiveness in improving generalization in deep neural network training by explicitly minimizing sharpness in the loss landscape. Its success, however, relies on the assumption that there exists sufficient variability of flatness in the solution space-a condition commonly facilitated by overparameterization. Yet, the interaction between SAM and overparameterization has not been thoroughly investigated, leaving a gap in understanding precisely how overparameterization affects SAM. Thus, in this work, we analyze SAM under varying degrees of overparameterization, presenting both empirical and theoretical findings that reveal its critical influence on SAM's effectiveness. First, we conduct extensive numerical experiments across diverse domains, demonstrating that SAM consistently benefits from overparameterization. Next, we attribute this phenomenon to the interplay between the enlarged solution space and increased implicit bias resulting from overparameterization. Furthermore, we show that this effect is particularly pronounced in practical settings involving label noise and sparsity, and yet, sufficient regularization is necessary. Last but not least, we provide other theoretical insights into how overparameterization helps SAM achieve minima with more uniform Hessian moments compared to SGD, and much faster convergence at a linear rate.
Online posting effects: Unveiling the non-linear journeys of users in depression communities on Reddit
Venue: arXiv cs.SI 2025
Year: 2025

Social media platforms have become pivotal as self-help forums, enabling individuals to share personal experiences and seek support. However, on topics as sensitive as depression, what are the consequences of online self-disclosure? Here, we delve into the dynamics of mental health discourse on various Reddit boards focused on depression. To this aim, we introduce a data-informed framework reconstructing online dynamics from 303k users interacting over two years. Through user-generated content, we identify 4 distinct clusters representing different psychological states. Our analysis unveils online posting effects: a user can transition to another psychological state after online exposure to peers' emotional/semantic content. As described by conditional Markov chains and different levels of social exposure, users' transitions reveal navigation through both positive and negative phases in a spiral rather than a linear progression. Interpreted in light of psychological literature, related particularly to the Patient Health Engagement (PHE) model, our findings can provide evidence that the type and layout of online social interactions have an impact on users' "journeys" when posting about depression.
End-to-end Joint Punctuated and Normalized ASR with a Limited Amount of Punctuated Training Data
Venue: arXiv cs.CL 2025
Year: 2025

Joint punctuated and normalized automatic speech recognition (ASR) aims at outputing transcripts with and without punctuation and casing. This task remains challenging due to the lack of paired speech and punctuated text data in most ASR corpora. We propose two approaches to train an end-to-end joint punctuated and normalized ASR system using limited punctuated data. The first approach uses a language model to convert normalized training transcripts into punctuated transcripts. This achieves a better performance on out-of-domain test data, with up to 17% relative Punctuation-Case-aware Word Error Rate (PC-WER) reduction. The second approach uses a single decoder conditioned on the type of output. This yields a 42% relative PC-WER reduction compared to Whisper-base and a 4% relative (normalized) WER reduction compared to the normalized output of a punctuated-only model. Additionally, our proposed model demonstrates the feasibility of a joint ASR system using as little as 5% punctuated training data with a moderate (2.42% absolute) PC-WER increase.
Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
Venue: arXiv cs.DS 2025
Year: 2025

Metric embeddings are a widely used method in algorithm design, where generally a ``complex'' metric is embedded into a simpler, lower-dimensional one. Historically, the theoretical computer science community has focused on bi-Lipschitz embeddings, which guarantee that every pairwise distance is approximately preserved. In contrast, alternative embedding objectives that are commonly used in practice avoid bi-Lipschitz distortion; yet these approaches have received comparatively less study in theory. In this paper, we focus on Multi-dimensional Scaling (MDS), where we are given a set of non-negative dissimilarities $\{d_{i,j}\}_{i,j\in [n]}$ over $n$ points, and the goal is to find an embedding $\{x_1,\dots,x_n\} \subset R^k$ that minimizes $$\textrm{OPT}=\min_{x}\mathbb{E}_{i,j\in [n]}\left(1-\frac{\|x_i - x_j\|}{d_{i,j}}\right)^2.$$ Despite its popularity, our theoretical understanding of MDS is extremely limited. Recently, Demaine et. al. (arXiv:2109.11505) gave the first approximation algorithm with provable guarantees for this objective, which achieves an embedding in constant dimensional Euclidean space with cost $\textrm{OPT} +ε$ in $n^2\cdot 2^{\textrm{poly}(Δ/ε)}$ time, where $Δ$ is the aspect ratio of the input dissimilarities. For metrics that admit low-cost embeddings, $Δ$ scales polynomially in $n$. In this work, we give the first approximation algorithm for MDS with quasi-polynomial dependency on $Δ$: for constant dimensional Euclidean space, we achieve a solution with cost $O(\log Δ)\cdot \textrm{OPT}^{Ω(1)}+ε$ in time $n^{O(1)} \cdot 2^{\text{poly}((\log(Δ)/ε))}$. Our algorithms are based on a novel geometry-aware analysis of a conditional rounding of the Sherali-Adams LP Hierarchy, allowing us to avoid exponential dependency on the aspect ratio, which would typically result from this rounding.
Proofs of NP = coNP = PSPACE: Current upgrade
Venue: arXiv cs.CC 2025
Year: 2025

In this paper we present a more transparent upgrade of our proofs and comment on Jerabek's paper [8] that tried to refute our results by providing exponential lower bounds on the implicational minimal logic.
Algorithmic Persuasion Through Simulation
Venue: arXiv cs.GT 2025
Year: 2025

We study a Bayesian persuasion game where a sender wants to persuade a receiver to take a binary action, such as purchasing a product. The sender is informed about the (real-valued) state of the world, such as the quality of the product, but only has limited information about the receiver's beliefs and utilities. Motivated by customer surveys, user studies, and recent advances in AI, we allow the sender to learn more about the receiver by querying an oracle that simulates the receiver's behavior. After a fixed number of queries, the sender commits to a messaging policy and the receiver takes the action that maximizes her expected utility given the message she receives. We characterize the sender's optimal messaging policy given any distribution over receiver types. We then design a polynomial-time querying algorithm that optimizes the sender's expected utility in this game. We also consider approximate oracles, more general query structures, and costly queries.
Spatial-Temporal Conditional Random Field for Human Trajectory Prediction
Venue: arXiv cs.CV 2025
Year: 2025

Trajectory prediction is of significant importance in computer vision. Accurate pedestrian trajectory prediction benefits autonomous vehicles and robots in planning their motion. Pedestrians' trajectories are greatly influenced by their intentions. Prior studies having introduced various deep learning methods only pay attention to the spatial and temporal information of trajectory, overlooking the explicit intention information. In this study, we introduce a novel model, termed the \textbf{S-T CRF}: \textbf{S}patial-\textbf{T}emporal \textbf{C}onditional \textbf{R}andom \textbf{F}ield, which judiciously incorporates intention information besides spatial and temporal information of trajectory. This model uses a Conditional Random Field (CRF) to generate a representation of future intentions, greatly improving the prediction of subsequent trajectories when combined with spatial-temporal representation. Furthermore, the study innovatively devises a space CRF loss and a time CRF loss, meticulously designed to enhance interaction constraints and temporal dynamics, respectively. Extensive experimental evaluations on dataset ETH/UCY and SDD demonstrate that the proposed method surpasses existing baseline approaches.
Prompt-Based Exemplar Super-Compression and Regeneration for Class-Incremental Learning
Venue: arXiv cs.CV 2025
Year: 2025

Replay-based methods in class-incremental learning (CIL) have attained remarkable success. Despite their effectiveness, the inherent memory restriction results in saving a limited number of exemplars with poor diversity. In this paper, we introduce PESCR, a novel approach that substantially increases the quantity and enhances the diversity of exemplars based on a pre-trained general-purpose diffusion model, without fine-tuning it on target datasets or storing it in the memory buffer. Images are compressed into visual and textual prompts, which are saved instead of the original images, decreasing memory consumption by a factor of 24. In subsequent phases, diverse exemplars are regenerated by the diffusion model. We further propose partial compression and diffusion-based data augmentation to minimize the domain gap between generated exemplars and real images. PESCR significantly improves CIL performance across multiple benchmarks, e.g., 3.2% above the previous state-of-the-art on ImageNet-100.
A Survey on Deep Learning for Polyp Segmentation: Techniques, Challenges and Future Trends
Venue: arXiv cs.CV 2025
Year: 2025

Early detection and assessment of polyps play a crucial role in the prevention and treatment of colorectal cancer (CRC). Polyp segmentation provides an effective solution to assist clinicians in accurately locating and segmenting polyp regions. In the past, people often relied on manually extracted lower-level features such as color, texture, and shape, which often had issues capturing global context and lacked robustness to complex scenarios. With the advent of deep learning, more and more outstanding medical image segmentation algorithms based on deep learning networks have emerged, making significant progress in this field. This paper provides a comprehensive review of polyp segmentation algorithms. We first review some traditional algorithms based on manually extracted features and deep segmentation algorithms, then detail benchmark datasets related to the topic. Specifically, we carry out a comprehensive evaluation of recent deep learning models and results based on polyp sizes, considering the pain points of research topics and differences in network structures. Finally, we discuss the challenges of polyp segmentation and future trends in this field. The models, benchmark datasets, and source code links we collected are all published at https://github.com/taozh2017/Awesome-Polyp-Segmentation.
LiteQSign: Lightweight and Quantum-Safe Signatures for Heterogeneous IoT Applications
Venue: arXiv cs.CR 2025
Year: 2025

The rapid proliferation of resource-constrained IoT devices across sectors like healthcare, industrial automation, and finance introduces major security challenges. Traditional digital signatures, though foundational for authentication, are often infeasible for low-end devices with limited computational, memory, and energy resources. Also, the rise of quantum computing necessitates post-quantum (PQ) secure alternatives. However, NIST-standardized PQ signatures impose substantial overhead, limiting their practicality in energy-sensitive applications such as wearables, where signer-side efficiency is critical. To address these challenges, we present LightQSign (LightQS), a novel lightweight PQ signature that achieves near-optimal signature generation efficiency with only a small, constant number of hash operations per signing. Its core innovation enables verifiers to obtain one-time hash-based public keys without interacting with signers or third parties through secure computation. We formally prove the security of LightQSign in the random oracle model and evaluate its performance on commodity hardware and a resource-constrained 8-bit AtMega128A1 microcontroller. Experimental results show that LightQSign outperforms NIST PQC standards with lower computational overhead, minimal memory usage, and compact signatures. On an 8-bit microcontroller, it achieves up to 1.5-24x higher energy efficiency and 1.7-22x shorter signatures than PQ counterparts, and 56-76x better energy efficiency than conventional standards-enabling longer device lifespans and scalable, quantum-resilient authentication.
Predictable Reinforcement Learning Dynamics through Entropy Rate Minimization
Venue: arXiv cs.LG 2025
Year: 2025

In Reinforcement Learning (RL), agents have no incentive to exhibit predictable behaviors, and are often pushed (through e.g. policy entropy regularisation) to randomise their actions in favor of exploration. This often makes it challenging for other agents and humans to predict an agent's behavior, triggering unsafe scenarios (e.g. in human-robot interaction). We propose a novel method to induce predictable behavior in RL agents, termed Predictability-Aware RL (PARL), employing the agent's trajectory entropy rate to quantify predictability. Our method maximizes a linear combination of a standard discounted reward and the negative entropy rate, thus trading off optimality with predictability. We show how the entropy rate can be formally cast as an average reward, how entropy-rate value functions can be estimated from a learned model and incorporate this in policy-gradient algorithms, and demonstrate how this approach produces predictable (near-optimal) policies in tasks inspired by human-robot use-cases.
The Feature Speed Formula: a flexible approach to scale hyper-parameters of deep neural networks
Venue: arXiv cs.LG 2025
Year: 2025

Deep learning succeeds by doing hierarchical feature learning, yet tuning hyper-parameters (HP) such as initialization scales, learning rates etc., only give indirect control over this behavior. In this paper, we introduce a key notion to predict and control feature learning: the angle $θ_\ell$ between the feature updates and the backward pass (at layer index $\ell$). We show that the magnitude of feature updates after one GD step, at any training time, can be expressed via a simple and general \emph{feature speed formula} in terms of this angle $θ_\ell$, the loss decay, and the magnitude of the backward pass. This angle $θ_\ell$ is controlled by the conditioning of the layer-to-layer Jacobians and at random initialization, it is determined by the spectrum of a certain kernel, which coincides with the Neural Tangent Kernel when $\ell=\text{depth}$. Given $θ_\ell$, the feature speed formula provides us with rules to adjust HPs (scales and learning rates) so as to satisfy certain dynamical properties, such as feature learning and loss decay. We investigate the implications of our approach for ReLU MLPs and ResNets in the large width-then-depth limit. Relying on prior work, we show that in ReLU MLPs with iid initialization, the angle degenerates with depth as $\cos(θ_\ell)=Θ(1/\sqrt{\ell})$. In contrast, ResNets with branch scale $O(1/\sqrt{\text{depth}})$ maintain a non-degenerate angle $\cos(θ_\ell)=Θ(1)$. We use these insights to recover key properties of known HP scalings and also to introduce a new HP scaling for large depth ReLU MLPs with favorable theoretical properties.
Communication-Efficient Federated Optimization over Semi-Decentralized Networks
Venue: arXiv cs.LG 2025
Year: 2025

In large-scale federated and decentralized learning, communication efficiency is one of the most challenging bottlenecks. While gossip communication -- where agents can exchange information with their connected neighbors -- is more cost-effective than communicating with the remote server, it often requires a greater number of communication rounds, especially for large and sparse networks. To tackle the trade-off, we examine the communication efficiency under a semi-decentralized communication protocol, in which agents can perform both agent-to-agent and agent-to-server communication in a probabilistic manner. We design a tailored communication-efficient algorithm over semi-decentralized networks, referred to as PISCO, which inherits the robustness to data heterogeneity thanks to gradient tracking and allows multiple local updates for saving communication. We establish the convergence rate of PISCO for nonconvex problems and show that PISCO enjoys a linear speedup in terms of the number of agents and local updates. Our numerical results highlight the superior communication efficiency of PISCO and its resilience to data heterogeneity and various network topologies.
Generalized Robot 3D Vision-Language Model with Fast Rendering and Pre-Training Vision-Language Alignment
Venue: arXiv cs.CV 2025
Year: 2025

Deep neural network models have achieved remarkable progress in 3D scene understanding while trained in the closed-set setting and with full labels. However, the major bottleneck is that these models do not have the capacity to recognize any unseen novel classes beyond the training categories in diverse real-world applications. Therefore, we are in urgent need of a framework that can simultaneously be applicable to both 3D point cloud segmentation and detection, particularly in the circumstances where the labels are rather scarce. This work presents a generalized and straightforward framework for dealing with 3D scene understanding when the labeled scenes are quite limited. To extract knowledge for novel categories from the pre-trained vision-language models, we propose a hierarchical feature-aligned pre-training and knowledge distillation strategy to extract and distill meaningful information from large-scale vision-language models, which helps benefit the open-vocabulary scene understanding tasks. To encourage latent instance discrimination and to guarantee efficiency, we propose the unsupervised region-level semantic contrastive learning scheme for point clouds, using confident predictions of the neural network to discriminate the intermediate feature embeddings at multiple stages. In the limited reconstruction case, our proposed approach, termed WS3D++, ranks 1st on the large-scale ScanNet benchmark on both the task of semantic segmentation and instance segmentation. Extensive experiments with both indoor and outdoor scenes demonstrated the effectiveness of our approach in both data-efficient learning and open-world few-shot learning. The code is made publicly available at: https://drive.google.com/drive/folders/1M58V-PtR8DBEwD296zJkNg_m2qq-MTAP?usp=sharing.