Fungsi acak tingkat rendah sebagai polinomial nyata

Apakah ada (wajar) cara untuk sampel fungsi boolean acak seragam yang derajatnya sebagai polinomial nyata paling banyak ? $f:\{0,1\}^n \to \{0,1\}$ $d$

EDIT: Nisan dan Szegedy telah menunjukkan bahwa fungsi derajat tergantung pada paling banyak koordinat , jadi kita dapat berasumsi bahwa . Masalah yang saya lihat adalah sebagai berikut: 1) Di satu sisi jika kita memilih fungsi boolean acak pada koordinat , maka derajatnya akan mendekati , jauh lebih tinggi dari . 2) Di sisi lain, jika kita memilih setiap koefisien tingkat paling secara acak, maka fungsi tidak akan boolean. $d$ $d2^d$ $n \leq d2^d$ $d2^d$ $d2^d$ $d$ $d$

Jadi pertanyaannya adalah: adakah cara untuk mengambil sampel fungsi boolean tingkat rendah yang menghindari dua masalah ini?

randomness boolean-functions bounded-degree Igor Shinkar
sumber

Apakah Anda ingin fungsi yang sebenarnya menjadi pembatasan polinomial nyata derajat untuk 0-1 masukan, atau apakah Anda ingin menjadi yang jika dan hanya jika untuk beberapa polinomial nyata dari gelar paling banyak ? Atau sesuatu yang lain?

d

$d$

f (x) = 1

$f(x) = 1$

p (x) > 0

$p(x) > 0$

p

$p$

d

$d$

Joshua Grochow

@ JoshuaGrochow Saya ingin fungsi yang ekspansi Fourier memiliki gelar . Itu pilihan pertama kamu.

d

$d$

Igor Shinkar

Apa model anda? Menulis fungsi sampel membutuhkan waktu , atau jika Anda ingin menampilkan ekspansi Fourier. Apakah konstanta tetap?

2^{n}

$2^n$

n^{O (d)}

$n^{O(d)}$

d

$d$

MCH

Saya menambahkan beberapa detail dalam pertanyaan.

Igor Shinkar

@MCH Jika fungsi jika derajat

(dengan nol berat badan di atas permukaan

), maka tidak dapat bergantung pada lebih dari

koordinat. Ini akibat dari Nisan dan Szegedy. Pikirkan kasus khusus

. Dalam hal ini kita tahu bahwa fungsi tergantung pada (paling banyak) 1 koordinat.

d

$d$

d

$d$

d 2^{d}

$d2^d$

d = 1

$d=1$

Igor Shinkar

Jawaban:

Berikut adalah algoritma yang mengalahkan upaya sepele.

Berikut ini adalah fakta yang diketahui (Latihan 1.12 dalam buku O'Donnell): Jika $f:\{-1,1\}^n\to\{-1,1\}$ adalah fungsi Boolean yang memiliki derajat $\le d$ sebagai polinomial, maka setiap koefisien Fourier dari $f$ , merupakan kelipatan bilangan bulat dari . Menggunakan Cauchy-Schwarz dan Parseval mendapatkan bahwa ada paling banyak koefisien Fourier bukan nol dan $\hat{f}(S)$ $2^{-d}$ $4^d$ $\sum_{S}{|\hat{f}(S)|}\le 2^{d}$ .

Ini menyarankan metode pengambilan sampel -

Pilih bilangan bulat non-negatif acak $a_S$ untuk semua set $S\subseteq[n]$ dari ukuran paling $d$ , yang jumlah sampai dengan $\le 4^d$ .
Biarkan $f(x) = \sum_{S}{\frac{a_S}{2^d} \chi_S(x)}$ .
Verifikasi bahwa $f$ adalah Boolean. Jika demikian, kembalikan $f$ . Lain, kembali ke $1$ .

Perhatikan bahwa untuk setiap derajat $\le d$ polinomial $f$ tepat satu pilihan bilangan bulat acak pada Langkah 1 akan menghasilkan polinomial $f$ . Probabilitas untuk mendapatkan derajat spesifik $\le d$ polinomial adalah

1 / (\binom{(\binom{n}{\leq d}) + 4^{d}}{4^{d}}) = 1 / O (n / d)^{d 4^{d}} .

$1/\binom{\binom{n}{\le d}+4^d}{4^d} =1/O(n/d)^{d4^d}.$ Oleh karena itu, kita perlu mengulangi proses ini paling banyak

O (n / d)^{d 4^{d}}

$O(n/d)^{d4^d}$ kali, dengan harapan, sebelum berhenti.

Tetap menunjukkan bagaimana melakukan langkah 3. Seseorang dapat mendefinisikan $A = \bigcup\{S:a_S\neq 0\}$ . Periksa itu $|A| \le d 2^d$ (yang harus dipegang oleh Nisan-Szegedy untuk setiap fungsi Boolean) dan kemudian mengevaluasi $f$ pada semua tugas mungkin untuk variabel dalam $A$ . Ini dapat dilakukan dalam waktu $2^{d 2^d}$ . Gur dan Tamuz menawarkan algoritma acak yang jauh lebih cepat untuk tugas ini, namun karena bagian ini tidak mendominasi kompleksitas waktu, ini sudah cukup.

Secara keseluruhan, algoritma menghasilkan sampel acak dengan derajat polinomial $\le d$ dalam waktu $O(\frac{n}{d})^{d4^d}$ . Dengan asumsi bahwa $n \le d2^d$ kompleksitas waktu adalah $2^{O(d^2 4^d)}$ .

Ini bukan waktu polinomial sampel algoritma, meskipun jauh lebih cepat kemudian sampling fungsi-benar acak (dalam hal probabilitas mendapatkan gelar tertentu $\le d$ polinomial adalah $1/2^{2^n}$ ).

Avishay Tal
sumber

Bagus! Sebenarnya ini memberikan suatu algoritma yang whp (wrt

) menghasilkan jumlah maksimum koordinat yang mungkin bergantung pada fungsi derajat rendah. Ambillah

untuk menjadi cukup besar, sampel banyak fungsi, dan untuk setiap fungsi hitung jumlah koordinat yang berpengaruh. Keluarkan jumlah maksimum yang Anda lihat.

d

$d$

n = 10 d 2^{d}

$n = 10d2^{d}$

Igor Shinkar