Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
理論計算機科学における 数学の応用: 擬似ランダムネス
Search
Nobutaka Shimizu
August 16, 2024
Science
1
420
理論計算機科学における 数学の応用: 擬似ランダムネス
東北大学数学科で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
140
Hardness Self-Amplification: Simplified, Optimized, and Unified
nobushimi
0
260
Hardness Self-Amplification from Feasible Hard-Core Sets
nobushimi
0
190
Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH
nobushimi
0
130
How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?
nobushimi
0
110
Quasi-majority Functional Voting on Expander Graphs
nobushimi
0
59
Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models
nobushimi
0
110
Other Decks in Science
See All in Science
生成AI による論文執筆サポートの手引き(ワークショップ) / A guide to supporting dissertation writing with generative AI (workshop)
ks91
PRO
0
450
機械学習 - pandas入門
trycycle
PRO
0
150
CV_3_Keypoints
hachama
0
130
システム数理と応用分野の未来を切り拓くロードマップ・エンターテインメント(スポーツ)への応用 / Applied mathematics for sports entertainment
konakalab
1
260
テンソル分解による糖尿病の組織特異的遺伝子発現の統合解析を用いた関連疾患の予測
tagtag
2
130
The thin line between reconstruction, classification, and hallucination in brain decoding
ykamit
1
1.4k
Online Feedback Optimization
floriandoerfler
0
1.1k
All-in-One Bioinformatics Platform Realized with Snowflake ~ From In Silico Drug Discovery, Disease Variant Analysis, to Single-Cell RNA-seq
ktatsuya
0
360
点群ライブラリPDALをGoogleColabにて実行する方法の紹介
kentaitakura
1
150
MoveItを使った産業用ロボット向け動作作成方法の紹介 / Introduction to creating motion for industrial robots using MoveIt
ry0_ka
0
370
重複排除・高速バックアップ・ランサムウェア対策 三拍子そろったExaGrid × Veeam連携セミナー
climbteam
0
230
機械学習 - 授業概要
trycycle
PRO
0
110
Featured
See All Featured
The Straight Up "How To Draw Better" Workshop
denniskardys
232
140k
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
233
17k
Become a Pro
speakerdeck
PRO
27
5.3k
Optimising Largest Contentful Paint
csswizardry
36
3.2k
Docker and Python
trallard
44
3.3k
Principles of Awesome APIs and How to Build Them.
keavy
126
17k
Typedesign – Prime Four
hannesfritz
41
2.6k
Build The Right Thing And Hit Your Dates
maggiecrowley
35
2.6k
Improving Core Web Vitals using Speculation Rules API
sergeychernyshev
13
670
Exploring the Power of Turbo Streams & Action Cable | RailsConf2023
kevinliebholz
32
5.4k
Keith and Marios Guide to Fast Websites
keithpitt
411
22k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
34
2.2k
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]