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