Hans si sedl před tabuli na chodbě na KAMu a dělal, že je studentem, kterého mám naučit jeho předmět. V angličtině jsem začal u tabule přednášet:
- polytop, extended formulation, extended comlexity
- slack matrix, non-negative rank, jejich souvislost
- protokol, souvislost s rankem
- aplikace pro spanning tree polytope (tady jsem popleltl s cut-polytope, pak totiz šel řešit NP-úplný max-cut v poly-čase, ale nakonec to přešel)
- konkrétně protokol pro span. tree polytope
Doplňující otázky (přemýšlecí, co nebylo na přednášce):
- jak upravit protokol pro čistě 1-směrnou komunikaci
[Jeden hráč "simuluje" zaslané bity 2. hráče pravděpodobnostně a pošle informaci o simulovaných bitech druhému. Pokud je byl býval nemohl zaslat, vydá nulový výstup, jinak je zakomponuje do výpočtu. - viz příklad dále]
- 1-směrný protokol pro span. tree polytope.
[Bob simuluje pravděpodobnostně Alicin výběr kořene , a pošle ho společně s orientovanou hranou Alice. Pokud ona měla , započítá do výstupu, jinak vrátí . Ke konci se musí upravit pravděpodobnosti, vynásobením vhodného faktoru úměrného velikosti
- Bipyramida (polytop s horní a spodní špičkou v přidané dimenzi, něco jako 2 homog. kužele nahoru a dolu) -> jeji ext. complexity oproti původnímu polytopu
(zespoda aspoň , protože je projekce . Zeshora nejvýše , důsledek věty o ext. complexity konvexního sjednocení.
I když jsem některé doplň. ot. nevěděl, dostal jsem nakonec za 1, páč je to fakt nová oblast matematiky.