People: Prof. Dr. Tobias Friedrich, Dr. Davis Issac
Links: Lehrveranstaltungen IT-Systems Engineering, Algorithm Engineering Moodle

The seminar will consist of students giving presentations about some recent results on the topic of binary matrix factorization (BMF). We will meet once a week (virtually). In the initial couple of lectures, we will give an overview of the topic and review some basics required for reading the papers. Each student presentation will be about 75 minutes on a topic from one of the papers below, followed by a 15 minutes discussion. The number of presentations per student will be determined on basis of the number of participants (maximum 3 per student). The presenting student is also required to prepare a 1-2 page handout for the audience and a 2-6 page summary of the presentation afterwards. The student should prepare the first draft of the presentation at least a couple of days before the date of presentation and discuss the presentation with us in a personal meeting.The grading will be 75% based on the presentation and the other 25% will be based on the handouts and the summary. The course will be conducted completely online.

Binary matrix factorization (BMF) is a topic having applications in the areas of data mining, machine learning, and bioinformatics and has been recently gathering attraction in the theoretical computer science community. In BMF, we are given a matrix \(A\in \{0,1\}^{m\times n}\) and a positive integer k, and we want to find matrices \(U\in \{0,1\} ^{m\times k}\) and \(V\in \{0,1\}^{k\times n}\) such that \(||A-U\boldsymbol\cdot V||_p\) is minimized for some \(p\ge 0\). Depending on the choice of the arithmetic for the multiplication \(U\boldsymbol\cdot V\) and the choice of the norm \(||\dots ||_p\), we obtain different problems. The most commonly used arithmetics are boolean arithmetic, standard integer arithmetic and GF(2) arithmetic, and the most commonly used norms are \(\ell_0,\ell_1\) and \(\ell_2\). 

There are no formal requirements, but we expect the students to have the ability to read and understand mathematically involved proofs.

Here is a prelliminary list of papers from which the results to be presented will be selected:

1. Approximation Schemes for Low-Rank Binary Matrix Approximation Problems. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov,  Fahad Panolan and Saket Saurabh. TALG 2019.

2. A PTAS for ℓ_p-Low Rank Approximation. Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee and David P. Woodruff. SODA 2019.

3. Faster Algorithms for Binary Matrix Factorization. Ravi Kumar, Rina Panigrahy, Ali Rahimi, David Woodruff . ICML 2019.

4. Parameterized Low-Rank Binary Matrix Approximation. Fedor V. Fomin, Petr A. Golovach, Fahad Panolan. ICALP 2018.

5. Streaming PTAS for Binary ℓ₀-Low Rank Approximation. Anup Bhattacharya, Dishant Goyal, Ragesh Jaiswal, and Amit Kumar. 2019.

We meet weekly tuesdays, 11:00-12:30.