Best Student Paper at SODA 2022
At SODA this year BARC is represented with two papers, one of which has been awarded Best Student Paper written by two of our PhD students Lorenzo Beretta and Jakub Tětek.
BARC is always proud to present papers at the ACM-SIAM Symposium on Discrete Algorithms but this year we are especially excited to have two of our talented young PhD students present their paper Better Sum Estimation via Weighted Sampling, which was awarded Best Student Paper for SODA 22.
In their paper, Lorenzo Beretta and Jakub Tětek revisit fundamental questions concerning what can be inferred about a large data set while only looking at a small sample of it. Such sampling algorithms are essential in many applications dealing with large data sets. Consider, for example, a large network representing some relationship (e.g. friendships on Facebook). What can be said about the average number of friendships of user, from just looking at a sample? If we sample nodes in the graph (users in the Facebook example), we risk getting the wrong idea about the average if there is a small number of nodes with many connections. If, in addition, we are able to sample a random edge in the graph, it is possible to get considerably more accurate estimates with the same number of samples. Lorenzo Beretta and Jakub Tětek present improved such algorithms, and furthermore show lower bounds which imply that the upper bounds on sample size and estimation error are optimal up to constant factors, answering an open question raised by computer scientists at Stanford in 2007.
To read the full paper, click here.
Lorenzo Beretta joined BARC in October 2020 as a PhD student in the AC section, under the supervision of Mikkel Thorup and Mikkel Abrahamsen. Lorenzo holds a BSc in Mathematics from the University of Pisa, Italy, where he completed a dissertation on the "continuum random tree", the limit object of some families of random discrete trees. He also holds an MSc in Computer Science from the University of Pisa, where he focused on discrete algorithms and writing a dissertation on the well-known problems of sorting and selection in the special case in which some comparisons might return incorrect answers (known as "Sorting with Liars").
Jakub Tětek joined BARC in August 2021 as a PhD student in the AC section also under the supervision of Mikkel Thorup. Jakub holds a BSc in Computer Science from Charles University, Prague, Czech Republic, and a MSc in Computer Science from DIKU. At DIKU, his research focuses on understanding the role randomness plays in computation on large data sets.
Furthermore, BARC members Christian Wulff-Nilsen and Debarati Das in collaboration with BARC alumni Maximilian Probst Gutenberg (now at ETH Zurich) have also had their paper A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs accepted at this years SODA.
Click here to go to the abstract of Best Student Paper at SIAM’s website: Better Sum Estimation via Weighted Sampling | Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) | Society for Industrial and Applied Mathematics
Click here to go to the abstract of Das, Gutenberg and Wulff-Nilsen’s paper A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs | Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) | Society for Industrial and Applied Mathematics