The BLR (Blum-Luby-Rubinfeld) linearity test checks whether f: {0,1}^n -> {0,1} is a linear function by sampling random x, y and verifying f(x) + f(y) = f(x+y) (mod 2). If f is epsilon-far from every linear function, the test rejects with probability at least epsilon. Why does this work with O(1/epsilon) repetitions?
AEach test independently has probability epsilon of detecting a nonlinearity, so O(1/epsilon) tests give constant detection probability by the coupon collector argument
BIf f is epsilon-far from linear, then for a random x,y the probability that f(x) + f(y) != f(x+y) is at least epsilon — each random test has at least epsilon probability of catching a violation, and O(1/epsilon) independent tests boost this to constant probability
CThe test exhaustively checks all pairs within a random subset of size 1/epsilon
DThe linearity test requires O(n/epsilon) queries, not O(1/epsilon)
The key theorem states: if f is epsilon-far from every linear function, then Pr[f(x) + f(y) != f(x+y)] >= epsilon for uniformly random x, y. This is not obvious — it requires Fourier analysis over GF(2)^n. Given this, each independent test catches a violation with probability >= epsilon. After O(1/epsilon) tests, the probability of catching at least one violation is 1 - (1-epsilon)^(1/epsilon) >= 1 - 1/e ≈ 0.63, which exceeds 2/3 with a slightly larger constant. The test uses O(1/epsilon) queries total (3 per test), independent of n.
Question 2 True / False
In the dense graph model (adjacency matrix queries), every graph property expressible in first-order logic is testable with query complexity depending only on epsilon.
TTrue
FFalse
Answer: True
This is a consequence of Szemerédi's regularity lemma and the work of Alon and Shapira. The regularity lemma decomposes any dense graph into a bounded number of 'pseudo-random' parts (the number depends only on epsilon). First-order properties can be evaluated on the regularity partition, which has bounded size. The tester samples O(1/epsilon^c) vertices (for some constant c depending on the property) and checks the property on the induced subgraph. The query complexity is enormous (due to the tower-function bounds in the regularity lemma) but independent of n. This is an existence result — the testers are often impractical but theoretically fundamental.
Question 3 Short Answer
Explain the difference between one-sided and two-sided error in property testing, and give an example where one-sided error requires more queries than two-sided error.
Think about your answer, then reveal below.
Model answer: A one-sided tester always accepts inputs with the property (zero false negatives); a two-sided tester may reject valid inputs with probability up to 1/3 (both types may accept epsilon-far inputs with probability up to 1/3). For triangle-freeness in the dense graph model, two-sided testing requires O(1/epsilon^c) queries (via regularity-based sampling), while one-sided testing — which must find an actual triangle witness when rejecting — requires Theta(n^(1-delta)) queries for some delta depending on epsilon. The gap arises because one-sided testers must produce a certificate of violation (an explicit triangle), while two-sided testers can reject based on statistical evidence without finding an explicit witness.
The one-sided vs two-sided gap is dramatic for some properties. In the sparse graph model, bipartiteness is testable one-sided with O(sqrt(n) / epsilon^O(1)) queries but requires Omega(sqrt(n)) even for two-sided testing, so the gap is smaller. Understanding which properties have efficient one-sided testers is a major open direction.
Question 4 True / False
Property testing in the bounded-degree graph model (where each vertex has degree at most d and queries are adjacency list queries) can always be done with query complexity independent of the graph size n.
TTrue
FFalse
Answer: False
In the bounded-degree graph model, many important properties require query complexity that depends on n. For example, testing whether a bounded-degree graph is connected requires Omega(sqrt(n)) queries, and testing bipartiteness requires Omega(sqrt(n)) queries. This contrasts with the dense graph model where many properties have query complexity independent of n. The difference arises from information density: in a dense graph, each sampled vertex reveals O(n) adjacency bits, while in a bounded-degree graph each query reveals only O(d) bits. The graph model fundamentally affects testability.