Inhalt des Dokuments
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.
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 |
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.