9 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…
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-degre…
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 pertur…
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…