Our IT specialist at a conference with a Nobel laureate!
We talked with professor Jarosław Byrka from the Institute of Computer Science at the University of Wrocław. Prof. Byrka participated in the prestigious FOCS 2024 conference in Chicago at the end of October, presenting his work titled The Bidirected Cut Relaxation for Steiner Tree has Integrality Hap Smaller than 2.
How prestigious is the FOCS conference, and who does it attract?
The FOCS conference is one of the two flagship computer science conferences in the world, with the other being the STOC conference. It showcases the most important scientific results in the field and attracts researchers from leading universities in the United States. Among Polish academic institutions, only researchers from the University of Warsaw, the University of Wrocław, and occasionally the Jagiellonian University (UJ) have the opportunity to present their findings there. The significance of these conferences can be compared to the importance of Nature and Science journals for experimental sciences.
What is the subject of the work you presented at the conference?
The paper concerns the Steiner tree, a classic optimization problem: How can a given subset of vertices in a graph be connected at the lowest cost possible? Linear programming helps find the solution by modeling the selection of an appropriate subset of edges.
The simplest of them, UCR (Undirected Cut Relaxation), uses variables on the edges, but is weak (as a method of estimating the cost of the optimal solution). The strongest, HYP (hypergraphic), uses variables on subsets of vertices to be connected, which makes it highly accurate but also impractical due to a very large amount of variables. BCR (Bidirected Cut Relaxation) seems a promising middle ground approach, thanks to it using variables on directed edges, making it fast. However, its potential inaccuracy is yet not well understood.
In collaboration with prof. Fabrizio Grandoni (Lugano, Switzerland) and prof. Vera Traub (Bonn, Germany) we were able to show for the first time that BCR is much stronger than UCR. This discovery bears hope that in the future, efficient primal-dual BCR-based algorithms may be developed.
Which remarkable figures from the academic world did you meet?
Among the speakers was prof. Roger Myerson, the 2007 Nobel Prize Laureate in economics and the co-creator of the modern (economic and algorithmic) game theory. The conference features many acclaimed researchers, like Irit Dunur from the Weizmann Institute, Christos Papadimitriou from Columbia University, and Rajeev Alur from the University of Pennsylvania.
What topics dominated this year’s conference?
The increase in popularity of the topics related to the possibility of performing calculations on quantum computers and all probabilistic arguments concerning the processing of large data sets is becoming more and more noticeable.
Compiled by E. Kośmider, on behalf of the Institute of Computer Science, University of Wrocław.
Translated by Sebastian Halczyk (student of English Studies at the University of Wrocław) as part of the translation practice.
