OpenRaiser/Intern-Atlas huggingface dataset:
Matching Queues, Flexibility and Incentives
Venue: arXiv cs.GT 2026
Year: 2026

Problem definition: In many matching markets, some agents are fully flexible, while others only accept a subset of jobs. For example, ridesharing drivers can specify on the platform the destinations they are willing to accept. Conventional wisdom suggests reserving flexible agents, but this can backfire: anticipating higher matching chances, agents may misreport as specialized, reducing overall matches. We ask how platforms can design simple matching policies that remain effective when agents act strategically. Methodology/results: We model job allocation as a bipartite matching queueing system and analyze equilibrium throughput performance under different policies when agents choose which queue to join. We show that flexibility reservation is optimal under full information but can perform poorly with private information, sometimes substantially worse than random assignment. To address this, we propose a new policy -- flexibility reservation with fallback -- that guarantees robust performance across settings, without requiring precise knowledge of system parameters or agent utility functions. Managerial implications: Our results underscore the importance of accounting for strategic reporting in the design of matching policies: the proposed fallback policy both preserves flexibility and exploits latent flexibility when explicitly flexible agents are exhausted. Its simplicity and parameter-free nature also make it practical to implement in platforms such as ridesharing and affordable housing allocation.
Source Coding with Free Bits and the Multi-Way Number Partitioning Problem
Venue: arXiv cs.DS 2026
Year: 2026

We introduce a new variant of variable-length source coding for sending a source over two parallel channels, one of which is costly and the other free. We give a complete solution to this problem. Next, we relate the problem to the number partitioning problem, which is the task of dividing a given list of numbers into a pre-specified number of subsets such that the sum of the numbers in each subset is as nearly equal as possible. We introduce two new objective functions for this problem and show that an adapted version of the Huffman coding algorithm (with a runtime of $\mathcal{O}(n \log n)$ for input size $n$) produces the optimal solution for one objective function, and a nearly optimal solution for the other objective function.
Pizza Sharing is PPA-hard
Venue: arXiv cs.CC 2026
Year: 2026

We study the computational complexity of finding a solution for the straight-cut and square-cut pizza sharing problems. We show that computing an $\varepsilon$-approximate solution is PPA-complete for both problems, while finding an exact solution for the square-cut problem is FIXP-hard. Our PPA-hardness results apply for any $\varepsilon < 1/5$, even when all mass distributions consist of non-overlapping axis-aligned rectangles or when they are point sets, and our FIXP-hardness result applies even when all mass distributions are unions of squares and right-angled triangles. We also prove that the decision variants of both approximate problems are NP-complete, while the decision variant for the exact version of square-cut pizza sharing is $\exists\mathbb{R}$-complete.
Deep Ensembling with No Overhead for either Training or Testing: The All-Round Blessings of Dynamic Sparsity
Venue: arXiv cs.LG 2026
Year: 2026

The success of deep ensembles on improving predictive performance, uncertainty estimation, and out-of-distribution robustness has been extensively studied in the machine learning literature. Albeit the promising results, naively training multiple deep neural networks and combining their predictions at inference leads to prohibitive computational costs and memory requirements. Recently proposed efficient ensemble approaches reach the performance of the traditional deep ensembles with significantly lower costs. However, the training resources required by these approaches are still at least the same as training a single dense model. In this work, we draw a unique connection between sparse neural network training and deep ensembles, yielding a novel efficient ensemble learning framework called FreeTickets. Instead of training multiple dense networks and averaging them, we directly train sparse subnetworks from scratch and extract diverse yet accurate subnetworks during this efficient, sparse-to-sparse training. Our framework, FreeTickets, is defined as the ensemble of these relatively cheap sparse subnetworks. Despite being an ensemble method, FreeTickets has even fewer parameters and training FLOPs than a single dense model. This seemingly counter-intuitive outcome is due to the ultra training/inference efficiency of dynamic sparse training. FreeTickets surpasses the dense baseline in all the following criteria: prediction accuracy, uncertainty estimation, out-of-distribution (OoD) robustness, as well as efficiency for both training and inference. Impressively, FreeTickets outperforms the naive deep ensemble with ResNet50 on ImageNet using around only 1/5 of the training FLOPs required by the latter. We have released our source code at https://github.com/VITA-Group/FreeTickets.
Worst-case optimal adaptive alphabetic prefix-free coding
Venue: arXiv cs.DS 2026
Year: 2026

We give the first algorithm for adaptive alphabetic prefix-free coding that is worst-case optimal in terms of time and compression when $σ\in o \left( \frac{n^{1 / 2}}{\log n} \right)$, where $σ$ is the size of the alphabet and $n$ is the length of the input.
On complexity of substructure connectivity and restricted connectivity of graphs
Venue: arXiv cs.CC 2026
Year: 2026

The connectivity of a graph is an important parameter to evaluate its reliability. $k$-restricted connectivity (resp. $R^h$-restricted connectivity) of a graph $G$ is the minimum cardinality of a set $S$ of vertices in $G$, if exists, whose deletion disconnects $G$ and leaves each component of $G-S$ with more than $k$ vertices (resp. $δ(G-S)\geq h$). In contrast, structure (substructure) connectivity of $G$ is defined as the minimum number of vertex-disjoint subgraphs whose deletion disconnects $G$. As generalizations of the concept of connectivity, structure (substructure) connectivity, restricted connectivity and $R^h$-restricted connectivity have been extensively studied from the combinatorial point of view. Very little is known about the computational complexity of these variants, except for the recently established NP-completeness of $k$-restricted edge-connectivity. In this paper, we prove that the problems of determining structure, substructure, restricted, and $R^h$-restricted connectivity are all NP-complete.
GFlowNet Foundations
Venue: arXiv cs.LG 2026
Year: 2026

Generative Flow Networks (GFlowNets) have been introduced as a method to sample a diverse set of candidates in an active learning context, with a training objective that makes them approximately sample in proportion to a given reward function. In this paper, we show a number of additional theoretical properties of GFlowNets. They can be used to estimate joint probability distributions and the corresponding marginal distributions where some variables are unspecified and, of particular interest, can represent distributions over composite objects like sets and graphs. GFlowNets amortize the work typically done by computationally expensive MCMC methods in a single but trained generative pass. They could also be used to estimate partition functions and free energies, conditional probabilities of supersets (supergraphs) given a subset (subgraph), as well as marginal distributions over all supersets (supergraphs) of a given set (graph). We introduce variations enabling the estimation of entropy and mutual information, sampling from a Pareto frontier, connections to reward-maximizing policies, and extensions to stochastic environments, continuous actions and modular energy functions.
Simplicial approximation to CW complexes with spherical Delaunay triangulations
Venue: arXiv cs.CG 2026
Year: 2026

Simplicial approximation provides a framework for constructing simplicial complexes that are homotopy equivalent to a given manifold, provided a CW structure is explicitly known. However, its conventional implementation quickly becomes intractable on a computer: barycentric subdivision produces poorly shaped simplices, and the star condition introduces many vertices. To address these limitations, this article develops a subdivision scheme based on spherical Delaunay triangulations, which attains better refinement properties than barycentric subdivisions. Moreover, the star condition is reframed as two independent problems, one geometric and the other combinatorial, respectively tackled in the language of locally equiconnected spaces and the list homomorphism problem, allowing an exponential reduction in the number of vertices. Via a prototype implementation, we obtain simplicial complexes homotopy equivalent to Grassmannians and Stiefel manifolds up to dimension 5.
Efficiency of ANS Entropy Encoders
Venue: arXiv cs.IT 2026
Year: 2026

Asymmetric Numeral Systems (ANS) is a class of entropy encoders that had an immense impact on the data compression, substituting arithmetic and Huffman coding. It was studied by different authors but the precise asymptotics of its redundancy (in relation to the entropy) was not completely understood. We obtain optimal bounds for the redundancy of the tabled ANS (tANS), the most popular ANS variant. Given a sequence $a_1,a_2,\ldots,a_n$ of symbols from an alphabet $\{0,1,\ldots,σ-1\}$ such that each symbol $a$ occurs in it $f_a$ times and $n=2^r$, the tANS encoder using Duda's ``precise initialization'' to fill tANS tables transforms this sequence into a bit string of the following length (the frequencies are not included in the encoding): $\sum\limits_{a\in[0..σ)}f_a\cdot\log\frac{n}{f_a}+O(σ+r)$, where $O(σ+r)$ can be bounded by $σ\log e+r$. The $r$-bit term is an artifact indispensable to ANS; the rest incurs a redundancy of $O(\fracσ{n})$ bits per symbol. We complement this by examples showing that an $Ω(σ+r)$ redundancy is necessary. We argue that similar examples exist for most adequate initialization methods for tANS. Thus, we refute Duda's conjecture that the redundancy is $O(\fracσ{n^2})$ bits per symbol. We also propose a variant of the range ANS (rANS), called rANS with fixed accuracy, parameterized by $k\ge 1$ that in certain conditions might be faster than the standard rANS because it avoids slow explicit division operations. We bound the redundancy for our rANS variant by $\frac{n}{2^k-1}\log e+r+k$.
Fast Reconfiguration for Programmable Matter
Venue: arXiv cs.DC 2026
Year: 2026

The concept of programmable matter envisions a very large number of tiny and simple robot particles forming a smart material. Even though the particles are restricted to local communication, local movement, and simple computation, their actions can nevertheless result in the global change of the material's physical properties and geometry. A fundamental algorithmic task for programmable matter is to achieve global shape reconfiguration by specifying local behavior of the particles. In this paper we describe a new approach for shape reconfiguration in the \emph{amoebot} model. The amoebot model is a distributed model which significantly restricts memory, computing, and communication capacity of the individual particles. Thus the challenge lies in coordinating the actions of particles to produce the desired behavior of the global system. Our reconfiguration algorithm is the first algorithm that does not use a canonical intermediate configuration when transforming between arbitrary shapes. We introduce new geometric primitives for amoebots and show how to reconfigure particle systems, using these primitives, in a linear number of activation rounds in the worst case. In practice, our method exploits the geometry of the symmetric difference between input and output shape: it minimizes unnecessary disassembly and reassembly of the particle system when the symmetric difference between the initial and the target shapes is small. Furthermore, our reconfiguration algorithm moves the particles over as many parallel shortest paths as the problem instance allows.
A proof of P != NP (New symmetric encryption algorithm against any linear attacks and differential attacks)
Venue: arXiv cs.CC 2026
Year: 2026

P vs NP problem is the most important unresolved problem in the field of computational complexity. Its impact has penetrated into all aspects of algorithm design, especially in the field of cryptography. The security of cryptographic algorithms based on short keys depends on whether P is equal to NP. In fact, the security requirements for cryptographic keys are much stricter than those for P$\neq$NP, the security of the key must ensure not only a sufficiently high computational complexity to crack it, but also consider the security of each bit of the key, while fully avoiding the effectiveness of various attack methods. In this paper, we innovatively propose a new encoding mechanism and develop a novel block symmetric encryption algorithm, whose encryption and decryption can be completed in linear time. For the attacker, in the case where only the plaintext-ciphertext correspondence is known, the problem of cracking the key is equivalent to solving a system of equations which contains at least one free variable that cannot be eliminated, and the number of possible values for each variable is exponentially to the length of the key. To solve this system of equations, it is necessary to exhaustively search for at least one variable, thus proving that the computational complexity of cracking the key is exponential. So the decryption is a one-way function, and according to "the existence of one-way function means P$\neq$NP", thus solving the unsolved problem of P vs NP. In addition, this paper delves into the underlying mathematical laws of this new encoding mechanism, and develops a right multiplication operation to binary. Based on this right multiplication operation, we further constructed a nonlinear operation and designed another block symmetric encryption algorithm that is resistant to all forms of linear and differential attacks.
Real-Time BDI Agents: a model and its implementation
Venue: arXiv cs.MA 2026
Year: 2026

The BDI model proved to be effective for developing applications requiring high-levels of autonomy and to deal with the complexity and unpredictability of real-world scenarios. The model, however, has significant limitations in reacting and handling contingencies within the given real-time constraints. Without an explicit representation of time, existing real-time BDI implementations overlook the temporal implications during the agent's decision process that may result in delays or unresponsiveness of the system when it gets overloaded. In this paper, we redefine the BDI agent control loop inspired by well established algorithms for real-time systems to ensure a proper reaction of agents and their effective application in typical real-time domains. Our model proposes an effective real-time management of goals, plans, and actions with respect to time constraints and resources availability. We propose an implementation of the model for a resource-collection video-game and we validate the approach against a set of significant scenarios.
Reinforced Inverse Scattering
Venue: arXiv cs.LG 2026
Year: 2026

Inverse wave scattering aims at determining the properties of an object using data on how the object scatters incoming waves. In order to collect information, sensors are put in different locations to send and receive waves from each other. The choice of sensor positions and incident wave frequencies determines the reconstruction quality of scatterer properties. This paper introduces reinforcement learning to develop precision imaging that decides sensor positions and wave frequencies adaptive to different scatterers in an intelligent way, thus obtaining a significant improvement in reconstruction quality with limited imaging resources. Extensive numerical results will be provided to demonstrate the superiority of the proposed method over existing methods.
Density-Based Algorithms for Corruption-Robust Contextual Search and Convex Optimization
Venue: arXiv cs.LG 2026
Year: 2026

We study the problem of contextual search, a generalization of binary search in higher dimensions, in the adversarial noise model. Let $d$ be the dimension of the problem, $T$ be the time horizon and $C$ be the total amount of adversarial noise in the system. We focus on the $ε$-ball and the symmetric loss. For the $ε$-ball loss, we give a tight regret bound of $O(C + d \log(1/ε))$ improving over the $O(d^3 \log(1/ε) \log^2(T) + C \log(T) \log(1/ε))$ bound of Krishnamurthy et al (Operations Research '23). For the symmetric loss, we give an efficient algorithm with regret $O(C+d \log T)$. To tackle the symmetric loss case, we study the more general setting of Corruption-Robust Convex Optimization with Subgradient feedback, which is of independent interest. Our techniques are a significant departure from prior approaches. Specifically, we keep track of density functions over the candidate target vectors instead of a knowledge set consisting of the candidate target vectors consistent with the feedback obtained.
Mean-based incomplete pairwise comparisons method with the reference values
Venue: arXiv cs.AI 2026
Year: 2026

In this article, we propose two quantitative methods for calculating weight vectors for incomplete pairwise comparison matrices using reference values. Both procedures are extensions of arithmetic and geometric heuristic estimation (HRE) methods. The proposed solutions allow flexible selection of the number of reference alternatives and the range of comparisons, from the acceptable minimum to a complete set. In this paper, we prove that the newly introduced geometric HRE method for incomplete data is optimal. For this method, we also prove the existence of a feasible solution. In the paper, we also provide sufficient conditions for the existence of a solution for the second arithmetic variant of the HRE method. We illustrate the presented methods with numerical examples.
OrderedCuts: A new approach for computing Gomory-Hu tree
Venue: arXiv cs.DS 2026
Year: 2026

The Gomory-Hu tree, or a cut tree, is a classic data structure that stores minimum $s$-$t$ cuts of an undirected weighted graph for all pairs of nodes $(s,t)$. We propose a new approach for computing the cut tree based on a reduction to the problem that we call {\tt OrderedCuts}. Given a sequence of nodes $s,v_1,\ldots,v_\ell$, its goal is to compute minimum $\{s,v_1,\ldots,v_{i-1}\}$-$v_i$ cuts for all $i\in[\ell]$. We show that the cut tree can be computed by $\tilde O(1)$ calls to {\tt OrderedCuts}. We also establish new results for {\tt OrderedCuts} that may be of independent interest. First, we prove that all $\ell$ cuts can be stored compactly with $O(n)$ space in a data structure that we call an {\em {\tt OC} tree}. Second, we prove results that allow divide-and-conquer algorithms for computing OC tree. Finally, we describe a practical implementation based on {\tt OrderedCuts}, and compare it experimentally with two existing implementations of the classical Gomory-Hu tree algorithm as well as with our implementations. The results suggest that the {\tt OrderedCuts}-based approach is the most robust: on many family of problems it outperforms other algorithms by 1-2 orders of magnitude, and is never slower by more than a small factor. Our implementation is publicly available at https://pub.ist.ac.at/~vnk/software.html.
Reproduction and Replication of an Adversarial Stylometry Experiment
Venue: arXiv cs.CL 2026
Year: 2026

Maintaining anonymity in natural language communication remains a challenging task. Even when the number of candidate authors is large, standard authorship attribution techniques that analyze writing style predict the original author with uncomfortably high accuracy. Adversarial stylometry provides a defense against authorship attribution, helping users avoid unwanted deanonymization. This paper reproduces and replicates experiments from a seminal study of defenses against authorship attribution (Brennan et al., 2012). After reproducing the experiment using the original data, we then replicate the experiment by repeating the online field experiment using the procedures described in the original paper. Although we reach the same conclusion as the original paper, our results suggest that the defenses studied may be overstated in their effectiveness. This is largely due to the absence of a control group in the original study. In our replication, we find evidence suggesting that an entirely automatic method, round-trip translation, warrants re-examination because it appears to reduce the effectiveness of established authorship attribution methods.
Bounded Model Checking for Unbounded Client Server Systems
Venue: arXiv cs.LO 2026
Year: 2026

Bounded model checking (BMC) is an efficient formal verification technique which allows for desired properties of a software system to be checked on bounded runs of an abstract model of the system. The properties are frequently described in some temporal logic and the system is modeled as a state transition system. In this paper we propose a novel counting logic, $\mathcal{L}_{C}$, to describe the temporal properties of client-server systems with an unbounded number of clients. We also propose two dimensional bounded model checking ($2D$-BMC) strategy that uses two distinguishable parameters, one for execution steps and another for the number of tokens in the net representing a client-server system, and these two evolve separately, which is different from the standard BMC techniques in the Petri Nets formalism. This $2D$-BMC strategy is implemented in a tool called DCModelChecker which leverages the $2D$-BMC technique with a state-of-the-art satisfiability modulo theories (SMT) solver Z3. The system is given as a Petri Net and properties specified using $\mathcal{L}_{C}$ are encoded into formulas that are checked by the solver. Our tool can also work on industrial benchmarks from the Model Checking Contest (MCC). We report on these experiments to illustrate the applicability of the $2D$-BMC strategy.
Development of a Deep Learning-Driven Control Framework for Exoskeleton Robots
Venue: arXiv cs.RO 2026
Year: 2026

The purpose of this study is to develop a computationally efficient deep learning based control framework for high degree of freedom exoskeleton robots to address the real time computational limitations associated with conventional model based control. A parallel structured deep neural network was designed for a seven degree of freedom human lower extremity exoskeleton robot. The network consists of four layers with 49 densely connected neurons and was trained using physics based data generated from the analytical dynamic model. During real time implementation, the trained neural network predicts joint torque commands required for trajectory tracking, while a proportional derivative controller compensates for residual prediction errors. Stability of the proposed control scheme was analytically established, and robustness to parameter variations was evaluated using analysis of variance. Comparative simulations were conducted against computed torque, model reference computed torque, sliding mode, adaptive, and linear quadratic controllers under identical robot dynamics. Results demonstrate accurate trajectory tracking with torque profiles comparable to conventional nonlinear controllers while reducing computational burden. These findings suggest that the proposed deep learning based hybrid controller offers an efficient and robust alternative for controlling multi degree of freedom exoskeleton robots.