5 presentations at FOCS '23 by BARC members and affiliates
The 64th IEEE Symposium on Foundations of Computer Science, takes place this week in Santa Cruz, and BARC members as well as affiliates ensure we are well represented.
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)
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.
We wish everyone at FOCS'23 a splendid time presenting, discussing and celebrating their new results.