Recall testing 🔎: you have a notion of distance d(x,y), a parameter ε, and "access" to an object x (function f, graph G, proba. distribution p...); and in mind, a property ℘. Goal: does x have ℘, or do we have d(x,y) > ε for all y in ℘?
[x has ℘, or is ε-far from it]
2/7
[x has ℘, or is ε-far from it]
2/7
Now, "adaptivity"? Well, to decide the above question, you have to access your object x by making 'queries' (fct eval, edge lookups, samples, etc.). If the queries are decided in advance: non-adaptive algo; if queries depends on the answers to previous ones: adaptive algo.
3/7
3/7
In particular, adaptive algos can be much more query-efficient; non-adaptive ones are much more parallelizable 💡. So, how much can adaptivity help (in terms of queries)?
Q1: Let's say, when testing Boolean functions: unknown object x is f: {0,1}ⁿ → {0,1}.
4/7
Q1: Let's say, when testing Boolean functions: unknown object x is f: {0,1}ⁿ → {0,1}.
4/7
OK, but now, graphs? Let's first say in the "dense graph model," where the distance b/w n-node graphs is the fraction of their n×n adjacency matrices that differs, and the access is querying the adjacency matrix.
Q2: how much can adaptivity help in the dense graph model?
5/7
Q2: how much can adaptivity help in the dense graph model?
5/7
That was for graphs, so now... graphs? Consider "bounded-degree graphs," where the distance b/w n-node degree-d graphs is the fraction of their adj. lists that ≠, and the access is querying the incidence f'ct.
Q2: how much can adaptivity help in the bdd-degree model?
6/7
Q2: how much can adaptivity help in the bdd-degree model?
6/7
That's all for now. There are of course many other questions (what about "limited adaptivity"? What about other types of objects? Etc.). I hope to discuss some of that tomorrow, with the answers to today's quiz.
7/end
7/end
Clearly, that's Q3. Numbers are hard.
