# Extended formulations of polytopes Tiwary 14. 5. 2014

<{ForumPost(poster="mathemage", timestamp=2014-05-18 14:14:26)}>
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 $u$, a pošle ho společně s orientovanou hranou Alice. Pokud ona měla $u\in U$, započítá do výstupu, jinak vrátí $0$. Ke konci se musí upravit pravděpodobnosti, vynásobením vhodného faktoru úměrného velikosti $U$
* Bipyramida $B$ (polytop $P$ 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 $P$  
(zespoda aspoň $xc(P)$, protože $P$ je projekce $B$. Zeshora nejvýše $xc(P)+2$, 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.  :twisted:
<{/ForumPost}>