Property Testing in Bounded Degree Hypergraphs

Hugo Aaronson, Gaia Carenini, Atreyi Chanda

We extend the bounded degree graph model for property testing introduced by Goldreich and Ron (Algorithmica, 2002) to hypergraphs. In this framework, we analyse the query complexit…