5 presentations at FOCS '23 by BARC members and affiliates

BARC papers that will be presented at FOCS’23:

• Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming” is authored by BARC’s Rasmus Pagh and Mikkel Thorup together with Praneeth Kacham and David P. Woodruff from Carnegie Mellon University.
  It presents a powerful construction of hash functions that can be used to improve several well-known algorithms for data streams, including count-sketch (a heavy hitters sketch that can be used to estimate frequencies in a data stream), as well as Lp estimation (a measure of skew for data distributions) for p>2. The key idea is to generalize Nisan’s pseudorandom generator to a symmetric form that supports these applications, and furthermore extend it to offer a trade-off between the space usage and the time complexity, paving the way for using it as a fast hashing primitive.

• Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1 by Vincent Cohen-Addad (Google Research, France); Hung Le (University of Massachusetts); Marcin Pilipczuk (University of Warsaw and IT University of Copenhagen); Micha≈Ç Pilipczuk (University of Warsaw)

• Locally Uniform Hashing by Ioana-Oriana Bercea (IT University of Copenhagen); Lorenzo Beretta, Jonas Klausen, Jakob Bæk Tejs Houen, and Mikkel Thorup (University of Copenhagen).
  Hashing is a widely-used method in data processing that significantly impacts computation time and resources. Normally we think of hashing as uniform or fully-random, but uniform hashing is an abstraction that cannot be implemented. Our focus is on creating practical hash functions with strong theoretical guarantees. We introduce Tornado Tabulation Hashing, a simple and fast approach which provides a certain local uniformity. The local uniformity ensures that many algorithms perform almost as well as with abstract uniform hashing. In particular, we get better implementations of classic techniques like linear probing, the HyperLogLog algorithm for counting distinct elements, and the one-permutation hashing used in machine learning. 

MIAO paper accepted and presented at FOCS'23:

• Graph Colouring is Hard on Average for Polynomial Calculus and Nullstellensatz by Jonas Conneryd (Lund University and University of Copenhagen); Susanna F. de Rezende (Lund University); Jakob Nordström and Shuo Pang (University of Copenhagen and Lund University); Kilian Risse (EPFL)

Our newcomer, professor Amir Yehudayoff, also has a paper accepted at this years FOCS conference based on work done prior to joining BARC: 

• Replicability and stability in learning is authored by BARC's Amir Yehudayoff together with Zachary Chase and Shay Moran from the Technion. This work studied two fundamental properties in machine learning: replicability and stability. The paper defines a new complexity measure (the list number) for machine learning problem. List numbers in some sense capture the ability to solve the problem in a stable manner. The paper develops a framework for controlling list numbers that is based on topology. Using this framework, it is proved that certain machine learning problems can not be solved in a stable way. 

See the full list of accepted papers here

We wish everyone at FOCS'23 a splendid time presenting, discussing and celebrating their new results.

Topics