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.)
