Penerapan teori representasi kelompok simetris

42

Terinspirasi oleh pertanyaan ini dan khususnya paragraf terakhir dari jawaban Or, saya memiliki pertanyaan berikut:

Apakah Anda tahu ada aplikasi dari teori representasi kelompok simetris di TCS?

Grup simetris adalah grup dari semua permutasi dari dengan komposisi operasi grup. Representasi adalah homomorfisme dari ke grup linear umum matriks kompleks. Representasi bekerja pada dengan perkalian matriks. Representasi tak tereduksi dari adalah tindakan yang tidak meninggalkan subruang yang tepat dari invarian. Representasi tak terhingga kelompok terbatas memungkinkan seseorang untuk mendefinisikan transformasi Fourier atas kelompok non-abelian $S_n$ $\{1, \ldots, n\}$ $S_n$ $S_n$ $n \times n$ $\mathbb{C}^n$ $S_n$ $\mathbb{C}^n$ . Transformasi Fourier ini berbagi beberapa sifat bagus dari transformasi Fourier diskrit atas grup siklik / abelian. Sebagai contoh, konvolusi menjadi perkalian titik-titik dalam basis Fourier.

The perwakilan teori dari grup simetris indah kombinatorial. Setiap representasi tak tereduksi dari sesuai dengan partisi integer dari . Apakah struktur ini dan / atau transformasi Fourier atas grup simetris menemukan aplikasi dalam TCS? $S_n$ $n$

co.combinatorics permutations fourier-analysis gr.group-theory Sasho Nikolov
sumber

lihat juga aplikasi grup simetris , wikipedia

vzn

semua jawaban yang sangat menarik. Saya akan kesulitan memilih satu untuk menerima.

Sasho Nikolov

pengantar / tinjauan teoretis murni yang layak, Young Tableaux dan Representasi dari Symmetric Group, oleh Zhao

vzn

2

Makalah ini baru saja mencapai arXiv-ph kuant: Sebuah solusi untuk tipikalitas dua pihak menggunakan teori representasi kelompok simetris oleh Janis Noetzel.

Tyson Williams

Faktorisasi Matriks Berbasis Simetri oleh Egner dan Puschel menggunakan elemen dan teori representasi untuk faktorisasi / dekomposisi / perkalian matriks yang efisien. lihat S3.2 tentang Perm-Perm simetri.

S_{n}

$S_n$

vzn

27

Berikut adalah beberapa contoh lainnya.

Diaconis dan Shahshahani (1981) mempelajari berapa banyak transposisi acak diperlukan untuk menghasilkan permutasi yang hampir seragam. Mereka membuktikan ambang yang tajam dari 1/2 n log (n) +/- O (n). Menghasilkan Permutasi Acak dengan Transposisi Acak .
Kassabov (2005) membuktikan bahwa seseorang dapat membangun expander derajat terbatas pada kelompok simetris. Grup Simetris dan Grafik Expander .
Kuperberg, Lovett dan Peled (2012) membuktikan bahwa ada set permutasi kecil yang bekerja secara seragam pada k-tuple. Keberadaan probabilistik dari struktur kombinatorial yang kaku .

Shachar Lovett
sumber

3

Terima kasih Shachar, dan selamat datang di cstheory! Saya mengambil kebebasan untuk memperbaiki tautan Anda: mereka agak tidak cocok

Sasho Nikolov

14

Pertanyaan yang sangat bagus. Saya tidak tahu jawaban lengkapnya dan ingin mengetahuinya sendiri. Namun, Anda mungkin menemukan hal-hal berikut yang menarik. Jika, alih-alih grup , kami menganggap 0-Hecke monoid , ia memiliki representasi pada kelas tertentu dari matriks bilangan bulat yang bertindak dengan tropis -plikasi ganda. Ini memiliki banyak aplikasi menarik dalam stringologi, melalui jalur terpendek banyak sumber dalam grafik mirip grid. Untuk detailnya, lihat laporan teknis saya: $S_n$ $H_0(S_n)$ $(\min,+)$

A. Tiskin. Perbandingan string semi-lokal: Teknik dan aplikasi algoritma. http://arxiv.org/abs/0707.3619

Alexander Tiskin
sumber

Terima kasih! Ini terlihat sangat menarik dan saya pasti akan memeriksanya.

Sasho Nikolov

14

Inilah salah satu contoh yang saya tahu:

`` Pada dugaan 'Log-Rank' dalam Kompleksitas Komunikasi '' , R.Raz, B.Spieker,

Proceeding of the 34th FOCS, 1993, pp. 168-177
Combinatorica 15(4) (1995) pp. 567-588

Saya percaya bahwa ada lebih banyak lagi.

Klim
sumber

3

Bisakah Anda meringkas model representasi apa dan bagaimana penerapannya?

Vijay D

@ VijayD mungkin Klim tahu lebih banyak, tetapi masalahnya di sini adalah bagaimana kompleksitas komunikasi suatu fungsi terkait dengan log peringkatnya (menganggap sebagai matriks nyata ). Mereka membangun dari peringkat dan CC . Pangkat dihitung dengan menuliskannya sebagai jumlah matriks dalam representasi reguler

f : {0, 1}^{n} \times {0, 1}^{n} \to {0, 1}

$f:\{0,1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}$

f

$f$

2^{d} \times 2^{d}

$2^d \times 2^d$

f

$f$

2^{O (n)}

$2^{O(n)}$

Ω (n \log \log n)

$\Omega(n \log \log n)$

f

$f$

S_{n}

$S_n$

Sasho Nikolov

Sebenarnya saya membaca makalah ini beberapa waktu yang lalu jadi sekarang saya tidak terlalu mengingatnya.

Klim

11

Berikut ini contoh dari komputasi kuantum:

Roland, Jeremie; Roetteler, Martin; Magnin, Loïck; Ambainis, Andris (2011), "Musuh Berbantuan Simetri untuk Generasi Negara Kuantum", Prosiding Konferensi Tahunan ke-26 IEEE 2011 tentang Kompleksitas Komputasi, CCC '11, Masyarakat Komputer IEEE, hlm. 167–177, doi: 10.1109 / CCC. 2011.24

Mereka menunjukkan bahwa kompleksitas kueri kuantum dari masalah tertentu yang disebut Penghapusan Indeks adalah menggunakan teori representasi dari kelompok simetris untuk membangun matriks musuh yang optimal untuk dihubungkan ke metode musuh kuantum. $\Omega(\sqrt{n})$

Robin Kothari
sumber

10

Knuth 3rd volume The Art of Computer Programming dikhususkan untuk mencari dan menyortir dan mencurahkan banyak untuk kombinatorik dan permutasi dan untuk korespondensi Robinson-Schensted-Knuth , yang merupakan pusat dalam teori representasi kelompok simetris.
Ada beberapa makalah oleh Ellis-Friedgut-Pilpel, dan Ellis-Friedgut-Filmus yang memecahkan masalah kombinatorial ekstrem menggunakan analisis harmonik pada . Tidak cukup TCS, tapi cukup dekat. $S_n$
Pada awal 90-an, Ajtai memiliki hasil yang luar biasa pada representasi modular yang dimotivasi oleh pertanyaan kompleksitas komputasi. Saya tidak ingat detailnya atau apakah itu dipublikasikan, tetapi ini layak untuk dibaca! $S_n$

Gil Kalai
sumber

Gil terima kasih! Saya percaya salah satu makalah oleh Ajtaj yang ada dalam pikiran Anda adalah yang ini: eccc.hpi-web.de/eccc-reports/1994/TR94-015/index.html . Saya pikir aplikasinya adalah kompleksitas bukti dari prinsip pigeonhole, tapi saya belum mengerti hubungannya.

Sasho Nikolov

6

Grup Symmetric Menentang Strong Fourier Sampling oleh Moore, Russell, Schulman

"Kami menunjukkan bahwa masalah subkelompok tersembunyi di atas kelompok simetris tidak dapat diselesaikan secara efisien dengan pengambilan sampel Fourier yang kuat ... Hasil ini berlaku untuk kasus khusus yang relevan dengan masalah Graph Isomorphism."

dengan koneksi untuk memecahkan masalah Graph Isomorphism melalui pendekatan QM

bagian 5 Teori representasi dari kelompok simetris

vzn
sumber

5

Lebih banyak statistik daripada ilmu komputer, tetapi masih menarik: Dalam bab 8 dalam monograf Diaconis tentang Presentasi Kelompok dalam Probabilitas dan Statistik , teknik analisis spektral untuk data yang terkait dengan grup dikembangkan. Ini memperluas analisis spektral yang lebih klasik dari data deret waktu mengatakan di mana alami adalah real atau bilangan bulat yang ditambahkan. Masuk akal untuk mengambil menjadi saat data diberikan oleh peringkat. Monograf tersebut menafsirkan koefisien Fourier dari data peringkat. Dalam hal set data diwakili oleh $G$ $G$ $G$ $S_n$ $f:S_n \rightarrow \mathbb{R}^+$ yang memetakan peringkat (diberikan oleh permutasi) ke fraksi populasi yang lebih memilih peringkat.

Juga dalam bab yang sama, analisis Fourier atas kelompok simetris dan lainnya digunakan untuk mendapatkan model dan tes ANOVA.

Perpanjangan alami ini akan menjadi teori pembelajaran statistik untuk masalah peringkat yang mendapat manfaat dari teknik teori representasi dengan cara yang mirip dengan cara belajar teori untuk klasifikasi biner di bawah distribusi seragam telah mendapat manfaat dari analisis Fourier pada kubus boolean.

Sasho Nikolov
sumber

Apa struktur kelompok alami untuk masalah peringkat?

Suresh Venkat

1

@Suresh Saya telah memikirkan grup simetris, tetapi paragraf terakhir saya lebih angan-angan daripada yang lain. Saya ada dalam pikiran masalah seperti junta pada peringkat: mempelajari fungsi yang tergantung pada pemesanan relatif hanya beberapa elemen dari beberapa sampel. Mungkin teknik fourier dapat memberikan batas sampel non-sepele

f : S_{n} \to {0, 1}

$f:S_n \rightarrow \{0, 1\}$

[n]

$[n]$

Sasho Nikolov

5

Teori representasi kelompok simetris memainkan peran kunci dalam pendekatan Teori Kompleksitas Geometrik untuk menurunkan batas pada determinan atau pada perkalian matriks.

Bürgisser dan Ikenmeyer membuktikan batas bawah pada peringkat perbatasan dari perkalian matriks menggunakan teori representasi . $S_n$
Untuk bagaimana teori representasi berhubungan dengan batas bawah pada determinan, lihat Teori Kompleksitas Geometrik II: Menuju Penghalang Eksplisit untuk Penyuluhan antara Varietas Kelas dan Teori Kompleksitas Geometris VI: Flip via positivity $S_n$

Joshua Grochow
sumber

4

Tesis Phs Huang, ALASAN PROBABILISTIK DAN PEMBELAJARAN PERMUTASI: mengeksploitasi dekomposisi struktural dari kelompok simetris . aplikasi ini adalah "skenario pelacakan multi-orang yang nyata berbasis kamera."
Fourier Theoretic Probabilityistic Inference atas Permutasi oleh Huang, Guestrin, Guibas; Jurnal Penelitian Pembelajaran Mesin 10 (2009) 997-1070. lihat misal 5. Teori Representasi pada Grup Symmetric
kertas aplikasi multitracking lain. Pelacakan multi-objek dengan representasi kelompok simetris (2007) oleh Kondor, Howard, Jebara
Belajar distribusi probabilitas melalui Permutasi oleh Sarana Koefisien Fourier, Irurozki, Calvo, Lozano (Dept CS / AI). lihat bagian 2 Transformasi Fourier pada Grup Symmetric

vzn
sumber

1

Saya sarankan menggabungkan jawaban ini dengan referensi permutasi pembelajaran lainnya

Sasho Nikolov

ok ... penggabungan ...

vzn

lihat juga Menafsirkan Spektrum Fase dalam Analisis Fourier Data Peringkat Parsial dan Pendekatan pemrosesan sinyal terhadap analisis data peringkat Fourier: pentingnya fase oleh Kakarala yang tampaknya memperpanjang kerja jauh sebelumnya oleh Diaconis

vzn

-1

Penerapan Teori Representasi Grup Symmetric untuk Perhitungan Polinomial Grafis oleh Grafik dan Klin

vzn
sumber

aplikasi

ps—

-2

makalah yang sangat dikutip oleh Beals, 1997, STOC ini tampaknya membuktikan bahwa perhitungan Quantum dari transformasi Fourier atas kelompok simetris adalah dalam BQP yaitu waktu polinomial kuantum

vzn
sumber

2

sekali lagi ini berlaku dengan kertas kuantum lain yang Anda rujuk. motivasi utama untuk mengembangkan transformasi Fourier non-abelian adalah menggunakannya untuk memecahkan masalah subkelompok tersembunyi di atas kelompok simetris. makalah lain yang Anda kutip menunjukkan bahwa pendekatan ini tidak menyelesaikan masalah.

Sasho Nikolov

btw menjadi jelas: apa yang saya maksud dengan komentar di atas adalah menyarankan untuk menggabungkan jawaban ini dengan jawaban QM lainnya dan menjelaskan bagaimana keduanya terkait (karena mereka)

Sasho Nikolov

ok Moore et al mengutip Beals meskipun bukan itu cara saya menemukan kertas Beals. mungkin bergabung nanti, tetapi saat ini beberapa audiens sepertinya tidak menyukai ref Beals ini karena alasan apa pun (tua, digantikan, dll ...?)

vzn

saya tidak yakin, saya pikir itu referensi yang ok. satu masalah bagi saya adalah bahwa Anda tidak menjelaskan mengapa penting untuk dapat menghitung transformasi fourier non-abelian, bagaimana ia termotivasi.

Sasho Nikolov

1

Saya lebih suka jika jawaban berdiri sendiri dan memberi pembaca cukup petunjuk untuk dapat memutuskan apakah akan membaca makalah lengkap atau tidak. Saya ingin jawaban untuk menunjukkan lebih dari sekadar pemahaman materi.

Sasho Nikolov

-5

contoh yang lebih tua, tetapi masih dengan penelitian terbaru / sedang berlangsung, beberapa teori ini muncul dalam matematika "shuffle sempurna" , dilihat sebagai elemen dari kelompok simetris & yang merupakan penemuan terkenal pada saat itu. [1] menyebutkan aplikasi dari shuffle sempurna untuk algoritma pemrosesan paralel dan juga koneksi ke Cooley-Tukey O (n log n) DFT. [2] lebih baru. shuffle sempurna muncul dalam pemrosesan paralel [3], desain memori, dan jaringan penyortiran.

[1] Matematika shuffle sempurna oleh Diaconis, Graham, Cantor. 1983

[2] Siklus permutasi shuffle multi -arah sempurna oleh Ellis, Fan, Shallit (2002)

[3] Pemrosesan paralel dengan pengocokan sempurna oleh Stone, 1971

[4] Jaringan Omega berdasarkan pengocokan yang sempurna

[5] Pengganti paralel dan berurutan di tempat dan pengocokan sempurna menggunakan involusi Yang et al (2012)

vzn
sumber

1

Apakah teori representasi digunakan dalam makalah ini?

Sasho Nikolov

tampaknya menjadi kasus khusus

vzn

2

apa kasus khusus apa? shuffle sempurna adalah permutasi. saya bertanya, apakah teori representasi digunakan dalam bukti di makalah ini? saya tidak menemukan apapun.

Sasho Nikolov

3

jika tidak, ada model probabilistik dari pengocokan (tidak sempurna), dan pengocokan berulang menggunakan salah satu dari model ini adalah berjalan acak pada permutasi. kita kadang-kadang dapat menganalisis waktu pencampuran jalan acak dengan menggunakan analisis fourier pada kelompok simetris: Shachar memberikan satu contoh untuk pengocokan transposisi acak. referensi Anda menarik, tetapi saya tidak melihat hubungan dengan teori representasi: makalah berkaitan dengan beberapa (dua dalam [1]) pengocokan deterministik dan kelompok permutasi yang mereka hasilkan. analisisnya tampaknya kombinasi

Sasho Nikolov

Pengocokan yang tidak sempurna juga menarik, tetapi seluruh jawabannya adalah pengocokan yang sempurna. Tampaknya hasil yang sama di atas dapat disusun kembali, atau dibuktikan melalui teori representasi, atau menggunakan beberapa aspek inti tanpa rujukan yang jelas / langsung. note shachars answer mengutip Diaconis, penulis yang sama pada salah satu makalah dalam jawaban ini. dengan kata lain penulis di atas pasti bisa menjawab pertanyaan Anda dengan lebih baik tetapi harapan saya adalah mereka akan menjawab setidaknya sedikit di afirmatif =) ... selain itu Anda baru saja menggambarkan teori representasi sebagai "kombinatorial yang indah" dalam pertanyaan Anda sendiri!

vzn

Penerapan teori representasi kelompok simetris

Jawaban: