OpenRaiser/Intern-Atlas huggingface dataset:
Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
Venue: arXiv cs.DS 2026
Year: 2026

We generalize the monotone local search approach of Fomin, Gaspers, Lokshtanov and Saurabh [J. ACM 2019], by establishing a connection between parameterized approximation and exponential-time approximation algorithms for monotone subset minimization problems. In a monotone subset minimization problem the input implicitly describes a non-empty set family over a universe of size $n$ which is closed under taking supersets. The task is to find a minimum cardinality set in this family. Broadly speaking, we use approximate monotone local search to show that a parameterized $α$-approximation algorithm that runs in $c^k \cdot n^{O(1)}$ time, where $k$ is the solution size, can be used to derive an $α$-approximation randomized algorithm that runs in $d^n \cdot n^{O(1)}$ time, where $d$ is the unique value in $d \in (1,1+\frac{c-1}α)$ such that $\mathcal{D}(\frac{1}α\|\frac{d-1}{c-1})=\frac{\ln c}α$ and $\mathcal{D}(a \|b)$ is the Kullback-Leibler divergence. This running time matches that of Fomin et al. for $α=1$, and is strictly better when $α>1$, for any $c > 1$. Furthermore, we also show that this result can be derandomized at the expense of a sub-exponential multiplicative factor in the running time. We demonstrate the potential of approximate monotone local search by deriving new and faster exponential approximation algorithms for Vertex Cover, $3$-Hitting Set, Directed Feedback Vertex Set, Directed Subset Feedback Vertex Set, Directed Odd Cycle Transversal and Undirected Multicut. For instance, we get a $1.1$-approximation algorithm for Vertex Cover with running time $1.114^n \cdot n^{O(1)}$, improving upon the previously best known $1.1$-approximation running in time $1.127^n \cdot n^{O(1)}$ by Bourgeois et al. [DAM 2011].
Maximizing Nash Social Welfare in 2-Value Instances: Delineating Tractability
Venue: arXiv cs.GT 2026
Year: 2026

We study the problem of allocating a set of indivisible goods among a set of agents with \emph{2-value additive valuations}. In this setting, each good is valued either $1$ or $p/q$, for some fixed co-prime numbers $p,q\in \mathbb{N}$ such that $1\leq q < p$. Our goal is to find an allocation maximizing the \emph{Nash social welfare} (\NSW), i.e., the geometric mean of the valuations of the agents. In this work, we give a complete characterization of polynomial-time tractability of \NSW\ maximization that solely depends on the values of $q$. We start by providing a rather simple polynomial-time algorithm to find a maximum \NSW\ allocation when the valuation functions are \emph{integral}, that is, $q=1$. We then exploit more involved techniques to get an algorithm producing a maximum \NSW\ allocation for the \emph{half-integral} case, that is, $q=2$. Finally, we show it is \classNP-hard to compute an allocation with maximum \NSW\ whenever $q\geq3$.
Improved Bounds for Rectangular Monotone Min-Plus Product and Applications
Venue: arXiv cs.DS 2026
Year: 2026

In a recent breakthrough paper, Chi et al. (STOC'22) introduce an $\tilde{O}(n^{\frac{3 + ω}{2}})$ time algorithm to compute Monotone Min-Plus Product between two square matrices of dimensions $n \times n$ and entries bounded by $O(n)$. This greatly improves upon the previous $\tilde O(n^{\frac{12 + ω}{5}})$ time algorithm and as a consequence improves bounds for its applications. Several other applications involve Monotone Min-Plus Product between rectangular matrices, and even if Chi et al.'s algorithm seems applicable for the rectangular case, the generalization is not straightforward. In this paper we present a generalization of the algorithm of Chi et al. to solve Monotone Min-Plus Product for rectangular matrices with polynomial bounded values. We next use this faster algorithm to improve running times for the following applications of Rectangular Monotone Min-Plus Product: $M$-bounded Single Source Replacement Path, Batch Range Mode, $k$-Dyck Edit Distance and 2-approximation of All Pairs Shortest Path. We also improve the running time for Unweighted Tree Edit Distance using the algorithm by Chi et al.
Category Theory for Programming
Venue: arXiv cs.PL 2026
Year: 2026

In these lecture notes, we give a brief introduction to some elements of category theory. The choice of topics is guided by applications to functional programming. Firstly, we study initial algebras, which provide a mathematical characterization of datatypes and recursive functions on them. Secondly, we study monads, which give a mathematical framework for effects in functional languages. The notes include many problems and solutions.
Graphon Mean-Field Control for Cooperative Multi-Agent Reinforcement Learning
Venue: arXiv cs.MA 2026
Year: 2026

The marriage between mean-field theory and reinforcement learning has shown a great capacity to solve large-scale control problems with homogeneous agents. To break the homogeneity restriction of mean-field theory, a recent interest is to introduce graphon theory to the mean-field paradigm. In this paper, we propose a graphon mean-field control (GMFC) framework to approximate cooperative multi-agent reinforcement learning (MARL) with nonuniform interactions and show that the approximate order is of $\mathcal{O}(\frac{1}{\sqrt{N}})$, with $N$ the number of agents. By discretizing the graphon index of GMFC, we further introduce a smaller class of GMFC called block GMFC, which is shown to well approximate cooperative MARL. Our empirical studies on several examples demonstrate that our GMFC approach is comparable with the state-of-art MARL algorithms while enjoying better scalability.
Auxilio and Beyond: Comparative Evaluation, Usability, and Design Guidelines for Head Movement-based Assistive Mouse Controllers
Venue: arXiv cs.HC 2026
Year: 2026

Upper limb disability due to neurological disorders or other factors restricts computer interaction for affected individuals using a generic optical mouse. This work reports the findings of a comparative evaluation of Auxilio, a sensor-based wireless head-mounted Assistive Mouse Controller (AMC), that facilitates computer interaction for such individuals. Combining commercially available, low-cost motion and infrared sensors, Auxilio utilizes head movements and cheek muscle twitches for mouse control. Its performance in pointing tasks with subjects without motor impairments has been juxtaposed against a commercially available and patented vision-based head-tracking AMC developed for similar stakeholders. Furthermore, our study evaluates the usability of Auxilio using the System Usability Scale, supplemented by a qualitative analysis of participant interview transcripts to identify the strengths and weaknesses of both AMCs. Experimental results demonstrate the feasibility and effectiveness of Auxilio, and we summarize our key findings into design guidelines for the development of similar future AMCs.
Teeth3DS+: An Extended Benchmark for Intraoral 3D Scans Analysis
Venue: arXiv cs.CV 2026
Year: 2026

Intraoral 3D scanning is now widely adopted in modern dentistry and plays a central role in supporting key tasks such as tooth segmentation, detection, labeling, and dental landmark identification. Accurate analysis of these scans is essential for orthodontic and restorative treatment planning, as it enables automated workflows and minimizes the need for manual intervention. However, the development of robust learning-based solutions remains challenging due to the limited availability of high-quality public datasets and standardized benchmarks. This article presents Teeth3DS+, an extended public benchmark dedicated to intraoral 3D scan analysis. Developed in the context of the MICCAI 3DTeethSeg and 3DTeethLand challenges, Teeth3DS+ supports multiple fundamental tasks, including tooth detection, segmentation, labeling, 3D modeling, and dental landmark identification. The dataset consists of rigorously curated intraoral scans acquired using state-of-the-art scanners and validated by experienced orthodontists and dental surgeons. In addition to the data, Teeth3DS+ provides standardized data splits and evaluation protocols to enable fair and reproducible comparison of methods, with the goal of fostering progress in learning-based analysis of 3D dental scans. Detailed instructions for accessing the dataset are available at https://crns-smartvision.github.io/teeth3ds
Efficient Bayesian Updates for Deep Active Learning via Laplace Approximations
Venue: arXiv cs.LG 2026
Year: 2026

Deep active learning (AL) selects batches of instances for annotation to avoid retraining deep neural networks (DNNs) after each new label. Employing a naive top-$b$ selection can result in a batch of redundant (similar) instances. To address this, various AL strategies employ clustering techniques that ensure diversity within a batch. We approach this issue by substituting the costly retraining with an efficient Bayesian update. Our proposed update represents a second-order optimization step using the Gaussian posterior from a last-layer Laplace approximation. Thereby, we achieve low computational complexity by computing the inverse Hessian in closed form. We demonstrate that in typical AL settings, our update closely approximates retraining while being considerably faster. Leveraging our update, we introduce a new framework for batch selection through sequential construction, updating the DNN after each label acquisition. Furthermore, we incorporate our update into a look-ahead selection strategy as a feasible upper baseline approximating optimal batch selection. Our results highlight the potential of efficient updates to advance deep AL research.
Towards a Higher-Order Mathematical Operational Semantics
Venue: arXiv cs.LO 2026
Year: 2026

Compositionality proofs in higher-order languages are notoriously involved, and general semantic frameworks guaranteeing compositionality are hard to come by. In particular, Turi and Plotkin's bialgebraic abstract GSOS framework, which has been successfully applied to obtain off-the-shelf compositionality results for first-order languages, so far does not apply to higher-order languages. In the present work, we develop a theory of abstract GSOS specifications for higher-order languages, in effect transferring the core principles of Turi and Plotkin's framework to a higher-order setting. In our theory, the operational semantics of higher-order languages is represented by certain dinatural transformations that we term pointed higher-order GSOS laws. We give a general compositionality result that applies to all systems specified in this way and discuss how compositionality of the SKI calculus and the $λ$-calculus w.r.t. a strong variant of Abramsky's applicative bisimilarity are obtained as instances.
Visual Adversarial Attacks and Defenses in the Physical World: A Survey
Venue: arXiv cs.CV 2026
Year: 2026

Although Deep Neural Networks (DNNs) have been widely applied in various real-world scenarios, they remain vulnerable to adversarial examples. Adversarial attacks in computer vision can be categorized into digital attacks and physical attacks based on their different forms. Compared to digital attacks, which generate perturbations in digital pixels, physical attacks are more practical in real-world settings. Due to the serious security risks posed by physically adversarial examples, many studies have been conducted to evaluate the physically adversarial robustness of DNNs in recent years. In this paper, we provide a comprehensive survey of current physically adversarial attacks and defenses in computer vision. We establish a taxonomy by organizing physical attacks according to attack tasks, attack forms, and attack methods. This approach offers readers a systematic understanding of the topic from multiple perspectives. For physical defenses, we categorize them into pre-processing, in-processing, and post-processing for DNN models to ensure comprehensive coverage of adversarial defenses. Based on this survey, we discuss the challenges facing this research field and provide an outlook on future directions.
Effects of Backtracking on PageRank
Venue: arXiv cs.SI 2026
Year: 2026

In this paper, we consider three variations on standard PageRank: Non-backtracking PageRank, $μ$-PageRank, and $\infty$-PageRank, all of which alter the standard formula by adjusting the likelihood of backtracking in the algorithm's random walk. We show that in the case of regular and bipartite biregular graphs, standard PageRank and its variants are equivalent. We also compare each centrality measure and investigate their clustering capabilities.
Dynamic Kernel Graph Sparsifiers
Venue: arXiv cs.DS 2026
Year: 2026

A geometric graph associated with a set of points $P= \{x_1, x_2, \cdots, x_n \} \subset \mathbb{R}^d$ and a fixed kernel function $\mathsf{K}:\mathbb{R}^d\times \mathbb{R}^d\to\mathbb{R}_{\geq 0}$ is a complete graph on $P$ such that the weight of edge $(x_i, x_j)$ is $\mathsf{K}(x_i, x_j)$. We present a fully-dynamic data structure that maintains a spectral sparsifier of a geometric graph under updates that change the locations of points in $P$ one at a time. The update time of our data structure is $n^{o(1)}$ with high probability, and the initialization time is $n^{1+o(1)}$. Under certain assumption, our data structure can be made robust against adaptive adversaries, which makes our sparsifier applicable in iterative optimization algorithms. We further show that the Laplacian matrices corresponding to geometric graphs admit a randomized sketch for maintaining matrix-vector multiplication and projection in $n^{o(1)}$ time, under sparse updates to the query vectors, or under modification of points in $P$.
PC-SNN: Predictive Coding-based Local Hebbian Plasticity Learning in Spiking Neural Networks
Venue: arXiv cs.NE 2026
Year: 2026

Spiking Neural Networks (SNNs), regarded as the third generation of neural networks, emulate the brain's information processing with unparalleled biological plausibility compared to traditional neural networks. However, their non-linear, event-driven dynamics pose significant challenges for training, and existing methods often deviate from neuroscientific principles of cortical learning. Drawing inspiration from predictive coding theory-a leading model of brain information processing-we propose PC-SNN, a novel learning framework that integrates predictive coding with SNNs to enable biologically plausible, local Hebbian plasticity without reliance on backpropagation. Unlike conventional SNN training approaches, PC-SNN leverages only local computations, aligning with the brain's distributed processing and overcoming the biological implausibility of global error propagation. Our classification model achieves competitive performance on the benchmark datasets, including Caltech Face/Motorbike, MNIST, and CIFAR10, surpassing state-of-the-art multi-layer SNNs. Furthermore, our predictive coding-based regression model outperforms backpropagation-based methods while adhering to local plasticity constraints, offering a scalable and biologically grounded alternative for SNN training. PC-SNN drives progress in neuromorphic computing through validating the adaptability of bio-inspired algorithms within spiking neural architectures, but also unveils novel understandings of neurocognitive learning processes, presenting a conceptual framework distinguished by its theoretical originality and functional efficacy.
FC-PINO: High Precision Physics-Informed Neural Operators via Fourier Continuation
Venue: arXiv cs.LG 2026
Year: 2026

The physics-informed neural operator (PINO) is a machine learning paradigm that has demonstrated promising results for learning solutions to partial differential equations (PDEs). It leverages the Fourier Neural Operator to learn solution operators in function spaces and leverages physics losses during training to penalize deviations from known physics laws. Spectral differentiation provides an efficient way to compute derivatives for the physics losses, but it inherently assumes periodicity. When applied to non-periodic functions, this assumption can lead to significant errors, including Gibbs phenomena near domain boundaries which degrade the accuracy of both function representations and derivative computations. To overcome this limitation, we introduce the FC-PINO (Fourier-Continuation-based Physics-Informed Neural Operator) architecture which extends the accuracy and efficiency of PINO and spectral differentiation to non-periodic and non-smooth PDEs. In FC-PINO, we propose integrating Fourier continuation into the PINO framework, and test two different continuation approaches: FC-Legendre and FC-Gram. By transforming non-periodic signals into periodic functions on extended domains in a well-conditioned manner, Fourier continuation enables fast and accurate derivative computations. This approach avoids the discretization sensitivity of finite differences and the memory overhead of automatic differentiation. We demonstrate that standard PINO fails (without padding) or struggles (even with padding) to solve non-periodic and non-smooth PDEs with high precision, across challenging benchmarks. In contrast, the proposed FC-PINO provides accurate, robust, and scalable solutions, substantially outperforming PINO alternatives, and demonstrating that Fourier continuation is critical for extending PINO to a wider range of PDE problems when high-precision solutions are needed.
Perfectly Covert Communication Assisted by an Intelligent Reflecting Surface
Venue: arXiv cs.IT 2026
Year: 2026

This work investigates the fundamental limits of \emph{perfect} covert communication assisted by an Intelligent Reflecting Surface (IRS). We first characterize the necessary and sufficient conditions for perfect covertness, defined as zero received energy at the warden (Willie), and provide a complete analytical solution for the two-element case. For general array sizes, we prove that the probability of achieving perfect covertness converges to $1$ almost surely as the number of reflecting elements increases. To enable practical implementation, we formulate the phase design problem as an interference-minimization problem. A key contribution is proving that the objective satisfies the \emph{strict-saddle} property. Consequently, we establish that gradient descent with random initialization converges almost surely to a global minimizer (zero interference), thereby identifying a feasible, perfectly covert configuration whenever one exists. Finally, to address physical limitations, such as imperfect CSI, we introduce the notion of \emph{operational perfect covertness}. In this setting, we assume a bounded CSI error model and an analogous constraint on Willie. We derive robust conditions guaranteeing that the warden's detection capability remains effectively nullified even when exact signal cancellation is infeasible.
Distributed Sparse Linear Regression under Communication Constraints
Venue: arXiv cs.LG 2026
Year: 2026

In multiple domains, statistical tasks are performed in distributed settings, with data split among several end machines that are connected to a fusion center. In various applications, the end machines have limited bandwidth and power, and thus a tight communication budget. In this work we focus on distributed learning of a sparse linear regression model, under severe communication constraints. We propose several two round distributed schemes, whose communication per machine is sublinear in the data dimension. In our schemes, individual machines compute debiased lasso estimators, but send to the fusion center only very few values. On the theoretical front, we analyze one of these schemes and prove that with high probability it achieves exact support recovery at low signal to noise ratios, where individual machines fail to recover the support. We show in simulations that our scheme works as well as, and in some cases better, than more communication intensive approaches.
Quantitative Verification with Neural Networks
Venue: arXiv cs.LO 2026
Year: 2026

We present a data-driven approach to the quantitative verification of probabilistic programs and stochastic dynamical models. Our approach leverages neural networks to compute tight and sound bounds for the probability that a stochastic process hits a target condition within finite time. This problem subsumes a variety of quantitative verification questions, from the reachability and safety analysis of discrete-time stochastic dynamical models, to the study of assertion-violation and termination analysis of probabilistic programs. We rely on neural networks to represent supermartingale certificates that yield such probability bounds, which we compute using a counterexample-guided inductive synthesis loop: we train the neural certificate while tightening the probability bound over samples of the state space using stochastic optimisation, and then we formally check the certificate's validity over every possible state using satisfiability modulo theories; if we receive a counterexample, we add it to our set of samples and repeat the loop until validity is confirmed. We demonstrate on a diverse set of benchmarks that, thanks to the expressive power of neural networks, our method yields smaller or comparable probability bounds than existing symbolic methods in all cases, and that our approach succeeds on models that are entirely beyond the reach of such alternative techniques.
The Leafed Induced Subtree in chordal and bounded treewidth graphs
Venue: arXiv cs.DS 2026
Year: 2026

In the Fully Leafed Induced Subtrees, one is given a graph $G$ and two integers $a$ and $b$ and the question is to find an induced subtree of $G$ with $a$ vertices and at least $b$ leaves. This problem is known to be NP-complete even when the input graph is $4$-regular. Polynomial algorithms are known when the input graph is restricted to be a tree or series-parallel. In this paper we generalize these results by providing an FPT algorithm parameterized by treewidth. We also provide a polynomial algorithm when the input graph is restricted to be a chordal graph.
A Robust Multi-Item Auction Design with Statistical Learning
Venue: arXiv cs.GT 2026
Year: 2026

We propose a novel statistical learning method for multi-item auctions that incorporates credible intervals. Our approach employs nonparametric density estimation to estimate credible intervals for bidder types based on historical data. We introduce two new strategies that leverage these credible intervals to reduce the time cost of implementing auctions. The first strategy screens potential winners' value regions within the credible intervals, while the second strategy simplifies the type distribution when the length of the interval is below a threshold value. These strategies are easy to implement and ensure fairness, dominant-strategy incentive compatibility, and dominant-strategy individual rationality with a high probability, while simultaneously reducing implementation costs. We demonstrate the effectiveness of our strategies using the Vickrey-Clarke-Groves mechanism and evaluate their performance through simulation experiments. Our results show that the proposed strategies consistently outperform alternative methods, achieving both revenue maximization and cost reduction objectives.
The Temporal Logic Synthesis Format TLSF v1.2
Venue: arXiv cs.LO 2026
Year: 2026

We present an extension of the Temporal Logic Synthesis Format (TLSF). TLSF builds on standard LTL, but additionally supports high-level constructs, such as sets and functions, as well as parameters that allow a specification to define a whole a family of problems. Our extension introduces operators and a new semantics option for LTLf, i.e., LTL on finite executions.