Monday, December 4, 2017
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
Relating the volume with the Minkowski (vectorial) addition of compact
(not necessarily convex) sets, one is led to the famous and powerful
Brunn-Minkowski inequality. One form of it states that
$\vol(K+L)^{1/n}\geq\vol(K)^{1/n}+\vol(L)^{1/n}$ for any compact sets
$K,L\subset\R^n$. In 2001, Gardner \& Gronchi moved it to the discrete
setting and proved a discrete version of the Brunn-Minkowski inequality
for finite subsets of the integer lattice $\Z^n$: if $A,B\subset\Z^n$ are
finite with $\dim B=n$, then the cardinality $|A+B|\geq
\bigl|D_{|A|}^B+D_{|B|}^B\bigr|$, where $D_{|A|}^B$ is, roughly speaking,
like an intersection of a simplex with $\Z^n$. In this talk we aim also to
present a new type of discrete Brunn-Minkowski inequality: if
$A,B\subset\Z^n$ are finite, then
\[
\bigl|\bar{A}+B\bigr|^{1/n}\geq |A|^{1/n}+|B|^{1/n},
\]
where $\bar{A}$ is an {\it extension} of $A$ which is obtained by adding
some new integer points in a particular way.
Joint work with Jesús Yepes Nicolás and David Iglesias.
* * *
For a PDF version please click
here
Colloquium - 16:00
Abstract:
Can we approximate a semidefinite program by a linear program?
Is it possible to approximately check nonnegativity of a multivariate
polynomial by few pointwise evaluations? These questions fall into general
framework of approximating the cone of nonnegative polynomials with
polyhedral cones.
In this talk, we will show inapproximability of the cone of nonnegative
polynomials in the dense case (i.e. the case of all polynomials of a fixed
degree). We will also show the existence of polyhedral approximations with
polynomial number of facets in the sparse case (i.e. the case of a
subspace of polynomials with small dimension). Our approximation result is
an application of the recent solution of Kadison-Singer problem, and hence
it is not constructive. Time permits, we will also discuss randomized
construction of a polyhedral approximation in the sparse case.