Information theory in property testing and monotonicity testing in higher dimensionstar, open

by Nir Ailon and Bernard Chazelle
Information and Computation
Volume 204, Issue 11 , November 2006, Pages 1704-1717
http://dx.doi.org/10.1016/j.ic.2006.06.001

彼らのSTACS2005論文のジャーナル版。
Property testing (「性質テスト」と私は訳しいるが、「性質検査」もいいかも) に関する論文。
乱択アルゴリズムのファンは要注目。
Property testingでは対象の族の上でのmetricを設定することが重要であるが、この論文ではそれを確率分布を通して考察している。
つまり、ある定義域D (有限集合と仮定) 上の2つの関数f,gの間の距離をf(x)\neq g(x)となるx\in Dの数として定義するのが今までの研究で行なわれていることだが、これをD上の一様分布からxをサンプルしたときにf(x)\neq g(x)となる確率と見なすのである。
よって、D上の分布として一様分布とは違うものを採用すれば違うmetricを誘導することができる。
この論文ではd次元超立方体(の頂点集合)上の関数の単調性に対するepsilon-testerとして、query complexityがO(2^d H/epsilon)というものを設計している。
ここでHは与えられた確率分布のエントロピーであるが、ただし、その分布に対して、周辺分布どうしが独立であることを仮定している。
このように計算量にエントロピーが入って来て、これによって既存のアルゴリズムよりよい計算量を導出できているところが面白い。