Fachgebiet Algorithmische AlgebraOberseminar Algorithmische Mathematik und Komplexitätstheorie

# Oberseminar Algorithmische Mathematik und Komplexitätstheorie

Im Oberseminar tragen Mitarbeiter und Gäste über aktuelle Themen ihrer Forschung vor. In der Regel findet das Oberseminar jeden Donnerstag von 10:00 s.t. bis etwa 11:30 Uhr im Raum MA 313/314 statt.

Vorträge
Vortragender
Titel
Datum
Peter Bürgisser
Saturations of monoids of representations in Geometric Complexity Theory, Part I
24.04.2014
Peter Bürgisser
Saturations of monoids of representations in Geometric Complexity Theory, Part II
08.05.2014
Christian Ikenmeyer
Hypergraph colorings and explicit formulas for Ottaviani's invariant of cubic threefolds
22.05.2014
-
Entfällt
05.06.2014
Reinhold Schneider
Low rank hierarchical tensors approximation

12.06.2014
Paul Breiding
Condition in Linear Optimization
19.06.2014
Felipe Cucker
A Theory of Complexity, Condition and Roundoff
26.06.2014
Pierre Lairez
Complexity and efficiency of the integration of rational function
03.07.2014
Dennis Amelunxen
Beyond counting faces: Integral geometry of polyhedral cones
10.07.2014
Jesko Hüttenhain
Finding regular functions of a given weight on a toric variety
17.07.2014

# Abstracts

## A Theory of Complexity, Condition and Roundoff

We develop a theory of complexity for numerical computations that takes into account the condition of the input data and allows for roundoff in the computations. We follow the lines of the theory developed by Blum, Shub, and Smale for computations over R (which in turn followed those of the classical, discrete, complexity theory as laid down by Cook, Karp, and Levin among others). In particular, we focus on complexity classes of decision problems and paramount among them, on appropriate versions of the classes P, NP and EXP of polynomial, nondeterministic polynomial, and exponential time, respectively. We exhibit a natural NP-complete problem and prove the existence of problems solvable with exponential cost but not with nondeterministic polynomial time.

## Finding regular functions of a given weight on a toric variety

We consider orbit closures with respect to the action of an algebraic torus $T=(\mathbb C^\times)^n$ on some $\mathbb C$-vector space $V\cong\mathbb C^m$. For the closure $Z$ of a $T$-orbit in $V$, we are interested in finding regular functions $f\in \mathbb C[Z]$ which have a certain weight $\omega\in\mathbb Z^n$ with respect to the torus action. This is equivalent to finding monomials in $\mathbb C[V]=\mathbb C[x_1,\ldots,x_m]$ whose exponent vector $\mu\in\mathbb N^m$ satisfies a certain $\mathbb Z$-linear condition. We investigate the computational complexity of determining whether such a $\mu$ exists and if so, how to compute one (of minimal absolute value). In the special case where $\omega=(1,\ldots,1)$ this is a toy analogue of the search for regular $\operatorname{SL}$-invariant functions on $\operatorname{GL}$-orbit closures.