OpenRaiser/Intern-Atlas huggingface dataset:
On Single Server Private Information Retrieval with Private Coded Side Information
Venue: arXiv cs.IT 2025
Year: 2025

Motivated by an open problem and a conjecture, this work studies the problem of single server private information retrieval with private coded side information (PIR-PCSI) that was recently introduced by Heidarzadeh et al. The goal of PIR-PCSI is to allow a user to efficiently retrieve a desired message $\bm{W}_{\bmθ}$, which is one of $K$ independent messages that are stored at a server, while utilizing private side information of a linear combination of a uniformly chosen size-$M$ subset ($\bm{\mathcal{S}}\subset[K]$) of messages. The settings PIR-PCSI-I and PIR-PCSI-II correspond to the constraints that $\bmθ$ is generated uniformly from $[K]\setminus\bm{\mathcal{S}}$, and $\bm{\mathcal{S}}$, respectively. In each case, $(\bmθ,\bm{\mathcal{S}})$ must be kept private from the server. The capacity is defined as the supremum over message and field sizes, of achievable rates (number of bits of desired message retrieved per bit of download) and is characterized by Heidarzadeh et al. for PIR-PCSI-I in general, and for PIR-PCSI-II for $M>(K+1)/2$ as $(K-M+1)^{-1}$. For $2\leq M\leq (K+1)/2$ the capacity of PIR-PCSI-II remains open, and it is conjectured that even in this case the capacity is $(K-M+1)^{-1}$. We show the capacity of PIR-PCSI-II is equal to $2/K$ for $2 \leq M \leq \frac{K+1}{2}$, which is strictly larger than the conjectured value, and does not depend on $M$ within this parameter regime. Remarkably, half the side-information is found to be redundant. We also characterize the infimum capacity (infimum over fields instead of supremum), and the capacity with private coefficients. The results are generalized to PIR-PCSI-I ($θ\in[K]\setminus\mathcal{S}$) and PIR-PCSI ($θ\in[K]$) settings.
Language Inclusion for Boundedly-Ambiguous Vector Addition Systems is Decidable
Venue: arXiv cs.FL 2025
Year: 2025

We consider the problems of language inclusion and language equivalence for Vector Addition Systems with States (VASS) with the acceptance condition defined by the set of accepting states (and more generally by some upward-closed conditions). In general, the problem of language equivalence is undecidable even for one-dimensional VASS, thus to get decidability we investigate restricted subclasses. On the one hand, we show that the problem of language inclusion of a VASS in k-ambiguous VASS (for any natural k) is decidable and even in Ackermann. On the other hand, we prove that the language equivalence problem is already Ackermann-hard for deterministic VASS. These two results imply Ackermann-completeness for language inclusion and equivalence in several possible restrictions. Some of our techniques can be also applied in much broader generality in infinite-state systems, namely for some subclass of well-structured transition systems.
On Efficient Noncommutative Polynomial Factorization via Higman Linearization
Venue: arXiv cs.CC 2025
Year: 2025

In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring F of polynomials in noncommuting variables x1,x2,...,xn over the field F. We obtain the following result Given a noncommutative algebraic branching program of size s computing a noncommutative polynomial f in F as input, where F=Fq is a finite field, we give a randomized algorithm that runs in time polynomial in s, n and log q that computes a factorization of the polynomial f as a product f=f1f2...fr, where each fi is an irreducible polynomial that is output as a noncommutative algebraic branching program. The algorithm works by first transforming the given algebraic branching program computing f into a linear matrix L using Higman's linearization of polynomials. We then factorize the linear matrix L and recover the factorization of the polynomial f. We use basic elements from Cohn's theory of free ideals rings combined with Ronyai's randomized polynomial-time algorithm for computing invariant subspaces of a collection of matrices over finite fields.
AgileWatts: An Energy-Efficient CPU Core Idle-State Architecture for Latency-Sensitive Server Applications
Venue: arXiv cs.AR 2025
Year: 2025

User-facing applications running in modern datacenters exhibit irregular request patterns and are implemented using a multitude of services with tight latency requirements. These characteristics render ineffective existing energy conserving techniques when processors are idle due to the long transition time from a deep idle power state (C-state). While prior works propose management techniques to mitigate this inefficiency, we tackle it at its root with AgileWatts (AW): a new deep C-state architecture optimized for datacenter server processors targeting latency-sensitive applications. AW is based on three key ideas. First, AW eliminates the latency overhead of saving/restoring the core context (i.e., micro-architectural state) when powering-off/-on the core in a deep idle power state by i) implementing medium-grained power-gates, carefully distributed across the CPU core, and ii) retaining context in the power-ungated domain. Second, AW eliminates the flush latency overhead (several tens of microseconds) of the L1/L2 caches when entering a deep idle power state by keeping L1/L2 cache content power-ungated. A minimal control logic also remains power-ungated to serve cache coherence traffic (i.e., snoops) seamlessly. AW implements sleep-mode in caches to reduce caches leakage power consumption and lowers a core voltage to the minimum operational voltage level to minimize the leakage power of the power-ungated domain. Third, using a state-of-the-art power efficient all-digital phase-locked loop (ADPLL) clock generator, AW keeps the PLL active and locked during the idle state, further cutting precious microseconds of wake-up latency at a negligible power cost. Our evaluation with an accurate simulator calibrated against an Intel Skylake server shows that AW reduces the energy consumption of Memcached by up to 71% (35% on average) with up to 1% performance degradation.
Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems
Venue: arXiv cs.CG 2025
Year: 2025

Let $\mathcal{T}$ be a set of $n$ flat (planar) semi-algebraic regions in $\mathbb{R}^3$ of constant complexity (e.g., triangles, disks), which we call plates. We wish to preprocess $\mathcal{T}$ into a data structure so that for a query object $γ$, which is also a plate, we can quickly answer various intersection queries, such as detecting whether $γ$ intersects any plate of $\mathcal{T}$, reporting all the plates intersected by $γ$, or counting them. We also consider two simpler cases of this general setting: (i) the input objects are plates and the query objects are constant-degree parametrized algebraic arcs in $\mathbb{R}^3$ (arcs, for short), or (ii) the input objects are arcs and the query objects are plates in $\mathbb{R}^3$. Besides being interesting in their own right, the data structures for these two special cases form the building blocks for handling the general case. By combining the polynomial-partitioning technique with additional tools from real algebraic geometry, we present many different data structures for intersection queries, which also provide trade-offs between their size and query time. For example, if $\mathcal{T}$ is a set of plates and the query objects are algebraic arcs, we obtain a data structure that uses $O^*(n^{4/3})$ storage (where the $O^*(\cdot)$ notation hides factors of the form $n^ε$, for an arbitrarily small $ε>0$) and answers an arc-intersection query in $O^*(n^{2/3})$ time. This result is significant since the exponents do not depend on the specific shape of the input and query objects. We generalize and slightly improve this result: for a parameter $s\in [n^{4/3}, n^{t_q}]$, where ${t_q}\ge 3$ is the number of real parameters needed to specify a query arc, the query time can be decreased to $O^*((n/s^{1/{t_q}})^{\tfrac{2/3}{1-1/{t_q}}})$ by increasing the storage to $O^*(s)$.
Learning Rules from Rewards
Venue: arXiv cs.AI 2025
Year: 2025

Humans can flexibly generalize knowledge across domains by leveraging structured relational representations. While prior research has shown how such representations support analogical reasoning, less is known about how they are recruited to guide adaptive behavior. We address this gap by introducing the Relational Regression Tree Learner (RRTL), a model that incrementally builds policies over structured relational inputs by selecting task-relevant relations during the learning process. RRTL is grounded in the framework of relational reinforcement learning but diverges from traditional approaches by focusing on ground (i.e., non-variabilized) rules that refer to specific object configurations. Across three Atari games of increasing relational complexity (Breakout, Pong, Demon Attack), the model learns to act effectively by identifying a small set of relevant relations from a broad pool of candidate relations. A comparative version of the model, which partitions the state space using relative magnitude values (e.g., "more", "same", "less"), showed more robust learning than a version using logical (binary) splits. These results provide a proof of principle that reinforcement signals can guide the selection of structured representations, offering a computational framework for understanding how relational knowledge is learned and deployed in adaptive behavior.
How fragile is your network? More than you think
Venue: arXiv cs.SI 2025
Year: 2025

Graphs are pervasive in our everyday lives, with relevance to biology, the internet, and infrastructure, as well as numerous other applications. It is thus necessary to have an understanding as to how quickly a graph disintegrates, whether by random failure or by targeted attack. While much of the interest in this subject has been focused on targeted removal of nodes, there has been some recent interest in targeted edge removal. Here, we focus on how robust a graph is against edge removal. We define a measure of network fragility that relates the fraction of edges removed to the largest connected component. We construct a class of graphs that is robust to edge removal. Furthermore, it is demonstrated that graphs generally disintegrate faster than would be anticipated by greedy targeted attack. Finally it is shown that our fragility measure as demonstrated real and natural networks.
UAST: Unicode Aware Sanskrit Transliteration
Venue: arXiv cs.HC 2025
Year: 2025

Devanāgarī is the writing system that is adapted by various languages like Sanskrit. International Alphabet of Sanskrit Transliteration (IAST) is a transliteration scheme for romanisation of Sanskrit language. IAST makes use of diacritics to represent various characters. On a computer, these are represented using Unicode standard which differs from how the Sanskrit language behaves at a very fundamental level. This results in an issue that is encountered while designing typesetting software for devanāgarī and IAST. We hereby discuss the problems and provide a solution that solves the issue of incompatibilities between various transliteration and encoding schemes. The base implementation that should be used is available at https://github.com/dhruvildave/uast.rs. Another implementation that extends UAST to around $10$ scripts is available at https://github.com/aneri0x4f/uast-cli and https://github.com/dhruvildave/uast .
Minimum mean-squared error estimation with bandit feedback
Venue: arXiv cs.LG 2025
Year: 2025

We consider the problem of sequentially learning to estimate, in the mean squared error (MSE) sense, a Gaussian $K$-vector of unknown covariance by observing only $m < K$ of its entries in each round. We propose two MSE estimators, and analyze their concentration properties. The first estimator is non-adaptive, as it is tied to a predetermined $m$-subset and lacks the flexibility to transition to alternative subsets. The second estimator, which is derived using a regression framework, is adaptive and exhibits better concentration bounds in comparison to the first estimator. We frame the MSE estimation problem with bandit feedback, where the objective is to find the MSE-optimal subset with high confidence. We propose a variant of the successive elimination algorithm to solve this problem. We also derive a minimax lower bound to understand the fundamental limit on the sample complexity of this problem.
Instability of backoff protocols with arbitrary arrival rates
Venue: arXiv cs.DS 2025
Year: 2025

In contention resolution, multiple processors are trying to coordinate to send discrete messages through a shared channel with limited communication. If two processors send at the same time, the messages collide and are not transmitted successfully. Queue-free backoff protocols are an important special case - for example, Google Drive and AWS instruct their users to implement binary exponential backoff to handle busy periods. It is a long-standing conjecture of Aldous (IEEE Trans. Inf. Theory 1987) that no stable backoff protocols exist for any positive arrival rate of processors. This foundational question remains open; instability is only known in general when the arrival rate of processors is at least 0.42 (Goldberg et al. SICOMP 2004). We prove Aldous' conjecture for all backoff protocols outside of a tightly-constrained special case using a new domination technique to get around the main difficulty, which is the strong dependencies between messages.
Iceberg Sensemaking: A Process Model for Critical Data Analysis and Visualization
Venue: arXiv cs.HC 2025
Year: 2025

We offer a new model of the sensemaking process for data analysis and visualization. Whereas past sensemaking models have been grounded in positivist assumptions about the nature of knowledge, we reframe data sensemaking in critical, humanistic terms by approaching it through an interpretivist lens. Our three-phase process model uses the analogy of an iceberg, where data is the visible tip of underlying schemas. In the Add phase, the analyst acquires data, incorporates explicit schemas from the data, and absorbs the tacit schemas of both data and people. In the Check phase, the analyst interprets the data with respect to the current schemas and evaluates whether the schemas match the data. In the Refine phase, the analyst considers the role of power, articulates what was tacit into explicitly stated schemas, updates data, and formulates findings. Our model has four important distinguishing features: Tacit and Explicit Schemas, Schemas First and Always, Data as a Schematic Artifact, and Schematic Multiplicity. We compare the roles of schemas in past sensemaking models and draw conceptual distinctions based on a historical review of schemas in different academic traditions. We validate the descriptive and prescriptive power of our model through four analysis scenarios: noticing uncollected data, learning to wrangle data, downplaying inconvenient data, and measuring with sensors. We conclude by discussing the value of interpretivism, the virtue of epistemic humility, and the pluralism this sensemaking model can foster.
Can Visual Dialogue Models Do Scorekeeping? Exploring How Dialogue Representations Incrementally Encode Shared Knowledge
Venue: arXiv cs.CL 2025
Year: 2025

Cognitively plausible visual dialogue models should keep a mental scoreboard of shared established facts in the dialogue context. We propose a theory-based evaluation method for investigating to what degree models pretrained on the VisDial dataset incrementally build representations that appropriately do scorekeeping. Our conclusion is that the ability to make the distinction between shared and privately known statements along the dialogue is moderately present in the analysed models, but not always incrementally consistent, which may partially be due to the limited need for grounding interactions in the original task.
CoDe: A Cooperative and Decentralized Collision Avoidance Algorithm for Small-Scale UAV Swarms Considering Energy Efficiency
Venue: arXiv cs.RO 2025
Year: 2025

This paper introduces a cooperative and decentralized collision avoidance algorithm (CoDe) for small-scale UAV swarms consisting of up to three UAVs. CoDe improves energy efficiency of UAVs by achieving effective cooperation among UAVs. Moreover, CoDe is specifically tailored for UAV's operations by addressing the challenges faced by existing schemes, such as ineffectiveness in selecting actions from continuous action spaces and high computational complexity. CoDe is based on Multi-Agent Reinforcement Learning (MARL), and finds cooperative policies by incorporating a novel credit assignment scheme. The novel credit assignment scheme estimates the contribution of an individual by subtracting a baseline from the joint action value for the swarm. The credit assignment scheme in CoDe outperforms other benchmarks as the baseline takes into account not only the importance of a UAV's action but also the interrelation between UAVs. Furthermore, extensive experiments are conducted against existing MARL-based and conventional heuristic-based algorithms to demonstrate the advantages of the proposed algorithm.
Qunity: A Unified Language for Quantum and Classical Computing (Extended Version)
Venue: arXiv cs.PL 2025
Year: 2025

We introduce Qunity, a new quantum programming language designed to treat quantum computing as a natural generalization of classical computing. Qunity presents a unified syntax where familiar programming constructs can have both quantum and classical effects. For example, one can use sum types to implement the direct sum of linear operators, exception-handling syntax to implement projective measurements, and aliasing to induce entanglement. Further, Qunity takes advantage of the overlooked BQP subroutine theorem, allowing one to construct reversible subroutines from irreversible quantum algorithms through the uncomputation of "garbage" outputs. Unlike existing languages that enable quantum aspects with separate add-ons (like a classical language with quantum gates bolted on), Qunity provides a unified syntax and a novel denotational semantics that guarantees that programs are quantum mechanically valid. We present Qunity's syntax, type system, and denotational semantics, showing how it can cleanly express several quantum algorithms. We also detail how Qunity can be compiled into a low-level qubit circuit language like OpenQASM, proving the realizability of our design.
Transfer Learning with Pre-trained Conditional Generative Models
Venue: arXiv cs.LG 2025
Year: 2025

Transfer learning is crucial in training deep neural networks on new target tasks. Current transfer learning methods always assume at least one of (i) source and target task label spaces overlap, (ii) source datasets are available, and (iii) target network architectures are consistent with source ones. However, holding these assumptions is difficult in practical settings because the target task rarely has the same labels as the source task, the source dataset access is restricted due to storage costs and privacy, and the target architecture is often specialized to each task. To transfer source knowledge without these assumptions, we propose a transfer learning method that uses deep generative models and is composed of the following two stages: pseudo pre-training (PP) and pseudo semi-supervised learning (P-SSL). PP trains a target architecture with an artificial dataset synthesized by using conditional source generative models. P-SSL applies SSL algorithms to labeled target data and unlabeled pseudo samples, which are generated by cascading the source classifier and generative models to condition them with target samples. Our experimental results indicate that our method can outperform the baselines of scratch training and knowledge distillation.
On the uncertainty principle of neural networks
Venue: arXiv cs.LG 2025
Year: 2025

In this study, we explore the inherent trade-off between accuracy and robustness in neural networks, drawing an analogy to the uncertainty principle in quantum mechanics. We propose that neural networks are subject to an uncertainty relation, which manifests as a fundamental limitation in their ability to simultaneously achieve high accuracy and robustness against adversarial attacks. Through mathematical proofs and empirical evidence, we demonstrate that this trade-off is a natural consequence of the sharp boundaries formed between different class concepts during training. Our findings reveal that the complementarity principle, a cornerstone of quantum physics, applies to neural networks, imposing fundamental limits on their capabilities in simultaneous learning of conjugate features. Meanwhile, our work suggests that achieving human-level intelligence through a single network architecture or massive datasets alone may be inherently limited. Our work provides new insights into the theoretical foundations of neural network vulnerability and opens up avenues for designing more robust neural network architectures.
Seed-Guided Topic Discovery with Out-of-Vocabulary Seeds
Venue: arXiv cs.CL 2025
Year: 2025

Discovering latent topics from text corpora has been studied for decades. Many existing topic models adopt a fully unsupervised setting, and their discovered topics may not cater to users' particular interests due to their inability of leveraging user guidance. Although there exist seed-guided topic discovery approaches that leverage user-provided seeds to discover topic-representative terms, they are less concerned with two factors: (1) the existence of out-of-vocabulary seeds and (2) the power of pre-trained language models (PLMs). In this paper, we generalize the task of seed-guided topic discovery to allow out-of-vocabulary seeds. We propose a novel framework, named SeeTopic, wherein the general knowledge of PLMs and the local semantics learned from the input corpus can mutually benefit each other. Experiments on three real datasets from different domains demonstrate the effectiveness of SeeTopic in terms of topic coherence, accuracy, and diversity.
Near-optimal Algorithms for Stochastic Online Bin Packing
Venue: arXiv cs.DS 2025
Year: 2025

We study the online bin packing problem under two stochastic settings. In the bin packing problem, we are given n items with sizes in (0,1] and the goal is to pack them into the minimum number of unit-sized bins. First, we study bin packing under the i.i.d. model, where item sizes are sampled independently and identically from a distribution in (0,1]. Both the distribution and the total number of items are unknown. The items arrive one by one and their sizes are revealed upon their arrival and they must be packed immediately and irrevocably in bins of size 1. We provide a simple meta-algorithm that takes an offline $α$-asymptotic approximation algorithm and provides a polynomial-time $(α+ \varepsilon)$-competitive algorithm for online bin packing under the i.i.d. model, where $\varepsilon$>0 is a small constant. Using the AFPTAS for offline bin packing, we thus provide a linear time $(1+\varepsilon)$-competitive algorithm for online bin packing under i.i.d. model, thus settling the problem. We then study the random-order model, where an adversary specifies the items, but the order of arrival of items is drawn uniformly at random from the set of all permutations of the items. Kenyon's seminal result [SODA'96] showed that the Best-Fit algorithm has a competitive ratio of at most 3/2 in the random-order model, and conjectured the ratio to be around 1.15. However, it has been a long-standing open problem to break the barrier of 3/2 even for special cases. Recently, Albers et al. [Algorithmica'21] showed an improvement to 5/4 competitive ratio in the special case when all the item sizes are greater than 1/3. For this special case, we settle the analysis by showing that Best-Fit has a competitive ratio of 1. We make further progress by breaking the barrier of 3/2 for the 3-Partition problem, a notoriously hard special case of bin packing, where all item sizes lie in (1/4,1/2].