Contoh Matematika “Tidak Terkait” yang Memainkan Peran Mendasar dalam TCS?

74

Harap sebutkan contoh-contoh di mana teorema dari matematika yang biasanya tidak dianggap berlaku dalam ilmu komputer pertama kali digunakan untuk membuktikan hasil dalam ilmu komputer. Contoh terbaik adalah mereka yang hubungannya tidak jelas, tetapi begitu ditemukan, itu jelas "cara yang tepat" untuk melakukannya.

Ini adalah arah yang berlawanan dari pertanyaan Aplikasi TCS ke matematika klasik?

Sebagai contoh, lihat "Teorema Green dan Isolasi dalam Grafik Planar" , di mana teorema isolasi (yang sudah dikenal menggunakan bukti teknis) terbukti kembali menggunakan Teorema Green dari kalkulus multivariat.

Apa contoh lain yang ada?

Derrick Stolee
sumber
Wiki komunitas.
Dave Clarke
Wiki komunitas sekarang sudah ada.
Derrick Stolee
Mengejutkan berapa banyak contoh tentang topologi dan geometri. Apakah kita hanya lebih terkejut dengan dua topik ini?
Suresh Venkat
7
Setelah cukup banyak contoh Area X diberikan, apakah itu membuat Area X tidak lagi "tidak berhubungan"?
András Salamon

Jawaban:

38

Maurice Herlihy, Michael Saks, Nir Shavit dan Fotios Zaharoglou mendapatkan hadiah Godel pada tahun 2004 untuk penggunaan topologi aljabar dalam studi beberapa masalah dalam komputasi terdistribusi.

Warren Schudy
sumber
1
Ini adalah contoh yang bagus!
Ryan Williams
25

Saya punya contoh dari sebuah karya yang saya tulis bersama Noga Alon dan Muli Safra beberapa tahun yang lalu:

Noga menggunakan teorema titik tetap aljabar tetap untuk membuktikan "Teorema Pembelah Kalung": jika Anda memiliki kalung dengan manik-manik jenis t dan Anda ingin membagi bagian-bagiannya di antara b orang sehingga masing-masing mendapat jumlah manik-manik yang sama dari masing-masing jenis ( anggap b membagi t), Anda selalu dapat melakukannya dengan memotong kalung di paling banyak (b-1) tempat.

Kami menggunakan teorema ini untuk membangun objek kombinatorial yang kami gunakan untuk membuktikan kekerasan dari Set-Cover.

Beberapa info lebih lanjut ada di sini: http://people.csail.mit.edu/dmoshkov/papers/k-restrictions/k-rest.html

Dana Moshkovitz
sumber
25

Dalam retrospeksi, ini mungkin jelas, tetapi saya selalu menyukai aplikasi Steele, Yao, dan Ben-Or untuk teorema Oleinik-Petrovsky / Milnor / Thom (membatasi jumlah Betti set semi-aljabar nyata) untuk membuktikan lebih rendah batas dalam pohon keputusan aljabar dan model perhitungan komputasi aljabar.

Jeffε
sumber
1
Jenis "dalam retrospeksi, sudah jelas" adalah jenis aplikasi terbaik. Hindsight adalah 20/20.
Derrick Stolee
25

Salah satu hasil favorit saya adalah penggunaan argumen topologis dalam bukti Lovasz tentang dugaan Kneser , dan penggunaan metode topologis ( dan teori kelompok ) dalam serangan Kahn-Saks-Sturtevant pada dugaan kuat Aandera-Rosenberg-Karp tentang penghindaran. .

Suresh Venkat
sumber
+1. Penggunaan argumen topologis dalam membuktikan pernyataan kombinatorial benar-benar epik. Pembaca yang tertarik dapat menemukan info lebih lanjut di sini: en.wikipedia.org/wiki/Topological_combinatorics
Robin Kothari
1
@Robin: Atau bagaimana dengan argumen geometris? Teorema utama kertas Bayer-Diaconis klasik pada pengocokan pas ditemukan dengan memikirkan pengocokan sebagai transformasi pengawet volume (peta pembuat roti: dobel dan lipat (mod 1) di sepanjang setiap sumbu) dari 52-cube. Sayangnya mereka menghilangkan sebagian besar jejak intuisi geometris dari kertas akhir dengan menggantinya dengan kombinatorik diskrit.
Per Vognsen
@ Per Vognsen: Saya tidak terbiasa dengan pekerjaan itu, jadi terima kasih untuk penunjuknya. Saya akan melihatnya.
Robin Kothari
2
Anda mungkin ingin menambahkan " metode topologi dan kelompok-teori " untuk Kahn-Saks-Sturtevant. Lagi pula, mereka benar-benar menggunakan aksi kelompok pada kompleks yang sederhana.
Joshua Grochow
2
Saya bertanya-tanya apakah layak "membangunkan" utas ini setelah satu tahun untuk menunjukkan referensi .. tapi itu utas yang bagus jadi mengapa tidak. Hasil Lovasz dan hasil lainnya, serta intro untuk "topologi aljabar untuk kombinatorialis" dapat ditemukan dalam monograf Matousek
Sasho Nikolov
22

Teori representasi kelompok hingga digunakan dalam pendekatan Cohn-Kleinberg-Szegedy-Umans untuk perkalian matriks . Mereka menunjukkan bahwa jika keluarga produk karangan bunga abelian dengan kelompok simetris memenuhi kondisi tertentu ada, maka ada algoritma perkalian matriks kompleksitas kuadratik.

Teori representasi (dari kelompok aljabar) juga muncul dalam pendekatan teori kompleksitas geometris Mulmuley dan Sohoni pada batas bawah. Belum jelas apakah ini dianggap sebagai aplikasi, karena tidak ada hasil kompleksitas baru yang telah dibuktikan dengan pendekatan ini, tetapi setidaknya koneksi yang menarik telah dibuat antara dua area yang pada awalnya memerah tampak sama sekali tidak berhubungan.

Joshua Grochow
sumber
21

sayaP=PSPSEBUAHCE

Ryan Williams
sumber
7
Saya juga menikmati trik polinomial untuk menemukan kecocokan sempurna dalam grafik bipartit dengan secara acak mengambil sampel determinan (terima kasih, Lovász).
Derrick Stolee
21

Teori aproksimasi (yang berurusan dengan aproksimasi fungsi rumit yang mungkin rumit atau tidak wajar dengan fungsi sederhana, seperti polinomial tingkat rendah) telah banyak digunakan dalam kompleksitas Sirkuit, kompleksitas kueri kompleksitas, Pseudorandomness dll.

Saya pikir salah satu aplikasi paling keren alat dari daerah ini berasal dari ini kertas Beigel, Reingold, dan Spielman, di mana mereka menunjukkan bahwa PP kelas kompleksitas ditutup di bawah persimpangan dengan menggunakan fakta bahwa fungsi tanda dapat didekati dengan rendah Fungsi rasional -degree.

Nisan dan Szegedy dan Paturi menunjukkan batas bawah untuk mendekati fungsi simetris oleh polinomial derajat rendah. Metode ini sering digunakan dalam membuktikan kompleksitas kuantum Quantum batas bawah. Lihat catatan kuliah Scott Aaronson , misalnya.

Srikanth
sumber
20

Gagasan lain yang indah: Gagasan Yao untuk menggunakan prinsip-prinsip minimum dan bukti bahwa game campuran memiliki keseimbangan (pada dasarnya dualitas pemrograman linier) untuk menunjukkan batas yang lebih rendah pada algoritma acak (dengan cara membangun distribusi melalui input ke algoritma deterministik).

Suresh Venkat
sumber
7
Juga bukti Noam Nisan terhadap Hard Core Lemma karya Russell Impagliazzo (dalam karya asli Russell)
Dana Moshkovitz
17

Teorema titik tetap ada di semua tempat ...

nHAI(catatann!)perbandingan, ya). Bukti dari fakta ini berjalan melalui geometri polytopes dimensi tinggi. Secara khusus, buktinya menggunakan ketidaksetaraan Brunn-Minkowski. Presentasi yang baik mengenai hal ini ada dalam buku Matousek tentang Lectures on Discrete Geometry (Bagian 12.3). Bukti asli adalah oleh Kahn dan Linial, dari sini .

Sariel Har-Peled
sumber
15

Ada banyak kegunaan teori informasi dalam ilmu komputer teoretis: misalnya, dalam membuktikan batas bawah untuk kode yang dapat didekode secara lokal (lihat Katz dan Trevisan), dalam bukti Raz tentang teorema pengulangan paralel, dalam kompleksitas komunikasi (lihat, misalnya, utas pekerjaan kompresi komunikasi, misalnya, karya Barak, Braverman, Chen dan Rao yang relatif baru, dan referensi di sana), dan masih banyak lagi pekerjaan lainnya.

Dana Moshkovitz
sumber
Tetapi apakah penggunaan ini benar-benar "tidak berhubungan"? Setidaknya dari sudut pandang yang naif, menurut saya teori informasi adalah salah satu bidang pertama yang terlintas dalam pikiran ketika seseorang pertama kali mendengar definisi, katakanlah, kode yang dapat didekodekan secara lokal.
arnab
Saya setuju bahwa teori informasi terkait dengan kode, misalnya, dan kode terkait dengan TCS. Pengulangan paralel mungkin merupakan contoh yang lebih kuat: mengapa Anda berpikir untuk menggunakannya untuk amplifikasi kesehatan untuk PCP?
Dana Moshkovitz
Ya, saya sepenuhnya setuju bahwa pengulangan paralel adalah contoh yang mengejutkan.
arnab
14

Alon dan Naor menggunakan ketidaksamaan Grothendieck untuk membuktikan algoritma perkiraan pada masalah max-cut . Saya pikir ada karya-karya berikutnya tentang topik itu, tetapi saya bukan ahli.

Menariknya, teorema yang sama digunakan oleh Cleve, Hoyer, Toner dan Watrous untuk menganalisis game XOR kuantum, dan Linial dan Shraibman menggunakannya untuk kompleksitas komunikasi kuantum. Setahu saya, hubungan antara ketimpangan Grothendieck dan dasar fisika kuantum ditemukan oleh Tsirelson pada 85, tetapi dua hasil yang saya sebutkan secara khusus membahas ilmu komputer.

Marc
sumber
Uhm, ini tidak akurat. Alon dan Naor memperkirakan norma cut dari sebuah matriks - ini terkait dengan max cut tetapi tidak sama.
Sasho Nikolov
13

Contoh yang bagus adalah teorema Barrington:

fdf4d .

S5

Diego de Estrada
sumber
12

Steker Shameless: penggunaan dugaan Isotropik (dan geometri cembung pada umumnya) dalam mendesain mekanisme privat diferensial yang optimal untuk pertanyaan linear dalam pekerjaan saya dengan Moritz Hardt .

Untuk menjawab sebagian pertanyaan Suresh di atas, saya pikir pertanyaan asli agak rumit karena "tidak biasanya dianggap berlaku dalam ilmu komputer". Beberapa teknik ini yang awalnya tampak "tidak berhubungan" menjadi "normal" seiring waktu. Jadi teknik yang paling sukses (mis. Analisis Fourier di Kahn-Kalai-Linial, metric embeddings di Linial-London-Rabinovich) bukan jawaban yang valid lagi.

Kunal
sumber
Mungkin saya akan menulis ulang pertanyaan untuk mengatasi ini.
Derrick Stolee
12

Teori kombinatorik / angka tambahan banyak digunakan dalam literatur ekstraktor. Saya pikir contoh pertama datang dari memperhatikan bahwa grafik Paley dapat digunakan sebagai ekstraktor yang baik, dan beberapa pertanyaan terbuka dalam teori bilangan aditif akan menyiratkan yang lebih baik. Referensi paling awal yang saya tahu adalah Zuckerman 1990 (lihat tesisnya ), tetapi dalam beberapa tahun terakhir ini telah menjadi area aktif dengan bolak-balik yang menarik antara TCS dan kombinatorik aditif. (Salah satu yang menonjol adalah bukti Dvir tentang dugaan bidang terbatas Kakeya, tapi ini tentu saja merupakan kontribusi TCS untuk matematika dan bukan sebaliknya.) A-priori tidak jelas mengapa pertanyaan matematika semacam ini, tentang jumlah dan produk set, akan menjadi penting untuk CS.

Boaz Barak
sumber
6
Contoh lain yang baik dalam uraian ini adalah penggunaan dugaan Hales-Jewitt baru-baru ini untuk membuktikan batas bawah nonlinier pada jaring epsilon untuk ruang rentang dimensi VC 2.
Suresh Venkat
11

Sleator, Tarjan dan Thurston membuktikan keberadaan keluarga tak terbatas pasangan pohon pencarian biner dengan nsimpul dan jarak rotasi 2n-6menggunakan geometri hiperbolik.

zotachidil
sumber
7

Hai(k2) baris :

k2 penghalang untuk matriks RIP eksplisit. STOC 2011: 637-644.

Aljabar linier yang digunakan untuk menyebarkan grafik:

Joshua D. Batson, Daniel A. Spielman, Nikhil Srivastava: Sparsifiers dua kali-ramanujan. STOC 2009: 255-262.

Jelani Nelson
sumber
6

Ini mungkin atau mungkin tidak masuk hitungan, tetapi baru-baru ini teori set Zermelo-Fraenkel dengan atom (ZFA) dan Fraenkel-Mostowski (FM) telah diterapkan pada studi sintaksis abstrak dengan pengikatan nama. ZFA diperkenalkan pada awal abad ke-20 sebagai alat untuk membuktikan kemandirian CH dan kemudian dilupakan, tetapi ditemukan kembali pada akhir 1990-an oleh dua ilmuwan komputer --- Gabbay dan Pitts --- mempelajari sesuatu yang sama sekali tidak terhubung.

Lihat makalah survei ini misalnya.

Dominic Mulligan
sumber
4

Aplikasi Kahn dan Kim untuk entropi grafik untuk menyortir di bawah informasi parsial (http://portal.acm.org/citation.cfm?id=129731). Mereka memberikan algoritma waktu polinomial pertama yang melakukan perbandingan jumlah yang optimal secara teoritis (hingga konstanta). Makalah ini merupakan karyawisata kecil dalam matematika, menggunakan beberapa argumen kombinatorial klasik, bersama dengan geometri cembung, entropi grafik, dan pemrograman cembung. Ada algoritma sederhana yang lebih baru, tetapi kami masih tahu bagaimana menganalisisnya tanpa entropi grafik.

Sasho Nikolov
sumber
3

Teori bilangan digunakan untuk mengembangkan RSA dan skema kriptografi kunci publik lainnya.

Antonio Valerio Miceli-Barone
sumber
0

Penemuan penggandaan Karatsuba mengejutkan.

pengguna3493
sumber
2
Gauss tidak akan setuju.
Jeffε