Zhao Song

Dynamic Kernel Graph Sparsifiers

On Differential Private $\ell_1$, $\ell_2$ and $\ell_p^p$ Distance Queries

Training Overparametrized Neural Networks in Sublinear Time

A Dynamic Low-Rank Fast Gaussian Transform

Sublinear Time Quantum Algorithm for Attention Approximation

Sublinear Time Quantum Sensitivity Sampling

Provable Guarantees for Flow-Based Generative Models in Time Series

On Fine-Grained I/O Complexity of Attention Backward Passes

Decoupling Sign and Magnitude in Optimization with Adaptive Momentum Scaling

Towards Sampling Data Structures for Tensor Products in Turnstile Streams

Tensor Power Methods: Faster and Robust for Arbitrary Order

T2VPhysBench: A First‑Principles Benchmark for Physical Consistency in Text‑to‑Video Generation

A Theoretical Analysis of Discrete Flow Matching Generative Models

Text-to-Image Diffusion Models Cannot Count, and Prompt Refinement Cannot Help

RoPE Attention Can Be Trained in Almost Linear Time

Minimalist Softmax Attention Provably Learns Constrained Boolean Functions

Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform

Accept More, Reject Less: Reducing up to 19% Unnecessary Desk-Rejections over 11 Years of ICLR Data

Towards High-Order Mean Flow Generative Models: Feasibility, Expressivity, and Provably Efficient Criteria

Theoretical Constraints on the Expressive Power of RoPE-based Tensor Attention Transformers

Exploring the Frontiers of Softmax: Provable Optimization, Applications in Diffusion Model, and Beyond

Training Tensor Attention Efficiently: From Cubic to Almost Linear Time

Advancing the understanding of fixed point iterations in deep neural networks: a detailed analytical study

Video Latent Flow Matching: Optimal Polynomial Projections for Video Interpolation and Extrapolation

One-Shot Clustering for Contextual Bandits with Knapsacks

Are Hallucinations Bad Estimations?

Circuit Complexity Bounds for Visual Autoregressive Model

Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers

HOFAR: High-Order Augmentation of Flow Autoregressive Transformers

RichSpace: Enriching Text-to-Video Prompt Space via Text Embedding Interpolation

Orthonormal Regularization in Low-Rank Adaptation

Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective

Differentially Private Lewis Weight Computation

On Differentially Private String Distances

Theoretical Guarantees for High Order Trajectory Refinement in Generative Flows

Thinking Isn't an Illusion: Overcoming the Limitations of Reasoning Models via Tool Augmentations

Dynamic Weighted Projection Maintenance with $\ell^p$-Lewis Weight

Your Vision-Language Model Can’t Even Count to 20: Exposing the Failures of VLMs in Compositional Counting

T2VTextBench: A Human Evaluation Benchmark for Textual Control in Video Generation Models

Training Multi-Layer Transformers in Almost Linear Time

DPBloomfilter: Securing Bloom Filters with Differential Privacy

Modern Hopfield Networks Cannot Solve $\mathsf{NC}^1$-Hard Problems

Visual Autoregressive Transformers Must Use $\Omega(n^2 d)$ Memory

On Computational Limits and Provably Efficient Criteria of Visual Autoregressive Models: A Fine-Grained Complexity Analysis

Quantum Attention: Fast Algorithms for Scalable Computation

Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse

MathViz-Bench: Evaluating Text-to-Image Models on Visually Solving Math Problems

Fast Block Attention Computation via Dynamic Algorithm

Provably Efficient High-Order Flow Matching in Pixel Space

High-Order Matching for One-Step Shortcut Diffusion Models

Which Coauthor Should I Nominate in My 99 ICLR Submissions? A Mathematical Analysis of the ICLR 2026 Reciprocal Reviewer Nomination Policy

Faster Sinkhorn’s Algorithm with Small Treewidth

Differentially Private Random Spanning Tree Generation

Too Easily Fooled? Prompt Injection Breaks LLMs on Frustratingly Simple Multiple-Choice Questions

On Differential Privacy for Adaptively Solving Search Problems via Sketching

Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programming

Efficient $k$-Sparse Band–Limited Interpolation with Improved Approximation Ratio

Discrepancy Minimization in Input-Sparsity Time

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap

Faster Algorithms for Structured John Ellipsoid Computation

Faster Algorithms for Structured Linear and Kernel Support Vector Machines

Attention Mechanism, Max-Affine Partition, and Universal Approximation

High-Order Flow Matching: Unified Framework and Sharp Statistical Rates

Fine-grained Attention I/O Complexity: Comprehensive Analysis for Backward Passes

Fundamental Limits of Prompt Tuning Transformers: Universality, Capacity and Efficiency

Dissecting Submission Limit in Desk-Rejections: A Mathematical Analysis of Fairness in AI Conference Policies

In-Context Deep Learning via Transformer Models

Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation

A Dynamic Low-Rank Fast Gaussian Transform

Differential Privacy of Cross-Attention with Provable Guarantee

Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time

Beyond Linear Approximations: A Novel Pruning Approach for Attention Matrix

Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models

Tensor Attention Training: Provably Efficient Learning of Higher-order Transformers

Pretrained Transformers are Deep Optimizers: Provable In-Context Learning for Deep Model Training

Towards Infinite-Long Prefix in Transformer

Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform

Training Overparametrized Neural Networks in Sublinear Time

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities

Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters

Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers

Dynamic Kernel Sparsifiers

On Differentially Private String Distances

Binary Hypothesis Testing for Softmax Models and Leverage Score Models

An $O(k\log n)$ Time Fourier Set Query Algorithm

Towards Sampling Data Structures for Tensor Products

Unlocking the Theory Behind Scaling 1-Bit Neural Networks

Binary Hypothesis Testing for Softmax Models and Leverage Score Models

HSR-Enhanced Sparse Attention Acceleration

One Pass Streaming Algorithm for Super Long Token Attention Approximation in Sublinear Space