Cover Image

A Dynamic Low-Rank Fast Gaussian Transform

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Huang, Baihe, Song, Zhao, Weinstein, Omri, Yin, Junze, Zhang, Hengjie, Zhang, Ruizhe
Format:	Preprint
Published:	2022
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

InstaHide's Sample Complexity When Mixing Two Private Images
by: Huang, Baihe, et al.
Published: (2020)

Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
by: Gu, Yuzhou, et al.
Published: (2023)

Discrepancy Minimization in Input-Sparsity Time
by: Deng, Yichuan, et al.
Published: (2022)

Improved Sparse Recovery for Approximate Matrix Multiplication
by: Uffenheimer, Yahel, et al.
Published: (2026)

Fast and Efficient Matching Algorithm with Deadline Instances
by: Song, Zhao, et al.
Published: (2023)

Hardness Amplification for Dynamic Binary Search Trees
by: Jiang, Shunhua, et al.
Published: (2024)

Dynamic Kernel Graph Sparsifiers
by: Cao, Yang, et al.
Published: (2022)

A Framework for Building Data Structures from Communication Protocols
by: Andoni, Alexandr, et al.
Published: (2025)

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
by: Koh, Zhuan Khye, et al.
Published: (2024)

(Approximate) Matrix Multiplication via Convolutions
by: Uffenheimer, Yahel, et al.
Published: (2025)

Training Overparametrized Neural Networks in Sublinear Time
by: Deng, Yichuan, et al.
Published: (2022)

Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems
by: Alman, Josh, et al.
Published: (2024)

Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance
by: Song, Zhao, et al.
Published: (2022)

A Faster $k$-means++ Algorithm
by: Liang, Jiehao, et al.
Published: (2022)

Robust Streaming Against Low-Memory Adversaries
by: Ben-Eliezer, Omri, et al.
Published: (2025)

Dynamic Rank, Basis, and Matching
by: Brand, Jan van den, et al.
Published: (2026)

Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform
by: Alman, Josh, et al.
Published: (2025)

Consistent Low-Rank Approximation
by: Woodruff, David P., et al.
Published: (2026)

Sublinear Time Algorithm for Online Weighted Bipartite Matching
by: Hu, Hang, et al.
Published: (2022)

Fast DCT+: A Family of Fast Transforms Based on Rank-One Updates of the Path Graph
by: Fernández-Menduiña, Samuel, et al.
Published: (2024)

Changing Base Without Losing Pace: A GPU-Efficient Alternative to MatMul in DNNs
by: Ailon, Nir, et al.
Published: (2025)

Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture
by: Björklund, Andreas, et al.
Published: (2024)

Efficient Dynamic Rank Aggregation
by: Alimi, Morteza, et al.
Published: (2025)

On Socially Fair Low-Rank Approximation and Column Subset Selection
by: Song, Zhao, et al.
Published: (2024)

Fast and Efficient Parallel Breadth-First Search with Power-law Graph Transformation
by: Jiang, Zite, et al.
Published: (2020)

Faster Algorithms for Schatten-p Low Rank Approximation
by: Kacham, Praneeth, et al.
Published: (2024)

Coloring 3-Colorable Graphs with Low Threshold Rank
by: Hsieh, Jun-Ting
Published: (2025)

High-Dimensional Geometric Streaming for Nearly Low Rank Data
by: Esfandiari, Hossein, et al.
Published: (2024)

Dynamic PageRank: Algorithms and Lower Bounds
by: Jayaram, Rajesh, et al.
Published: (2024)

Approximate counting of permutation patterns
by: Ben-Eliezer, Omri, et al.
Published: (2024)

Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck
by: Kuszmaul, William, et al.
Published: (2025)

Fast and Compact Sketch-Based Dynamic Connectivity
by: De Man, Quinten, et al.
Published: (2025)

IBB: Fast Burrows-Wheeler Transform Construction for Length-Diverse DNA Data
by: Adler, Enno, et al.
Published: (2025)

Entrywise Low-Rank Approximation and Matrix $p \rightarrow q$ Norms via Global Correlation Rounding
by: Anderson, Prashanti, et al.
Published: (2026)

QuadRank: Engineering a High Throughput Rank
by: Koerkamp, R. Groot
Published: (2026)

Fully Dynamic $k$-Clustering with Fast Update Time and Small Recourse
by: Bhattacharya, Sayan, et al.
Published: (2024)

Approximate Graph Propagation Revisited: Dynamic Parameterized Queries, Tighter Bounds and Dynamic Updates
by: Zhao, Zhuowei, et al.
Published: (2025)

Parallelize Single-Site Dynamics up to Dobrushin Criterion
by: Liu, Hongyang, et al.
Published: (2021)

Quantum Filtering and Analysis of Multiplicities in Eigenvalue Spectra
by: Ding, Zhiyan, et al.
Published: (2025)

A Simple Analysis of Ranking in General Graphs
by: Derakhshan, Mahsa, et al.
Published: (2025)