[Facets-of-complexity] Invitation to Monday Lecture & Colloquium - November 12th 2018

[Ita Brunke <i.brunke@inf.fu-berlin.de>]

You are cordially invited to our Monday Lecture & Colloquium on November 12th at 14:15 h & 16:00 h at HU Berlin.

Location:

Humboldt-Kabinett (between House 3&4 / 1st Floor) [British Reading]
Humboldt-Universität zu Berlin
Institut für Informatik
Johann von Neumann-Haus
Rudower Chaussee 25
12489 Berlin

Time: Monday, November 12th - 14:15 h

Lecture: Christoph Berkholz (Humboldt-Universität zu Berlin)

Title: A comparison of algebraic and semi-algebraic proof systems

Abstract:

In this lecture I will give an introduction to algebraic and semi-algebraic methods for proving the unsatisfiability of systems of real polynomial 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-algebraic proof systems Sherali-Adams and sum-of-squares (a.k.a. Lasserre), which are based on linear and semi-definite programming relaxations. On the other hand, I will discuss polynomial calculus, which is a dynamic algebraic proof system that models Gröbner basis computations.
I am going to present two recent results on the relative strength between algebraic and semi-algebraic proof systems:¹
The first result is that sum-of-squares simulates polynomial calculus: any polynomial calculus refutation of degree d can be transformed into a sum-of-squares refutation of degree 2d and only polynomial increase in size. In contrast, the second result shows that this is not the case for Sherali-Adams: there are systems of polynomial equations that have polynomial calculus refutations of degree 3 and polynomial size, but require Sherali-Adams refutations of large degree and exponential size.

¹) this work was presented at STACS 2018; a preprint is available at https://eccc.weizmann.ac.il/report/2017/154/

Coffee & Tea Break :

Before Humboldt-Kabinett (between House 3&4 / 1st Floor) [British Reading]

Time: Monday, November 12th - 16:00 h

Colloquium: Till Fluschnik (Technische Universität Berlin)

Title: Fractals for Kernelization Lower Bounds

Abstract:

Kernelization is a key concept in fixed-parameter algorithmics for polynomial-time preprocessing of NP-hard problems. Herein one seeks to preprocess any instance of a parameterized problem with parameter k to an “equivalent” instance (the so-called (problem) kernel) with size upper-bounded by some function (preferably by some polynomial) in k. Ten years ago, with the development of the so-called composition technique, first NP-hard parameterized problems were proven to presumably admit no polynomial-size problem kernel. Since then the line of Research concerning "limits of kernelization" received a lot of attention. We contribute to this line and present a new technique exploiting triangle-based fractal structures (so called T-fractals) for extending the range of applicability of compositions. Our technique makes it possible to prove new no-polynomial-kernel results for a number of graph problems dealing with some sort of cuts, hereby answering an open question stated in 2009. Our T-fractals---due to their fractal structure---admit easy-to-prove useful properties exploitable for constructing compositions. They also apply for planar as well as directed variants of the basic problems and also apply to both edge and vertex-deletion problems. This is joint work with Danny Hermelin, André Nichterlein, and Rolf Niedermeier.
(Journal version appeared in SIAM Journal on Discrete Mathematics 2018.)