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.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20181112-L-Berkholz.html
END:VEVENT
END:VCALENDAR