An der Fakultät für Informatik wurde die Stelle einer Universitätsprofessorin/eines Universitätsprofessors für “Algorithms and Data Structures” zur Besetzung ausgeschrieben.
Im Rahmen des Berufungsverfahrens sind öffentliche Berufungsvorträgen vorgesehen. Alle Vorträge werden im Sitzungszimmer des Dekanats der Fakultät für Informatik, Erzherzog-Johann-Platz 1, 4. Stock, 1040 Wien abgehalten.
Termine
| Datum | Uhrzeit | Titel |
|---|---|---|
| Freitag, 16. Mai 2014 | 09:00 | Analysis of Randomized Algorithms |
| Freitag, 16. Mai 2014 | 12:00 | Random Processes and Quasirandom Algorithms |
| Montag, 19. Mai 2014 | 08:30 | Approximation Algorithms for Wireless Networks |
| Montag, 19. Mai 2014 | 11:30 | Algorithms for Hard Problems in Computational Intelligence |
| Mittwoch, 21. Mai 2014 | 15:30 | Models and Algorithms for Scheduling under Uncertainty |
| Freitag, 23. Mai 2014 | 09:00 | Problems with two quantifiers |
| Freitag, 23. Mai 2014 | 14:00 | Sublinear algorithms for the analysis of very large graphs |
Abstracts
Analysis of Randomized Algorithms
I will begin the talk by giving an introduction to the topic of “randomised algorithms”. I will specifically highlight the simplicity, applicability and elegance of randomised algorithms. After briefly introducing the problems and models, I will illustrate this by discussing two concrete examples, namely load balancing and random walks. I will conclude the talk by presenting my future research plans, and how these align with TU Wien’s research and teaching landscape.
Random Processes and Quasirandom Algorithms
Randomness is essential for understanding our physical world and is ubiquitous in our daily life. Randomness also plays a crucial role in algorithms research. I will present a number of examples for the use of randomness in the design and analysis of algorithms. We start with the simulation of physical growth processes and random walks. Further examples will be from discrete optimization, high-dimensional volume computation and distributed computing. The key ingredient will be the appropriate use of randomness. I will give several examples where the right dose of randomness makes algorithms both simpler and faster.
Approximation Algorithms for Wireless Networks
This talk gives an insight into my current research on algorithms and game theory in wireless networks. A central problem is efficient usage of frequency spectrum by a set of communication requests. Here the consideration of realistic interference conditions gives rise to novel classes of independent set problems in graphs. We survey some of our approaches in this area, especially online algorithms for requests arriving over time. In addition, I survey my current and planned research and teaching activities as well as possible connections within the scientific environment in Vienna.
Algorithms for Hard Problems in Computational Intelligence
Many important algorithmic problems are NP-hard and therefore considered intractable. However, not all is lost: realistic problem inputs are not random and contain some kind of a hidden structure which can be captured by problem parameters. Fixed-parameter algorithms, in turn, can utilise these parameters to solve the problems efficiently in a way that scales well with the input size.
This talk will focus on fixed-parameter algorithms for hard problems that arise in various areas of computational intelligence. We will discuss approaches for capturing the hidden structure in terms of problem decomposability and problem backdoors, and present showcase results from recent and ongoing research. We will also discuss how the power of fixed-parameter algorithms can be further significantly increased by means of a bounded number of calls to a satisfiability solver.
Models and Algorithms for Scheduling under Uncertainty
Uncertainty in the input data is an omnipresent issue in real-world planning processes: jobs may take more or less time than originally estimated, resources may become unavailable, material arrives late, weather conditions may cause severe delays, etc. Uncertain data is typically modeled through stochastic parameters or as online information that is incrementally revealed. In this talk, I will discuss different models and solution methods for optimization under uncertainty. As example I choose machine scheduling problems. The particular focus of this talk will lie on mathematically provable (worst-case) performance guarantees, robustness of solutions, and the tradeoff between performance and adaptivity.
Problems with two quantifiers
The talk discusses some algorithmic problems that are (most likely) situated in the area above NP. The first problem is taken from geometry, and the second problem comes from bilevel optimization.
Sublinear algorithms for the analysis of very large graphs
Does the Facebook graph of a country reflect its political system? Can we distinguish just by looking at this graph, whether the country is a democracy or a totalitarian state?
To study this and similar questions we require algorithms that are capable of determining structural properties of very large graphs. Since it is often impossible to determine exactly, if a very large graph has a certain property or not, the field of Property Testing studies the question, which graph properties can be approximately decided using random sampling. In my talk I would like to explain the recent developments in Property Testing for bounded-degree graphs. In particular, I will describe recent work of Ilan Newman and myself, where we prove that the local structure of a bounded degree planar graph (given as the distribution of BFS-neighborhoods of constant depth) describes its global structure up to epsilon n edges.