BEGIN:VCALENDAR CALSCALE:GREGORIAN PRODID:iCalendar-Ruby VERSION:2.0 BEGIN:VEVENT DESCRIPTION: In this lecture I will give an introduction to algebraic and s emi-algebraic methods for proving the unsatisfiability of systems of real p olynomial equations over the Boolean hypercube. The main goal of this talk is to compare the relative strength of these approaches using methods from proof complexity. On the one hand\, I will focus on the static semi-alge braic proof systems Sherali-Adams and sum-of-squares (a.k.a. Lasserre)\, wh ich are based on linear and semi-definite programming relaxations. On the o ther hand\, I will discuss polynomial calculus\, which is a dynamic algebra ic proof system that models Gröbner basis computations. I am going to pr esent two recent results on the relative strength between algebraic and sem i-algebraic proof systems:¹ The first result is that sum-of-squares simu lates polynomial calculus: any polynomial calculus refutation of degree d c an be transformed into a sum-of-squares refutation of degree 2d and only po lynomial increase in size. In contrast\, the second result shows that this is not the case for Sherali-Adams: there are systems of polynomial equation s that have polynomial calculus refutations of degree 3 and polynomial size \, but require Sherali-Adams refutations of large degree and exponential si ze. ¹) this work was presented at STACS 2018\; a preprint is available a t https://eccc.weizmann.ac.il/report/2017/154/ DTSTAMP:20181108T142800 DTSTART:20181112T141500 CLASS:PUBLIC LOCATION:Humboldt-Universität zu Berlin\n Institut für Informatik\n Humbold t-Kabinett (between House 3&4 / 1st Floor [British Reading])\n Johann von N eumann-Haus\n Rudower Chaussee 25\n 12489 Berlin SEQUENCE:0 SUMMARY:Christoph Berkholz (Humboldt-Universität zu Berlin): A comparison o f algebraic and semi-algebraic proof systems UID:94442671@/www.mi.fu-berlin.de URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20181112-L-Ber kholz.html END:VEVENT END:VCALENDAR