Many algorithms have lately been designed to work well on average (i.e., on inputs coming from some distribution D), but then when running this algorithm on a specific input x, we are forced to ask the question — can we really trust the algorithm on this input?
In this work we define a class of problems — that we call quality control problems, whose definition allows the algorithm to exploit the randomness of instances, while still being safe to use on a specific input. A quality control problem is given by a pair (rho,D) where rho is a real valued quality parameter and D a distribution on inputs. We assume that inputs from D are "high quality" (i.e., have rho(x) close to 1) with high probability. An algorithm A is said to solve the problem if it satisfies (1) Completeness - it accepts inputs from D w.h.p. and (2) Soundness - if rho(x) is far from 1, it rejects (w.h.p. over internal randomness). [This definition is inspired by Feige's work on refutation of random CSPs and also by Rubinfeld and Vasilian's work on testable learning.] So the algorithm does not accept every high quality input, but does accept most of them; while rejecting every poor quality input w.h.p.
Quality control problems get technically interesting when the condition "rho(x) ~= 1" is not easily certifiable. We consider a natural class of such problems - namely counting constant sized subgraphs in an Erdos-Renyi random graph (G(n,p)) where edges appear independently with probability p. Among our results we give quality control algorithms that make (1/p)^O(k) queries to the adjacency matrix of a graph G to confirm that the number of k-cliques is roughly the expected number in G(n,p). In contrast it is known that a sublinear algorithm solving this problem on worst case inputs would require (1/p)^Theta(k^2) queries.
Our proofs highlight the nice composability features of quality control problems while also invoking tools from probability theory and quasirandomness of graphs that may be of general interest.
Joint work with Cassandra Marcussen (Harvard) and Ronitt Rubinfeld (MIT).
Short Bio:
