O(N log N) to CLS-Complete: Navigating the Spectrum of Computational Complexity in Modern AI/ML

Latest 34 papers on computational complexity: Sep. 19, 2026

The relentless pursuit of efficiency and capability drives innovation across AI and machine learning. From optimizing massive simulations to securing wireless communications, computational complexity is a constant, critical constraint. Recent research showcases a fascinating spectrum of advancements, pushing the boundaries of what’s feasible with clever algorithmic design, novel architectures, and profound theoretical insights. This digest dives into some of these breakthroughs, exploring how researchers are tackling challenges from the highly efficient O(N log N) realm to the fundamentally hard, CLS-complete problems.

The Big Idea(s) & Core Innovations

Many of the featured papers address the dual challenge of scaling up complex problems while simultaneously improving performance. A common theme is the decomposition of problems or models into more manageable parts, often leveraging inherent structure for efficiency. For instance, in scientific machine learning, LSR-Net: Learning the Forward Evolution Operator for Nonlinear Fluid Dynamics by Qian Hou et al. (The Hong Kong University of Science and Technology) introduces a neural operator that efficiently learns evolution operators for dynamical systems. Their key innovation is decomposing the learnable integral kernel into long-range and short-range components, where the long-range part uses a sum-of-exponentials representation for an impressive O(n log n) complexity, drastically outperforming baselines like FNO and DeepONet on 2D PDE benchmarks. This decomposition allows capturing both local fine-grained structures and global patterns in fluid dynamics, a significant step forward for data-driven PDE solvers.

Similarly, in numerical analysis, A Matrix-free Augmented High Order Compact Solver for Variable-Coefficient Biharmonic Problems by Jin Li et al. (National University of Defense Technology, China) tackles biharmonic equations with O(n log n) complexity by treating unavailable boundary values as augmented unknowns, reducing global coupling to a lower-dimensional Schur complement system. This elegant approach allows solving problems with over a billion degrees of freedom in minutes, a major leap for high-order PDE solvers.

For inverse problems, Mirjeta Pasha et al. (Virginia Tech) in A provably convergent MM-GKS variant for large-scale inverse problems introduce LM-MM-GKS, a limited-memory variant of a Majorization-Minimization method. This method achieves provable convergence even with bounded search space dimensions and offers constant memory bounds, enabling high-quality edge-preserving reconstructions in applications like image deblurring and medical imaging, without the memory bottlenecks of prior approaches.

In the realm of autonomous systems, efficiency is paramount. Yasin Sonmez et al. (University of California, Berkeley) revolutionize robust controlled invariant set synthesis in Real-Time Synthesis of Robust Controlled Invariant Sets for Monotone Systems by representing lower-closed sets as threshold functions. This transforms complex fixed-point iterations into embarrassingly parallel binary searches, leading to thousands-fold speedups. They achieve real-time synthesis on grids with 10^14 cells in under two minutes, making online safety verification for autonomous vehicles a reality. Meanwhile, Bingheng Wang et al. (National University of Singapore) present Trust-Region Neural Moving Horizon Estimation for Robots, efficiently training neural estimators by reusing Kalman filter computations for the MHE Hessian. This maintains linear computational complexity while achieving superior disturbance estimation for quadrotors with minimal data and parameters.

From a foundational perspective, the paper Descriptive Complexity in Lean: Completeness by First-Order Reductions by Pierre Senellart and Anton Gnatenko (DI ENS, PSL University, Inria) presents a groundbreaking framework for mechanizing computational complexity using descriptive complexity, entirely bypassing the overhead of Turing machine models. They prove 73 completeness theorems, including all of Karp’s 21 NP-complete problems, demonstrating a 7x reduction in code size for the Cook-Levin theorem compared to machine-based approaches. This work shows that first-order reductions offer stronger theoretical statements and more practical formalization.

Not all problems are easily optimizable. On the Complexity of Finding Fixed Points for Set-Valued Contractions by Emmanouil-Vasileios Vlatakis-Gkaragkounis and Pucheng Xiong (University of Wisconsin-Madison) delves into the fundamental limits of computation, proving that finding fixed points for set-valued contractions (Nadler’s theorem) is CLS-complete. This places it at the same complexity level as Banach’s contraction principle for single-valued maps, highlighting the intrinsic difficulty of these problems. Similarly, The Complexity of Weak Partition Connectivity in Hedgegraphs by Yuanhao Wang and Wei Wang (Xi’an Jiaotong University) proves the NP-completeness of weak partition connectivity even in highly restricted hedgegraph classes, answering a longstanding open question and showing that optimizing over arbitrary numbers of partitions is harder than two-block cuts. The new Scheduling Jobs with Multiple Operational Modes and Tail Times by Bo Chen et al. (Warwick Business School) reveals that adding just one operational mode to a job can turn a polynomially solvable scheduling problem into an NP-hard one, underscoring how seemingly minor design choices impact complexity.

Under the Hood: Models, Datasets, & Benchmarks

These papers introduce and leverage a variety of tools and methodologies to achieve their breakthroughs:

• LSR-Net: Employs a novel neural operator architecture with sum-of-exponentials (SOE) representation for long-range convolutions. Evaluated on 2D Burgers, wave, and shallow water equations.
• Matrix-free HOC Solver: Utilizes an augmented finite difference formulation, GMRES for Schur complement systems, and FFT-based solvers. Tested on 2D and 3D variable-coefficient biharmonic problems.
• LM-MM-GKS: A Majorization-Minimization Generalized Krylov Subspace method with alternating expansion/compression. Applied to image deblurring, dynamic photoacoustic tomography (PAT), and computerized tomography (CT).
• Real-Time Controlled Invariant Sets: Threshold-function representation of lower-closed sets for monotone systems. Demonstrated in an MPPI controller for an unprotected left-turn scenario; code available at pFaces-MonoSynth.
• Trust-Region NeuroMHE: Neural Moving Horizon Estimation trained with a trust-region policy optimization method leveraging Kalman filters for Hessian computation. Validated on real quadrotor flight data for aerodynamic disturbance estimation; code at TR-NeuroMHE.
• Descriptive Complexity in Lean: A comprehensive Lean library for formalizing computational complexity via isomorphism-invariant predicates and first-order reductions. The library contains 73 completeness theorems across 14 complexity classes; code at descriptive-complexity.
• Hybrid-Field Channel Tracking for XL-MIMO: Utilizes discrete fractional Fourier transform (DFrFT) and Newton-based refinement for channel tracking in extremely large-scale MIMO. Benchmarked against hybrid-field OMP and NOMP.
• BO-pro-c: Bayesian optimization using product-of-experts Gaussian process models with uncertainty calibration (GP-pro-c). Evaluated on 47 synthetic benchmark functions; code at bo-pro-c.
• Sewer-Transformer-ML: Hierarchical Vision Transformer with multi-level feature fusion, and lightweight variants Sewer-MobileNet-ML and Sewer-Mobile-TransNet. Achieves SOTA on the Sewer-ML Dataset and Sewer-Capsule Dataset.
• PIRFNs: Physics-Informed Random Feature Networks leveraging product random features and kernel methods. Outperforms PINNs, SA-PINNs, and ELM on Helmholtz, transport, and wave equations.
• gr-PHYSEC: GNU Radio out-of-tree module for real-time physical-layer key generation using a CNN with quadruplet loss and Reed-Solomon encoding. Implemented on ADALM Pluto SDRs and NVIDIA Jetson Orin platforms; code at gr-PHYSEC.
• Sparse-BEVNet: Multi-view BEV 3D object detection with Bi-Level Routing Attention, Cascaded Group Attention, and Sparse Spatial Cross-Attention. Achieves strong performance on the nuScenes dataset; built on mmdetection3d.
• TempTPI: Informer-based trajectory prediction for maritime vessels with multi-channel Fourier-like temporal encoding. Uses Danish AIS Data from Søfartsstyrelsen.
• XLSDFT: A linear-scaling density functional theory framework. Achieves world-record 100-200 million atom DFT calculations on the LineShine exascale supercomputer; code at XLSDFT.
• CZPR: Set-based state estimation using constrained zonotopes and polyhedral relaxations for nonlinear systems. Implemented in the ZETA toolbox.
• Efficient RF Chain Selection: Greedy eigen-based (GES) and cofactor-based (GCS) selection for MIMO ISAC systems using a unified mutual information metric.
• Symmetric Models for Syndrome Decoding: Uses elementary symmetric polynomials for ESDP, impacting code-based cryptography security estimates.
• Continuous-Time Machine Learning: A comprehensive survey unifying neural differential equations, state-space models, liquid neural networks, and continuous-time transformers.

Impact & The Road Ahead

The implications of this research are profound, extending from fundamental theoretical advancements to tangible real-world applications. The ability to perform O(N log N) computational fluid dynamics, solve biharmonic equations for a billion unknowns in minutes, or achieve real-time safety verification for autonomous systems on 10^14 cells will unlock new frontiers in scientific discovery, engineering design, and critical infrastructure. The world-record 200-million-atom DFT calculations achieved by XLSDFT, detailed in Extreme-Scale Linear-Scaling Kohn-Sham DFT at 100 Million Atoms: Bridging Quantum Simulations and Experiments by Qimen Xu et al. (National Supercomputing Center in Shenzhen), exemplify how algorithmic breakthroughs combined with exascale computing can bridge the gap between quantum simulations and experimental reality, accelerating material design.

For machine learning, the insights into optimal feature fusion for Transformers in Vision Transformer-Based Multi-Level Feature Fusion for Multi-Label Sewer Defect Classification by Xu Fang et al. (Shenzhen Polytechnic University) and the development of lightweight, yet highly accurate models (Sewer-MobileNet-ML) promise efficient, deployable AI for tasks like infrastructure inspection. Similarly, the advancements in 4D radar preprocessing for autonomous driving by Woo-Jin Jung et al. (KAIST) in Accuracy- and Real-Time-Aware 4D Radar Preprocessing for Autonomous Driving Perception Systems will enhance perception systems, making autonomous vehicles safer and more reliable. The development of gr-PHYSEC by Jose A. Sanchez Viloria et al. (Florida Atlantic University) for real-time physical-layer key generation marks a significant step towards more secure and decentralized wireless communications.

On the theoretical front, the CLS-completeness results for set-valued contractions and the NP-completeness of weak partition connectivity provide crucial boundaries, informing researchers where to focus on approximation or heuristics rather than seeking exact polynomial-time solutions. The rigorous formalization of complexity theory in Lean (as presented by Senellart and Gnatenko) opens up avenues for verified, trustworthy computational complexity statements, a crucial step for the robustness of our theoretical foundations. Continuous-time machine learning, unified by Waleed Razzaq et al. (University of Science and Technology of China), offers a powerful lens to view and develop new sequence models, with insights connecting seemingly disparate architectures like LSTMs and State-Space Models.

The papers collectively point to a future where computational bottlenecks are increasingly overcome by exploiting problem structure, leveraging advanced mathematical tools, and designing algorithms with an acute awareness of real-world constraints. The journey from O(N log N) efficiency to understanding CLS-complete intractability is not just about solving problems faster, but about understanding the fundamental limits and potentials of computation itself, paving the way for the next generation of intelligent systems.

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.