Public defence in Computer Science, M.Sc. Nidia Obscura Acosta

Title of the thesis: On the connectivity interdiction problem, the geometry of data structures and Eulerian circuits

Doctoral student: Nidia Obscura Acosta
Opponent: Professor Guy Even, Tel Aviv University, Israel
Custos: Professor Parinya Chalermsook, Aalto Univesity School of Science, Department of Computer Science

Over the last century and since the introduction of practical computers, the study of algorithms for optimization problems has become one of the main areas in theoretical computer science. Computer algorithms are nowadays an ubiquitous tool in our technology and society, allowing us to enhance productivity, improve our communication and connectivity, and overall as a driving force of innovation. Efficient computer algorithms play a crucial role in the design and implementation of solutions for optimization problems, which have numerous societal, industrial and governmental applications in for example food production, voting systems, route scheduling, transportation, game design, protein synthesis, control of infectious diseases, study-place allocations, genome assembly and drug delivery.

However, the progress in this area has faced big theoretical and practical challenges, like the lack of computing resources, the increasing volume of data in big networks and other theoretical and structural barriers like NP-hardness.
In order to bypass some of these theoretical barriers, this thesis explores three main problems in graphs and combinatorial optimization: the Eulerian circuit problem, the connectivity interdiction problem and the geometry of the binary search tree data structure.

Our results improve on the state-of-the-art in all these problems by establishing new structural graph theoretic results and by using techniques from approximation algorithms, extremal combinatorics and geometric methods, allowing us to prove both better algorithmic results (like improved running times, upper bounds and correctness guarantees) and new computational complexity characterizations for these problems. These results have particular applications in genome assembly and network design problems like transportation and routing systems.

Keywords: Efficient algorithms, Eulerian Circuits, Data Structures, Connectivity, Approximation algorithms

Thesis available for public display 10 days prior to the defence at: https://aaltodoc.aalto.fi/doc_public/eonly/riiputus/ 

Contact information: 

Doctoral theses of the School of Science: https://aaltodoc.aalto.fi/handle/123456789/52 

Zoom Quick Guide: https://www.aalto.fi/en/services/zoom-quick-guide