Cover Image

A Note on Fine-Grained Quantum Reductions for Linear Algebraic Problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Doney, Kyle, Musco, Cameron
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Complexity Numerical Analysis
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Stability of the Lanczos Method for Matrix Function Approximation
by: Musco, Cameron, et al.
Published: (2017)

Sublinear Time Low-Rank Approximation of Toeplitz Matrices
by: Musco, Cameron, et al.
Published: (2024)

Sublinear Time Low-Rank Approximation of Hankel Matrices
by: Kapralov, Michael, et al.
Published: (2025)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
by: Rohwedder, Lars, et al.
Published: (2024)

Near-optimal hierarchical matrix approximation from matrix-vector products
by: Chen, Tyler, et al.
Published: (2024)

Fixed-sparsity matrix approximation from matrix-vector products
by: Amsel, Noah, et al.
Published: (2024)

Query Efficient Structured Matrix Learning
by: Amsel, Noah, et al.
Published: (2025)

The Fine-Grained Complexity of Episode Matching
by: Bille, Philip, et al.
Published: (2021)

Fine-Grained Classification Of Detecting Dominating Patterns
by: Dransfeld, Jonathan, et al.
Published: (2025)

Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions
by: Chia, Nai-Hui, et al.
Published: (2026)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
by: Nederlof, Jesper
Published: (2026)

Why Linear Programming cannot solve large instances of NP-complete problems in polynomial time
by: Hofman, Radoslaw
Published: (2006)

Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop
by: Amsel, Noah, et al.
Published: (2026)

Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning
by: Dereziński, Michał, et al.
Published: (2024)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut
by: Huang, Jeremy Ahrens, et al.
Published: (2024)

A Note on Approximability of Densest At-Least-k-Subgraph
by: Laekhanukit, Bundit, et al.
Published: (2026)

Fine-Grained Complexity of Continuous Euclidean k-Center
by: Blank, Lotte, et al.
Published: (2026)

Alphabet Reduction for Reconfiguration Problems
by: Ohsaka, Naoto
Published: (2024)

Finer-Grained Hardness of Kernel Density Estimation
by: Alman, Josh, et al.
Published: (2024)

Linear Hashing Is Optimal
by: Jaber, Michael, et al.
Published: (2025)

On Optimal Testing of Linearity
by: Arora, Vipul, et al.
Published: (2024)

Scheduling Problems with Constrained Rejections
by: Davies, Sami, et al.
Published: (2025)

A Complexity Analysis of the c-Closed Vertex Deletion Problem
by: Lehner, Lisa, et al.
Published: (2025)

Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms
by: Jia, He, et al.
Published: (2020)

Complex Mean and Variance of Linear Regression Model for High-Noised Systems by Kriging
by: Suslo, Tomasz
Published: (2005)

Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
by: Kenig, Batya
Published: (2025)

String Consensus Problems with Swaps and Substitutions
by: Gabory, Estéban, et al.
Published: (2025)

Equivalent Instances for Scheduling and Packing Problems
by: Jansen, Klaus, et al.
Published: (2025)

Pseudodeterministic Algorithms for Minimum Cut Problems
by: Agarwala, Aryan, et al.
Published: (2025)

Neighborhood-Aware Graph Labeling Problem
by: Shahverdikondori, Mohammad, et al.
Published: (2026)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
by: Jansen, Bart M. P., et al.
Published: (2026)

Linear Space Streaming Lower Bounds for Approximating CSPs
by: Chou, Chi-Ning, et al.
Published: (2021)

Generalized Graph Packing Problems Parameterized by Treewidth
by: Esmer, Barış Can, et al.
Published: (2025)

On the (In)Approximability of the Monitoring Edge Geodetic Set Problem
by: Bilò, Davide, et al.
Published: (2025)

Complexity of Local Search for Euclidean Clustering Problems
by: Manthey, Bodo, et al.
Published: (2023)

NP-Hardness and a PTAS for the Pinwheel Problem
by: Kleinberg, Robert, et al.
Published: (2026)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
by: Chudigiewitsch, Florian, et al.
Published: (2026)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
by: Sajith, Thejas Radhika
Published: (2025)

Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions
by: Cheng, Kuan, et al.
Published: (2025)