Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ATREYI CHANDA:
All reports by Author Atreyi Chanda:

TR25-025 | 10th March 2025
Hugo Aaronson, Gaia Carenini, Atreyi Chanda

Property Testing in Bounded Degree Hypergraphs

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 complexity of three fundamental hypergraph properties: colorability, $k$-partiteness, and independence number. We present a randomized algorithm for testing $k$-partiteness within families of $k$-uniform $n$-vertex ... more >>>




ISSN 1433-8092 | Imprint