OpenRaiser/Intern-Atlas huggingface dataset:
A Tail Estimate with Exponential Decay for the Randomized Incremental Construction of Search Structures
Venue: arXiv cs.CG 2025
Year: 2025

The Randomized Incremental Construction (RIC) of search DAGs for point location in planar subdivisions, nearest-neighbor search in 2D points, and extreme point search in 3D convex hulls, are well known to take ${\cal O}(n \log n)$ expected time for structures of ${\cal O}(n)$ expected size. Moreover, searching takes w.h.p. ${\cal O}(\log n)$ comparisons in the first and w.h.p. ${\cal O}(\log^2 n)$ comparisons in the latter two DAGs. However, the expected depth of the DAGs and high probability bounds for their size are unknown. Using a novel analysis technique, we show that the three DAGs have w.h.p. i) a size of ${\cal O}(n)$, ii) a depth of ${\cal O}(\log n)$, and iii) a construction time of ${\cal O}(n \log n)$. One application of these new and improved results are \emph{remarkably simple} Las Vegas verifiers to obtain search DAGs with optimal worst-case bounds. This positively answers the conjectured logarithmic search cost in the DAG of Delaunay triangulations [Guibas et al.; ICALP 1990] and a conjecture on the depth of the DAG of Trapezoidal subdivisions [Hemmer et al.; ESA 2012].
A Behavioural Analysis of Credulous Twitter Users
Venue: arXiv cs.SI 2025
Year: 2025

Thanks to platforms such as Twitter and Facebook, people can know facts and events that otherwise would have been silenced. However, social media significantly contribute also to fast spreading biased and false news while targeting specific segments of the population. We have seen how false information can be spread using automated accounts, known as bots. Using Twitter as a benchmark, we investigate behavioural attitudes of so called `credulous' users, i.e., genuine accounts following many bots. Leveraging our previous work, where supervised learning is successfully applied to single out credulous users, we improve the classification task with a detailed features' analysis and provide evidence that simple and lightweight features are crucial to detect such users. Furthermore, we study the differences in the way credulous and not credulous users interact with bots and discover that credulous users tend to amplify more the content posted by bots and argue that their detection can be instrumental to get useful information on possible dissemination of spam content, propaganda, and, in general, little or no reliable information.
Lower Bounds on Information Requirements for Causal Network Inference
Venue: arXiv cs.IT 2025
Year: 2025

Recovery of the causal structure of dynamic networks from noisy measurements has long been a problem of interest across many areas of science and engineering. Many algorithms have been proposed, but there is little work that compares the performance of the algorithms to converse bounds in a non-asymptotic setting. As a step to address this problem, this paper gives lower bounds on the error probability for causal network support recovery in a linear Gaussian setting. The bounds are based on Monte Carlo estimation of receiver operating characteristic (ROC) curves based on likelihood ratio samples assuming side information is available. The estimated ROC curves and curves obtained through the use of Bhattacharyya coefficients or Kullback--Leibler divergences are also compared.
Early-Bird GCNs: Graph-Network Co-Optimization Towards More Efficient GCN Training and Inference via Drawing Early-Bird Lottery Tickets
Venue: arXiv cs.LG 2025
Year: 2025

Graph Convolutional Networks (GCNs) have emerged as the state-of-the-art deep learning model for representation learning on graphs. However, it remains notoriously challenging to train and inference GCNs over large graph datasets, limiting their application to large real-world graphs and hindering the exploration of deeper and more sophisticated GCN graphs. This is because as the graph size grows, the sheer number of node features and the large adjacency matrix can easily explode the required memory and data movements. To tackle the aforementioned challenges, we explore the possibility of drawing lottery tickets when sparsifying GCN graphs, i.e., subgraphs that largely shrink the adjacency matrix yet are capable of achieving accuracy comparable to or even better than their full graphs. Specifically, we for the first time discover the existence of graph early-bird (GEB) tickets that emerge at the very early stage when sparsifying GCN graphs, and propose a simple yet effective detector to automatically identify the emergence of such GEB tickets. Furthermore, we advocate graph-model co-optimization and develop a generic efficient GCN early-bird training framework dubbed GEBT that can significantly boost the efficiency of GCN training by (1) drawing joint early-bird tickets between the GCN graphs and models and (2) enabling simultaneously sparsification of both the GCN graphs and models. Experiments on various GCN models and datasets consistently validate our GEB finding and the effectiveness of our GEBT, e.g., our GEBT achieves up to 80.2% ~ 85.6% and 84.6% ~ 87.5% savings of GCN training and inference costs while offering a comparable or even better accuracy as compared to state-of-the-art methods. Our source code and supplementary appendix are available at https://github.com/RICE-EIC/Early-Bird-GCN.
Competitive Information Design for Pandora's Box
Venue: arXiv cs.GT 2025
Year: 2025

We study a natural competitive-information-design strategic variant for the celebrated Pandora's Box problem (Weitzman, 1979), where each box is associated with a strategic information sender who can design what information about the box's prize value to be revealed to the agent when the agent inspects the box. This variant with strategic boxes is motivated by a wide range of real-world economic applications for Pandora's Box. Our contributions are three-fold: (1) given the boxes' information policies, we characterize the agent's optimal search and stopping strategy; (2) we fully characterize the pure symmetric equilibrium for the game of boxes' competitive information revelation in a symmetric environment; and (3) we reveal various insights regarding information competition and the resultant agent payoff at equilibrium, and additionally, we study informational properties of Pandora's Box by establishing an intrinsic connection between informativeness of any box's value distribution and the utility order of the search agent.
Fuzzy Logic-based Robust Failure Handling Mechanism for Fog Computing
Venue: arXiv cs.DC 2025
Year: 2025

Fog computing is an emerging computing paradigm which is mainly suitable for time-sensitive and real-time Internet of Things (IoT) applications. Academia and industries are focusing on the exploration of various aspects of Fog computing for market adoption. The key idea of the Fog computing paradigm is to use idle computation resources of various handheld, mobile, stationery and network devices around us, to serve the application requests in the Fog-IoT environment. The devices in the Fog environment are autonomous and not exclusively dedicated to Fog application processing. Due to that, the probability of device failure in the Fog environment is high compared with other distributed computing paradigms. Solving failure issues in Fog is crucial because successful application execution can only be ensured if failure can be handled carefully. To handle failure, there are several techniques available in the literature, such as checkpointing and task migration, each of which works well in cloud based enterprise applications that mostly deals with static or transactional data. These failure handling methods are not applicable to highly dynamic Fog environment. In contrast, this work focuses on solving the problem of managing application failure in the Fog environment by proposing a composite solution (combining fuzzy logic-based task checkpointing and task migration techniques with task replication) for failure handling and generating a robust schedule. We evaluated the proposed methods using real failure traces in terms of application execution time, delay and cost. Average delay and total processing time improved by 56% and 48% respectively, on an average for the proposed solution, compared with the existing failure handling approaches.
A Versatile Depth Video Encoding Scheme Based on Low-rank Tensor Modeling for Free Viewpoint Video
Venue: arXiv cs.MM 2025
Year: 2025

The compression quality losses of depth sequences determine quality of view synthesis in free-viewpoint video. The depth map intra prediction in 3D extensions of the HEVC applies intra modes with auxiliary depth modeling modes (DMMs) to better preserve depth edges and handle motion discontinuities. Although such modes enable high efficiency compression, but at the cost of very high encoding complexity. Skipping conventional intra coding modes and DMMs in depth coding limits practical applicability of the HEVC for 3D display applications. In this paper, we introduce a novel low-complexity scheme for depth video compression based on low-rank tensor decomposition and HEVC intra coding. The proposed scheme leverages spatial and temporal redundancy by compactly representing the depth sequence as a high-order tensor. Tensor factorization into a set of factor matrices following CANDECOMP PARAFAC (CP) decomposition via alternating least squares give a low-rank approximation of the scene geometry. Further, compression of factor matrices with HEVC intra prediction support arbitrary target accuracy by flexible adjustment of bitrate, varying tensor decomposition ranks and quantization parameters. The results demonstrate proposed approach achieves significant rate gains by efficiently compressing depth planes in low-rank approximated representation. The proposed algorithm is applied to encode depth maps of benchmark Ballet and Breakdancing sequences. The decoded depth sequences are used for view synthesis in a multi-view video system, maintaining appropriate rendering quality.
Kelly Bets and Single-Letter Codes: Optimal Information Processing in Natural Systems
Venue: arXiv cs.IT 2025
Year: 2025

In an information-processing investment game, such as the growth of a population of organisms in a changing environment, Kelly betting maximizes the expected log rate of growth. In this paper, we show that Kelly bets are closely related to optimal single-letter codes (i.e., they can achieve the rate-distortion bound with equality). Thus, natural information processing systems with limited computational resources can achieve information-theoretically optimal performance. We show that the rate-distortion tradeoff for an investment game has a simple linear bound, and that the bound is achievable at the point where the corresponding single-letter code is optimal. This interpretation has two interesting consequences. First, we show that increasing the organism's portfolio of potential strategies can lead to optimal performance over a continuous range of channels, even if the strategy portfolio is fixed. Second, we show that increasing an organism's number of phenotypes (i.e., its number of possible behaviours in response to the environment) can lead to higher growth rate, and we give conditions under which this occurs. Examples illustrating the results in simplified biological scenarios are presented.
Multi-Structural Games and Number of Quantifiers
Venue: arXiv cs.LO 2025
Year: 2025

We study multi-structural games, played on two sets $\mathcal{A}$ and $\mathcal{B}$ of structures. These games generalize Ehrenfeucht-Fraïssé games. Whereas Ehrenfeucht-Fraïssé games capture the quantifier rank of a first-order sentence, multi-structural games capture the number of quantifiers, in the sense that Spoiler wins the $r$-round game if and only if there is a first-order sentence $ϕ$ with at most $r$ quantifiers, where every structure in $\mathcal{A}$ satisfies $ϕ$ and no structure in $\mathcal{B}$ satisfies $ϕ$. We use these games to give a complete characterization of the number of quantifiers required to distinguish linear orders of different sizes, and develop machinery for analyzing structures beyond linear orders.
Semantic Journeys: Quantifying Change in Emoji Meaning from 2012-2018
Venue: arXiv cs.CL 2025
Year: 2025

The semantics of emoji has, to date, been considered from a static perspective. We offer the first longitudinal study of how emoji semantics changes over time, applying techniques from computational linguistics to six years of Twitter data. We identify five patterns in emoji semantic development and find evidence that the less abstract an emoji is, the more likely it is to undergo semantic change. In addition, we analyse select emoji in more detail, examining the effect of seasonality and world events on emoji semantics. To aid future work on emoji and semantics, we make our data publicly available along with a web-based interface that anyone can use to explore semantic change in emoji.
Massive MIMO-NOMA Systems Secrecy in the Presence of Active Eavesdroppers
Venue: arXiv cs.IT 2025
Year: 2025

Non-orthogonal multiple access (NOMA) and massive multiple-input multiple-output (MIMO) systems are highly efficient. Massive MIMO systems are inherently resistant to passive attackers (eavesdroppers), thanks to transmissions directed to the desired users. However, active attackers can transmit a combination of legitimate user pilot signals during the channel estimation phase. This way they can mislead the base station (BS) to rotate the transmission in their direction, and allow them to eavesdrop during the downlink data transmission phase. In this paper, we analyse this vulnerability in an improved system model and stronger adversary assumptions, and investigate how physical layer security can mitigate such attacks and ensure secure (confidential) communication. We derive the secrecy outage probability (SOP) and a lower bound on the ergodic secrecy capacity, using stochastic geometry tools when the number of antennas in the BSs tends to infinity. We adapt the result to evaluate the secrecy performance in massive orthogonal multiple access (OMA). We find that appropriate power allocation allows NOMA to outperform OMA in terms of ergodic secrecy rate and SOP.
Faster Algorithms for Longest Common Substring
Venue: arXiv cs.DS 2025
Year: 2025

In the classic longest common substring (LCS) problem, we are given two strings $S$ and $T$, each of length at most $n$, over an alphabet of size $σ$, and we are asked to find a longest string occurring as a fragment of both $S$ and $T$. Weiner, in his seminal paper that introduced the suffix tree, presented an $O(n \log σ)$-time algorithm for this problem [SWAT 1973]. For polynomially-bounded integer alphabets, the linear-time construction of suffix trees by Farach yielded an $O(n)$-time algorithm for the LCS problem [FOCS 1997]. However, for small alphabets, this is not necessarily optimal for the LCS problem in the word RAM model of computation, in which the strings can be stored in $O(n \log σ/\log n )$ space and read in $O(n \log σ/\log n )$ time. We show that, in this model, we can compute an LCS in time $O(n \log σ/ \sqrt{\log n})$, which is sublinear in $n$ if $σ=2^{o(\sqrt{\log n})}$ (in particular, if $σ=O(1)$), using optimal space $O(n \log σ/\log n)$. In fact, it was recently shown that this result is conditionally optimal [Kempa and Kociumaka, STOC 2025]. We then lift our ideas to the problem of computing a $k$-mismatch LCS, which has received considerable attention in recent years. In this problem, the aim is to compute a longest substring of $S$ that occurs in $T$ with at most $k$ mismatches. Thankachan et al.~showed how to compute a $k$-mismatch LCS in $O(n \log^k n)$ time for $k=O(1)$ [J. Comput. Biol. 2016]. We show an $O(n \log^{k-1/2} n)$-time algorithm, for any constant $k>0$ and irrespective of the alphabet size, using $O(n)$ space as the previous approaches. We thus notably break through the well-known $n \log^k n$ barrier, which stems from a recursive heavy-path decomposition technique that was first introduced in the seminal paper of Cole et al. [STOC 2004] for string indexing with $k$ errors.
Infinitely growing configurations in Emil Post's tag system problem
Venue: arXiv cs.DM 2025
Year: 2025

Emil Post's tag system problem posed the question of whether or not a tag system $\{N=3, P(0) = 00, P(1) = 1101\}$ has a configuration, simulation of which will never halt or end up in a loop. Over the subsequent decades, there were several attempts to find an answer to this question, including a recent study, during which the first $2^{84}$ initial configurations were checked. This paper presents a family of configurations of this type in the form of strings $A^{n} B C^{m}$ that evolve to $A^{n+1} B C^{m+1}$ after a finite number of steps. The proof of this behavior for all non-negative $n$ and $m$ is described later in this paper as a finite verification procedure, which is computationally bounded by 20 000 iterations of tag.
Quantitative and Approximate Monitoring
Venue: arXiv cs.LO 2025
Year: 2025

In runtime verification, a monitor watches a trace of a system and, if possible, decides after observing each finite prefix whether or not the unknown infinite trace satisfies a given specification. We generalize the theory of runtime verification to monitors that attempt to estimate numerical values of quantitative trace properties (instead of attempting to conclude boolean values of trace specifications), such as maximal or average response time along a trace. Quantitative monitors are approximate: with every finite prefix, they can improve their estimate of the infinite trace's unknown property value. Consequently, quantitative monitors can be compared with regard to a precision-cost trade-off: better approximations of the property value require more monitor resources, such as states (in the case of finite-state monitors) or registers, and additional resources yield better approximations. We introduce a formal framework for quantitative and approximate monitoring, show how it conservatively generalizes the classical boolean setting for monitoring, and give several precision-cost trade-offs for monitors. For example, we prove that there are quantitative properties for which every additional register improves monitoring precision.
Relational Reasoning Networks
Venue: arXiv cs.AI 2025
Year: 2025

Neuro-symbolic methods integrate neural architectures, knowledge representation and reasoning. However, they have been struggling at both dealing with the intrinsic uncertainty of the observations and scaling to real-world applications. This paper presents Relational Reasoning Networks (R2N), a novel end-to-end model that performs relational reasoning in the latent space of a deep learner architecture, where the representations of constants, ground atoms and their manipulations are learned in an integrated fashion. Unlike flat architectures like Knowledge Graph Embedders, which can only represent relations between entities, R2Ns define an additional computational structure, accounting for higher-level relations among the ground atoms. The considered relations can be explicitly known, like the ones defined by logic formulas, or defined as unconstrained correlations among groups of ground atoms. R2Ns can be applied to purely symbolic tasks or as a neuro-symbolic platform to integrate learning and reasoning in heterogeneous problems with both symbolic and feature-based represented entities. The proposed model overtakes the limitations of previous neuro-symbolic methods that have been either limited in terms of scalability or expressivity. The proposed methodology is shown to achieve state-of-the-art results in different experimental settings.
Data-Driven Invariant Learning for Probabilistic Programs
Venue: arXiv cs.PL 2025
Year: 2025

Morgan and McIver's weakest pre-expectation framework is one of the most well-established methods for deductive verification of probabilistic programs. Roughly, the idea is to generalize binary state assertions to real-valued expectations, which can measure expected values of probabilistic program quantities. While loop-free programs can be analyzed by mechanically transforming expectations, verifying loops usually requires finding an invariant expectation, a difficult task. We propose a new view of invariant expectation synthesis as a regression problem: given an input state, predict the average value of the post-expectation in the output distribution. Guided by this perspective, we develop the first data-driven invariant synthesis method for probabilistic programs. Unlike prior work on probabilistic invariant inference, our approach can learn piecewise continuous invariants without relying on template expectations, and also works with black-box access to the program. We also develop a data-driven approach to learn sub-invariants from data, which can be used to upper- or lower-bound expected values. We implement our approaches and demonstrate their effectiveness on a variety of benchmarks from the probabilistic programming literature.
Linear Space Streaming Lower Bounds for Approximating CSPs
Venue: arXiv cs.CC 2025
Year: 2025

We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on $n$ variables taking values in $\{0,\ldots,q-1\}$, we prove that improving over the trivial approximability by a factor of $q$ requires $Ω(n)$ space even on instances with $O(n)$ constraints. We also identify a broad subclass of problems for which any improvement over the trivial approximability requires $Ω(n)$ space. The key technical core is an optimal, $q^{-(k-1)}$-inapproximability for the Max $k$-LIN-mod $q$ problem, which is the Max CSP problem where every constraint is given by a system of $k-1$ linear equations $\bmod q$ over $k$ variables. Our work builds on and extends the breakthrough work of Kapralov and Krachun (Proc. STOC 2019) who showed a linear lower bound on any non-trivial approximation of the MaxCut problem in graphs. MaxCut corresponds roughly to the case of Max $k$-LIN-mod $q$ with ${k=q=2}$. For general CSPs in the streaming setting, prior results only yielded $Ω(\sqrt{n})$ space bounds. In particular no linear space lower bound was known for an approximation factor less than $1/2$ for any CSP. Extending the work of Kapralov and Krachun to Max $k$-LIN-mod $q$ to $k>2$ and $q>2$ (while getting optimal hardness results) is the main technical contribution of this work. Each one of these extensions provides non-trivial technical challenges that we overcome in this work.
KOALA: A Kalman Optimization Algorithm with Loss Adaptivity
Venue: arXiv cs.LG 2025
Year: 2025

Optimization is often cast as a deterministic problem, where the solution is found through some iterative procedure such as gradient descent. However, when training neural networks the loss function changes over (iteration) time due to the randomized selection of a subset of the samples. This randomization turns the optimization problem into a stochastic one. We propose to consider the loss as a noisy observation with respect to some reference optimum. This interpretation of the loss allows us to adopt Kalman filtering as an optimizer, as its recursive formulation is designed to estimate unknown parameters from noisy measurements. Moreover, we show that the Kalman Filter dynamical model for the evolution of the unknown parameters can be used to capture the gradient dynamics of advanced methods such as Momentum and Adam. We call this stochastic optimization method KOALA, which is short for Kalman Optimization Algorithm with Loss Adaptivity. KOALA is an easy to implement, scalable, and efficient method to train neural networks. We provide convergence analysis and show experimentally that it yields parameter estimates that are on par with or better than existing state of the art optimization algorithms across several neural network architectures and machine learning tasks, such as computer vision and language modeling.