Abstract

Yiqiao Bao

Title: Nearly Tight Bounds on Testing of Metric Properties

Abstract: Given a non-negative $n \times n$ matrix viewed as a set of distances between $n$ points, we consider the property testing problem of deciding if it is a metric. For general metrics, our paper is the first to consider these questions. We prove an upper bound of $O(n^{2/3}/\epsilon^{4/3})$ on the query complexity for this problem.  Our algorithm is simple, but the analysis requires great care in bounding the variance on the number of violating triangles in a sample. When $\epsilon$ is a slowly decreasing function of $n$ (rather than a constant, as is standard), we prove a lower bound of matching dependence on $n$ of $\Omega (n^{2/3})$, ruling out any property testers with $o(n^{2/3})$ query complexity unless their dependence on $1/\epsilon$ is super-polynomial.

Based on joint work with Sampath Kannan and Erik Waingarten.

Amir Azarmehr

Title: Stochastic Matching via In-n-Out Local Computation Algorithms

Abstract: This talk is based on joint work with Soheil Behnezhad, Alma Ghafari, and Ronitt Rubinfeld.

Consider the following stochastic matching problem. We are given a known graph G = (V, E). An unknown subgraph G_p = (V, E_p) is realized where E_p includes every edge of E independently with some probability p ∈ (0, 1]. The goal is to query a sparse subgraph H of G, such that the realized edges in H include an approximate maximum matching of G_p.

We show that a poly(1/p)-degree subgraph can obtain a (1 − ε)-approximation for any desirably small fixed ε > 0, unifying two long lines of work that achieve O(1)-approximations using poly(1/p) degree, and (1 − ε)-approximation using quasipoly(1/p) degree. Beyond its quantitative improvement, a key conceptual contribution of our work is to connect local computation algorithms (LCAs) to the stochastic matching problem for the first time. While prior work on LCAs mainly focuses on their out-queries (the number of vertices probed to produce the output of a given vertex), our analysis also bounds the in-queries (the number of vertices that probe a given vertex). We prove that the outputs of LCAs with bounded in- and out-queries (in-n-out LCAs for short) have limited correlation, a property that our analysis crucially relies on and might find applications beyond stochastic matchings.

Janani Sundaresan

Title: Distributed Triangle Detection is Hard in Few Rounds

Abstract: In the CONGEST model, $n$ vertices with information only about their neighborhoods are allowed to communicate to each other over the edges of the input graph. Communication happens in synchronous rounds with a bandwidth of $O(\log n)$. We prove that detecting a triangle in this model requires $\Omega(\log \log n)$ rounds. 
Prior to our work, the only lower bound was that at least two rounds are necessary.

It is known that standard communication complexity arguments that have been used to get lower bounds in the CONGEST model in the past are incapable of giving any meaningful multi-round lower bounds for this problem. Our main contribution is a new information-theoretic technique that combines classical round elimination arguments of communication complexity with the point-to-point communication aspects of distributed networks and can be of independent interest.

Joint work with Sepehr Assadi (https://arxiv.org/abs/2504.01802).