You are cordially invited to our first Monday Lecture &
Colloquium since Corona crisis stopped our curriculum.

Monday Lecture & Colloquium will be held online.
Invitation for Zoom will follow by Invitor.

First Monday Lecture & Colloquium will start on October
19th 2020 at 14:15 h & 16:00 h.

Zoom - Invitation will follow

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

__Lecture__: Mikkel Abrahamsen (University of
Copenhagen)

__Title__: A framework for ∃R-completeness of
two-dimensional packing problems

We show that
many natural two-dimensional packing problems are
algorithmically equivalent to finding real roots of
multivariate polynomials. A two-dimensional packing problem is
defined by the type of pieces, containers, and motions that
are allowed. The aim is to decide if a given set of pieces can
be placed inside a given container. The pieces must be placed
so that they are pairwise interior-disjoint, and only motions
of the allowed type can be used to move them there. We
establish a framework which enables us to show that for many
combinations of allowed pieces, containers, and motions, the
resulting problem is ∃R-complete. This means that the problem
is equivalent (under polynomial time reductions) to deciding
whether a given system of polynomial equations and
inequalities with integer coefficients has a real solution. We
consider packing problems where only translations are allowed
as the motions, and problems where arbitrary rigid motions are
allowed, i.e., both translations and rotations. When rotations
are allowed, we show that the following combinations of
allowed pieces and containers are ∃R-complete: - simple
polygons, each of which has at most 8 corners, into a square,
- convex objects bounded by line segments and hyperbolic
curves into a square, - convex polygons into a container
bounded by line segments and hyperbolic curves. Restricted to
translations, we show that the following combinations are
∃R-complete: - objects bounded by segments and hyperbolic
curves into a square, - convex polygons into a container
bounded by segments and hyperbolic curves. Joint work by
Mikkel Abrahamsen, Tillmann Miltzow, and Nadja Seiferth. The
paper has been accepted for FOCS.

**Wherever you are.**** **

__Colloquium__: Tillmann Miltzow (Utrecht University**)**

__Title__: A practical algorithm with performance
guarantees for the art-gallery problem

Given a closed simple polygon P, we
say two points p,q see each other if the segment pq is fully
contained in P. The art gallery problem seeks a minimum size
set G⊂P of guards that sees P completely. The only known
algorithm to solve the art gallery problem exactly is
attributed to Sharir and uses algebraic methods. As the art
gallery problem is ∃R-complete, it seems impossible to avoid
algebraic methods without additional assumptions.

To circumvent this problem, we introduce the notion of vision
stability.

In order to describe vision stability, consider an enhanced
guard that can see "around the corner" by an angle of δ or a
diminished guard whose vision is "blocked" by an angle δ by
reflex vertices. A polygon P has vision stability δ if the
optimal number of enhanced guards to guard P is the same as
the optimal number of diminished guards to guard P. We will
argue that most relevant polygons are vision-stable. We
describe a one-shot algorithm that computes an optimal guard
set for vision-stable polygons using polynomial time besides
solving one integer program.

We implemented an iterative version of the vision-stable
algorithm. Its practical performance is slower, but comparable
to other

state-of-the-art algorithms. Our iterative algorithm is a
variation of the one-shot algorithm. It delays some steps and
only computes them only when deemed necessary. Given a chord c
of a polygon, we denote by n(c) the number of vertices visible
from c. The chord-width of a polygon is the maximum n(c) over
all possible chords c. The set of vision-stable polygons
admits an FPT algorithm when parametrized by the chord-width.
Furthermore, the one-shot algorithm runs in FPT time when
parameterized by the number of reflex vertices.

Joint work by Simon Hengeveld & Tillmann Miltzow.

please find invitation link for zoom here:

https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

You may also find the link on our homepage:

http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Valid for all Monday Lectures to come for winter term 20/21.

You are cordially invited to our first Monday Lecture &
Colloquium since Corona crisis stopped our curriculum.

Monday Lecture & Colloquium will be held online.
Invitation for Zoom will follow by Invitor.

First Monday Lecture & Colloquium will start on October
19th 2020 at 14:15 h & 16:00 h.

Zoom - Invitation will follow

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

__Lecture__: Mikkel Abrahamsen (University of
Copenhagen)

__Title__: A framework for ∃R-completeness of
two-dimensional packing problems

We show
that many natural two-dimensional packing problems are
algorithmically equivalent to finding real roots of
multivariate polynomials. A two-dimensional packing problem
is defined by the type of pieces, containers, and motions
that are allowed. The aim is to decide if a given set of
pieces can be placed inside a given container. The pieces
must be placed so that they are pairwise interior-disjoint,
and only motions of the allowed type can be used to move
them there. We establish a framework which enables us to
show that for many combinations of allowed pieces,
containers, and motions, the resulting problem is
∃R-complete. This means that the problem is equivalent
(under polynomial time reductions) to deciding whether a
given system of polynomial equations and inequalities with
integer coefficients has a real solution. We consider
packing problems where only translations are allowed as the
motions, and problems where arbitrary rigid motions are
allowed, i.e., both translations and rotations. When
rotations are allowed, we show that the following
combinations of allowed pieces and containers are
∃R-complete: - simple polygons, each of which has at most 8
corners, into a square, - convex objects bounded by line
segments and hyperbolic curves into a square, - convex
polygons into a container bounded by line segments and
hyperbolic curves. Restricted to translations, we show that
the following combinations are ∃R-complete: - objects
bounded by segments and hyperbolic curves into a square, -
convex polygons into a container bounded by segments and
hyperbolic curves. Joint work by Mikkel Abrahamsen, Tillmann
Miltzow, and Nadja Seiferth. The paper has been accepted for
FOCS.

**Wherever you are.**** **

__Colloquium__: Tillmann Miltzow (Utrecht University**)**

__Title__: A practical algorithm with performance
guarantees for the art-gallery problem

Given a closed simple polygon P,
we say two points p,q see each other if the segment pq is
fully contained in P. The art gallery problem seeks a
minimum size set G⊂P of guards that sees P completely. The
only known algorithm to solve the art gallery problem
exactly is attributed to Sharir and uses algebraic methods.
As the art gallery problem is ∃R-complete, it seems
impossible to avoid algebraic methods without additional
assumptions.

To circumvent this problem, we introduce the notion of
vision stability.

In order to describe vision stability, consider an enhanced
guard that can see "around the corner" by an angle of δ or a
diminished guard whose vision is "blocked" by an angle δ by
reflex vertices. A polygon P has vision stability δ if the
optimal number of enhanced guards to guard P is the same as
the optimal number of diminished guards to guard P. We will
argue that most relevant polygons are vision-stable. We
describe a one-shot algorithm that computes an optimal guard
set for vision-stable polygons using polynomial time besides
solving one integer program.

We implemented an iterative version of the vision-stable
algorithm. Its practical performance is slower, but
comparable to other

state-of-the-art algorithms. Our iterative algorithm is a
variation of the one-shot algorithm. It delays some steps
and only computes them only when deemed necessary. Given a
chord c of a polygon, we denote by n(c) the number of
vertices visible from c. The chord-width of a polygon is the
maximum n(c) over all possible chords c. The set of
vision-stable polygons admits an FPT algorithm when
parametrized by the chord-width. Furthermore, the one-shot
algorithm runs in FPT time when parameterized by the number
of reflex vertices.

Joint work by Simon Hengeveld & Tillmann Miltzow.

You are cordially invited to our second Monday Lecture since
Corona crisis stopped our curriculum.

All Monday Lectures and Colloquia of winter term 20/21 will be
held online via zoom.

You may find valid Invitation for zoom throughout all winter
term here:

http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Invitation link:

https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

Second Monday Lecture will be on October 26th 2020 at 14:15 h.

Zoom - Invitation

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

__Lecture__: Sophie Spirkl (University of Waterloo)

__Title__: k-coloring graphs with forbidden induced
subgraphs

A k-coloring of
a graph G is a function c that assigns an integer between 1 and
k to every vertex of G such that c(u) is not equal to c(v) for
every edge uv of G. Deciding, given a graph G, whether G has a
k-coloring, is NP-hard for all k at least 3.

In this talk, we will consider what happens when we restrict the input, that is: For a graph H and integer k, what is the complexity of deciding if a given graph G with no induced subgraph isomorphic to H has a k-coloring?

We know the answer for many pairs H and k. Possibly the most interesting open cases are those in which H is a path; I will talk about recent results and open questions related to this.

You are cordially invited to our next Monday Lecture.

All Monday Lectures and Colloquia of winter term 20/21 will be
held online via zoom.

You may find valid Invitation for zoom throughout all winter
term here:

http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Invitation link:

https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

Monday Lecture will be on November 2nd 2020 at 14:15 h.

Zoom - Invitation

__Time__: **Monday, November 2nd - 14:15 h**

__Lecture__: Markus Bläser (Universität Saarbrücken)

__Title__: Irreversibility of tensors of minimal border
rank and barriers for fast matrix multiplication

Determining
the asymptotic algebraic complexity of matrix multiplication
is a central problem in algebraic complexity theory. The best
upper bounds on the so-called exponent of matrix
multiplication if obtained by starting with an "efficient"
tensor, taking a high power and degenerating a matrix
multiplication out of it. In the recent years,
several so-called barrier results have been established. A
barrier result shows a lower bound on the best upper bound
for the exponent of matrix multiplication that can be
obtained by a certain restriction starting with a certain
tensor. We prove the following barrier over the complex
numbers: Starting with a tensor of minimal border rank
satisfying a certain genericity condition, except for the
diagonal tensor, it is impossible to prove ω = 2 using
arbitrary restrictions. This is astonishing since the
tensors of minimal border rank look like the most natural
candidates for designing fast matrix multiplication
algorithms. We prove this by showing that all of these
tensors are irreversible, using a structural
characterisation of these tensors. Joint
work with Vladimir Lysikov.

You are cordially invited to our next Monday Lecture.

All Monday Lectures and Colloquia of winter term 20/21 will be
held online via zoom.

You may find valid Invitation for zoom throughout all winter term
here:

http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Invitation link:

https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

Monday Lecture will be on November 16th 2020 at 14:15 h.

Zoom - Invitation

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

__Lecture__: Lisa Sauermann (IAS, Princeton)

__Title__: On the extension complexity of low-dimensional
polytopes

You are cordially invited to our next Monday Lecture.

All Monday Lectures and Colloquia of winter term 2020/21 will be
given online via zoom.

http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Invitation link:

https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

Monday Lecture will be on November 30th 2020 at 14:15 h.

Zoom - Invitation

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

__Lecture__: Stefan Mengel (CNRS)

__Title__: A Biased Introduction to Decomposable Negation
Normal Form**s**

--------------A05D3B73ECAFDE788B55CD50-- From itabrunke@zedat.fu-berlin.de Wed Dec 02 18:30:20 2020 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from

You are cordially invited to our next Monday Lecture. Next
Monday, there will be the hearing of the PhD candidates.

We will have three talks. Talks will be 30 min. 15 min
discussions, 15 min break.

All Monday Lectures and Colloquia of winter term 2020/21 will be
given online via zoom.

http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Invitation link:

https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

Monday Lecture will be on December 7th 2020 at 14:00 h, 15:00,
16:00.

Zoom - Invitation

__Time__: **Monday, December 7th - 14:00 h**

__Lecture__: Hussein Houdrouge

__Title__: Subquadratic High-Dimensional Hierarchical
Clustering

This leads to an algorithm running in time ~O (dn) + n1+O() for d-dimensional Euclidean space. We then provide experiments showing that this algorithm performs as well as the non-approximate version for classic classication tasks while achieving a signicant speed-up.

__Time__: **Monday, December 7th - 15:00 h**

__Lecture__: Kemal Rose

__Title__: tba

__Time__: **Monday, December 7th - 16:00 h**

__Lecture__: Filippos Christodoulou

__Title__: tba

--------------EA1028161CC319B14347DCEF-- From itabrunke@zedat.fu-berlin.de Wed Dec 09 18:42:43 2020 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from

You are cordially invited to our next Monday Lecture. Next
Monday, there will be the hearing of the next PhD candidates.

We will have three talks. Talks will be 30 min. 15 min
discussions, 15 min break.

All Monday Lectures and Colloquia of winter term 2020/21 will be
given online via zoom.

http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Invitation link:

https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

Monday Lecture will be on December 14th 2020 at 14:00 h, 15:00,
16:00.

Zoom - Invitation

__Time__: **Monday, December 14th - 14:00 h**

__Lecture__: Matthias Himmelmann

__Title__: Generalized Principal Component Analysis for
Algebraic Varieties

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

__Lecture__: Dante Luber

__Title__: Boundary Complexes for Moduli Spaces of Curves

__Time__: **Monday, December 14th - 16:00 h**

__Lecture__: Jannik Peters

__Title__: Efficiency and Stability in Euclidean Network
Design

--------------FC6008046FE7A8903CE2FB01-- From itabrunke@zedat.fu-berlin.de Wed Dec 16 16:08:44 2020 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from

You are cordially invited to our next Monday Lecture - in the New
Year. Next Monday Lecture, there will be again the hearing of our
PhD candidates.

We will have three talks. Talks will be 30 min. 15 min
discussions, 15 min break.

All Monday Lectures and Colloquia of winter term 2020/21 will be
given online via zoom.

http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Invitation link:

https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

Monday Lecture will be on **January 4th 2021** at 14:00 h,
15:00, 16:00.

Zoom - Invitation

__Time__: **Monday, January 4th - 14:00 h**

__Lecture__: Sampada Kolhatkar

__Title__: Bivariate chromatic polynomials of mixed graphs

__Time__: **Monday, ****January 4th -**
15:00 h

__Lecture__: Alp Müyesser

__Title__: Rainbow factors and trees

__Time__: **Monday, ****January 4th -**
16:00 h

__Lecture__: Shubhang Mittal

__Title__: tba

--------------384EF14B8AABC9003B27361B--