(For All)s

At a Dagstuhl meeting sometime ago, two communities of researchers came together: property testing, and streaming algorithms. As all theoreticians, both groups wanted theorems that hold for all inputs (with some property). The difference was, streaming algorithms research proposed theorems for particular problems such as estimating L_1 norms, while property testing research, perhaps because of the complexity-theoretic flavor, sought theorems that hold for all problems in certain class., eg, all monotone graph properties. Sudipto Guha, Piotr Indyk and others used this observation to incite streaming research to seek more general techniques and results that hold for classes of problems (all distances with certain properties, say). There is some fledgling progress on this. Guha, Indyk and McGregor have results showing general lower bounds on classes of distances (COLT 07?) and I liked Trithapura's recent talk where he reduces a bunch of problems to one (range efficient distinct element estimation) thereby relating them to each other. More general streaming results will be cool.