Best Student Papers at ICALP 2022

We are proud to announce that both Best Student Papers for Track A this year’s ICALP are written by representatives of BARC.

ICALP is the main conference and annual meeting of the European Association for Theoretical Computer Science (EATCS) and has granted BARC PhD student Jakub Tětek as well as and long term visiting researcher at BARC PhD student Joakim Blikstad the awards for both Best Student Paper for Track A of this years’ conference.

Jakub Tětek joined BARC in August 2021 as a PhD student at UCPH, supervised by Professor Mikkel Thorup. Jakub’s ICALP paper, which is actually his Master's thesis is titled Approximate Triangle Counting via Sampling and Fast Matrix Multiplication. In his paper, Jakub revisits the well-studied problem of counting triangles in a graph. Triangle counting has various applications; for example, sociologists have asked questions such as "how many triples of people that all know each other are there on a social network?" in order to understand social communities. Answering this question exactly reduces to counting triangles in a graph. While optimal algorithms for approximately counting triangles were known in the setting when there are relatively many triangles, the case with few triangles was not understood. Jakub resolved this case by combining sampling methods with efficient algorithms for matrix multiplication.

Joakim Blikstad joined BARC as a long term visitor from KTH in Stockholm, Sweden in August 2021 under the supervision of Professor Danupon Nanongkai. His paper is titled Sublinear-round Parallel Matroid Intersection and in this work, Joakim takes a look at the problem of matroid intersection. Matroid intersection is a well-studied optimization problem which is not only interesting from a theoretical point of view, but also because of its rich set of applications, such as solving continuous systems arising in electrical networks and chemical processing plants. Despite a lot of recent progress in obtaining faster algorithms for matroid intersection, the most efficient parallel algorithm (i.e. where multiple operations can be performed simultaneously) was still a linear-round algorithm from the 1960s. By leveraging modern techniques, Joakim shows the first parallel algorithm for matroid intersection running in a sub-linear number of rounds, thus also beating the over 50 years old previous algorithm.

The 49th EATCS International Colloquium on Automata, Languages and Programming (ICALP) is hosted in Paris, France, on July 4-8, 2022 as a hybrid conference.