Buchumschlag

Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum

Fuente: arXiv

Gespeichert in:

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

Ähnliche Einträge

Asymptotic Rank Speedup Theorems, Revisited
von: Alman, Josh, et al.
Veröffentlicht: (2026)

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)

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

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

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

Lazy Kronecker Product
von: Song, Zhao
Veröffentlicht: (2026)

Kronecker scaling of tensors with applications to arithmetic circuits and algorithms
von: Björklund, Andreas, et al.
Veröffentlicht: (2025)

The Planted Orthogonal Vectors Problem
von: Kühnemann, David, et al.
Veröffentlicht: (2025)

Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems
von: Alman, Josh, et al.
Veröffentlicht: (2024)

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

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
von: Moroie, Gregory
Veröffentlicht: (2025)

FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set
von: Chu, Huairui, et al.
Veröffentlicht: (2023)

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

Vector TSP: A Traveling Salesperson Problem with Racetrack-like Acceleration Constraints
von: Casteigts, Arnaud, et al.
Veröffentlicht: (2020)

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)

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

On the Maximum Distance Sublattice Problem and Closest Vector Problem
von: Kumar, Rajendra, et al.
Veröffentlicht: (2018)

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)

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)

Quantum Worst-Case to Average-Case Reduction for Matrix-Vector Multiplication
von: Aggarwal, Divesh, et al.
Veröffentlicht: (2025)

Explicit Orthogonal Arrays and Universal Hashing with Arbitrary Parameters
von: Harvey, Nicholas, et al.
Veröffentlicht: (2024)

Distance Vector Domination
von: Cordasco, Gennaro, et al.
Veröffentlicht: (2024)

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2024)

On the Power of Interactive Proofs for Learning
von: Gur, Tom, et al.
Veröffentlicht: (2024)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
von: Greilhuber, Jakob, et al.
Veröffentlicht: (2025)

The Trichotomy of Regular Property Testing
von: Bathie, Gabriel, et al.
Veröffentlicht: (2025)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
von: Fujie, Yuto, et al.
Veröffentlicht: (2025)

Precoloring extension with demands on paths
von: Das, Arun Kumar, et al.
Veröffentlicht: (2025)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
von: Gholizadeh, Hossein, et al.
Veröffentlicht: (2025)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
von: Herrmann, Anton, et al.
Veröffentlicht: (2025)