- Fifty Shades of Adaptivity ...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in April 2017
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
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:
Created by Rebecca Yadegar at Thursday, March 16, 2017 at 2:14 PM.