Quantum speedups for linear programming via interior point methods
From MaRDI portal
Cites work
- _p row sampling by Lewis weights
- A faster algorithm for solving general LPs
- A faster cutting plane method and its implications for combinatorial and convex optimization
- A mathematical view of interior-point methods in convex optimization
- A new algorithm for minimizing convex functions over convex sets
- A new polynomial-time algorithm for linear programming
- A polynomial-time algorithm, based on Newton's method, for linear programming
- A quantum-inspired classical algorithm for recommendation systems
- A strong direct product theorem for quantum query complexity
- A technique for bounding the number of iterations in path following algorithms
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Computing Lewis weights to high precision
- Efficient use of quantum linear system algorithms in inexact infeasible IPMs for linear optimization
- Extensions of Lipschitz mappings into a Hilbert space
- Finite dimensional subspaces of $L_{p}$
- From independence to expansion and back again
- Graph sparsification by effective resistances
- scientific article; zbMATH DE number 3644821 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- Improved iteration complexities for overconstrained p -norm regression
- Improvements in quantum SDP-solving with applications
- Interior point methods are not worse than simplex
- Iterative row sampling
- L1 Regression with Lewis Weights Subsampling
- Las Vegas algorithms for linear and integer programming when the dimension is small
- Linear Programming in Linear Time When the Dimension Is Fixed
- Low-rank approximation and regression in input sparsity time
- Minimum cost flows, MDPs, and ℓ 1 -regression in nearly linear time for dense instances
- Minimum-volume ellipsoids. Theory and algorithms
- Near-optimal Quantum algorithms for multivariate mean estimation
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- On sampling determinantal and Pfaffian point processes on a quantum computer
- On the composition of randomized query complexity and approximate degree
- Optimal direct sum results for deterministic and randomized decision tree complexity
- Optimality of the Johnson-Lindenstrauss lemma
- Optimizing quantum optimization algorithms via faster quantum gradient computation
- Proceedings of the 36th annual ACM-SIAM symposium on discrete algorithms, SODA 2025, New Orleans, LA, USA, January 12--15, 2025
- Quantum lower bounds by polynomials
- Quantum Query Complexity of Some Graph Problems
- Quantum SDP solvers: large speed-ups, optimality, and applications to quantum learning
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- Quantum speed-ups for solving semidefinite programs
- Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
- Quantum speedup of Monte Carlo methods
- Randomized Algorithms for Matrices and Data
- Reflections for quantum query algorithms
- Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning
- Solving Linear Programs in the Current Matrix Multiplication Time
- Solving tall dense linear programs in nearly linear time
- Space-efficient interior point method, with applications to linear programming and maximum weight bipartite matching
- Sublinear time algorithms
- The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
- Uniform sampling for matrix approximation
- User-friendly tail bounds for sums of random matrices
- Volumetric path following algorithms for linear programming
This page was built for publication: Quantum speedups for linear programming via interior point methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6858928)
