Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-129 | 7th September 2025 15:37

Expansion without Connectivity: A Property Testing Perspective

RSS-Feed

Abstract:

We consider the query complexity of testing whether a bounded-degree graph is expanding, regardless of whether or not it is connected.

Whereas prior work studied testing the property of being an expander (equiv., testing the set of expander graphs), here we study testing the set of graphs that consist of connected components that are each an expander.
Within the context of simplicial complexes, such graphs are called coboundary expanders.
Loosely speaking, we show that testing expansion of $n$-vertex graphs requires $\Omega(n^{1/2})$ queries and can be done using $O(n^{0.667})$ queries.
Recall that testing whether a $n$-vertex graph is an expander has query complexity ${\tilde\Theta}(n^{1/2})$.

Our upper bound combines a distribution tester for generalized uniformity (i.e., uniformity over an unspecified subset of the domain) with a tester for expander graphs.

We also consider the problem of testing the girth of a graph.
We prove that, as long as the girth of the (not necessarily connected) graph is at most logarithmic in its size, the query complexity must be exponential in the girth.
This matches the upper bound established by the straightforward tester.



ISSN 1433-8092 | Imprint