O(N) Complexity: Scaling AI and Optimization to New Horizons

Latest 24 papers on computational complexity: Sep. 13, 2026

In the fast-evolving landscape of AI and computational science, efficiency is paramount. As models grow larger and data volumes explode, the ability to process information with linear, or near-linear, computational complexity (O(N) or O(N log N)) becomes a game-changer. This digest explores a fascinating collection of recent research that tackles this challenge head-on, delivering breakthroughs across diverse fields from time series analysis and robot dynamics to wireless communications and complex optimization problems.

The Big Idea(s) & Core Innovations

Many of the papers coalesce around the theme of achieving high performance without quadratic or cubic scaling, often through clever algorithmic reformulations, architectural innovations, or the judicious application of approximation techniques. For instance, in time series classification, the paper “MomentQuant: an even more minimalist interval method with linear time complexity for time series classification” by Johann Faouzi (Univ Rennes) introduces MomentQuant. This novel algorithm replaces the costly exact quantile calculation of previous methods with an approximate moment-based approach (using the Cornish-Fisher expansion), cutting complexity from O(L log L) to a blazing O(L) for long series. This is a classic example of how a slight, well-calibrated approximation can unlock massive computational gains.

Similarly, in wireless communications, the paper “Efficient Graph Neural Networks for Multicarrier Wideband Hybrid Beamforming Optimization” by Beier Li and Mai Vu (Department of Electrical and Computer Engineering) showcases how Graph Neural Networks (GNNs) can optimize hybrid beamforming in 6G systems. Their GNN structures achieve superior spectral efficiency over traditional methods while maintaining a quadratic O(Nt²) complexity, a significant improvement over the cubic O(Nt³) of manifold optimization, especially in massive MIMO systems. The direct learning of analog beamformer phases instead of complex entries also simplifies constraints and improves efficiency.

Another significant innovation comes from “Efficient Sensor Fusion Through Covariance-Constrained Observation Decimation (CCOD)” by Andres Enriquez Fernandez et al. (The University of Texas at El Paso and Air Force Research Laboratory). CCOD addresses the challenge of optimizing Kalman filter updates. By reformulating the Discrete Algebraic Riccati Equation (DARE) with equivalent ‘decimated’ system matrices, they can directly predict steady-state error covariance, avoiding the computationally expensive lifted system representations or coupled periodic Riccati equations previously required. This allows for maximum observation decimation while guaranteeing estimation accuracy – critical for resource-constrained systems like space object trackers.

Meanwhile, in theoretical computer science, the paper “Promise Systems of Equations over Magmas with Identity and over Algebras in Congruence Modular Varieties” by Nick Jamesson delivers a P vs. NP-hard dichotomy for promise systems of equations over algebras in congruence modular varieties. This profound theoretical work provides a quasi-polynomial time algorithm for deciding the complexity of these problems, pushing the boundaries of what we understand about algebraic tractability.

From a different angle, “APEX-RBD: Mixed-Precision Exploration Framework for Hardware-Efficient Robot Dynamics Accelerator Design” by Xingyu Liu et al. (The Hong Kong University of Science and Technology) addresses computational efficiency for robotics hardware. They introduce a framework for mixed-precision quantization of Rigid Body Dynamics (RBD) computations. By using physics-driven search space pruning, a data-efficient surrogate model, and hybrid optimization, they achieve up to 1.9x area reduction and 1.8x power savings with minimal accuracy loss, demonstrating that a ‘one-size-fits-all’ precision approach is suboptimal for complex robotic computations.

Under the Hood: Models, Datasets, & Benchmarks

These innovations are often built upon or validated by significant models, datasets, and benchmarks:

• MomentQuant: Evaluated extensively on 142 UCR archive datasets, showing broad applicability. Relies on the Cornish-Fisher expansion for moment-based quantile estimation.
• TempTPI: From Kevin Ferneding et al. (Technical University of Denmark), their “TempTPI: Informer-Based trajectory prediction for maritime vessels” leverages the Informer architecture with ProbSparse self-attention (reducing complexity from quadratic to near-linear O((2-ε)L log L)) and a multi-channel Fourier-like temporal encoding on Danish AIS Data.
• Sewer-Transformer-ML: The paper “Vision Transformer-Based Multi-Level Feature Fusion for Multi-Label Sewer Defect Classification” by Xu Fang et al. (Shenzhen Polytechnic University) introduces Sewer-Transformer-ML, a hierarchical vision Transformer achieving state-of-the-art on the Sewer-ML benchmark (the largest open-source multi-label sewer defect dataset with 1.3M+ images). They also propose Sewer-MobileNet-ML and Sewer-Mobile-TransNet for lightweight, edge-deployable solutions, achieving comparable accuracy with ~95% parameter reduction. Code and models are available upon request.
• GNN for Hybrid Beamforming: Li and Vu’s work utilizes bipartite graph representations and three GNN structures (NU-GNN, EU-GNN, AN-GNN) to handle multicarrier wideband MIMO-OFDM systems.
• KLPCDA: Lingxiao Qu and Yan Pei (University of Aizu) in “A Kernel-Based Modular Discriminant Analysis Framework for Small-Sample Learning” analyze KLPCDA on diverse small-sample datasets including Indian Pines hyperspectral image, CWRU Bearing Dataset, GSE44076 Colon Cancer Dataset, and JAFFE face dataset. Its O(N³) complexity scales with training samples, not data dimensions.
• CZPR: Brenner S. Rego et al. (University of Sao Paulo) introduce CZPR in “Set-based state estimation of nonlinear discrete-time systems using constrained zonotopes and polyhedral relaxations”, which utilizes constrained zonotopes and polyhedral relaxations (available in the ZETA toolbox: https://github.com/ZETA-Toolbox) for linear complexity growth in state estimation.
• APEX-RBD: The framework uses a Random Forest surrogate model and is validated on robotics dynamics from Pinocchio library, KUKA iiwa, HyQ quadruped, and Atlas humanoid robot models.
• Sparse Approximation via Polynomial Equations: Matija Tomić et al. (University of British Columbia, KU Leuven) reformulate sparse approximation using sparsity-inducing monomial equations and elementary symmetric polynomials. Their methods, SESP-D and SESP-P, leverage resources like Tensorlab 3.0 (https://www.tensorlab.net).

Impact & The Road Ahead

The collective impact of this research is profound, offering pathways to more scalable, efficient, and robust AI and optimization systems. The move towards linear or near-linear complexity is not just an academic achievement; it directly translates to real-world benefits: enabling sophisticated AI on edge devices (Sewer-MobileNet-ML, APEX-RBD), improving real-time decision-making in critical infrastructure (TempTPI for maritime, GNN for 6G), and making complex optimization problems tractable (MomentQuant, CCOD).

Theoretical advancements, such as the strongly NP-hard result for SDP exactness in “On the Complexity of Recognizing SDP Exactness for the Maximum Cut Problem” by Avinash Bhardwaj (Indian Institute of Technology Bombay) and the Holant problem dichotomy in “The Computational Complexity of Holant Problems on 4-regular Graphs from the Stable Subgroup Sequence of SL(2, C)” by Yuan Huang and Zhiguo Fu, establish fundamental limits, guiding future research toward areas where efficiency gains are truly possible. Similarly, “On the Tightness of Standard Relaxations for Mixed-Integer Bilevel Linear Programs” by Sergey S. Ketkov and Oleg A. Prokopyev (University of Zurich) provides theoretical justification for the limitations of current relaxation methods, preventing wasted effort on intractable improvements.

From understanding why AI models sometimes “overthink” through fractal basins of attraction (“Fractal basins trap latent reasoning” by Jeffrey Lai et al., The University of Texas at Austin), to applying parameterised graph theory to tensor networks for quantum information (“Parameterised graph theory for tensor networks: entanglement rerouting, structural simplification, and agnostic tomography” by Matthias C. Caro et al.), this research pushes the boundaries of what is computationally feasible and theoretically understood.

The road ahead involves further exploring these efficient algorithms, integrating them into production systems, and developing new theoretical frameworks that account for real-world constraints like data scarcity and energy consumption. As AI continues its rapid expansion, the pursuit of O(N) complexity solutions will remain a cornerstone for unlocking its full potential, making advanced intelligence accessible and sustainable.

Please leave this field empty

Hi there 👋

Get a roundup of the latest AI paper digests in a quick, clean weekly email.

Check your inbox or spam folder to confirm your subscription.