Extended formulations of polytopes Tiwary 14. 5. 2014
Napsal: 18. 5. 2014 14:14
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
- 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í.