Polynomial optimization methods often encompass many major scalability issues on the practical side. Fortunately, for many real-world problems, we can look at them in the eyes and exploit the inherent data structure arising from the input cost and constraints. The first part of my lecture will focus on the notion of 'correlative sparsity', occurring when there are few correlations between the variables of the input problem. The second part will present a complementary framework, where we show how to exploit a distinct notion of sparsity, called 'term sparsity', occurring when there are a small number of terms involved in the input problem by comparison with the fully dense case. At last but not least, I will present a very recently developed type of sparsity that we call 'ideal-sparsity', which exploits the presence of equality constraints. Several illustrations will be provided on important applications arising from various fields, including computer arithmetic, robustness of deep networks, quantum entanglement, optimal power-flow, and matrix factorization ranks.[-]

Polynomial optimization methods often encompass many major scalability issues on the practical side. Fortunately, for many real-world problems, we can look at them in the eyes and exploit the inherent data structure arising from the input cost and constraints. The first part of my lecture will focus on the notion of 'correlative sparsity', occurring when there are few correlations between the variables of the input problem. The second part will present a complementary framework, where we show how to exploit a distinct notion of sparsity, called 'term sparsity', occurring when there are a small number of terms involved in the input problem by comparison with the fully dense case. At last but not least, I will present a very recently developed type of sparsity that we call 'ideal-sparsity', which exploits the presence of equality constraints. Several illustrations will be provided on important applications arising from various fields, including computer arithmetic, robustness of deep networks, quantum entanglement, optimal power-flow, and matrix factorization ranks.[-]

Asymmetric cryptographic constructions used today could be attacked given a powerful enough quantum computer. Even if such a computer does not exist yet, it is important to anticipate its possible construction and to prepare a transition to cryptographic tools having a security resistant against attacks from quantum computers. I will introduce lattice-based cryptography, which is the most promising candidate to build post-quantum cryptographic constructions, and in particular, how we build efficient constructions based on structured lattice problems.[-]