9 papers
Computing Lewis weights to high precision using local relative smoothness
Sander Gribling, Aaron Sidford, Chenyi Zhang
We provide algorithms that compute -estimates of the -Lewis weights of a matrix for using rounds of lever…
Squared polynomial approximation kernels for the hypercube: improved error bounds and implications for Lasserre hierarchies
Sander Gribling, Etienne de Klerk, Juan C. Vera
We propose a new family of polynomial approximation kernels for approximating nonnegative polynomials on the hypercube . Our Kernels produce polynomial sums-of-squares of…
Quantum speedups for linear programming via interior point methods
Simon Apers, Sander Gribling
We describe a quantum algorithm based on an interior point method for solving a linear program with inequality constraints on variables. The algorithm explicitly returns a…
Self-concordant Schrödinger operators: spectral gaps and optimization without condition numbers
Sander Gribling, Simon Apers, Harold Nieuwboer +1
Spectral gaps play a fundamental role in many areas of mathematics, computer science, and physics. In quantum mechanics, the spectral gap of Schrödinger operators has a long histo…
Revisiting the convergence rate of the Lasserre hierarchy for polynomial optimization over the hypercube
Sander Gribling, Etienne de Klerk, Juan Vera
We revisit the problem of minimizing a given polynomial on the hypercube . Lasserre's hierarchy (also known as the moment- or sum-of-squares hierarchy) provides a seq…
Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs
Sander Gribling, Lennart Sinjorgo, Renata Sotirov
We study polynomial-time approximation algorithms for the Quantum Max-Cut (QMC) problem. Given an edge-weighted graph on n vertices, the QMC problem is to determine the largest…