Fifty Shades of Adaptivity (in Property Testing)

Speaker: Clement Canonne , Columbia University

Date: Wednesday, April 05, 2017

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host: Pritish Kamath and Akshay Degwekar, CSAIL MIT

Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Fifty Shades of Adaptivity (in Property Testing)

Abstract: 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).

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Seminar Series 2016/2017.

Created by Rebecca Yadegar at Thursday, March 16, 2017 at 2:14 PM.