You are cordially invited to our Monday Lecture & Colloquium
on October 22nd at 14:15 h & 16:00 h at TU Berlin.

__Location__**: **

Technische Universität Berlin

Straße des 17. Juni 136

10623 Berlin

__Time__: **Monday, October 22nd - 14:15 h**

__Lecture__: Alexander Fink (Queen Mary University London)

__Title__: Stiefel tropical linear spaces

As we tell our undergraduates, if K is a field, then there are a great number of different ways to describe a linear subspace of K^n. If the base is an algebraic object with less structure than a field, linear algebra becomes more subtle, and some of these descriptions cease to agree. One such setting is tropical geometry. Tropical geometers have reached consensus as to what the "correct" notion of tropical linear subspace is (one way to get it is by a vector of determinants). My subject will be one of the "wrong" descriptions, namely row spaces of matrices, which only produces a subset of the tropical linear spaces. Applications include generalisations of Mason's results from the '70s on presentations of transversal matroids, and a construction in the new area of tropical ideal theory.

This work is variously joint with Felipe Rinc\'on, Jorge Alberto Olarte, and Jeffrey and Noah Giansiracusa.

R

__Time__: **Monday, ****October 22nd** -
16:00 h

__Colloquium__: Akiyoshi Tsuchiya (Osaka University)

__Title__: Polyhedral characterizations of perfect graphs

__Abstract__:

Perfect graphs are important objects in graph theory. The perfect
graphs include many important families of graphs, and serve to
unify results relating colorings and cliques in those families.
One of the most famous and most important results is the strong
perfect graph theorem conjectured by Claude Berge and proved by
Chudnovsky, Robertson and Thomas. This theorem characterizes
perfect graphs. Our interest is to give other characterizations of
perfect graphs. In this talk, we construct several lattice
polytopes arising from a finite simple graph and characterize when
the graph is perfect in terms of the lattice polytopes.

This talk is based on joint work with Takayuki Hibi and Hidefumi
Ohsugi.

You are cordially invited to our next Monday Colloquium on
October 29th at 16:00 h at TU Berlin.

__Location__**: **

Technische Universität Berlin

Straße des 17. Juni 136

10623 Berlin

__Time__: **Monday, October 29th - 16:00 h**

__Colloquium__: Jan Goedgebeur (Ghent University**)**

__Title__: **Obstructions for 3-coloring graphs with
one forbidden induced subgraph**

For several graph classes without long induced paths there
exists a finite forbidden subgraph characterization for
k-colourability. Such a finite set of minimal obstructions allows
to provide a “no-certificate" which proves that a graph is not
k-colourable. We prove that there are only finitely many
4-critical P6-free graphs, and give the complete list that
consists of 24 graphs. In particular, we obtain a certifying
algorithm for 3-colouring P6-free graphs, which solves an open
problem posed by Golovach et al. (Here, P6 denotes the induced
path on six vertices.) Our result leads to the following dichotomy
theorem: if H is a connected graph, then there are finitely many
4-critical H-free graphs if and only if H is a subgraph of P6.
This answers a question of Seymour. The proof of our main result
involves two distinct automatic proofs, and an extensive
structural analysis by hand. In this talk we will mainly focus on
the algorithmic results by presenting a new algorithm for
generating all minimal forbidden subgraphs to k-colourability for
given graph classes. This algorithm (combined with new theoretical
results) has been successfully applied to fully characterise all
forbidden subgraphs for k-colourability for various classes of
graphs without long induced paths.

--------------B0C79390DF0CF419FB05C14C-- From i.brunke@inf.fu-berlin.de Thu Nov 01 12:41:47 2018 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (envelope-from

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

__Location__**: **

Humboldt-Universität zu Berlin

Institut für Informatik

Johann von Neumann-Haus

Rudower Chaussee 25

12489 Berlin

__Time__: **Monday, November 5th - 14:15 h**

__Lecture__: Henning Meyerhenke (Humboldt-Universität zu
Berlin)

__Title__: Algorithms for Large-scale Network Analysis

Network centrality measures indicate the importance of nodes
(or edges) in a network. In this talk we will discuss a few
popular measures and algorithms for computing complete or
partial node rankings based on these measures. These algorithms
are implemented in NetworKit, an open-source framework for
large-scale network analysis, on which we provide an overview,
too.

One focus of the talk will be on techniques for speeding up a
greedy (1-1/e)-approximation algorithm for the NP-hard group
closeness centrality problem.

Compared to a straightforward implementation, our approach is
orders of magnitude faster and, compared to a heuristic proposed
by Chen et al., we always find a solution with better quality in
a comparable running time in our experiments. Our

method Greedy++ allows us to approximate the group with maximum
closeness centrality on networks with up to hundreds of millions
of edges in minutes or at most a few hours.

In a comparison with the optimum, our experiments show that the
solution found by Greedy++ is actually much better than the
theoretical guarantee.

__Time__: **Monday, ****November 5th** -
16:00 h

__Colloquium__: Alexander van der Grinten (Universität zu
Köln)

__Title__: Scalable Katz Ranking Computation

__Abstract__:

Network analysis defines a number of centrality measures to identify the most central nodes in a network. Fast computation of those measures is a major challenge in algorithmic network analysis. Aside from closeness and betweenness, Katz centrality is one of the established centrality measures. We consider the problem of computing rankings for Katz centrality. In particular, we propose upper and lower bounds on the Katz score of a given node. While previous approaches relied on numerical approximation or heuristics to compute Katz centrality rankings, we construct an algorithm that iteratively improves those upper and lower bounds until a correct Katz ranking is obtained. For a certain class of inputs, this yields an optimal algorithm for Katz ranking computation. Furthermore, Experiments demonstrate that our algorithm outperforms both numerical approaches and heuristics with speedups between 1.5x and 3.5x, depending on the desired quality guarantees. Specifically, we provide efficient parallel CPU and GPU implementations of the algorithms that enable near real-time Katz centrality computation for graphs with hundreds of millions of nodes in fractions of seconds.

--------------48B0CBBC3FF41BA60B153F33-- From i.brunke@inf.fu-berlin.de Thu Nov 08 12:19:07 2018 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (envelope-fromYou are cordially invited to our Monday Lecture &
Colloquium on November 12th at 14:15 h & 16:00 h at HU
Berlin.

__Location__**: **

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
**

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/

Before

__Time__: **Monday, ****November 12th** -
16:00 h

__Colloquium__: Till Fluschnik (Technische Universität
Berlin)

__Title__: Fractals for Kernelization Lower Bounds

__Abstract__:

(Journal version appeared in SIAM Journal on Discrete Mathematics 2018.)

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

__Location__**: **

Technische Universität Berlin

Straße des 17. Juni 136

10623 Berlin

__Time__: **Monday, November 19th - 14:15 h**

__Lecture__: Jörg Rambau (Universität Bayreuth)

__Title__: **Optimal Diplomacy
**

Picture yourself in a committee numerically evaluating a
scientific proposal that you find worth funding: A rating of "0"
means "easily achievable but not at all innovative", whereas "1"
means "very innovative but totally unachievable". In both cases,
funding is not recommended. In contrast, "1/2" means "innovative
and achievable", in other words: worth funding. All intermediate
values are possible. Any rating that is closer to "1/2" than to
"1/4" and "3/4" is considered a vote for funding. The proposal
passes if 50% of the members support funding, i.e., rate the
proposal between "1/2 - 1/8" and "1/2 + 1/8". Now, there are 10
meetings ahead of you. You have an idea how the opinions of the
committee members develop. How should your statements look like
in the meetings one through ten if you want to have eventually
as many supporters of the proposal as possible? This is an
instance of the "Optimal Diplomacy Problem" (ODP), introduced by
Hegselmann, König, Kurz, Niemann, and Rambau in 2010, published
in 2015. How do opinions interact? How is the dynamics of
opinions modeled mathematically? What does it mean to "influence
others" in this dynamical system? How difficult is it to find
optimal diplomacies? How can one compute or at least narrow down
optimal diplomacies? What happens if not all informations about
committee members are known to the diplomat? In this talk we
will discuss our findings, techniques, and open questions based
on the arguably most influential model: the Bounded-Confidence
model by Hegselmann and Krause. We draw on joint work with
Andreas Deuerling, Rainer Hegselmann, Stefan König, Julia
Kinkel, Sascha Kurz, and Christoph Niemann.

__Time__: **Monday, ****November 19th** -
16:00 h

__Colloquium__: Jean-Philippe Labbé (Freie Universität
Berlin)

__Title__: (At least) three hard problems behind the
multiassociahedron

__Abstract__:

--------------86EBBCF3B65B9D6142037AA1-- From i.brunke@inf.fu-berlin.de Tue Nov 20 16:25:21 2018 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (envelope-from

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

__Location__**: **

Humboldt-Universität zu Berlin

Institut für Informatik

Johann von Neumann-Haus

Rudower Chaussee 25

12489 Berlin

__Time__: **Monday, November 26th - 14:15 h**

__Lecture__: Marcin Pilipczuk (University of Warsaw)

__Title__: **The square root phenomenon:
subexponential algorithms in sparse graph classes
**

While most NP-hard graph problems remain NP-hard when restricted to planar graphs, they become somewhat simpler: they often admit algorithms with running time exponential in the square root of the size of the graph (or some other meaningful parameter). This behavior has been dubbed "the square root phenomenon". For many problems, such an algorithm follows from the theory of bidimensionality relying on a linear dependency on the size of the largest grid minor and treewidth of a planar graph. In recent years we have seen a number of other algorithmic techniques, significantly extending the boundary of the applicability of the "square root phenomenon". In my talk I will survey this area and highlight main algorithmic approaches.

Before

__Time__: **Monday, ****November 26th** -
16:00 h

__Colloquium__: Sebastian Siebertz (Humboldt-Universität zu
Berlin)

__Title__: First-order interpretations of sparse graph
classes

__Abstract__:

--------------8AD132702276B7DB3B5F6A7A-- From rote@inf.fu-berlin.de Mon Dec 03 11:33:21 2018 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from

You are cordially invited to our next Monday Lecture &
Colloquium on December 10th at 14:15 h & 16:00 h at FU Berlin.

__Location__**: **

Freie Universität Berlin

Takustr. 9

14195 Berlin

__Time__: **Monday, December 10th - 14:15 h**

__Lecture__: Marijn Heule (University** of Texas,
Austin)**

__Title__: Everything's Bigger in Texas: "The Largest Math
Proof Ever"

Progress in satisfiability (SAT) solving has enabled answering
long-standing open questions in mathematics completely
automatically resulting in clever though potentially gigantic
proofs. We illustrate the success of this approach by presenting
the solution of the Boolean Pythagorean triples problem. We also
produced and validated a proof of the solution, which has been
called the ``largest math proof ever''. The enormous size of the
proof is not important. In fact a shorter proof would have been
preferable. However, the size shows that automated tools
combined with super computing facilitate solving bigger
problems. Moreover, the proof of 200 terabytes can now be
validated using highly trustworthy systems, demonstrating that
we can check the correctness of proofs no matter their size.

__Time__: **Monday, ****December 10th** -
16:00 h s.t.

__Colloquium__: Ander Lamaison (Freie Universität Berlin**)**

__Title__: Ramsey density of infinite paths

In a
two-colouring of the edges of the complete graph on the natural
numbers, what is the densest monochromatic infinite path that we
can always find? We measure the density of a path by the upper
asymptotic density of its vertex set. This question was first
studied by Erdös and Galvin, who proved that the best density is
between 2/3 and 8/9. In this talk we settle this question by
proving that we can always find a monochromatic path of upper
density at least (12+sqrt(8))/17=0.87226…, and constructing a
two-colouring in which no denser path exists. This represents
joint work with Jan Corsten, Louis DeBiasio and Richard Lang.

--------------0B873EBE9050253E371C2135--
From rote@inf.fu-berlin.de Fri Dec 14 11:58:14 2018
Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66])
by list1.zedat.fu-berlin.de (Exim 4.85)
for facets-of-complexity@lists.fu-berlin.de with esmtps
(TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256)
(envelope-from