Institute for Theoretical Computer Science

Wir gratulieren ganz herzlich Katharina Dannenberg zum besten Masterabschluss der Universität zu Lübeck, der von der Firma Capgemini mit einem Preis in Höhe von 1.000 Euro dotiert wurde.

We consider the bin packing problem with d different item sizes and revisit the structure theorem given by Goemans and Rothvoss about solutions of the integer cone. We present new techniques on how solutions can be modified and give a new structure theorem that relies on the set of vertices of the underlying integer polytope. As a result of our new structure theorem, we obtain an algorithm for the bin packing problem with running time |V|^{2^{O(d)}}⋅enc(I)^{O(1)}, where V is the set of vertices of the integer knapsack polytope and enc(I) is the encoding length of the bin packing instance. The algorithm is fixed parameter tractable, parameterized by the number of vertices of the integer knapsack polytope |V|. This shows that the bin packing problem can be solved efficiently when the underlying integer knapsack polytope has an easy structure, i.e. has a small number of vertices. Furthermore, we show that the presented bounds of the structure theorem are asymptotically tight. We give a construction of bin packing instances using new structural insights and classical number theoretical theorems which yield the desired lower bound.

This is the third event in a conference series that explores new ways of helping students to achieve 21st Century competencies in mathematics and computer science. The previous conferences, held in Darwin, Australia, in 2013 and in Chennai, India, in 2014 (Videos from 2014) saw a unique interaction between computer science / mathematics researchers and educators and artists (theatre, dance, graphic arts). 3rd CMSC 2016

Anlässlich der Tagung 4th ACM Workshop on Information Hiding and Multimedia Security im Juni 2016 in Vigo/Spanien, wurde die Arbeit von Sebastian Berndt und Maciej Liskiewicz "Provable Secure Universal Steganography of Optimal Rate" mit dem Best Student Paper Award ausgezeichnet. (Foto v.l.n.r.: Nuria González Prelcic, Patrick Bas, Sebastian Berndt, Fernando Pérez-González)

Die Deutsche Forschungsgemeinschaft (DFG) bewilligt dem Institut für Theoretische Informatik ein neues Forschungsprojekt zum Thema "Kausalität: algorithmischer Ansatz und komplexitätstheoretische Perspektive". Weitere Informationen...

In this talk I will present some recent results on sorting networks. Sorting networks are sorting algorithms which perform a sequence of comparisons on the input which only depends on the input size. This makes them relevant for hardware implementations. I will show how SAT encodings can be used to determine lower and upper bounds on some properties of sorting networks, and how improved encoding techniques led to new bounds. Finally, I will discuss an application of sorting networks for SAT encodings, so-called cardinality networks.

The paper "Separators and Adjustment Sets in Markov Equivalent DAGs" by Benito Van der Zander and Maciej Liśkiewicz has been accepted for presentation at the 30th AAAI Conference on Artificial Intelligence (AAAI-16). The competition was very strong this year, with a record-number 2132 submissions and only 549 papers accepted, for an acceptance rate of 26%. International Conference of Artificial Intelligence and Statistics

The paper "Searching for Generalized Instrumental Variables" by Benito Van der Zander and Maciej Liśkiewicz has been accepted at the 19th International Conference on Artificial Intelligence and Statistics (AISTATS-16). There were 537 submissions for AISTATS this year, of which the program committee accepted 165 for presentation at the conference. Conference on 'Artificial Intelligence

Staff Overview