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.

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.

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.