Addressing a problem of Goldreich and of Alon and Fox, we prove new sufficient and necessary criteria, guaranteeing that a graph property admits a removal lemma with a polynomial bound. Although both are simple combinatorial criteria, they imply almost all prior positive and negative results of this type, as well as many new ones. In particular, we will show that every semi-algebraic graph property admits a removal lemma with a polynomial bound. This confirms a conjecture of Alon. 

Joint work with L. Gishboliner

We introduce the concept of a randomness steward, a tool for saving random bits when executing a randomized estimation algorithm 𝖤𝗌𝗍 on many adaptively chosen inputs. For each execution, the chosen input to 𝖤𝗌𝗍 remains hidden from the steward, but the steward chooses the randomness of 𝖤𝗌𝗍 and, crucially, is allowed to modify the output of 𝖤𝗌𝗍. The notion of a steward is inspired by adaptive data analysis, introduced by Dwork et al. Suppose 𝖤𝗌𝗍 outputs values in ℝd, has ℓ∞ error ϵ, has failure probability δ, uses n coins, and will be executed k times. For any γ>0, we construct a computationally efficient steward with ℓ∞ error O(ϵd), failure probability kδ+γ, and randomness complexity n+O(klog(d+1)+(logk)log(1/γ)). To achieve these parameters, the steward uses a PRG for what we call the block decision tree model, combined with a scheme for shifting and rounding the outputs of 𝖤𝗌𝗍. (The generator is a variant of the INW generator.)

As applications of our steward, we give time- and randomness-efficient algorithms for estimating the acceptance probabilities of many adaptively chosen Boolean circuits and for simulating any algorithm with an oracle for 𝗉𝗋𝗈𝗆𝗂𝗌𝖾-𝖡𝖯𝖯 or 𝖠𝖯𝖯. We also give a randomness-efficient version of the Goldreich-Levin algorithm; our algorithm finds all Fourier coefficients with absolute value at least θ of a function F:{0,1}n→{−1,1} using O(nlogn)⋅poly(1/θ) queries to F and O(n) random bits, improving previous work by Bshouty et al. Finally, we prove a randomness complexity lower bound of n+Ω(k)−log(δ′/δ) for any steward with failure probability δ′, which nearly matches our upper bounds in the case d≤O(1).

Maybe surprisingly, for testing with respect to the cut metric, we prove there is a universal (not depending on the property), polynomial in $1/\epsilon$ query complexity bound for two-sided testing hereditary properties of sufficiently large permutations. We further give a nearly linear bound with respect to a closely related metric which also depends on the smallest forbidden subpermutation for the property. Finally, we show that several different permutation metrics of interest are related to the cut metric, yielding similar results for testing withrespect to these metrics. 

This is a joint work with Jacob Fox.