Monthly Archives: November 2023

Sublinear Algorithms Program at the Simons Institute in 2024

Exciting news!* Next year, the Simons Institute will host a summer program on Sublinear Algorithms. from May 20 to August 9, 2024. Organised by Artur Czumaj, Piotr Indyk, Jelani Nelson, Noga Ron-Zewi, Ronitt Rubinfeld, Asaf Shapira and myself, the summer program will feature 4 workshops:

This is, of course, in addition to the bulk of the program itself: research discussions, reading groups, talks, social activities… If you happen to be in the area, you’re more than welcome to come and take part in some of these!

While each workshop will have its own set of attendees (more details soon), there are also some slots for (1) long-term visitors and (2) Simons Research Fellows (within five years of the award of their PhD at the start of academic year 2024-25, may already hold faculty positions) you can apply to! The deadline to apply is December 1, 2023:

Hope to see many of you next summer! Oh, and to conclude… have you seen our logo?

Sublinear Algorithms Wide Format Logo

* Full disclosure: I am biased, being an organizer, but do find that very exciting.

News for October 2023

Last month was a little slower, with only (unless we missed some) three papers: two papers appearing, and one that was overlooked from the month before.

Stability of Homomorphisms, Coverings and Cocycles I: Equivalence, by Michael Chapmanand Alexander Lubotzky (arXiv). This paper considers three “stability” problems in topological property testing: namely, problems of the form “are objects almost-X close to X”, where X (here) is one of homorphisms, coverings of a cell complex, or 1-cocycles. The main result of the paper is that the three property testing problems are equivalent: namely, they admit testing proximity-oblivious testers (POTs) with similar rejection probability rates.

Testing Higher-order Clusterability on graphs, by Yifei Li, Donghua Yang, and Jianzhong Li (arXiv). The authors propose a new notion of graph clusterability, higher-order clusterability, meant to generalize the previously studied notions of clusterability; and proceed to provide testing algorithms for this notion.

Private Distribution Testing with Heterogeneous Constraints: Your Epsilon Might Not Be Mine, by ClĂ©ment Canonne and Yucheng Sun (arXiv). This distribution testing paper (carry-over from the previous month) focuses on the extensively studied problem of closeness testing: given samples from two unknown distributions \(p\) and \(q\), decide whether \(p=q\) or if they are far. Now, add (differential) privacy: what if the two sets of samples, from \(p\) and \(q\) respectively, were sensitive data? And now, the focus of the paper… what if the two sets of samples were not equally sensitive? What are the trade-offs between the number of samples from \(p\) and the number from \(q\), then?