Quality control in sublinear time: a case study via random graphs
The research introduces 'Quality Control Problems' to assess whether an algorithm can trust its output when dealing with potentially adversarial inputs from a known distribution, like random graphs. By focusing on sublinear queries, it proves that quality control algorithms for counting graph motifs (like cliques) are provably more efficient than traditional methods, achieving query complexities scaling inversely with powers of the edge probability p.