Cover Image

A Tighter Complexity Analysis of SparseGPT

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Li, Xiaoyu, Liang, Yingyu, Shi, Zhenmei, Song, Zhao
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Artificial Intelligence Computation and Language Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Fast John Ellipsoid Computation with Differential Privacy Optimization
by: Li, Xiaoyu, et al.
Published: (2024)

Contrastive Identification and Generation in the Limit
by: Li, Xiaoyu, et al.
Published: (2026)

A Characterization of List Language Identification in the Limit
by: Charikar, Moses, et al.
Published: (2025)

On Characterizations for Language Generation: Interplay of Hallucinations, Breadth, and Stability
by: Kalavasis, Alkis, et al.
Published: (2024)

On the Limits of Language Generation: Trade-Offs Between Hallucination and Mode Collapse
by: Kalavasis, Alkis, et al.
Published: (2024)

Language Generation in the Limit
by: Kleinberg, Jon, et al.
Published: (2024)

Exploring Facets of Language Generation in the Limit
by: Charikar, Moses, et al.
Published: (2024)

The CLRS-Text Algorithmic Reasoning Language Benchmark
by: Markeeva, Larisa, et al.
Published: (2024)

Learning Linear Attention in Polynomial Time
by: Yau, Morris, et al.
Published: (2024)

On Language Generation in the Limit with Bounded Memory
by: Kleinberg, Jon, et al.
Published: (2026)

Differentially Private Language Generation and Identification in the Limit
by: Mehrotra, Anay, et al.
Published: (2026)

Language Generation with Infinite Contamination
by: Mehrotra, Anay, et al.
Published: (2025)

GateLoop: Fully Data-Controlled Linear Recurrence for Sequence Modeling
by: Katsch, Tobias
Published: (2023)

Pareto-optimal Non-uniform Language Generation
by: Charikar, Moses, et al.
Published: (2025)

The Library Theorem: How External Organization Governs Agentic Reasoning Capacity
by: Mainen, Zachary F.
Published: (2026)

Grams: Gradient Descent with Adaptive Momentum Scaling
by: Cao, Yang, et al.
Published: (2024)

Circuit Complexity Bounds for Visual Autoregressive Model
by: Ke, Yekun, et al.
Published: (2025)

HashEvict: A Pre-Attention KV Cache Eviction Strategy using Locality-Sensitive Hashing
by: Liu, Minghui, et al.
Published: (2024)

The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity
by: Chen, Yifang, et al.
Published: (2024)

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
by: Alman, Josh, et al.
Published: (2024)

Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing
by: Guo, Anxin, et al.
Published: (2026)

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
by: Banik, Aritra, et al.
Published: (2025)

On Fine-Grained I/O Complexity of Attention Backward Passes
by: Li, Xiaoyu, et al.
Published: (2024)

HSR-Enhanced Sparse Attention Acceleration
by: Chen, Bo, et al.
Published: (2024)

Diversity-aware clustering: Computational Complexity and Approximation Algorithms
by: Thejaswi, Suhas, et al.
Published: (2024)

Uncovering Fairness through Data Complexity as an Early Indicator
by: Ferreira, Juliett Suárez, et al.
Published: (2025)

Differentially Private Kernel Density Estimation
by: Liu, Erzhi, et al.
Published: (2024)

Circuit Complexity Bounds for RoPE-based Transformer Architecture
by: Chen, Bo, et al.
Published: (2024)

Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexity
by: Feng, Guhao, et al.
Published: (2023)

Block-Diagonal Guided DBSCAN Clustering
by: Zhao, Weibing
Published: (2024)

Theoretical Constraints on the Expressive Power of $\mathsf{RoPE}$-based Tensor Attention Transformers
by: Li, Xiaoyu, et al.
Published: (2024)

DiscQuant: A Quantization Method for Neural Networks Inspired by Discrepancy Theory
by: Chee, Jerry, et al.
Published: (2025)

MACKO: Sparse Matrix-Vector Multiplication for Low Sparsity
by: Macko, Vladimír, et al.
Published: (2025)

OpenTensor: Reproducing Faster Matrix Multiplication Discovering Algorithms
by: Sun, Yiwen, et al.
Published: (2024)

A Partition Cover Approach to Tokenization
by: Lim, Jia Peng, et al.
Published: (2025)

Learning-augmented smooth integer programs with PAC-learnable oracles
by: He, Hao-Yuan, et al.
Published: (2026)

Training Tensor Attention Efficiently: From Cubic to Almost Linear Time
by: Cao, Yang, et al.
Published: (2024)

Towards Infinite-Long Prefix in Transformer
by: Liang, Yingyu, et al.
Published: (2024)

On the Price of Privacy for Language Identification and Generation
by: Li, Xiaoyu, et al.
Published: (2026)

Efficiently Learning Branching Networks for Multitask Algorithmic Reasoning
by: Li, Dongyue, et al.
Published: (2025)