Universität Wien
Warning! The directory is not yet complete and will be amended until the beginning of the term.

250135 SE Decidability, Computability and Complexity (2020W)

4.00 ECTS (2.00 SWS), SPL 25 - Mathematik
Continuous assessment of course work
Moodle

Registration/Deregistration

Note: The time of your registration within the registration period has no effect on the allocation of places (no first come, first served).

Details

Language: English

Lecturers

Classes

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

Aims, contents and method of the course

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.

Assessment and permitted materials

Seminar Talk

Minimum requirements and assessment criteria

Examination topics

Reading list

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.

Association in the course directory

MAMS; MANS;

Last modified: Th 22.10.2020 12:09