Extended formulations of polytopes Tiwary 14. 5. 2014

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: