{"total":18,"rows":[{"id":"2209.04881","title":"On The Computational Complexity of Self-Attention","created":"2022-09-11","cited_by_count":139,"area":null},{"id":"2302.13214","title":"Fast Attention Requires Bounded Entries","created":"2023-02-26","cited_by_count":102,"area":null},{"id":"2310.04064","title":"How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation","created":"2023-10-06","cited_by_count":44,"area":null},{"id":"2406.03136","title":"Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models","created":"2024-06-05","cited_by_count":31,"area":null},{"id":"2402.04497","title":"The Fine-Grained Complexity of Gradient Computation for Training Large Language Models","created":"2024-02-07","cited_by_count":30,"area":null},{"id":"2211.14227","title":"Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing","created":"2022-11-25","cited_by_count":29,"area":null},{"id":"2206.14286","title":"TPU-KNN: K Nearest Neighbor Search at Peak FLOP/s","created":"2022-06-28","cited_by_count":18,"area":null},{"id":"2402.00943","title":"Approximate Nearest Neighbor Search with Window Filters","created":"2024-02-01","cited_by_count":11,"area":null},{"id":"2111.10912","title":"Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics","created":"2021-11-21","cited_by_count":8,"area":null},{"id":"2307.06877","title":"The complexity of non-stationary reinforcement learning","created":"2023-07-13","cited_by_count":7,"area":null},{"id":"2302.11508","title":"nSimplex Zen: A Novel Dimensionality Reduction for Euclidean and Hilbert Spaces","created":"2023-02-22","cited_by_count":3,"area":null},{"id":"2112.03222","title":"On Complexity of 1-Center in Various Metrics","created":"2021-12-06","cited_by_count":1,"area":null},{"id":"2309.05795","title":"On the Fine-Grained Hardness of Inverting Generative Models","created":"2023-09-11","cited_by_count":1,"area":null},{"id":"2102.02755","title":"Instance-based learning using the Half-Space Proximal Graph","created":"2021-02-04","cited_by_count":0,"area":null},{"id":"2407.11217","title":"Faster and Simpler Greedy Algorithm for $k$-Median and $k$-Means","created":"2024-07-15","cited_by_count":0,"area":null},{"id":"2508.06774","title":"Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair","created":"2025-08-09","cited_by_count":0,"area":null},{"id":"2607.09909","title":"Learning Partition Trees for Nearest Neighbor Search","created":"2026-07-10","cited_by_count":0,"area":null},{"id":"2609.37261","title":"Efficiently Approximating Attention Is Hard","created":"2026-09-29","cited_by_count":0,"area":null}],"next_cursor":null}