Workshop on Local Algorithms (WoLA)

Oded's comments

The 7th WoLA (Workshop on Local Algorithms) took place at the Simons Institute for the Theory of Computing in August 5-7, 2024.

This is an unusual entry, because I attended this workshop only virtually and partially. Furthermore, I was distracted by various technical problems, and consequently missed some of the presentations that I wanted to watch as well as central aspects of presentations that I did watch. Hence, I would not risk reviewing the presentations I enjoyed, but will rather highlight a few conceptual aspects that caught my attention in some of the presentations.

• On counting subgraphs and why counting seeds makes more sense (if one thinks about it clearly) by Talya Eden. Going over a sequence of works, Talya was intrigued by the question of when is bucketting used and when can and should it be avoided.
• Testing Intersectingness of Uniform Families or how Dana and I intersected by Michal Parnas. Here the issue was studying the testability of functions that are defined over a subset of a domain, where testablility over the entire domain is already understood. This theme reminded me of an analogous study in the context of testing linearity.
• Property Testing with Incomplete or Manipulated Inputs by Sofya Raskhodnikova. What caught my attention here is a generalization of the linarity tester to 2k-tuples of random points (where k=1 refers to the celebrated BLR linearity test). It turns out that $\eps$-far functions are rejected by the corresponding tester with probability $\Omega(k\eps)$. Furthermore, after querying $2k$ random points, one may check the value at the sum of any $2k'$-subset of them.
• Monotonicity testing, routing, and a theorem of Lehman and Ron by C. Seshadhri. Sesh was intrigued by a combinatorial result, which was used in the first study of monotonicity testing but abandoned afterwards. Indeed, this result is most appealing from the perspective of routing on the hypercube.
• Interactive proofs of proximity for distributions by Guy Rothblum with a follow-up by Tal Herman. What I found most interesting is the construction of interactive proofs of proximity for general properties of distributions, represented by circuits for deciding whether (the full description of) a distribution has the property, based on two other types of interactive proofs of proximity (IPPs).
  1. IPPs for assignments to fixed circuit circuits;
  2. IPPs (of a certain class) for any label-invariant property of distribution (where the known IPP for distributions is in this class).
  A key ingrediant is the construction of an interactive procedure by which the verifier can obtain a tagged sample of a distribution to which it has standard sampling access, where a tagged sample consists of pairs $(x,p(x))$ such that $x$ is drawn from the said distribution and $p(x)$ is the probability mass assigned to $x$ by this distribution. The verifier will be assisted by a potentially cheating prover, and (whp) it will either reject or obtain a distribution that is sufficiently closed to a tagged sample.
• Let's Try and Be More Tolerant: On Tolerant Property Testing and Distance Approximation (a Richard Karp Distinguished Lecture) by Dana Ron. The focus of this talk was on positive results that refer to natural properties. Still it is worty to bear in mind that seperations between the query complexity of tolerant versus standard testing do exist (and refer even to a natural property such as monotonicity), and that two-sided error is unavoidable in tolerant testing.
• The long path to sqrt(d) monotonicity testers by C. Seshadhri. Sesh surveyed the deep connections between testing monotonicity and isoperimetric inequalities.

Official introduction to the workshop

Local algorithms, that is, algorithms that compute and make decisions on parts of the output considering only a portion of the input, have been studied in a number of areas in theoretical computer science and mathematics. Some of these areas include sublinear-time algorithms, distributed algorithms, inference in large networks and graphical models. These communities have similar goals but a variety of approaches, techniques, and methods. This workshop is aimed at fostering dialogue and cross-pollination of ideas between the various communities. To this end, the workshop will feature a small number of longer talks that, in part, survey approaches by various communities, as well as short, focused talks on recent, exciting results.

See the workshop's webpage at the Simons Institute