OpenRaiser/Intern-Atlas huggingface dataset:
Explicit Group Sparse Projection with Applications to Deep Learning and NMF
Venue: arXiv cs.LG 2025
Year: 2025

We design a new sparse projection method for a set of vectors that guarantees a desired average sparsity level measured leveraging the popular Hoyer measure (an affine function of the ratio of the $\ell_1$ and $\ell_2$ norms). Existing approaches either project each vector individually or require the use of a regularization parameter which implicitly maps to the average $\ell_0$-measure of sparsity. Instead, in our approach we set the sparsity level for the whole set explicitly and simultaneously project a group of vectors with the sparsity level of each vector tuned automatically. We show that the computational complexity of our projection operator is linear in the size of the problem. Additionally, we propose a generalization of this projection by replacing the $\ell_1$ norm by its weighted version. We showcase the efficacy of our approach in both supervised and unsupervised learning tasks on image datasets including CIFAR10 and ImageNet. In deep neural network pruning, the sparse models produced by our method on ResNet50 have significantly higher accuracies at corresponding sparsity values compared to existing competitors. In nonnegative matrix factorization, our approach yields competitive reconstruction errors against state-of-the-art algorithms.
A flexible FPGA accelerator for convolutional neural networks
Venue: arXiv cs.DC 2025
Year: 2025

Though CNNs are highly parallel workloads, in the absence of efficient on-chip memory reuse techniques, an accelerator for them quickly becomes memory bound. In this paper, we propose a CNN accelerator design for inference that is able to exploit all forms of reuse available to minimize off-chip memory access while increasing utilization of available resources. The proposed design is composed of cores, each of which contains a one-dimensional array of processing elements. These cores can exploit different types of reuse available in CNN layers of varying shapes without requiring any reconfiguration; in particular, our design minimizes underutilization due to problem sizes that are not perfect multiples of the underlying hardware array dimensions. A major obstacle in the adoption of FPGAs as a platform for CNN inference is the difficulty to program these devices using hardware description languages. Our end goal is to also address this, and we develop preliminary software support via a codesign in order to leverage the accelerator through TensorFlow, a dominant high-level programming model. Our framework takes care of tiling and scheduling of neural network layers and generates necessary low-level commands to execute the CNN. Experimental evaluation on a real system with a PCI-express based Xilinx VC709 board demonstrates the effectiveness of our approach. As a result of an effective interconnection, the design maintains a high frequency when we scale the number of PEs. The sustained performance overall is a good fraction of the accelerator's theoretical peak performance.
Equivalences between Non-trivial Variants of 3LDT and Conv3LDT
Venue: arXiv cs.DS 2025
Year: 2025

The popular 3SUM conjecture states that there is no strongly subquadratic time algorithm for checking if a given set of integers contains three distinct elements $x_1, x_2, x_3$ such that $x_1+x_2=x_3$. A closely related problem is to check if a given set of integers contains distinct elements satisfying $x_1+x_2=2x_3$. This can be reduced to 3SUM in almost-linear time, but surprisingly a reverse reduction establishing 3SUM hardness was not known. We provide such a reduction, thus resolving an open question of Erickson. In fact, we consider a more general problem called 3LDT parameterized by integer parameters $α_1, α_2, α_3$ and $t$. In this problem, we need to check if a given set of integers contains distinct elements $x_1, x_2, x_3$ such that $α_1 x_1+α_2 x_2 +α_3 x_3 = t$. We prove that all non-trivial variants of 3LDT over the same universe $[-n^c,n^c]$ for some $c\geq2$ are equivalent under subquadratic reductions. The main technical tool used in our proof is an application of the famous Behrend's construction that partitions a given set of integers into few subsets that avoid a chosen linear equation. We extend our results to Conv3LDT and show that for all $c\geq2$, all non-trivial variants of 3LDT over the universe $[-n^c,n^c]$ and of Conv3LDT over the universe $[-n^{c-1},n^{c-1}]$ are subquadratic-equivalent, so in particular they are all equivalent to 3SUM under subquadratic reductions. Finally, we show how to apply the methods of Fischer et al. to show that we can reduce non-trivial variant of 3LDT (Conv3LDT) over an arbitrary universe to the same variant over cubic (quadratic) universe.
Notes on Theory of Distributed Systems
Venue: arXiv cs.DC 2025
Year: 2025

Notes for the Yale course CPSC 465/565 Theory of Distributed Systems. Table of Contents: 1 Introduction, 2 Model, 3 Broadcast and convergecast, 4 Distributed breadth-first search, 5 Leader election, 6 Causal ordering and logical clocks, 7 Synchronizers, 8 Coordinated attack, 9 Synchronous agreement, 10 Byzantine agreement, 11 Impossibility of asynchronous agreement, 12 Paxos, 13 Failure detectors, 14 Quorum systems, 15 Permissionless systems, 16 Model, 17 Distributed shared memory, 18 Mutual exclusion, 19 The wait-free hierarchy, 20 Atomic snapshots, 21 Lower bounds on perturbable objects, 22 Restricted-use objects, 23 Common2, 24 Randomized consensus and test-and-set, 25 Renaming, 26 Software transactional memory, 27 Obstruction-freedom, 28 BG simulation, 29 Topological methods, 30 Approximate agreement, 31 Overview, 32 Self-stabilization, 33 Distributed graph algorithms, 34 Population protocols, 35 Mobile robots, 36 Beeping
Safe Voting: Resilience to Abstention and Sybils
Venue: arXiv cs.MA 2025
Year: 2025

Voting rules may implement the will of the society when all eligible voters vote, and only them. However, they may fail to do so when sybil (fake or duplicate) votes are present and when only some honest (non sybil) voters actively participate. As, unfortunately, sometimes this is the case, our aim here is to address social choice in the presence of sybils and voter abstention. % To do so, we build upon the framework of Reality-aware Social Choice: we assume the status quo as an ever-present distinguished alternative, and study \emph{status quo Enforcing (QUE) voting rules}, which add virtual votes in support of the status quo. We characterize the tradeoff between \emph{safety} and \emph{liveness} (the ability of active honest voters to maintain/change the status quo, respectively) in several domains, and show that the voting rules are often optimal. \revision{Our characterization identifies the exact conditions under which mechanisms remain both resilient to sybils and responsive to verified participation, offering a quantitative tool for designers to measure the benefit of increased participation and verified identities.
DSAC: Distributional Soft Actor-Critic for Risk-Sensitive Reinforcement Learning
Venue: arXiv cs.LG 2025
Year: 2025

We present Distributional Soft Actor-Critic (DSAC), a distributional reinforcement learning (RL) algorithm that combines the strengths of distributional information of accumulated rewards and entropy-driven exploration from Soft Actor-Critic (SAC) algorithm. DSAC models the randomness in both action and rewards, surpassing baseline performances on various continuous control tasks. Unlike standard approaches that solely maximize expected rewards, we propose a unified framework for risk-sensitive learning, one that optimizes the risk-related objective while balancing entropy to encourage exploration. Extensive experiments demonstrate DSAC's effectiveness in enhancing agent performances for both risk-neutral and risk-sensitive control tasks.
On P Versus NP
Venue: arXiv cs.CC 2025
Year: 2025

It is shown that graph-theoretic problem CLIQUE can't be solved in polynomial time by any deterministic TM. This upgrades the well-known partial result that claims only monotone unsolvability thereof, and eventually implies P $\neq$ NP as CLIQUE is NP-complete. This paper essentially simplifies my previous presentation that used more complex models of computation based on standard Boolean semantics while fixing technical errors spotted by a generic proof assistant Isabelle that has been implemented by René Thiemann.
What Do Our Choices Say About Our Preferences?
Venue: arXiv cs.DS 2025
Year: 2025

Taking online decisions is a part of everyday life. Think of buying a house, parking a car or taking part in an auction. We often take those decisions publicly, which may breach our privacy - a party observing our choices may learn a lot about our preferences. In this paper we investigate the online stopping algorithms from the privacy preserving perspective, using a mathematically rigorous differential privacy notion. In differentially private algorithms there is usually an issue of balancing the privacy and utility. In this regime, in most cases, having both optimality and high level of privacy at the same time is impossible. We propose a natural mechanism to achieve a controllable trade-off, quantified by a parameter, between the accuracy of the online algorithm and its privacy. Depending on the parameter, our mechanism can be optimal with weaker differential privacy or suboptimal, yet more privacy-preserving. We conduct a detailed accuracy and privacy analysis of our mechanism applied to the optimal algorithm for the classical secretary problem. Thereby the classical notions from two distinct areas - optimal stopping and differential privacy - meet for the first time.
Beyond Grids: Multi-objective Bayesian Optimization With Adaptive Discretization
Venue: arXiv cs.LG 2025
Year: 2025

We consider the problem of optimizing a vector-valued objective function $\boldsymbol{f}$ sampled from a Gaussian Process (GP) whose index set is a well-behaved, compact metric space $({\cal X},d)$ of designs. We assume that $\boldsymbol{f}$ is not known beforehand and that evaluating $\boldsymbol{f}$ at design $x$ results in a noisy observation of $\boldsymbol{f}(x)$. Since identifying the Pareto optimal designs via exhaustive search is infeasible when the cardinality of ${\cal X}$ is large, we propose an algorithm, called Adaptive $\boldsymbolε$-PAL, that exploits the smoothness of the GP-sampled function and the structure of $({\cal X},d)$ to learn fast. In essence, Adaptive $\boldsymbolε$-PAL employs a tree-based adaptive discretization technique to identify an $\boldsymbolε$-accurate Pareto set of designs in as few evaluations as possible. We provide both information-type and metric dimension-type bounds on the sample complexity of $\boldsymbolε$-accurate Pareto set identification. We also experimentally show that our algorithm outperforms other Pareto set identification methods.
Delay Violation Probability and Effective Rate of Downlink NOMA over $α$-$μ$ Fading Channels
Venue: arXiv cs.IT 2025
Year: 2025

Non-orthogonal multiple access (NOMA) is a potential candidate to further enhance the spectrum utilization efficiency in beyond fifth-generation (B5G) standards. However, there has been little attention on the quantification of the delay-limited performance of downlink NOMA systems. In this paper, we analyze the performance of a two-user downlink NOMA system over generalized α-μ fading in terms of delay violation probability (DVP) and effective rate (ER). In particular, we derive an analytical expression for an upper bound on the DVP and we derive the exact sum ER of the downlink NOMA system. We also derive analytical expressions for high and low signal-to-noise ratio (SNR) approximations to the sum ER, as well as a fundamental upper bound on the sum ER which represents the ergodic sum-rate for the downlink NOMA system. We also analyze the sum ER of a corresponding time-division-multiplexed orthogonal multiple access (OMA) system. Our results show that while NOMA consistently outperforms OMA over the practical SNR range, the relative gain becomes smaller in more severe fading conditions, and is also smaller in the presence a more strict delay quality-of-service (QoS) constraint.
Goal Kernel Planning: Linearly-Solvable Non-Markovian Policies for Logical Tasks with Goal-Conditioned Options
Venue: arXiv cs.AI 2025
Year: 2025

In the domain of hierarchical planning, compositionality, abstraction, and task transfer are crucial for designing algorithms that can efficiently solve a variety of problems with maximal representational reuse. Many real-world problems require non-Markovian policies to handle complex structured tasks with logical conditions, often leading to prohibitively large state representations; this requires efficient methods for breaking these problems down and reusing structure between tasks. To this end, we introduce a compositional framework called Linearly-Solvable Goal Kernel Dynamic Programming (LS-GKDP) to address the complexity of solving non-Markovian Boolean sub-goal tasks with ordering constraints. LS-GKDP combines the Linearly-Solvable Markov Decision Process (LMDP) formalism with the Options Framework of Reinforcement Learning. LMDPs can be efficiently solved as a principal eigenvector problem, and options are policies with termination conditions used as temporally extended actions; with LS-GKDP we expand LMDPs to control over options for logical tasks. This involves decomposing a high-dimensional problem down into a set of goal-condition options for each goal and constructing a goal kernel, which is an abstract transition kernel that jumps from an option's initial-states to its termination-states along with an update of the higher-level task-state. We show how an LMDP with a goal kernel enables the efficient optimization of meta-policies in a lower-dimensional subspace defined by the task grounding. Options can also be remapped to new problems within a super-exponential space of tasks without significant recomputation, and we identify cases where the solution is invariant to the task grounding, permitting zero-shot task transfer.
Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions
Venue: arXiv cs.LG 2025
Year: 2025

First-price auctions have very recently swept the online advertising industry, replacing second-price auctions as the predominant auction mechanism on many platforms. This shift has brought forth important challenges for a bidder: how should one bid in a first-price auction, where unlike in second-price auctions, it is no longer optimal to bid one's private value truthfully and hard to know the others' bidding behaviors? In this paper, we take an online learning angle and address the fundamental problem of learning to bid in repeated first-price auctions, where both the bidder's private valuations and other bidders' bids can be arbitrary. We develop the first minimax optimal online bidding algorithm that achieves an $\widetilde{O}(\sqrt{T})$ regret when competing with the set of all Lipschitz bidding policies, a strong oracle that contains a rich set of bidding strategies. This novel algorithm is built on the insight that the presence of a good expert can be leveraged to improve performance, as well as an original hierarchical expert-chaining structure, both of which could be of independent interest in online learning. Further, by exploiting the product structure that exists in the problem, we modify this algorithm--in its vanilla form statistically optimal but computationally infeasible--to a computationally efficient and space efficient algorithm that also retains the same $\widetilde{O}(\sqrt{T})$ minimax optimal regret guarantee. Additionally, through an impossibility result, we highlight that one is unlikely to compete this favorably with a stronger oracle (than the considered Lipschitz bidding policies). Finally, we test our algorithm on three real-world first-price auction datasets obtained from Verizon Media and demonstrate our algorithm's superior performance compared to several existing bidding algorithms.
A Neuro-inspired Theory of Joint Human-Swarm Interaction
Venue: arXiv cs.HC 2025
Year: 2025

Human-swarm interaction (HSI) is an active research challenge in the realms of swarm robotics and human-factors engineering. Here we apply a cognitive systems engineering perspective and introduce a neuro-inspired joint systems theory of HSI. The mindset defines predictions for adaptive, robust and scalable HSI dynamics and therefore has the potential to inform human-swarm loop design.
SqueezeFacePoseNet: Lightweight Face Verification Across Different Poses for Mobile Platforms
Venue: arXiv cs.CV 2025
Year: 2025

Virtual applications through mobile platforms are one of the most critical and ever-growing fields in AI, where ubiquitous and real-time person authentication has become critical after the breakthrough of all services provided via mobile devices. In this context, face verification technologies can provide reliable and robust user authentication, given the availability of cameras in these devices, as well as their widespread use in everyday applications. The rapid development of deep Convolutional Neural Networks has resulted in many accurate face verification architectures. However, their typical size (hundreds of megabytes) makes them infeasible to be incorporated in downloadable mobile applications where the entire file typically may not exceed 100 Mb. Accordingly, we address the challenge of developing a lightweight face recognition network of just a few megabytes that can operate with sufficient accuracy in comparison to much larger models. The network also should be able to operate under different poses, given the variability naturally observed in uncontrolled environments where mobile devices are typically used. In this paper, we adapt the lightweight SqueezeNet model, of just 4.4MB, to effectively provide cross-pose face recognition. After trained on the MS-Celeb-1M and VGGFace2 databases, our model achieves an EER of 1.23% on the difficult frontal vs. profile comparison, and0.54% on profile vs. profile images. Under less extreme variations involving frontal images in any of the enrolment/query images pair, EER is pushed down to<0.3%, and the FRR at FAR=0.1%to less than 1%. This makes our light model suitable for face recognition where at least acquisition of the enrolment image can be controlled. At the cost of a slight degradation in performance, we also test an even lighter model (of just 2.5MB) where regular convolutions are replaced with depth-wise separable convolutions.
From Attack to Protection: Leveraging Watermarking Attack Network for Advanced Add-on Watermarking
Venue: arXiv cs.MM 2025
Year: 2025

Multi-bit watermarking (MW) has been designed to enhance resistance against watermarking attacks, such as signal processing operations and geometric distortions. Various benchmark tools exist to assess this robustness through simulated attacks on watermarked images. However, these tools often fail to capitalize on the unique attributes of the targeted MW and typically neglect the aspect of visual quality, a critical factor in practical applications. To overcome these shortcomings, we introduce a watermarking attack network (WAN), a fully trainable watermarking benchmark tool designed to exploit vulnerabilities within MW systems and induce watermark bit inversions, significantly diminishing watermark extractability. The proposed WAN employs an architecture based on residual dense blocks, which is adept at both local and global feature learning, thereby maintaining high visual quality while obstructing the extraction of embedded information. Our empirical results demonstrate that the WAN effectively undermines various block-based MW systems while minimizing visual degradation caused by attacks. This is facilitated by our novel watermarking attack loss, which is specifically crafted to compromise these systems. The WAN functions not only as a benchmarking tool but also as an add-on watermarking (AoW) mechanism, augmenting established universal watermarking schemes by enhancing robustness or imperceptibility without requiring detailed method context and adapting to dynamic watermarking requirements. Extensive experimental results show that AoW complements the performance of the targeted MW system by independently enhancing both imperceptibility and robustness.
Existence of EFX for Two Additive Valuations
Venue: arXiv cs.GT 2025
Year: 2025

Fair division of indivisible items is a well-studied topic in Economics and Computer Science. The objective is to allocate items to agents in a fair manner, where each agent has a valuation for each subset of items. Envy-freeness is one of the most widely studied notions of fairness. Since complete envy-free allocations do not always exist when items are indivisible, several relaxations have been considered. Among them, possibly the most compelling one is envy-freeness up to any item (EFX), where no agent envies another agent after the removal of any single item from the other agent's bundle. However, despite significant efforts by many researchers for several years, it is known that a complete EFX allocation always exists only in limited cases. In this paper, we show that a complete EFX allocation always exists when each agent is of one of two given types, where agents of the same type have identical additive valuations. This is the first such existence result for non-identical valuations when there are any number of agents and items and no limit on the number of distinct values an agent can have for individual items. We give a constructive proof, in which we iteratively obtain a Pareto dominating (partial) EFX allocation from an existing partial EFX allocation.
Understanding Boolean Function Learnability on Deep Neural Networks: PAC Learning Meets Neurosymbolic Models
Venue: arXiv cs.LG 2025
Year: 2025

Computational learning theory states that many classes of boolean formulas are learnable in polynomial time. This paper addresses the understudied subject of how, in practice, such formulas can be learned by deep neural networks. Specifically, we analyze boolean formulas associated with model-sampling benchmarks, combinatorial optimization problems, and random 3-CNFs with varying degrees of constrainedness. Our experiments indicate that: (i) neural learning generalizes better than pure rule-based systems and pure symbolic approach; (ii) relatively small and shallow neural networks are very good approximators of formulas associated with combinatorial optimization problems; (iii) smaller formulas seem harder to learn, possibly due to the fewer positive (satisfying) examples available; and (iv) interestingly, underconstrained 3-CNF formulas are more challenging to learn than overconstrained ones. Such findings pave the way for a better understanding, construction, and use of interpretable neurosymbolic AI methods.
4Seasons: A Cross-Season Dataset for Multi-Weather SLAM in Autonomous Driving
Venue: arXiv cs.CV 2025
Year: 2025

We present a novel dataset covering seasonal and challenging perceptual conditions for autonomous driving. Among others, it enables research on visual odometry, global place recognition, and map-based re-localization tracking. The data was collected in different scenarios and under a wide variety of weather conditions and illuminations, including day and night. This resulted in more than 350 km of recordings in nine different environments ranging from multi-level parking garage over urban (including tunnels) to countryside and highway. We provide globally consistent reference poses with up-to centimeter accuracy obtained from the fusion of direct stereo visual-inertial odometry with RTK-GNSS. The full dataset is available at https://go.vision.in.tum.de/4seasons.