| 講演名 | 2012-09-03 Partially Symmetric Functions are Efficiently Isomorphism-Testable , |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | |
| 抄録(英) | Given a function f : {0,1}^n {0,1}, the f-isomorphism testing problem requires a randomized algorithm to distinguish functions that are identical to f up to relabeling of the input variables from functions that are far from being so. An important open question in property testing is to determine for which functions f we can test f isomorphism with a constant number of queries. Despite much recent attention to this question, essentially only two classes of functions were known to be efficiently isomorphism testable: symmetric functions and juntas. We unify and extend these results by showing that all partially symmetric functions-functions invariant to the reordering of all but a constant number of their variables-are efficiently isomorphism-testable. This class of functions, first introduced by Shannon, includes symmetric functions, juntas, and many other functions as well. We conjecture that these functions are essentially the only functions efficiently isomorphism-testable. To prove our main result, we also show that partial symmetry is efficiently testable. In turn, to prove this result we had to revisit the junta testing problem. We provide a new proof of correctness of the nearly-optimal junta tester. Our new proof replaces the Fourier machinery of the original proof with a purely combinatorial argument that exploits the connection between sets of variables with low influence and intersecting families. Another important ingredient in our proofs is a new notion of symmetric influence. We use this measure of influence to prove that partial symmetry is efficiently testable and also to construct an efficient sample extractor for partially symmetric functions. We then combine the sample extractor with the testing-by-implicit-learning approach to complete the proof that partially symmetric functions are efficiently isomorphism-testable. |
| キーワード(和) | |
| キーワード(英) | Property testing / Function isomorphism / Boolean functions / Partially symmetric functions. |
| 資料番号 | COMP2012-31 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2012/8/27(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Partially Symmetric Functions are Efficiently Isomorphism-Testable |
| サブタイトル（和） | |
| キーワード(1)（和/英） | / Property testing |
| 第 1 著者 氏名（和/英） | / Eric BLAIS |
| 第 1 著者 所属（和/英） | School of Computer Science Carnegie Mellon University |
| 発表年月日 | 2012-09-03 |
| 資料番号 | COMP2012-31 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | 199 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |