computational complexity
A theoretical measure of the amount of computational resources (such as time and space) required to solve a problem, which is essential for understanding the feasibility of algorithms.
- A faster training algorithm for regression trees with linear leaves, and an analysis of its complexity
- Accelerated Evolving Set Processes for Local PageRank Computation
- Additive Models Explained: A Computational Complexity Approach
- Adversarial Graph Fusion for Incomplete Multi-view Semi-supervised Learning with Tensorial Imputation
- An Adaptive Quantum Circuit of Dempster's Rule of Combination for Uncertain Pattern Classification
- Attention on the Sphere
- Causal Spatio-Temporal Prediction: An Effective and Efficient Multi-Modal Approach
- Clustering via Hedonic Games: New Concepts and Algorithms
- Computational Hardness of Reinforcement Learning with Partial $q^{\pi}$-Realizability
- Constructing an Optimal Behavior Basis for the Option Keyboard
- Counteractive RL: Rethinking Core Principles for Efficient and Scalable Deep Reinforcement Learning
- Dataset Distillation of 3D Point Clouds via Distribution Matching
- Decomposing motor units through elimination for real-time intention driven assistive neurotechnology
- Differentiable Generalized Sliced Wasserstein Plans
- DuSA: Fast and Accurate Dual-Stage Sparse Attention Mechanism Accelerating Both Training and Inference
- E2Former: An Efficient and Equivariant Transformer with Linear-Scaling Tensor Products
- Efficient Algorithms for Robust and Partial Semi-Discrete Optimal Transport
- Efficient Rectified Flow for Image Fusion
- FLAME: Fast Long-context Adaptive Memory for Event-based Vision
- FastJAM: a Fast Joint Alignment Model for Images
- Faster Generic Identification in Tree-Shaped Structural Causal Models
- FlowPrune: Accelerating Attention Flow Calculation by Pruning Flow Network
- Frequency-Aware Token Reduction for Efficient Vision Transformer
- GAMMA: Gated Multi-hop Message Passing for Homophily-Agnostic Node Representation in GNNs
- Hessian-guided Perturbed Wasserstein Gradient Flows for Escaping Saddle Points
- Hierarchical Demonstration Order Optimization for Many-shot In-Context Learning
- Improving Energy Natural Gradient Descent through Woodbury, Momentum, and Randomization
- Learning single index models via harmonic decomposition
- Learning to Think: Information-Theoretic Reinforcement Fine-Tuning for LLMs
- Less but More: Linear Adaptive Graph Learning Empowering Spatiotemporal Forecasting
- Localized Data Shapley: Accelerating Valuation for Nearest Neighbor Algorithms
- MisoDICE: Multi-Agent Imitation from Mixed-Quality Demonstrations
- MoBA: Mixture of Block Attention for Long-Context LLMs
- MonarchAttention: Zero-Shot Conversion to Fast, Hardware-Aware Structured Attention
- Nearly-Linear Time and Massively Parallel Algorithms for $k$-anonymity
- Nyström-Accelerated Primal LS-SVMs: Breaking the $O(an^3)$ Complexity Bottleneck for Scalable ODEs Learning
- On Evaluating Policies for Robust POMDPs
- On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness
- Optimal Spectral Transitions in High-Dimensional Multi-Index Models
- PermLLM: Learnable Channel Permutation for N:M Sparse Large Language Models
- PhySwin: An Efficient and Physically-Informed Foundation Model for Multispectral Earth Observation
- RankSEG-RMA: An Efficient Segmentation Algorithm via Reciprocal Moment Approximation
- Rethinking Circuit Completeness in Language Models: AND, OR, and ADDER Gates
- Revolutionizing Training-Free NAS: Towards Efficient Automatic Proxy Discovery via Large Language Models
- S-Crescendo: A Nested Transformer Weaving Framework for Scalable Nonlinear System in S-Domain Representation
- SPARKE: Scalable Prompt-Aware Diversity and Novelty Guidance in Diffusion Models via RKE Score
- Shapley-Based Data Valuation for Weighted $k$-Nearest Neighbors
- Stackelberg Learning with Outcome-based Payment
- Tensor Decomposition Networks for Accelerating Machine Learning Force Field Computations
- The Complexity of Correlated Equilibria in Generalized Games
- The Computational Complexity of Counting Linear Regions in ReLU Neural Networks
- The Parameterized Complexity of Computing the VC-Dimension
- Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization
- UGM2N: An Unsupervised and Generalizable Mesh Movement Network via M-Uniform Loss
- Variational Polya Tree
- Vertical Federated Feature Screening
- Why Popular MOEAs are Popular: Proven Advantages in Approximating the Pareto Front