250135 SE Decidability, Computability and Complexity (2020W)
Prüfungsimmanente Lehrveranstaltung
Labels
An/Abmeldung
Hinweis: Ihr Anmeldezeitpunkt innerhalb der Frist hat keine Auswirkungen auf die Platzvergabe (kein "first come, first served").
- Anmeldung von Mo 14.09.2020 00:00 bis So 31.01.2021 23:59
- Abmeldung bis So 31.01.2021 23:59
Details
Sprache: Englisch
Lehrende
Termine
The seminar will be fully online!
The first meeting will be on Oct. 15, 14:30 - 16:00.A zoom link will be distributed to all registered students.Information
Ziele, Inhalte und Methode der Lehrveranstaltung
In this seminar we will get to know different notions to formalize the complexity of certain computations. These computations can be decidability questions (for example: does the given input belong to a certain set?), algorithmic problems (for example: can we find a polynomial time algorithm to train a neural network?) or numerical problems (for example: is it possible to compute a certain integral without incurring the curse of dimensionality?).To this end we will study different papers and references, for example those listed in the literature part.The material will require some mathematical maturity.
Art der Leistungskontrolle und erlaubte Hilfsmittel
Seminar Talk
Mindestanforderungen und Beurteilungsmaßstab
Prüfungsstoff
Literatur
Blum, Lenore, Mike Shub, and Steve Smale. "On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines." Bulletin (New Series) of the American Mathematical Society 21.1 (1989): 1-46.Blum, Avrim, and Ronald L. Rivest. "Training a 3-node neural network is NP-complete." Advances in neural information processing systems. 1989.Traub, Joseph Frederick, and Arthur G. Werschulz. Complexity and information. Vol. 26862. Cambridge University Press, 1998.Håstad, Johan Torkel. Computational limitations for small-depth circuits. MIT press, 1987.Ben-Artzi, Jonathan, et al. "Computing Spectra--On the Solvability Complexity Index Hierarchy and Towers of Algorithms." arXiv preprint arXiv:1508.03280 (2015).Heinrich, Stefan. Random approximation in numerical analysis. Universität Kaiserslautern. Fachbereich Informatik, 1992.Clements, G. F. "Entropies of several sets of real valued functions." Pacific Journal of Mathematics 13.4 (1963): 1085-1095.
Zuordnung im Vorlesungsverzeichnis
MAMS; MANS;
Letzte Änderung: Do 22.10.2020 12:09