Konstruksi lebih baik daripada yang acak.

10

Saya tertarik pada contoh konstruksi dalam teori kompleksitas yang lebih baik daripada konstruksi acak.

Satu-satunya contoh konstruksi yang saya tahu adalah di bidang kode koreksi kesalahan. Kode aljabar-geometri lebih baik dalam beberapa rentang parameter daripada kode acak.

Orang dapat dengan mudah membuat contoh buatan seperti itu. Saya tertarik pada contoh-contoh seperti kode geometri aljabar, di mana mudah membuat konstruksi acak dan tidak jelas bagaimana melakukan yang lebih baik.

reference-request big-list derandomization pr.probability Klim
sumber

7

Pertanyaan ini sangat tidak jelas. Harap sebutkan paling tidak bidang apa yang Anda bicarakan.

Dave Clarke

Saya menambahkan tag [daftar besar] dan memberi tanda untuk perhatian moderator yang meminta mereka menjadikan pertanyaan ini sebagai wiki komunitas.

Tsuyoshi Ito

4

Saya suka pertanyaannya, tapi kami mungkin ingin membatasi ruang lingkup entah bagaimana. Jelas bahwa hal-hal seperti grup hingga, pesawat proyektif, dll., Jika Anda membuat parameter dengan cara yang benar (misalnya, kembar tiga yang melanggar asosiatif), akan memiliki parameter yang jauh lebih baik daripada konstruksi acak.

Peter Shor

Saya setuju bahwa pertanyaannya tidak jelas. Saya tidak bagaimana membatasi ruang lingkup. Setiap saran dipersilahkan. Minat saya adalah contoh menarik. Misalnya ketika untuk waktu yang lama konstruksi acak adalah yang terbaik dan orang membutuhkan ide-ide non-sepele untuk mengalahkannya.

Klim

@Dave, tidak yakin apakah ini perlu tag CW atau [daftar besar], jika sebuah pertanyaan tidak jelas, kita harus meminta OP untuk mengklarifikasi, perhatikan bahwa CW tidak dapat dipulihkan. IMHO, pertanyaan seperti ini dapat dimodifikasi dengan cara yang memang perlu menjadi pertanyaan besar.

Kaveh

11

$\lambda_2\leq \frac{2\sqrt{D-1}}{D}$ $D$ $\lambda_2\leq \frac{2\sqrt{D-1}}{D} + o(1)$ $\lambda_2\geq \frac{2\sqrt{D-1}}{D} - o(1)$ $o(1)$ $0$ $D$ $N\rightarrow \infty$

alpoge
sumber

10

$\{ 1,\ldots,N \}$ $\{ 1,\ldots,N\}$ $N^{0.9}$ $N^{1-o(1)}$

Luca Trevisan
sumber

6

$n$ $n-1$

Peter Shor
sumber

5

Secara umum, konstruksi acak dan konstruksi serakah mencapai batas yang sama (misalnya, kode koreksi kesalahan). Suatu ketika saya mendengar ceramah oleh Lovasz di mana dia mengatakan bahwa pilihan serakah dan pilihan acak pada dasarnya sama. Jadi, setiap konstruksi yang mengalahkan konstruksi serakah harus memberikan jawaban untuk pertanyaan Anda. Sebagai contoh cepat, konstruksi yang mencapai kapasitas grafik Sperner adalah jenis ini. Seperti yang dikatakan Peter Shor, sebenarnya ada banyak contoh dalam kombinatorik ekstrem.

Ugo
sumber

Konstruksi lebih baik daripada yang acak.

Jawaban: