[Facets-of-complexity] Invitation to Monday Lecture & Colloquium - February 11th 2019

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

You are cordially invited to our last Monday Lecture & Colloquium for this term on February 11th at 14:15 h & 16:00 h at FU Berlin.

Location:

Room 005 - Ground Floor
Freie Universität Berlin
Takustr. 9
14195 Berlin

Time: Monday, February 11th - 14:15 h

Lecture: Sergio Cabello (University of Ljubljana)

Title: Computational geometry, optimization and Shapley values

Abstract:

I will discuss three unrelated sets of results combining geometry and algorithms. First we will see classes of graphs defined using the intersection of geometric objects in the plane, and discuss classical optimization problems for them. Then we will consider approximation algorithms for the potato peeling problem: find a maximum-area convex body inside a given polygon. The problem amounts to finding a maximum clique in the visibility graph of random samples of points inside the polygon, and results from stochastic geometry are used to bound the size of the samples. Finally, we will discuss the efficient computation of Shapley values for coalitional games defined by the area of usual geometric objects, such as the convex hull or the minimum axis-parallel bounding box.

Coffee & Tea Break:
Room 134

Time: Monday, February 11th - 16:00 h s.t.

Colloquium: Matías Bender (Sorbonne Université Paris)

Title: Solving sparse polynomial systems using Gröbner basis

Abstract:
Solving systems of polynomial equations is one of the oldest and most important problems in computational mathematics and has many applications in several domains of science and engineering. It is an intrinsically hard problem with complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial systems coming from applications have some kind of structure. For example, several problems in computer-aided design, robotics, computer vision, molecular biology and kinematics involve polynomial systems that are sparse that is, only a few monomials have non-zero coefficients.
We focus on exploiting the sparsity of the Newton polytopes of the polynomials to solve the systems faster than the worst case estimates. In this talk, I will present a Gröbner basis approach to solve sparse 0-dimensional systems whose input polynomials have different Newton polytopes. Under regularity assumptions, we can have an explicit combinatorial bound for the complexity of the algorithm.
This is joint work with Jean-Charles Faugère and Elias Tsigaridas.