Buchumschlag

Asymptotic Rank Speedup Theorems, Revisited

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Alman, Josh, Li, Baitian
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Computational Complexity Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum
von: Alman, Josh, et al.
Veröffentlicht: (2025)

Faster Convolutions: Yates and Strassen Revisited
von: Brand, Cornelius, et al.
Veröffentlicht: (2025)

A Refined Laser Method and Faster Matrix Multiplication
von: Alman, Josh, et al.
Veröffentlicht: (2020)

Learning Functions of Halfspaces
von: Alman, Josh, et al.
Veröffentlicht: (2026)

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
von: Alman, Josh, et al.
Veröffentlicht: (2024)

More Asymmetry Yields Faster Matrix Multiplication
von: Alman, Josh, et al.
Veröffentlicht: (2024)

Quadratic Speedup for Computing Contraction Fixed Points
von: Chen, Xi, et al.
Veröffentlicht: (2026)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians
von: Mataraarachchi, Ranitha, et al.
Veröffentlicht: (2026)

Online Orthogonal Vectors Revisited
von: Gajulapalli, Karthik, et al.
Veröffentlicht: (2026)

Parameterized Vertex Integrity Revisited
von: Hanaka, Tesshu, et al.
Veröffentlicht: (2024)

Parameterized Capacitated Vertex Cover Revisited
von: Lampis, Michael, et al.
Veröffentlicht: (2026)

Revisiting Tree Canonization using polynomials
von: Arvind, V., et al.
Veröffentlicht: (2024)

Parameterized Critical Node Cut Revisited
von: Knop, Dušan, et al.
Veröffentlicht: (2025)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

Structural Parameterizations for Two Bounded Degree Problems Revisited
von: Lampis, Michael, et al.
Veröffentlicht: (2023)

Near-Optimality for Single-Source Personalized PageRank
von: Jiang, Xinpeng, et al.
Veröffentlicht: (2025)

An Exact 56-Addition, Rank-23 Scheme for General 3*3 Matrix Multiplication
von: Sun, Yinqi
Veröffentlicht: (2026)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
von: Lee, Euiwoong, et al.
Veröffentlicht: (2024)

A Distributional-Lifting Theorem for PAC Learning
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
von: Blanc, Guy, et al.
Veröffentlicht: (2024)

Quantum Mass Production Theorems
von: Kretschmer, William
Veröffentlicht: (2022)

Trickle-down Theorems via C-Lorentzian Polynomials II: Pairwise Spectral Influence and Improved Dobrushin's Condition
von: Leake, Jonathan, et al.
Veröffentlicht: (2025)

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
von: Leake, Jonathan, et al.
Veröffentlicht: (2025)

Constructing self-referential instances for the clique problem
von: Li, Jiaqi, et al.
Veröffentlicht: (2026)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2025)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2024)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
von: Li, Qian, et al.
Veröffentlicht: (2025)

The Query Complexity of Local Search and Brouwer in Rounds
von: Brânzei, Simina, et al.
Veröffentlicht: (2020)

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
von: Chen, Xi, et al.
Veröffentlicht: (2026)

Omnipredictors for Regression and the Approximate Rank of Convex Functions
von: Gopalan, Parikshit, et al.
Veröffentlicht: (2024)

Downward self-reducibility in the total function polynomial hierarchy
von: Gajulapalli, Karthik, et al.
Veröffentlicht: (2025)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
von: Focke, Jacob, et al.
Veröffentlicht: (2023)

Detecting Low-Degree Truncation
von: De, Anindya, et al.
Veröffentlicht: (2024)

Fine-grained Meta-Theorems for Vertex Integrity
von: Lampis, Michael, et al.
Veröffentlicht: (2021)

The Fine-Grained Complexity of Episode Matching
von: Bille, Philip, et al.
Veröffentlicht: (2021)

A New Information Complexity Measure for Multi-pass Streaming with Applications
von: Braverman, Mark, et al.
Veröffentlicht: (2024)

On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank
von: Kurpisz, Adam, et al.
Veröffentlicht: (2026)

First Order Logic on Pathwidth Revisited Again
von: Lampis, Michael
Veröffentlicht: (2022)

Neighborhood-Aware Graph Labeling Problem
von: Shahverdikondori, Mohammad, et al.
Veröffentlicht: (2026)