Pengujian properti di metrik lain?

Ada literatur besar tentang "pengujian properti" - masalah membuat sejumlah kecil permintaan kotak hitam ke fungsi untuk membedakan antara dua kasus:$f\colon\{0,1\}^n \to R$

1. $f$ adalah anggota dari beberapa kelas fungsi$\mathcal{C}$

2. $f$ adalah -far dari setiap fungsi di kelas .$\varepsilon$$\mathcal{C}$

Rentang fungsi kadang-kadang Boolean: , tetapi tidak selalu.$R$$R = \{0,1\}$

Di sini, -far umumnya diartikan sebagai jarak Hamming: fraksi titik yang perlu diubah untuk menempatkan di kelas . Ini adalah metrik alami jika memiliki rentang Boolean, tetapi tampaknya kurang alami jika kisaran tersebut dikatakan bernilai nyata.$\varepsilon$$f$$f$$\mathcal{C}$$f$

Pertanyaan saya: apakah ada untaian literatur pengujian properti yang menguji kedekatan dengan beberapa kelas sehubungan dengan metrik lainnya?$\mathcal{C}$

Ya ada! Saya akan memberikan tiga contoh:

1. Diberikan himpunan S dan "tabel perkalian" di atas S x S, pertimbangkan masalah menentukan apakah input menggambarkan grup abelian atau apakah itu jauh dari satu. Friedl, Ivanyos, dan Santha dalam STOC '05 menunjukkan bahwa ada penguji properti dengan kerumitan kueri polylog (| S |) ketika ukuran jarak berkaitan dengan jarak edit tabel perkalian yang memungkinkan penambahan dan penghapusan baris dan kolom dari tabel perkalian. Masalah yang sama juga dipertimbangkan dalam model jarak Hamming oleh Ergun, Kannan, Kumar, Rubinfeld dan Viswanathan (JCSS '00) di mana mereka menunjukkan kompleksitas kueri O ~ (| S | ^ {3/2}).

2. Ada sejumlah besar pekerjaan yang dilakukan pada pengujian properti grafik di mana grafik diwakili menggunakan daftar adjacency dan ada terikat pada tingkat setiap titik. Dalam hal ini, model jarak bukan jarak Hamming tepatnya melainkan berapa banyak tepi yang dapat ditambahkan atau dihapus sambil mempertahankan batas derajat.

3. Dalam studi yang berkaitan erat dengan sifat pengujian distribusi, berbagai gagasan jarak antara distribusi telah dipelajari. Dalam model ini, input adalah distribusi probabilitas pada beberapa set dan algoritma mendapatkan akses ke sana dengan pengambilan sampel dari set sesuai dengan distribusi yang tidak diketahui. Algoritme kemudian diperlukan untuk menentukan apakah distribusi memenuhi beberapa properti atau "jauh" dari itu. Berbagai pengertian tentang jarak telah dipelajari di sini, seperti L_1, L_2, earthmover. Distribusi probabilitas melalui domain tak terbatas juga telah dipelajari di sini ( Adamaszek-Czumaj-Sohler, SODA '10 ).

Biasanya tidak disebut pengujian properti (dan sebenarnya tidak), tetapi ada banyak pekerjaan dalam menentukan properti dari matriks dengan melihat minor yang diinduksi kecil. Ini sangat mirip dengan tujuan dalam pengujian properti. Lihat misalnya makalah oleh Rudelson dan Vershynin:

http://portal.acm.org/citation.cfm?id=1255449

Ada makalah sebelumnya oleh Frieze-Kannan. Intinya adalah bahwa biasanya metrik yang mereka gunakan adalah beberapa norma matriks seperti norma spektral, norma frobenius atau norma potong. Jika mau, Anda dapat menganggap beberapa hasil ini sebagai algoritme pengujian properti dalam metrik selain jarak Hamming.

$f\colon [n]^d\to \mathbb{R}$$L_p$$p\geq 1$$L_p$

$L_p$

$L_1$$L_1$$L_1$$n$$1$

$L_p$

$k$