$30 off During Our Annual Pro Sale. View Details »
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
理論計算機科学における 数学の応用: 擬似ランダムネス
Search
Nobutaka Shimizu
August 16, 2024
Science
1
350
理論計算機科学における 数学の応用: 擬似ランダムネス
東北大学数学科で2024年5月27日に行った談話会での発表資料
keyword: 擬似ランダムネス, エクスパンダーグラフ
Nobutaka Shimizu
August 16, 2024
Tweet
Share
More Decks by Nobutaka Shimizu
See All by Nobutaka Shimizu
Planted Clique Conjectures are Equivalent
nobushimi
0
83
Hardness Self-Amplification: Simplified, Optimized, and Unified
nobushimi
0
220
Hardness Self-Amplification from Feasible Hard-Core Sets
nobushimi
0
170
Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH
nobushimi
0
120
How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?
nobushimi
0
93
Quasi-majority Functional Voting on Expander Graphs
nobushimi
0
50
Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models
nobushimi
0
96
Other Decks in Science
See All in Science
240510 COGNAC LabChat
kazh
0
140
教師なしテンソル分解に基づく、有糸分裂後の転写再活性化におけるヒストン修飾ブックマークとしての転写因子候補の抽出法
tagtag
0
120
All-in-One Bioinformatics Platform Realized with Snowflake ~ From In Silico Drug Discovery, Disease Variant Analysis, to Single-Cell RNA-seq
ktatsuya
0
240
生成AI による論文執筆サポートの手引き(ワークショップ) / A guide to supporting dissertation writing with generative AI (workshop)
ks91
PRO
0
280
拡散モデルの概要 −§2. スコアベースモデルについて−
nearme_tech
PRO
0
610
機械学習を支える連続最適化
nearme_tech
PRO
1
160
はじめての「相関と因果とエビデンス」入門:“動機づけられた推論” に抗うために
takehikoihayashi
17
6.9k
ABEMAの効果検証事例〜効果の異質性を考える〜
s1ok69oo
4
2.1k
Factorized Diffusion: Perceptual Illusions by Noise Decomposition
tomoaki0705
0
240
Machine Learning for Materials (Lecture 7)
aronwalsh
0
830
【人工衛星】座標変換についての説明
02hattori11sat03
0
110
学術講演会中央大学学員会八王子支部
tagtag
0
240
Featured
See All Featured
Sharpening the Axe: The Primacy of Toolmaking
bcantrill
38
1.8k
[RailsConf 2023 Opening Keynote] The Magic of Rails
eileencodes
28
9.1k
Typedesign – Prime Four
hannesfritz
40
2.4k
Put a Button on it: Removing Barriers to Going Fast.
kastner
59
3.6k
YesSQL, Process and Tooling at Scale
rocio
169
14k
Optimising Largest Contentful Paint
csswizardry
33
2.9k
GitHub's CSS Performance
jonrohan
1030
460k
Navigating Team Friction
lara
183
15k
The World Runs on Bad Software
bkeepers
PRO
65
11k
A better future with KSS
kneath
238
17k
How GitHub (no longer) Works
holman
310
140k
Building Your Own Lightsaber
phodgson
103
6.1k
Transcript
ཧܭࢉػՊֶʹ͓͚Δ ֶͷԠ༻: ٖࣅϥϯμϜωε ਗ਼ਫ ৳ߴ (౦ژۀେֶ) ஊձ (20245݄27@౦େֶ)
•ཧܭࢉػՊֶͰ(૾Ҏ্ʹ)ֶͷ֓೦͕෯͘ొ •ֶͱཧܭࢉػՊֶͷڞ௨෦ͷҰͭ: ٖࣅϥϯμϜੑ ൃදͷ֓ཁ 2
•ཧܭࢉػՊֶͰ(૾Ҏ্ʹ)ֶͷ֓೦͕෯͘ొ •ֶͱཧܭࢉػՊֶͷڞ௨෦ͷҰͭ: ٖࣅϥϯμϜੑ •ʮ͜Ε͕͜Μͳͱ͜Ζʹڞ௨͕͋Δͷ͔ʂ(ڻ)ʯͱࢥͬͯ΄͍͠ ൃදͷ֓ཁ 3
•ཧܭࢉػՊֶͰ(૾Ҏ্ʹ)ֶͷ֓೦͕෯͘ొ •ֶͱཧܭࢉػՊֶͷڞ௨෦ͷҰͭ: ٖࣅϥϯμϜੑ •ʮ͜Ε͕͜Μͳͱ͜Ζʹڞ௨͕͋Δͷ͔ʂ(ڻ)ʯͱࢥͬͯ΄͍͠ •ʮงғؾʯΛհ ‣ ݫີͳఆٛূ໌ׂѪ ൃදͷ֓ཁ 4
ৗੜ׆ʹ͓͚Δܭࢉػͷར༻ 5
•ܭࢉػͷཧతͳೳྗͦͷݶքΛֶΛͬͯղ໌ (Ԡ༻ֶ) ‣ ࠷దԽΞϧΰϦζϜ ‣ ࠔੑ (ܭࢉྔԼք; ༧) ‣ άϥϑΞϧΰϦζϜ
‣ ҉߸, ֶशཧ ‣ Ϛϧίϑ࿈ ‣ ܭࢉ ‣ ྔࢠΞϧΰϦζϜ ‣ ࢄΞϧΰϦζϜ ‣ σʔλߏ ‣ etc 𝖯 ≠ 𝖭 𝖯 ཧܭࢉػՊֶ (Theoretical Computer Science) 6
TCSͱ(७ਮ)ֶͷܨ͕Γ 7 ରιϘϨϑෆࣜ ϥϯμϜΥʔΫͷղੳ Green—Taoͷఆཧ ऑֶशثͷϒʔεςΟϯά Kazhdanͷੑ࣭ (T) ཚԽ ޡΓగਖ਼ූ߸
Bogolyubov—Ruzsaͷิ ࠷ѱ͔࣌Βฏۉ࣌ͷؼண ପԁۂઢ҉߸ ପԁۂઢ ଟ༷ମͷCheegerఆ ނোੑωοτϫʔΫ άϥεϚϯଟ༷ମ 2-to-2༧ Hilbert’s Nullstellensatz Combinatorial Nullstellensatz ΞΠσΞΛഈआ ྫͷߏ ৽ͨͳઃఆ Connes ͷຒΊࠐΈ༧ MIP*=REఆཧ Baum—Connes༧ ηΩϡϦςΟ ฏۉ࣌ܭࢉྔ ੑ࣭ݕࠪ
TCSͱ(७ਮ)ֶͷܨ͕Γ 8 ରιϘϨϑෆࣜ ϥϯμϜΥʔΫͷղੳ Green—Taoͷఆཧ ऑֶशثͷϒʔεςΟϯά ཚԽ ޡΓగਖ਼ූ߸ Bogolyubov—Ruzsaͷิ ࠷ѱ͔࣌Βฏۉ࣌ͷؼண
ପԁۂઢ҉߸ ପԁۂઢ ଟ༷ମͷCheegerఆ ނোੑωοτϫʔΫ άϥεϚϯଟ༷ମ 2-to-2༧ Hilbert’s Nullstellensatz Combinatorial Nullstellensatz ΞΠσΞΛഈआ ྫͷߏ ৽ͨͳઃఆ Connes ͷຒΊࠐΈ༧ MIP*=REఆཧ Baum—Connes༧ ηΩϡϦςΟ ฏۉ࣌ܭࢉྔ Kazhdanͷੑ࣭ (T) ٖࣅϥϯμϜੑ (pseudorandomness)
•ٖࣅཚͷੜ ‣ ཚΛ͏໘ : ϥϯμϜΥʔΫ, MCMC, ֬తޯ๏, etc. ‣ ࣮ࡍͷܭࢉػͰٖࣅཚΛͬͯΔ
- : ԿΒ͔ͷؔ - ͰٖࣅཚΛͨ͘͞Μੜ ( ΛγʔυͱݺͿ) ‣ ༗໊ͳؔ : ϝϧηϯψπΠελ, ઢܗ߹ಉ๏, etc ‣ ྑ࣭ͳ(=࣍ͷग़͕༧ଌͰ͖ͳ͍)ٖࣅཚ͕ཉ͍͠ f: {0,1}32 → {0,1}32 s → f(s) → f(f(s)) → ⋯ s ٖࣅཚ 9
ٖࣅཚ 10 ग़య: e-Gov ๏ྩݕࡧ (https://elaws.e-gov.go.jp/document?lawid=503M62000000001) Χ ジ ϊཧҕһձؔಛఆෳ߹؍ޫࢪઃ۠Ҭඋ๏ࢪߦنଇ ୈ176ผද
(H30੍ఆ)
ٖࣅཚ 11 ग़య: e-Gov ๏ྩݕࡧ (https://elaws.e-gov.go.jp/document?lawid=503M62000000001) Χ ジ ϊཧҕһձؔಛఆෳ߹؍ޫࢪઃ۠Ҭඋ๏ࢪߦنଇ ୈ176ผද
(H30੍ఆ) •࣭͕ѱ͍ٖࣅཚͷࣄྫ (࣮) ‣ 2006ʹൃച͞ΕͨήʔϜιϑτʹͯʮμΠεͷ࣍ͷग़ͷۮح͕ਪଌͰ͖Δʯ ͱ͍͏க໋తͳόά͕ݟ͔ͭΓɺճऩʹࢸͬͨ.
•ٖࣅཚʹཉ͍͠ੑ࣭ ‣ Ұ༷ϥϯμϜͳ ʹର͠, ͕Ұ༷ϥϯμϜ - ݪཧతʹෆՄೳ ( ͕ܾ·Δͱ ܾ·Δ͔Β)
s (s, f(s)) s f(s) ٖࣅϥϯμϜੑ 12
•ٖࣅཚʹཉ͍͠ੑ࣭ ‣ Ұ༷ϥϯμϜͳ ʹର͠, ͕Ұ༷ϥϯμϜ - ݪཧతʹෆՄೳ ( ͕ܾ·Δͱ ܾ·Δ͔Β)
•ٖࣅϥϯμϜωε ‣ Ұ༷ϥϯμϜͳ ʹର͠, ͕Ұ༷ϥϯμϜͬΆ͘ݟ͑Δ ‣ Ұ༷ͱࣝผͰ͖ͳ͍Α͏ͳ s (s, f(s)) s f(s) s (s, f(s)) ٖࣅϥϯμϜੑ 13 ݅Λ؇
ͷࣝผ 14 01010101010101010101 01000111001111001111 ͋Δ ͔Βੜ͞Εͨ20จࣈ 𝒟 ࣝผऀ A ͬͪ͜Ұ༷ϥϯμϜ͡Όͳ͍
ͬͪ͜Ұ༷ϥϯμϜͰ͋Ζ͏ Ұ༷ ͔Βੜ͞Εͨ20จࣈ 𝒰
ͷࣝผ 15 01010101010101010101 01000111001111001111 ͋Δ ͔Βੜ͞Εͨ20จࣈ 𝒟 Ұ༷ ͔Βੜ͞Εͨ20จࣈ 𝒰
ࣝผऀ A ؔ : 20จࣈ 0 or 1 A ↦ ࣝผऀ ͕ ͱ Λ -ࣝผ ͢Δ A 𝒟 𝒰 ε def ⟺ Pr[A( 𝒟 ) = 1] − Pr[A( 𝒰 ) = 1] > ε
• Λ ʮ01010101010ʯʮ10101010101ʯͷͲͪΒ͔͕֬ Ͱग़ݱ •ࣝผऀ : ‣ 0ͱ1͕ަޓͳΒ1, ͦ͏Ͱͳ͍ͳΒ0Λग़ྗ •
0.999-ࣝผ ‣ ‣ 𝒟 1/2 A(s) A Pr[A( 𝒟 ) = 1] = 1 Pr[A( 𝒰 ) = 1] = 2/211 ≈ 0.001 ͷࣝผ (ྫ) 16
•ٖࣅϥϯμϜωε ‣ ੍ݶ͞ΕͨࣝผऀͷΫϥε Λߟ͑Δ (ଟ߲ࣜ࣌ؒΞϧΰϦζϜͳͲ) 𝒜 ٖࣅϥϯμϜੑ 17
ʹରͯ͠ -ٖࣅϥϯμϜ Ͱ͋Δ ҙͷ ͕ ͱ Λ -ࣝผ͠ͳ͍ 𝒟 𝒜 ε def ⟺ A ∈ 𝒜 𝒟 𝒰 ε શશೳͷࣝผऀ ੍ݶ͞Εͨࣝผऀ 011010100 ૉ൪ͷจࣈ͕1ͩʂ 0ͱ1͕ަޓ͡Όͳ͍͔Β Ұ༷ϥϯμϜ͔ͳ͊
•ٖࣅϥϯμϜωε ‣ ੍ݶ͞ΕͨࣝผऀͷΫϥε Λߟ͑Δ (ଟ߲ࣜ࣌ؒΞϧΰϦζϜͳͲ) 𝒜 ٖࣅϥϯμϜੑ 18
ʹରͯ͠ -ٖࣅϥϯμϜ Ͱ͋Δ ҙͷ ͕ ͱ Λ -ࣝผ͠ͳ͍ 𝒟 𝒜 ε def ⟺ A ∈ 𝒜 𝒟 𝒰 ε ✓ ܭࢉྔతٖࣅϥϯμϜੑ = ͕ޮతͳΞϧΰϦζϜͷ (ྫ: ଟ߲ࣜ࣌ؒΞϧΰϦζϜ) ✓ ߹ͤతٖࣅϥϯμϜੑ = ͕߹ͤతʹఆ·Δؔͷ (ྫ: ࣍ଟ߲ࣜ) 𝒜 𝒜 d
ܭࢉྔతٖࣅϥϯμϜੑ ฏۉ࣌ܭࢉྔ
•ܭࢉྔ: ܭࢉͷෳࡶੑ (࣌ؒ, ۭؒetc) ΛਤΔई ‣ ͕༩͑ΒΕͨͱ͖, Λܭࢉ͢ΔखؒͲΕ͘Β͍͔? x f(x)
ฏۉ࣌ࠔੑ 20
•ܭࢉྔ: ܭࢉͷෳࡶੑ (࣌ؒ, ۭؒetc) ΛਤΔई ‣ ͕༩͑ΒΕͨͱ͖, Λܭࢉ͢ΔखؒͲΕ͘Β͍͔? •࠷ѱ࣌ܭࢉྔ: ࠷ѱͳೖྗʹର͢ΔΞϧΰϦζϜͷڍಈ
‣ ͘͝গͷίʔφʔέʔεʹӨڹ͞Ε͏Δ ‣ “pessimism of worst-case analysis” [Frieze, McDiarmid, 1986] ‣ ༧ x f(x) 𝖯 ≠ 𝖭 𝖯 ฏۉ࣌ࠔੑ 21
•ܭࢉྔ: ܭࢉͷෳࡶੑ (࣌ؒ, ۭؒetc) ΛਤΔई ‣ ͕༩͑ΒΕͨͱ͖, Λܭࢉ͢ΔखؒͲΕ͘Β͍͔? •࠷ѱ࣌ܭࢉྔ: ࠷ѱͳೖྗʹର͢ΔΞϧΰϦζϜͷڍಈ
‣ ͘͝গͷίʔφʔέʔεʹӨڹ͞Ε͏Δ ‣ “pessimism of worst-case analysis” [Frieze, McDiarmid, 1986] ‣ ༧ •ฏۉ࣌ܭࢉྔ: ฏۉతͳೖྗʹର͢ΔΞϧΰϦζϜͷڍಈ ‣ গͳ͍ίʔφʔέʔεʹӨڹ͞Εʹ͍͘ x f(x) 𝖯 ≠ 𝖭 𝖯 ฏۉ࣌ࠔੑ 22
•ؔ ͷܭࢉ͕ฏۉ࣌ࠔ ‣ Ұ༷ϥϯμϜͳ ʹରͯ͠, ͷܭࢉ͕͍͠ ‣ ྫ: 10ܻͷϥϯμϜͳೋͭͷૉͷੵͷૉҼղ͍͠ (RSA҉߸)
f x f(x) ฏۉ࣌ࠔੑ 23
•ؔ ͷܭࢉ͕ฏۉ࣌ࠔ ‣ Ұ༷ϥϯμϜͳ ʹରͯ͠, ͷܭࢉ͕͍͠ ‣ ྫ: 10ܻͷϥϯμϜͳೋͭͷૉͷੵͷૉҼղ͍͠ (RSA҉߸)
•ฏۉ࣌ࠔͳؔ ٖࣅཚੜث ‣ ʮ͍͠ʯͱ͍͏ωΨςΟϒͳੑ࣭ΛϙδςΟϒͳ݁ՌʹԠ༻ ‣ ͕ฏۉ࣌ࠔ ҙͷଟ߲ࣜ࣌ؒΞϧΰϦζϜʹͱٖͬͯࣅϥϯμϜ - Ұ༷ϥϯμϜͳ ʹରͯ͠ ͷܭࢉ͍͔͠Β f x f(x) ⇒ f ⟺ (s, f(s)) s f(s) ฏۉ࣌ࠔੑ 24 [Nisan, Wigderson, 1994]
҉߸ 25 •҉߸ •डͨ͠ୈࡾऀʹ͍͔ͳΔใ࿙Ε͍͚ͯͳ͍ ‣ ҉߸จʹԿΒ͔ͷ౷ܭతಛ͕͋ͬͨΒඇࣗ໌ͳใ͕࿙ΕΔ ‣ ୈࡾऀʹͱͬͯϥϯμϜͳจࣈྻʹݟ͑Δ͖ Apple 0011101000100
҉߸ 26 •҉߸ •डͨ͠ୈࡾऀʹ͍͔ͳΔใ࿙Ε͍͚ͯͳ͍ ‣ ҉߸จʹԿΒ͔ͷ౷ܭతಛ͕͋ͬͨΒඇࣗ໌ͳใ͕࿙ΕΔ ‣ ୈࡾऀʹͱͬͯϥϯμϜͳจࣈྻʹݟ͑Δ͖ - ୈࡾऀ੍ݶ͞ΕͨܭࢉೳྗΛ༗͢ΔͱԾఆ
Apple 0011101000100
҉߸ 27 •҉߸ •༗໊ͳ҉߸ํࣜ ‣ RSA҉߸ (ϥϯμϜͳڊେͳೋͭͷૉͷੵͷૉҼղͷࠔੑΛԾఆ) ‣ ֨ࢠ҉߸ (ϥϯμϜͳ֨ࢠ্Ͱͷ࠷֨ࢠͷࠔੑΛԾఆ)
‣ ڀۃతͳඪ: ͷԾఆͷԼͰ҆શͳ҉߸Λ࡞Δ •ฏۉ࣌ࠔͳ 㱺 ΄ͱΜͲͷೖྗͰਖ਼͘͠ղ͚ͳ͍ 𝖯 ≠ 𝖭 𝖯 Apple 0011101000100
҉߸ 28 ग़య: e-Gov ๏ྩݕࡧ (https://elaws.e-gov.go.jp/document?lawid=413M60000418002)
҉߸ 29 ग़య: e-Gov ๏ྩݕࡧ (https://elaws.e-gov.go.jp/document?lawid=413M60000418002) •๏ྩͷจݴʹʮૉҼղʯʮ༗ݶମʯʮପԁۂઢʯ •େਉ͕ೝΊΕOKΒ͍͠
߹ͤతٖࣅϥϯμϜੑ ΤΫεύϯμʔάϥϑ
• : -ਖ਼ଇάϥϑ ‣ શʹଓ͍ͯ͠Δล͕ ຊ • : ୯७ϥϯμϜΥʔΫͷભҠ֬ߦྻ ‣
୯७ϥϯμϜΥʔΫ : Ұ༷ϥϯμϜͳྡʹભҠ ‣ G d d P P(u, v) = { 1 d 0 ΤΫεύϯμʔάϥϑ 31 3-ਖ਼ଇάϥϑ ͕ลΛͳ͢ {u, v} ͦΕҎ֎
• : -ਖ਼ଇάϥϑ ‣ શʹଓ͍ͯ͠Δล͕ ຊ • : ୯७ϥϯμϜΥʔΫͷભҠ֬ߦྻ ‣
୯७ϥϯμϜΥʔΫ : Ұ༷ϥϯμϜͳྡʹભҠ ‣ G d d P P(u, v) = { 1 d 0 ΤΫεύϯμʔάϥϑ 32 3-ਖ਼ଇάϥϑ ͕ลΛͳ͢ {u, v} ͦΕҎ֎ ఆٛ (ΤΫεύϯμʔάϥϑ) ભҠ֬ߦྻ ͷݻ༗ ͕ Λຬͨ͢ͱ͖ -ΤΫεύϯμʔͱ͍͏. P 1 = λ1 ≥ … ≥ λn ≥ − 1 max{|λ2 |, |λn |} ≤ λ λ
• : -ਖ਼ଇάϥϑ ‣ શʹଓ͍ͯ͠Δล͕ ຊ • : ୯७ϥϯμϜΥʔΫͷભҠ֬ߦྻ ‣
୯७ϥϯμϜΥʔΫ : Ұ༷ϥϯμϜͳྡʹભҠ ‣ G d d P P(u, v) = { 1 d 0 ΤΫεύϯμʔάϥϑ 33 3-ਖ਼ଇάϥϑ ͕ลΛͳ͢ {u, v} ͦΕҎ֎ ఆٛ (ΤΫεύϯμʔάϥϑ) ભҠ֬ߦྻ ͷݻ༗ ͕ Λຬͨ͢ͱ͖ -ΤΫεύϯμʔͱ͍͏. P 1 = λ1 ≥ … ≥ λn ≥ − 1 max{|λ2 |, |λn |} ≤ λ λ ؆୯ͷͨΊৗʹਖ਼ଇੑΛԾఆ ( ରশͳͷͰ࣮ݻ༗Λͭ) P
•ϥϯμϜΥʔΫͷऩଋੑ ‣ άϥϑ͕͋Δ݅Λຬͨ͢ͱ ͷ ্ͷҰ༷ʹҰҙʹऩଋ ‣ ऩଋͷ͞ͲΕ͘Β͍͔? Xt V ϥϯμϜΥʔΫͱΤΫεύϯμʔ
34 ೋ෦άϥϑ্Ͱऩଋ͠ͳ͍ ඇ࿈݁ͩͱऩଋઌ͕ҰҙͰͳ͍
•ϥϯμϜΥʔΫͷऩଋੑ ‣ άϥϑ͕͋Δ݅Λຬͨ͢ͱ ͷ ্ͷҰ༷ʹҰҙʹऩଋ ‣ ऩଋͷ͞ͲΕ͘Β͍͔? •ΤΫεύϯμʔάϥϑ ‣ ϥϯμϜΥʔΫͷऩଋ͕͍άϥϑ
Xt V ϥϯμϜΥʔΫͱΤΫεύϯμʔ 35 ೋ෦άϥϑ্Ͱऩଋ͠ͳ͍ ඇ࿈݁ͩͱऩଋઌ͕ҰҙͰͳ͍
•ૄͳΤΫεύϯμʔάϥϑ : ૄͳͷʹ࿈݁ੑ͕ڧ͍ ΤΫεύϯμʔͷݟͨ 36 ؆୯ʹஅͰ͖ͦ͏ அ͠ʹ͍͘
‣ ( ) ‣ શͯͷ -ΤΫεύϯμʔ •ఆ ʹରͯ͠
-ΤΫεύϯμʔଘࡏ͢Δ͔? ‣ ϥϯμϜʹ࡞Δͱਖ਼ͷ֬Ͱ (֬తख๏) ‣ ϥϯμϜਖ਼ଇάϥϑ •ϥϯμϜωεΛΘͣʹߏͰ͖Δ͔? (ཚ) → ∞ i → ∞ Gi λ λ < 1 λ λ = 2 d − 1 d + 0.01 ΤΫεύϯμʔάϥϑ 37 -ਖ਼ଇάϥϑͷ -ΤΫεύϯμʔͰ͋Δ d (Gi )i∈ℕ λ def ⟺ [Friedman, 2008]
•తͳߏ ‣ έΠϦʔάϥϑ (܈ͷ࡞༻ΛௐΔॏཁͳಓ۩) ‣ Margulisͷߏ (1973) … ‣ Lubotzky,
Phillips, and Sarnak (1988) ‣ Margulis (1988) ‣ Morgenstern (1994) ‣ ࣍ ͕ಛผͳ߹ͷߏ λ = 5 2 8 < 0.9 d ΤΫεύϯμʔͷߏ 38
•తͳߏ ‣ έΠϦʔάϥϑ (܈ͷ࡞༻ΛௐΔॏཁͳಓ۩) ‣ Margulisͷߏ (1973) … ‣ Lubotzky,
Phillips, and Sarnak (1988) ‣ Margulis (1988) ‣ Morgenstern (1994) ‣ ࣍ ͕ಛผͳ߹ͷߏ λ = 5 2 8 < 0.9 d ΤΫεύϯμʔͷߏ 39 ϥϚψδϟϯάϥϑ (“࠷దͳ”ΤΫεύϯμʔੑΛͭ) λ ≈ 2 d − 1 d
•߹ͤతͳߏ ‣ తͳߏͩͱײ (ͳͥΤΫεύϯμʔੑ͕Γཱͭͷ͔? )͕͍͠ ‣ Reingold, Vadhan, Wigderson (2002)
- δάβάੵ ‣ Marcus, Spielman, Srinivasta (2015) - શͯͷೋ෦ϥϚψδϟϯάϥϑͷߏ - ৫Γࠞͥଟ߲ࣜ (interlacing polynomial) •ະղܾ: ࣍7ͷϥϚψδϟϯάϥϑͷߏ ΤΫεύϯμʔͷߏ (ଓ) 40
•ཁૉ ͷू߹ ʹର͠, ࣍ͷ ্ͷ Λߟ͑Δ ‣ ্ͷ -ਖ਼ଇΤΫεύϯμʔάϥϑ Λߟ͑Δ
‣ ΛҰ༷ϥϯμϜʹબͿ ‣ Λ࢝ͱ͢Δ͞ ͷϥϯμϜΥʔΫͷܦ༝ Λग़ྗ n V Vℓ 𝒟 V d G = (V, E) u1 u1 ℓ − 1 (u1 , …, uℓ ) ٖࣅϥϯμϜੑ 41 u1 u2 uℓ
ٖࣅϥϯμϜੑ 42 άϥϑ ͕ -ΤΫεύϯμʔͳΒ, ʹର͠ -ٖࣅϥϯμϜ G λ
𝒟 𝒜 = {AS : S ⊆ V} (λ/4) ෦ू߹ ʹର͠, Λ S ⊆ V AS : Vℓ → {0,1} AS (u1 , …, uℓ ) = { 1 0 {u1 , …, uℓ } ∩ S ≠ ∅ ͦΕҎ֎ ఆཧ u1 u2 uℓ S = ్தͰ ͷΛ௨ա͔ͨ͠Ͳ͏͔ AS (u1 , …, uℓ ) S
• ͷݩʹʮ͋ͨΓʯorʮͣΕʯ͕͋Δ ‣ গͳ͘ͱ ݸͷʮ͋ͨΓʯ͕͋Δ - Ұ༷ϥϯμϜʹҾ͍͕ͨ͋ͨΔ֬ = •ಠཱҰ༷ϥϯμϜʹ ճ͘͡ΛҾ͘
‣ ʮ͋ͨΓʯ͕ҰճҎ্ग़Δ֬ = ‣ ճҾ͚, 99%ͷ֬Ͱ͋ͨΓΛҾ͚Δ ‣ ͜ͷͱ͖, ϏοτͷϥϯμϜωε͕ඞཁ V δn δ ℓ 1 − (1 − δ)ℓ ℓ = 10/δ 10 log2 n δ Ԡ༻ 43
• ͷݩʹʮ͋ͨΓʯorʮͣΕʯ͕͋Δ ‣ গͳ͘ͱ ݸͷʮ͋ͨΓʯ͕͋Δ - Ұ༷ϥϯμϜʹҾ͍͕ͨ͋ͨΔ֬ = • -ΤΫεύϯμʔάϥϑ্Ͱ
ʹैͬͯ ճ͘͡ΛҾ͘ ‣ άϥϑͷ࣍ ʹґଘ͠ͳ͍ఆʹͰ͖Δ ‣ -ٖࣅϥϯμϜͳͷͰ98%ͷ֬Ͱʮ͋ͨΓʯΛҾ͘ ‣ ༻͍ͨϥϯμϜωε V δn δ 0.04 𝒟 ℓ d n 𝒟 0.01 log2 n + 10 log2 d δ Ԡ༻ 44 u1 u2 uℓ ʮ͋ͨΓʯ ಠཱαϯϓϦϯάΑΓগͳ͍ʂ
•PCPఆཧ •ޡΓగਖ਼ූ߸ •ٖࣅཚੜث •ϋογϡؔ •ฏۉ࣌ܭࢉྔ ΤΫεύϯμʔάϥϑͷԠ༻ 45 [Charles, ’09] [Guruswami,
Kabanets, ’08], [Goldreich, Impagliazzo, Levin, Venkatesan, Zuckerman, 90] [Goldreich, 00] [Sipser, Spielman, 96] [Dinur, 07]
•୯ମෳମͷΤΫεύϯμʔੑ ‣ ߴ࣍ݩΤΫεύϯμʔ •ͷະղܾͷղܾͷཱऀ ‣ ϚτϩΠυʹؔ͢ΔMihail—Vazirani༧ ‣ ہॴݕࠪՄೳޡΓగਖ਼ූ߸ͷߏ •ຊߨٛͰհ ۙͷಈ:
ߴ࣍ݩΤΫεύϯμʔ 46
•ٖࣅϥϯμϜωε ‣ ७ਮֶͱTCSͷ྆ํʹݱΕΔ֓೦ ‣ , ܈, زԿֶʹԠ༻͞Ε͍ͯΔ(Β͍͠) •ΤΫεύϯμʔάϥϑ ‣ έΠϦʔάϥϑΛͬͯߏ
‣ ϥϯμϜωεΛʮઅʯͯ͘͠͡ΛҾ͘ํ๏ •ߴ࣍ݩΤΫεύϯμʔ ‣ ۙͷTCSͰϗοτͳ ‣ ߨٛͰΓ·͢ʂ ·ͱΊ 47 [Lubotzky, ’12]