OpenRaiser/Intern-Atlas huggingface dataset:
Online Resource Allocation with Cancellations
Venue: arXiv cs.DS 2025
Year: 2025

We initiate the study of two-sided online resource allocation with costly cancellations. Our focus is on edge-weighted online bipartite matching (and several of its extensions), where nodes arrive online and request offline resources. In contrast to the classic literature, any fraction of an offline resource that was preallocated to an earlier online node can be reclaimed, resulting in the loss of the previously allocated edge-weight plus an additional penalty equal to a non-negative constant factor $f$ times the edge-weight. Parameterizing the problem by the buyback factor $f$, our main result is the development of optimal competitive algorithms for \emph{all possible values} of $f$ through a novel primal-dual family of algorithms in the fractional (or equivalently, large capacity) setting, and establishing their optimality by deriving matching lower bounds. Interestingly, our results reveal a phase transition: for the small buyback regime ($f < \frac{e-2}{2}$), the optimal competitive ratio is $\frac{e}{e-(1+f)}$, and for the large buyback regime ($f \geq \frac{e-2}{2}$), the competitive ratio is $-W_{-1}\left(\frac{-1}{e(1+f)}\right)$, where $W_{-1}$ is the non-principal branch of the Lambert $W$ function. We also study variants of this model, such as matching with deterministic integral allocations. We again show a phase transition: for the small buyback regime ($f < \frac{1}{3}$), the optimal competitive ratio is $\frac{2}{1-f}$, while for the large buyback regime ($f \geq \frac{1}{3}$), the competitive ratio is $1 + 2f + 2\sqrt{f(1+f)}$. We further consider various extensions, including to configuration allocations and submodular welfare maximization, as well as negative values of $f$, modeling a secondary supply channels or overflow capacities available at discounted rates. Our unifying primal-dual framework achieves the exact optimal competitive ratio across all these variants
Edge-weighted Online Stochastic Matching: Beating $1-\frac1e$
Venue: arXiv cs.DS 2025
Year: 2025

We study the edge-weighted online stochastic matching problem. Since Feldman, Mehta, Mirrokni, and Muthukrishnan proposed the $(1-\frac1e)$-competitive Suggested Matching algorithm, there has been no improvement for the general edge-weighted online stochastic matching problem. In this paper, we introduce the first algorithm beating the $1-\frac1e$ barrier in this setting, achieving a competitive ratio of $0.645$. Under the LP proposed by Jaillet and Lu, we design an algorithmic preprocessing, dividing all edges into two classes. Then based on the Suggested Matching algorithm, we adjust the matching strategy to improve the performance on one class in the early stage and on another class in the late stage, while keeping the matching events of different edges highly independent. By balancing them, we finally guarantee the matched probability of every single edge.
Robustness of Locally Differentially Private Graph Analysis Against Poisoning
Venue: arXiv cs.CR 2025
Year: 2025

Locally differentially private (LDP) graph analysis allows private analysis on a graph that is distributed across multiple users. However, such computations are vulnerable to data poisoning attacks where an adversary can skew the results by submitting malformed data. In this paper, we formally study the impact of poisoning attacks for graph degree estimation protocols under LDP. We make two key technical contributions. First, we observe LDP makes a protocol more vulnerable to poisoning -- the impact of poisoning is worse when the adversary can directly poison their (noisy) responses, rather than their input data. Second, we observe that graph data is naturally redundant -- every edge is shared between two users. Leveraging this data redundancy, we design robust degree estimation protocols under LDP that can significantly reduce the impact of data poisoning and compute degree estimates with high accuracy. We evaluate our proposed robust degree estimation protocols under poisoning attacks on real-world datasets to demonstrate their efficacy in practice.
Distributed Black-box Attack: Do Not Overestimate Black-box Attacks
Venue: arXiv cs.LG 2025
Year: 2025

As cloud computing becomes pervasive, deep learning models are deployed on cloud servers and then provided as APIs to end users. However, black-box adversarial attacks can fool image classification models without access to model structure and weights. Recent studies have reported attack success rates of over 95% with fewer than 1,000 queries. Then the question arises: whether black-box attacks have become a real threat against cloud APIs? To shed some light on this, our research indicates that black-box attacks are not as effective against cloud APIs as proposed in research papers due to several common mistakes that overestimate the efficiency of black-box attacks. To avoid similar mistakes, we conduct black-box attacks directly on cloud APIs rather than local models.
Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity
Venue: arXiv cs.DS 2025
Year: 2025

The Capacitated Vehicle Routing Problem (CVRP) is one of the most extensively studied problems in combinatorial optimization. Based on customer demand, we distinguish three variants of CVRP: unit-demand, splittable, and unsplittable. In this paper, we consider $k$-CVRP in general metrics and on general graphs, where $k$ is the vehicle capacity. All three versions are APX-hard for any fixed $k\geq3$. Assume that the approximation ratio of metric TSP is $\frac{3}{2}$. We present a $(\frac{5}{2}-Θ(\frac{1}{\sqrt{k}}))$-approximation algorithm for the splittable and unit-demand cases, and a $(\frac{5}{2}+\ln2-Θ(\frac{1}{\sqrt{k}}))$-approximation algorithm for the unsplittable case. Our approximation ratio is better than the previous results when $k$ is less than a sufficiently large value, approximately $1.7\times10^7$. For small values of $k$, we design independent and elegant algorithms with further improvements. For the splittable and unit-demand cases, we improve the approximation ratio from $1.792$ to $1.500$ for $k=3$, and from $1.750$ to $1.500$ for $k=4$. For the unsplittable case, we improve the approximation ratio from $1.792$ to $1.500$ for $k=3$, from $2.051$ to $1.750$ for $k=4$, and from $2.249$ to $2.157$ for $k=5$. The approximation ratio for $k=3$ surprisingly achieves the same value as in the splittable case. Our techniques, such as EX-ITP -- an extension of the classic ITP method, have the potential to improve algorithms for other routing problems as well.
DPM-Solver++: Fast Solver for Guided Sampling of Diffusion Probabilistic Models
Venue: arXiv cs.LG 2025
Year: 2025

Diffusion probabilistic models (DPMs) have achieved impressive success in high-resolution image synthesis, especially in recent large-scale text-to-image generation applications. An essential technique for improving the sample quality of DPMs is guided sampling, which usually needs a large guidance scale to obtain the best sample quality. The commonly-used fast sampler for guided sampling is DDIM, a first-order diffusion ODE solver that generally needs 100 to 250 steps for high-quality samples. Although recent works propose dedicated high-order solvers and achieve a further speedup for sampling without guidance, their effectiveness for guided sampling has not been well-tested before. In this work, we demonstrate that previous high-order fast samplers suffer from instability issues, and they even become slower than DDIM when the guidance scale grows large. To further speed up guided sampling, we propose DPM-Solver++, a high-order solver for the guided sampling of DPMs. DPM-Solver++ solves the diffusion ODE with the data prediction model and adopts thresholding methods to keep the solution matches training data distribution. We further propose a multistep variant of DPM-Solver++ to address the instability issue by reducing the effective step size. Experiments show that DPM-Solver++ can generate high-quality samples within only 15 to 20 steps for guided sampling by pixel-space and latent-space DPMs.
Road Markings Segmentation from LIDAR Point Clouds using Reflectivity Information
Venue: arXiv cs.RO 2025
Year: 2025

Lane detection algorithms are crucial for the development of autonomous vehicles technologies. The more extended approach is to use cameras as sensors. However, LIDAR sensors can cope with weather and light conditions that cameras can not. In this paper, we introduce a method to extract road markings from the reflectivity data of a 64-layers LIDAR sensor. First, a plane segmentation method along with region grow clustering was used to extract the road plane. Then we applied an adaptive thresholding based on Otsu s method and finally, we fitted line models to filter out the remaining outliers. The algorithm was tested on a test track at 60km/h and a highway at 100km/h. Results showed the algorithm was reliable and precise. There was a clear improvement when using reflectivity data in comparison to the use of the raw intensity data both of them provided by the LIDAR sensor.
Human alignment of neural network representations
Venue: arXiv cs.CV 2025
Year: 2025

Today's computer vision models achieve human or near-human level performance across a wide variety of vision tasks. However, their architectures, data, and learning algorithms differ in numerous ways from those that give rise to human vision. In this paper, we investigate the factors that affect the alignment between the representations learned by neural networks and human mental representations inferred from behavioral responses. We find that model scale and architecture have essentially no effect on the alignment with human behavioral responses, whereas the training dataset and objective function both have a much larger impact. These findings are consistent across three datasets of human similarity judgments collected using two different tasks. Linear transformations of neural network representations learned from behavioral responses from one dataset substantially improve alignment with human similarity judgments on the other two datasets. In addition, we find that some human concepts such as food and animals are well-represented by neural networks whereas others such as royal or sports-related objects are not. Overall, although models trained on larger, more diverse datasets achieve better alignment with humans than models trained on ImageNet alone, our results indicate that scaling alone is unlikely to be sufficient to train neural networks with conceptual representations that match those used by humans.
Certificate Games and Consequences for the Classical Adversary Bound
Venue: arXiv cs.CC 2025
Year: 2025

We introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function values and are asked to output some index $i$ such that $x_i\neq y_i$, in a zero-communication setting. We study four versions of certificate games, namely private coin, public coin, shared entanglement and non-signaling games. The public-coin variant of certificate games gives a new characterization of the classical adversary bound, a lower bound on randomized query complexity which was introduced as a classical version of the quantum (non-negative) quantum adversary bound. We show that complexity in the public coin model (therefore also the classical adversary) is bounded above by certificate complexity, as well as by expectational certificate complexity and sabotage complexity. On the other hand, it is bounded below by fractional and randomized certificate complexity. The quantum measure reveals an interesting and surprising difference between classical and quantum query models: the quantum certificate game complexity can be quadratically larger than quantum query complexity. We use non-signaling, a notion from quantum information, to give a lower bound of $n$ on the quantum certificate game complexity of the OR function, whose quantum query complexity is $Θ(\sqrt{n})$, then go on to show that this ``non-signaling bottleneck'' applies to all functions with high sensitivity, block sensitivity, fractional block sensitivity, as well as classical adversary. This implies the collapse of all models of certificate games, except private randomness, to the classical adversary bound. We consider the single-bit version of certificate games, where the inputs of the two players are restricted to having Hamming distance 1, and give a new characterization of sensitivity and spectral sensitivity.
Approximating Nash Social Welfare by Matching and Local Search
Venue: arXiv cs.GT 2025
Year: 2025

For any $\eps>0$, we give a simple, deterministic $(4+\eps)$-approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. We also consider the asymmetric variant of the problem, where the objective is to maximize the weighted geometric mean of agents' valuations, and give an $\ee (ω+ 2 + \eps)$-approximation if the ratio between the largest weight and the average weight is at most $ω$. We also show that the $\nfrac12$-EFX envy-freeness property can be attained simultaneously with a constant-factor approximation. More precisely, we can find an allocation in polynomial time that is both $\nfrac12$-EFX and a $(8+\eps)$-approximation to the symmetric NSW problem under submodular valuations.
On the Nucleolus of a Class of Linear Production Games
Venue: arXiv cs.GT 2025
Year: 2025

We study the nucleolus in a class of cooperative games where agents collaborate by sharing demands and production-distribution capacities across multiple markets. These production-distribution games form a structured subclass of linear production games and capture applications such as horizontal collaboration in logistics. While computing the nucleolus is generally NP-hard for linear production games, we show that structural properties of production-distribution games enable efficient computation in several cases. Our main results focus on the uncapacitated variant. First, we provide a polynomial-time characterization of instances where the core reduces to a singleton, allowing direct computation of the nucleolus. Second, when the number of markets is fixed, we design a separation-based polynomial-time algorithm. Third, in the single-market case, we develop a faster combinatorial primal-dual algorithm that runs in $O(n^4)$.
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
Venue: arXiv cs.CC 2025
Year: 2025

We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets $σ,ρ$ of non-negative integers, a $(σ,ρ)$-set of a graph $G$ is a set $S$ of vertices such that $|N(u)\cap S|\in σ$ for every $u\in S$, and $|N(v)\cap S|\in ρ$ for every $v\not\in S$. The problem of finding a $(σ,ρ)$-set (of a certain size) unifies standard problems such as Independent Set, Dominating Set, Independent Dominating Set, and many others. For all pairs of finite or cofinite sets $(σ,ρ)$, we determine (under standard complexity assumptions) the best possible value $c_{σ,ρ}$ such that there is an algorithm that counts $(σ,ρ)$-sets in time $c_{σ,ρ}^{\sf tw}\cdot n^{O(1)}$ (if a tree decomposition of width ${\sf tw}$ is given in the input). For example, for the Exact Independent Dominating Set problem (also known as Perfect Code) corresponding to $σ=\{0\}$ and $ρ=\{1\}$, we improve the $3^{\sf tw}\cdot n^{O(1)}$ algorithm of [van Rooij, 2020] to $2^{\sf tw}\cdot n^{O(1)}$. Despite the unusually delicate definition of $c_{σ,ρ}$, an accompanying paper shows that our algorithms are most likely optimal, that is, for any pair $(σ, ρ)$ of finite or cofinite sets where the problem is non-trivial, and any $\varepsilon>0$, a $(c_{σ,ρ}-\varepsilon)^{\sf tw}\cdot n^{O(1)}$-algorithm counting the number of $(σ,ρ)$-sets would violate the Counting Strong Exponential-Time Hypothesis (#SETH). For finite sets $σ$ and $ρ$, these lower bounds also extend to the decision version, and hence, our algorithms are optimal in this setting as well. In contrast, for many cofinite sets, we show that further significant improvements for the decision and optimization versions are possible using the technique of representative sets.
Vision-Based Online Key Point Estimation of Deformable Robots
Venue: arXiv cs.RO 2025
Year: 2025

The precise control of soft and continuum robots requires knowledge of their shape, which has, in contrast to classical rigid robots, infinite degrees of freedom. To partially reconstruct the shape, proprioceptive techniques use built-in sensors resulting in inaccurate results and increased fabrication complexity. Exteroceptive methods so far rely on expensive tracking systems with reflective markers placed on all components, which are infeasible for deformable robots interacting with the environment due to marker occlusion and damage. Here, a regression approach is presented for 3D key point estimation using a convolutional neural network. The proposed approach takes advantage of data-driven supervised learning and is capable of online marker-less estimation during inference. Two images of a robotic system are taken simultaneously at 25 Hz from two different perspectives, and are fed to the network, which returns for each pair the parameterized key point or PCC shape representations. The proposed approach outperforms marker-less state-of-the-art methods by a maximum of 4.5% in estimation accuracy while at the same time being more robust and requiring no prior knowledge of the shape. Online evaluations on two types of soft robotic arms and a soft robotic fish demonstrate our method's accuracy and versatility on highly deformable systems.
Ultraverse: A System-Centric Framework for Efficient What-If Analysis for Database-Intensive Web Applications
Venue: arXiv cs.DB 2025
Year: 2025

Existing what-if analysis systems are predominantly tailored to operate on either only the application layer or only the database layer of software. This isolated approach limits their effectiveness in scenarios where intensive interaction between applications and database systems occurs. To address this gap, we introduce Ultraverse, a what-if analysis framework that seamlessly integrates both application and database layers. Ultraverse employs dynamic symbolic execution to effectively translate application code into compact SQL procedure representations, thereby synchronizing application semantics at both SQL and application levels during what-if replays. A novel aspect of Ultraverse is its use of advanced query dependency analysis, which serves two key purposes: (1) it eliminates the need to replay irrelevant transactions that do not influence the outcome, and (2) it facilitates parallel replay of mutually independent transactions, significantly enhancing the analysis efficiency. Ultraverse is applicable to existing unmodified database systems and legacy application codes. Our extensive evaluations of the framework have demonstrated remarkable improvements in what-if analysis speed, achieving performance gains ranging from 7.7x to 291x across diverse benchmarks.
Enabling Efficient Attack Investigation via Human-in-the-Loop Security Analysis
Venue: arXiv cs.CR 2025
Year: 2025

System auditing is a vital technique for collecting system call events as system provenance and investigating complex multi-step attacks such as Advanced Persistent Threats. However, existing attack investigation methods struggle to uncover long attack sequences due to the massive volume of system provenance data and their inability to focus on attack-relevant parts. In this paper, we present Provexa, a defense system that enables human analysts to effectively analyze large-scale system provenance to reveal multi-step attack sequences. Provexa introduces an expressive domain-specific language, ProvQL, that offers essential primitives for various types of attack analyses (e.g., attack pattern search, attack dependency tracking) with user-defined constraints, enabling analysts to focus on attack-relevant parts and iteratively sift through the large provenance data. Moreover, Provexa provides an optimized execution engine for efficient language execution. Our extensive evaluations on a wide range of attack scenarios demonstrate the practical effectiveness of Provexa in facilitating timely attack investigation.
A Primer on Zadoff Chu Sequences
Venue: arXiv cs.IT 2025
Year: 2025

Zadoff-Chu (ZC) sequences are an important manifestation of spread spectrum in modern cellular systems, including LTE and 5G NR. They have to some extent displaced PN and Walsh sequences which were the mainstays of 3G cellular (WCDMA and cdma2000) and the 2G-era IS-95. ZC sequences are complex sequences with unit amplitude and particular phase shifts, as opposed to Walsh and PN codes which are real and binary valued, most commonly $\pm1$. ZC sequences have a number of remarkable and desirable properties that we define in the next section. Because of these properties, they are used for many key functions in current cellular systems, and are likely to be prevalent in future cellular systems as well. In LTE and 5G NR, they are widely used for a number of important initial access and overhead channel functions that are often overlooked by engineers who focus on data transmission. For example, ZC sequences are used for initial access in both the downlink (synchronization sequences) and uplink (random access premables). They are also used for transmitting uplink control information, and as pilot symbols for both uplink channel sounding and fine-grained channel estimation. It is not an exaggeration to say that most types of signals other than the data transmissions in modern cellular standards utilize ZC sequences. In this primer, we define ZC sequences and introduce their key properties, and provide some examples. We also discuss modified ZC sequences that are commonly used in practice, but are not, strictly speaking, ZC sequences. We also overview their uses in LTE and 5G.
Interpretable Few-shot Learning with Online Attribute Selection
Venue: arXiv cs.LG 2025
Year: 2025

Few-shot learning (FSL) presents a challenging learning problem in which only a few samples are available for each class. Decision interpretation is more important in few-shot classification due to a greater chance of error compared to traditional classification. However, the majority of the previous FSL methods are black-box models. In this paper, we propose an inherently interpretable model for FSL based on human-friendly attributes. Previously, human-friendly attributes have been utilized to train models with the potential for human interaction and interpretability. However, such approaches are not directly extendible to the few-shot classification scenario. Moreover, we propose an online attribute selection mechanism to effectively filter out irrelevant attributes in each episode. The attribute selection mechanism improves accuracy and helps with interpretability by reducing the number of attributes that participate in each episode. We further propose a mechanism that automatically detects the episodes where the pool of available human-friendly attributes is insufficient, and subsequently augments it by engaging some learned unknown attributes. We demonstrate that the proposed method achieves results on par with black-box few-shot learning models on four widely used datasets. We also empirically evaluate the level of decision alignment between different models and human understanding and show that our model outperforms the comparison methods based on this criterion.