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
290
理論計算機科学における 数学の応用: 擬似ランダムネス
東北大学数学科で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
45
Hardness Self-Amplification: Simplified, Optimized, and Unified
nobushimi
0
210
Hardness Self-Amplification from Feasible Hard-Core Sets
nobushimi
0
170
Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH
nobushimi
0
110
How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?
nobushimi
0
90
Quasi-majority Functional Voting on Expander Graphs
nobushimi
0
47
Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models
nobushimi
0
95
Other Decks in Science
See All in Science
Running llama.cpp on the CPU
ianozsvald
0
350
Cross-Media Information Spaces and Architectures (CISA)
signer
PRO
3
28k
ultraArmをモニター提供してもらった話
miura55
0
170
[NeurIPS 2023 論文読み会] Wasserstein Quantum Monte Carlo
stakaya
0
410
拡散モデルの原理紹介
brainpadpr
3
3.8k
Introduction to Graph Neural Networks
joisino
PRO
4
1.9k
第4回ナレッジグラフ勉強会 Knowledge Graph Embedding
maruru0090
0
240
Direct Preference Optimization
zchenry
0
260
位相的データ解析とその応用例
brainpadpr
1
360
HAS Dark Site Orientation
astronomyhouston
0
5.2k
20240420 Global Azure 2024 | Azure Migrate でデータセンターのサーバーを評価&移行してみる
olivia_0707
2
860
Machine Learning for Materials (Lecture 6)
aronwalsh
0
480
Featured
See All Featured
Large-scale JavaScript Application Architecture
addyosmani
508
110k
Producing Creativity
orderedlist
PRO
340
39k
Optimising Largest Contentful Paint
csswizardry
30
2.8k
The Cult of Friendly URLs
andyhume
76
6k
Statistics for Hackers
jakevdp
793
220k
How To Stay Up To Date on Web Technology
chriscoyier
786
250k
How to Ace a Technical Interview
jacobian
275
23k
Thoughts on Productivity
jonyablonski
66
4.2k
A designer walks into a library…
pauljervisheath
201
24k
Atom: Resistance is Futile
akmur
261
25k
Debugging Ruby Performance
tmm1
72
12k
Unsuck your backbone
ammeep
667
57k
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]