Jelani Nelson Awarded Best Paper at SIGMOD-SIGACT-SIGAI PODS 2022

minilek

CS Prof. Jelani Nelson has won the Best Paper Award at the 2022 ACM Symposium on Principles of Database Systems (PODS) on June 13th.  The symposium is a collaboration between three ACM Special Interest Groups: Management of Data (SIGMOD), Algorithms and Computation Theory (SIGACT), and Artificial Intelligence (SIGAI).  Nelson’s award is for a paper he co-wrote with Huacheng Yu titled “Optimal Bounds for Approximate Counting,” in which they describe research on the asymptotic space complexity of maintaining an approximate counter as it is dynamically incremented, proving both new upper and lower bounds that for the first time match up to a constant factor, completely resolving a problem that was first studied in the late 1970s.