[Proof Complexity] MIAO seminar Mon Sep 19 at 14:00 CET with Ilario Bonacina: On vanishing sums of roots of unity in polynomial calculus and sum-of-squares

[Jakob Nordström]

Dear all,

In the first seminar in the MIAO series after the summer break, on Monday September 19 at 14:00 Ilario Bonacina from Universitat Politècnica de Catalunya will give a talk titled "On vanishing sums of roots of unity in polynomial calculus and sum-of-squares". You find the abstract at the bottom of this message.

This will be a video seminar at https://lu-se.zoom.us/j/61925271827 . Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://www.youtube.com/channel/UCN0G2Wfl9-sAKrVLVza7z4A for people who would like to hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners an overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)

More information about upcoming MIAO seminars can be found at http://www.jakobnordstrom.se/miao-seminars/ . If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

Monday Sep 19 at 14:00 on Zoom
On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
(Ilario Bonacina, Universitat Politècnica de Catalunya)

Vanishing sums of roots of unity can be seen as a natural generalization of knapsack from Boolean variables to variables taking values over the roots of unity. We show that these sums are hard to prove for polynomial calculus and for sum-of-squares, both in terms of degree and size. This talk is based on a joint work with M. Lauria and N. Galesi.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +46 70 742 21 98
http://www.jakobnordstrom.se