Nabidka clanku k referovani na doktorandsky seminar

Tuto stranku spravuji Jiri Matousek a Robert Samal. Mate-li zajem o referovani nejakeho dosud nezadaneho clanku, domluvte se s nimi ci poslete jednomu z nich e-mail.

Rada: Autori nekterych clanku nekdy mivaji na webu i pocitacovou prezentaci (prednasku). Pokud takovou najdete, muze pomoct vyhmatnout hlavni myslenky a rychleji clanku porozumet. To neznamena, ze je takove cizi prezentace potreba pouzivat, i kdyz ani na tom neni nic spatneho - ale pozor, na seminari chceme jit do vetsich detailu.

Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees by Adam Marcus, Daniel A. Spielman, and Nikhil Srivastava

Moc hezky a pomerne hluboky clanek o vlastnich cislech grafu a grafovych polynomech. Jak udelat expandery z libovolnych d-regularnich bipartitnich grafu. Vysvetlit zakladni nastroje poradne, nektere technicke casti dukazu by sly vynechat.

Apollonian structure in the abelian sandpile -- Lionel Levine, Wesley Pegden, Charles K. Smart

Jednoduchý model hromady písku: začneme s mnoha zrníčky na jednom mřížovém bodě (v rovině), a pak opakujeme: pokud na jednom vrcholu jsou alespoň 4 zrníčka, přesuneme po jednom na každého souseda. Otázka je jak to skončí. Pro velká n se objevují zajímavé struktury, připomínající soustavu do sebe vepsaných kružnic (to jsou ty Apolloniovské struktury). Zajímavý článek plný hezkých obrázků a diferenciálních rovnic, je potřeba říct s citem. Pro úvod do tématu je možné pouzít následující popularizační článek autora.

Computing a Nonnegative Matrix Factorization - Provably by Sanjeev Arora, Rong Ge, Ravi Kannan and Ankur Moitra

Nezapornou matici chceme rozlozit na soucin nezapornych matic male hodnosti; to je potrebne v uzasne mnoha ruznych aplikacich. Tento clanek podava algoritmy (presny a priblizny), ktere jsou polynomialni pro konstantni hodnost, dolni odhady prevodem na 3-SAT, a polynomialni algoritmus pro matice specialniho typu. Staci zamerit se na jeden ci dva z techto hlavnich vysledku.

On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing by Michael A. Forbes and Amir Shpilka

Problem vysetrovany v clanku spada vpodstate do linearni algebry. Autori uvadeji nekolik motivaci a souvislosti (testovani polynomialnich identit, rekonstrukce matic maleh hodnosti, teorie kodu a dalsi), z nichz staci zminit jen nektere podle vyberu. K prezentaci vybrat jenom cast, napr. je mozne se zamerit na rekonstrukci matic maleh hodnosti - tim by se z tohoto dlouhatanskeho clanku mohl vybrat rozumne dlouhy kus.

Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels by Erdal Arikan

Polární kódy nesouvisejí s polárnictvím, nýbrž s polarizací, tedy vyhraňováním rozdělení na skupiny. Je to nedávný objev v teorii kódů, ve smyslu Shannonovy teorie přenosu informace - a zřejmě jedna z největších událostí v této oblasti od dob Shannona. Je potřeba se prokousat určitým objemem terminologie a zkratek, vysvětlit princip polárních kódů a ukázat, proč fungují, tj. asymptoticky dosahují kapacity kanálu. Možná přístupnějším zdrojem může být například tato doktorská práce.

From Irreducible Representations to Locally Decodable Codes by Klim Efremenko

Lokálně dekódovatelné kódy jsou důležité v souvislosti s PCP větou, neaproximovatelností apod. Tento článek poskytuje obecnější konstrukci, s parametry podobnými jako předchozí výsledky, a dává příležitost naučit se nebo zopakovat něco o reprezentacích grup.

A simple algorithm for random colouring G(n, d/n) using (2+epsilon)d colours by Charilaos Efthymiou

Vtipný algoritmus na generování (skoro uniformně) náhodných obarvení v polynomiálním čase.

Subgraph Densities in Signed Graphons and the Local Simonovits-Sidorenko Conjecture by László Lovász

Čarování s posloupnostmi grafů podobné, ale jiné než u flag-algeber. Zde se užívají graphony -- limitní objekty, které tvoří limity některých grafových posloupností. Cílem je dokázat jistou nerovnost z extrémální kombinatoriky.

Computing the Distance between Piecewise-Linear Bivariate Functions by Guillaume Moroz and Boris Aronov

Jsou dane dve funkce na nejake oblasti v rovine. Obe jsou po castech, tedy po trojuhelnicich, linearni, ale kazda je definovana na jine triangulaci (predstavte si jednu triangulaci s trojuhelniky protahlymi ve smeru osy x, a druhou s trojuhelniky protahlymi ve smeru osy y). Chceme rychle vypocitat L2 vzdalenost techto dvou funkci. Posloupnosti nekolika triku, z nichz nektere jsou docela mazane, se problem prevede na vypocet hodnot polynomu jedne promenne v hodne bodech zaroven, coz se pak dela znamym algoritmem. Doporucuju metody, napr. v sekci 5, vysvetlit na prikladu konkretni racionalni funkce (jednoduche - ne te, ktera vychazi z puvodniho problemu s triangulacemi), misto obecnych vzorcu jako v clanku. Soustava (vhodných) lineárních rovnic se řeší v čase téměř lineárním (v počtu nenulových koeficientů). (Srovnejte se složitostí Gaussovy eliminace!) Využívá předchozí článek, a také Spectral Sparsification of Graphs týchž autorů.

On the random satisfiable process by Michael Krivelevich, Benny Sudakov and Dan Vilenchik

Náhodnou splnitelnou booleovskou formuli s n proměnnými (ve tvaru CNF) získáme tak, že náhodně zpermutujeme všechny možné klauzule, a pak (v tom náhodném pořadí) přidáváme klazule, pokud tím formule nepřestane být splnitelná. Autoři popisují, jak pro typickou takovou formuli, vypadají všechna její splňující ohodnocení a popisují polynomiální algoritmus, který pro formule tohoto typu splňující ohodnocení najde. (To v jistém smyslu ukazuje, že SAT je pro mnoho formulí lehký.)

Random Walks, Electric Networks and The Transience Class problem of Sandpiles by Ayush Choure and Sundar Vishwanathan

Model hromady písku na grafu se už hodně studoval a je matematicky velice zajímavý. V tomto článku se pracuje s jeho spojitou aproximací pomocí náhodných procházek. což je pěkný příklad obecného trendu studia diskrétních jevů spojitými metodami. Vybrat jenom některá tvrzení, hlavně se soustředit na srozumitelné vysvětlení modelu hromady a základních výsledků.

Clanky zamluvene

Catching the k-NAESAT Threshold by Amin Coja-Oghlan and Konstantinos Panagiotou (Ondra Bílka)

Snaha porozumět tomu, kdy začnou náhodné instance jistých NP-úplných problémů splnitelnosti být skoro jistě nesplnitelné. O takové problémy se zajímají též ve statistické fyzice. Loni jsme vyslechli článek v podobném duchu, zde přichází další pokrok - podaří se překonat obtíže s tzv. kondenzací a určit asymptoticky přesný práh. V tomto případě půjde spíš o přehledovou přednášku - vysvětlit pojmy a základní přístup, a ukázat malou část z výpočtů.

The distance approach to approximate combinatorial counting by A. Barvinok and A. Samorodnitsky (Tomáš Gavenčiak)

Trochu starší, ale významný výsledek. Najít v grafu (s ohodnocenými hranami) maximální párování je možné v polynomiálním čase, spočítat pro daný graf počet všech párování nikoli. Autoři ukazují, jak počet párování odhadnout pomocí hledání maximálního párování pro náhodně zvolené váhy hran.

Hypercontractivity, Sum-of-Squares Proofs, and their Applicationsby Boaz Barak, Aram W. Harrow, Jonathan Kelner, David Steurer, and Yuan Zhou (Martin Bohm)

Poměrně náročný článek o mnoha věcech, v jedné z asi nejzajímavějších oblastí výpočetní složitosti. Snaha porozumět Unique Games Conjecture, její souvislosti s hierarchiemi semidefinitních relaxací, expandéry pro malé množiny, a aproximací jistých operátorových norem. Lahůdka pro ty, kdo usilují o širší záběr. Je potřeba něco vybrat, možno prezentovat na 1-2 seminářích, i dva řečníci.

Constructive Discrepancy Minimization by Walking on The Edges by Shachar Lovett and Raghu Meka (Marek Krčál)

Novy konstruktivni dukaz pro obarveni s malou diskrepanci. Kratke a ne moc tezke.

The critical window for the classical Ramsey-Turán problem -- Jacob Fox, Po-Shen Loh, Yufei Zhao (Martin Balko)

Jedna z prvních aplikací Szemerédiho regularity lemma byl důkaz následující (extremální) věty: graf s n vrcholy, bez K_4 a s nezávislými množinami o(n) má maximálně zhruba n^2/8 hran. V článku se zkoumají příbuzné otázky, např. jak velká funkce může být na místě o(n). Zajímavé jsou ale metody: věty, které bylo zvykem dokazovat pomocí regularity lemma (a tudíž mj. získat velké konstanty) se zde dokazují jinak, pomocí varianty metody dependent random choice.

Small Complete Minors Above the Extremal Edge Density -- Asaf Shapira, Benny Sudakov (Michaela Seifrtová)

Klasický výsledek Madera říká, že graf s vysokým průměrným stupněm obsahuje hodně souvislý podgraf se skoro stejným průměrným stupněm. Autoři tento výsledek zesílí tím, že místo grafu s velkou souvislostí najdou dobrý expander. Jako aplikaci dokáží větu o tom, že graf s hodně hranami obsahuje velký úplný graf jako minor.