Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BOUNDED DEGREE MODEL:
Reports tagged with Bounded degree model:
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 >>>


TR26-268 | 22nd October 2026
Amit Dror

A Linear Lower Bound on Testing Graph Isomorphism in the Bounded-Degree Model

We prove a linear query complexity lower bound for two-sided testing of graph isomorphism in the bounded-degree model.
Specifically, there are constants $d$ and $\varepsilon_0$ such that, for every sufficiently large $n$,
there exists an $n$-vertex graph $H_n$ of maximum degree at most $d$ such that testing isomorphism ... more >>>




ISSN 1433-8092 | Imprint