Cover Image

Quantum Speedups for Approximating the John Ellipsoid

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Li, Xiaoyu, Song, Zhao, Yu, Junwei
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Faster Algorithm for Structured John Ellipsoid Computation
by: Cao, Yang, et al.
Published: (2022)

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

John Ellipsoids via Lazy Updates
by: Woodruff, David P., et al.
Published: (2025)

Quantum Speedup for Spectral Approximation of Kronecker Products
by: Gao, Yeqi, et al.
Published: (2024)

Quantum Speedup for Hypergraph Sparsification
by: Liu, Chenghua, et al.
Published: (2025)

Lawler-Moore Speedups via Additive Combinatorics
by: Bringmann, Karl, et al.
Published: (2026)

Quantum Speedups for Bayesian Network Structure Learning
by: Harviainen, Juha, et al.
Published: (2023)

Quantum Speedup for Sampling Random Spanning Trees
by: Apers, Simon, et al.
Published: (2025)

Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms
by: Caroppo, Susanna, et al.
Published: (2025)

Asymptotic Rank Speedup Theorems, Revisited
by: Alman, Josh, et al.
Published: (2026)

R-enum Revisited: Speedup and Extension for Context-Sensitive Repeats and Net Frequencies
by: Kimura, Kotaro, et al.
Published: (2025)

Quadratic Speedup for Computing Contraction Fixed Points
by: Chen, Xi, et al.
Published: (2026)

Discrepancy Minimization in Input-Sparsity Time
by: Deng, Yichuan, et al.
Published: (2022)

On Speedups for Convex Optimization via Quantum Dynamics
by: Chakrabarti, Shouvanik, et al.
Published: (2025)

An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians
by: Mataraarachchi, Ranitha, et al.
Published: (2026)

Quantum Speedups for Group Relaxations of Integer Linear Programs
by: Augustino, Brandon, et al.
Published: (2026)

Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms
by: Mo, Guanlin, et al.
Published: (2024)

An Improved Approximation Algorithm for Metric Triangle Packing
by: Zhao, Jingyang, et al.
Published: (2024)

Improved Approximations for Dial-a-Ride Problems
by: Zhao, Jingyang, et al.
Published: (2026)

Dynamic Kernel Graph Sparsifiers
by: Cao, Yang, et al.
Published: (2022)

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
by: Zhao, Jingyang, et al.
Published: (2025)

Improved Approximations for the Unsplittable Capacitated Vehicle Routing Problem
by: Zhao, Jingyang, et al.
Published: (2026)

Approximation Algorithms for Packing Cycles and Paths in Complete Graphs
by: Zhao, Jingyang, et al.
Published: (2023)

Multidepot Capacitated Vehicle Routing with Improved Approximation Guarantees
by: Zhao, Jingyang, et al.
Published: (2023)

Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity
by: Zhao, Jingyang, et al.
Published: (2022)

An Improved Approximation Algorithm for Maximum Weight 3-Path Packing
by: Zhao, Jingyang, et al.
Published: (2025)

Approximation Algorithms for the Cumulative Vehicle Routing Problem with Stochastic Demands
by: Zhao, Jingyang, et al.
Published: (2025)

Improved Approximation for Ranking on General Graphs
by: Derakhshan, Mahsa, et al.
Published: (2025)

Parameterized Approximation Algorithms for TSP on Non-Metric Graphs
by: Zhao, Jingyang, et al.
Published: (2025)

Enhanced Approximation Algorithms for the Capacitated Location Routing Problem
by: Zhao, Jingyang, et al.
Published: (2025)

Polylogarithmic Approximation for Robust s-t Path
by: Li, Shi, et al.
Published: (2023)

Approximating Small Sparse Cuts
by: Anand, Aditya, et al.
Published: (2024)

Congestion-Approximators from the Bottom Up
by: Li, Jason, et al.
Published: (2024)

Hardness and Approximation Algorithms for Balanced Districting Problems
by: Dharangutte, Prathamesh, et al.
Published: (2025)

The Impact of Approximation on Algorithmic Progress
by: Li, Jeffery, et al.
Published: (2026)

Faster Weak Expander Decompositions and Approximate Max Flow
by: Fleischmann, Henry, et al.
Published: (2025)

Improved Approximation Algorithms for the Multiple-Depot Split Delivery Vehicle Routing Problem
by: Zhao, Jingyang, et al.
Published: (2026)

Sublinear Time Quantum Algorithm for Attention Approximation
by: Song, Zhao, et al.
Published: (2026)

Logarithmic Approximations for Fair k-Set Selection
by: Li, Shi, et al.
Published: (2025)

DynHAC: Fully Dynamic Approximate Hierarchical Agglomerative Clustering
by: Yu, Shangdi, et al.
Published: (2025)