Source author record

Lucas Slot

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.OC math.CO math.MG

Catalog footprint

Research overview

3works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A recursive Lovász theta number for simplex-avoiding sets

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 hypergraphs. As an application we reprove a result in Euclidean Ramsey theory in the measurable setting, namely that every $k$ -simplex is exponentially Ramsey, and we improve existing bounds for the base of the exponential.

preprint2022arXiv

Sum-of-squares hierarchies for binary polynomial optimization

We consider the sum-of-squares hierarchy of approximations for the problem of minimizing a polynomial $f$ over the boolean hypercube $\mathbb{B}^{n}=\{0,1\}^n$ . This hierarchy provides for each integer $r \in \mathbb{N}$ a lower bound $f_{(r)}$ on the minimum $f_{\min}$ of $f$ , given by the largest scalar $λ$ for which the polynomial $f - λ$ is a sum-of-squares on $\mathbb{B}^{n}$ with degree at most $2r$ . We analyze the quality of these bounds by estimating the worst-case error $f_{\min} - f_{(r)}$ in terms of the least roots of the Krawtchouk polynomials. As a consequence, for fixed $t \in [0, 1/2]$ , we can show that this worst-case error in the regime $r \approx t \cdot n$ is of the order $1/2 - \sqrt{t(1-t)}$ as $n$ tends to $\infty$ . Our proof combines classical Fourier analysis on $\mathbb{B}^{n}$ with the polynomial kernel technique and existing results on the extremal roots of Krawtchouk polynomials. This link to roots of orthogonal polynomials relies on a connection between the hierarchy of lower bounds $f_{(r)}$ and another hierarchy of upper bounds $f^{(r)}$ , for which we are also able to establish the same error analysis. Our analysis extends to the minimization of a polynomial over the $q$ -ary cube $(\mathbb{Z}/q\mathbb{Z})^{n}$ .

preprint2020arXiv

Improved convergence analysis of Lasserre's measure-based upper bounds for polynomial minimization on compact sets

We consider the problem of computing the minimum value $f_{\min,K}$ of a polynomial $f$ over a compact set $K \subseteq \mathbb{R}^n$ , which can be reformulated as finding a probability measure $ν$ on $K$ minimizing $\int_K f dν$ . Lasserre showed that it suffices to consider such measures of the form $ν= qμ$ , where $q$ is a sum-of-squares polynomial and $μ$ is a given Borel measure supported on $K$ . By bounding the degree of $q$ by $2r$ one gets a converging hierarchy of upper bounds $f^{(r)}$ for $f_{\min,K}$ . When $K$ is the hypercube $[-1, 1]^n$ , equipped with the Chebyshev measure, the parameters $f^{(r)}$ are known to converge to $f_{\min,K}$ at a rate in $O(1/r^2)$ . We extend this error estimate to a wider class of convex bodies, while also allowing for a broader class of reference measures, including the Lebesgue measure. Our analysis applies to simplices, balls and convex bodies that locally look like a ball. In addition, we show an error estimate in $O(\log r / r)$ when $K$ satisfies a minor geometrical condition, and in $O(\log^2 r / r^2)$ when $K$ is a convex body, equipped with the Lebesgue measure. This improves upon the currently best known error estimates in $O(1 / \sqrt{r})$ and $O(1/r)$ for these two respective cases.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.