Wednesday, April 5, 2017 - 4:00pm to 5:00pm

Location:

32-G575

Speaker:

Clément Canonne

Biography:

Columbia University

Seminar group:

Adaptivity is known to play a crucial role in property testing. In

particular, there exist properties for which there is an exponential gap

between the power of /adaptive/ testing algorithms, wherein each query

may be determined by the answers received to prior queries, and their

/non-adaptive/ counterparts, in which all queries are independent of

answers obtained from previous queries.

In this work, we investigate the role of adaptivity in property testing

at a finer level. We first quantify the degree of adaptivity of a

testing algorithm by considering the number of "rounds of adaptivity" it

uses. More accurately, we say that a tester is k-(round) adaptive if it

makes queries in k+1 rounds, where the queries in the i'th round may

depend on the answers obtained in the previous i-1 rounds. Then, we ask

the following question:

Does the power of testing algorithms smoothly grow with the number of

rounds of adaptivity?

We provide a positive answer to the foregoing question by proving an

adaptivity hierarchy theorem for property testing. Specifically, our

main result shows that for every integer n and 0 <= k <= n^{0.33} there

exists a property P_{n,k} of functions for which (1) there exists a

k-adaptive tester for P_{n,k} with query complexity ~O(k), yet (2) any

(k-1)-adaptive tester for P_{n,k} must make ~Omega(n/k^2) queries. In

addition, we show that such a qualitative adaptivity hierarchy can be

witnessed for testing natural properties of graphs.

Joint work with Tom Gur (Weizmann Institute).

particular, there exist properties for which there is an exponential gap

between the power of /adaptive/ testing algorithms, wherein each query

may be determined by the answers received to prior queries, and their

/non-adaptive/ counterparts, in which all queries are independent of

answers obtained from previous queries.

In this work, we investigate the role of adaptivity in property testing

at a finer level. We first quantify the degree of adaptivity of a

testing algorithm by considering the number of "rounds of adaptivity" it

uses. More accurately, we say that a tester is k-(round) adaptive if it

makes queries in k+1 rounds, where the queries in the i'th round may

depend on the answers obtained in the previous i-1 rounds. Then, we ask

the following question:

Does the power of testing algorithms smoothly grow with the number of

rounds of adaptivity?

We provide a positive answer to the foregoing question by proving an

adaptivity hierarchy theorem for property testing. Specifically, our

main result shows that for every integer n and 0 <= k <= n^{0.33} there

exists a property P_{n,k} of functions for which (1) there exists a

k-adaptive tester for P_{n,k} with query complexity ~O(k), yet (2) any

(k-1)-adaptive tester for P_{n,k} must make ~Omega(n/k^2) queries. In

addition, we show that such a qualitative adaptivity hierarchy can be

witnessed for testing natural properties of graphs.

Joint work with Tom Gur (Weizmann Institute).