21 citations · 50 across the 18 of their papers we have counts for
20 papers
On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank
Adam Kurpisz, Lucas Slot, Mikhail Zaytsev
We analyze the sum-of-squares rank of unweighted instances of the Minimum Knapsack (MK) problem, i.e., minimization of for 0/1 variables under the constraint $\s…
Agnostic learning in (almost) optimal time via Gaussian surface area
Lucas Pesenti, Lucas Slot, Manuel Wiedmer
The complexity of learning a concept class under Gaussian marginals in the difficult agnostic model is closely related to its -approximability by low-degree polynomials. For a…
Robustness of Persistent Topological Features and Minimum Homological Cuts
Pepijn Roos Hoefgeest, Lucas Slot
Persistent homology is a popular method for computing topological features of (metric) data. Standard approaches based on the Čech or Rips filtration are stable under small perturb…
Hesse's Redemption: Efficient Convex Polynomial Programming
Lucas Slot, David Steurer, Manuel Wiedmer
Efficient algorithms for convex optimization, such as the ellipsoid method, require an a priori bound on the radius of a ball around the origin guaranteed to contain an optimal sol…
Low degree conjecture implies sharp computational thresholds in stochastic block model
Jingqiu Ding, Yiding Hua, Lucas Slot +1
We investigate implications of the (extended) low-degree conjecture (recently formalized in [MW23]) in the context of the symmetric stochastic block model. Assuming the conjecture…
Computational complexity of sum-of-squares bounds for copositive programs
Marilena Palomba, Lucas Slot, Luis Felipe Vargas +1
In recent years, copositive programming has received significant attention for its ability to model hard problems in both discrete and continuous optimization. Several relaxations…
A Christoffel-like function for high-dimensional support inference in graphical models
Jean-Bernard Lasserre, Lucas Slot
Christoffel polynomials are classical tools from approximation theory. They can be used to estimate the (compact) support of a measure on based on its low-degree…
An Overview of Convergence Rates for Sum of Squares Hierarchies in Polynomial Optimization
Monique Laurent, Lucas Slot
In this survey we consider polynomial optimization problems, asking to minimize a polynomial function over a compact semialgebraic set, defined by polynomial inequalities. This mod…
Testably Learning Polynomial Threshold Functions
Lucas Slot, Stefan Tiegel, Manuel Wiedmer
Rubinfeld & Vasilyan recently introduced the framework of testable learning as an extension of the classical agnostic model. It relaxes distributional assumptions which are difficu…
Nonconvergence of a sum-of-squares hierarchy for global polynomial optimization based on push-forward measures
Lucas Slot, Manuel Wiedmer
Let be a closed set, and consider the problem of computing the minimum of a polynomial on . Given a measure suppo…
A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization
Sander Gribling, Sven Polak, Lucas Slot
The moment-sum-of-squares (moment-SOS) hierarchy is one of the most celebrated and widely applied methods for approximating the minimum of an n-variate polynomial over a feasible r…
Degree bounds for Putinar's Positivstellensatz on the hypercube
Lorenzo Baldi, Lucas Slot
The Positivstellensätze of Putinar and Schmüdgen show that any polynomial positive on a compact semialgebraic set can be represented using sums of squares. Recently, there has…
The Christoffel-Darboux kernel for topological data analysis
Pepijn Roos Hoefgeest, Lucas Slot
Persistent homology has been widely used to study the topology of point clouds in . Standard approaches are very sensitive to outliers, and their computational comple…
A recursive theta body for hypergraphs
Davi Castro-Silva, Fernando Mário de Oliveira Filho, Lucas Slot +1
The theta body of a graph, introduced by Grötschel, Lovász, and Schrijver in 1986, is a tractable relaxation of the independent-set polytope derived from the Lovász theta number. I…
Sum-of-squares hierarchies for polynomial optimization and the Christoffel-Darboux kernel
Lucas Slot
Consider the problem of minimizing a polynomial over a compact semialgebraic set . Lasserre introduces hierarchies of semidefinite programs…
An effective version of Schmüdgen's Positivstellensatz for the hypercube
Monique Laurent, Lucas Slot
Let be a compact semialgebraic set and let be a polynomial nonnegative on . Schmüdgen's Positivstellensatz then states that for any , the no…
A recursive Lovász theta number for simplex-avoiding sets
Davi Castro-Silva, Fernando Mário de Oliveira Filho, Lucas Slot +1
We recursively extend the Lovász theta number to geometric hypergraphs on the unit sphere and on Euclidean space, obtaining an upper bound for the independence ratio of these hyper…
Sum-of-squares hierarchies for binary polynomial optimization
Lucas Slot, Monique Laurent
We consider the sum-of-squares hierarchy of approximations for the problem of minimizing a polynomial over the boolean hypercube . This hierarchy prov…
Near-optimal analysis of Lasserre's univariate measure-based bounds for multivariate polynomial optimization
Lucas Slot, Monique Laurent
We consider a hierarchy of upper approximations for the minimization of a polynomial over a compact set proposed recently by Lasserre (arXiv:1907.097…
Improved convergence analysis of Lasserre's measure-based upper bounds for polynomial minimization on compact sets
Lucas Slot, Monique Laurent
We consider the problem of computing the minimum value of a polynomial over a compact set , which can be reformulated as finding a probab…