Clanky prednesene na doktorandskem seminari

Ramsey Theory, Integer Partitions and a New Proof of the Erdos-Szekeres Theorem by Guy Moshkovitz, Asaf Shapira (Jarda Hančl)

Pěkná souvislost mezi Ramseyovou teorií (nacházení jednobarevné monotónní cesty v hypergrafu) a počítáním vícerozměrných analogií rozkladů čísel.

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

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.

Independent sets in hypergraphs by Jozsef Balogh, Robert Morris, and Woiciech Samotij (Martin Bohm)

Podle odborniku jedna z nejvetsich udalosti poslednich let v teorii hypergrafu. Vybuduje se technicky nastroj, kterym se pak daji dokazovat vselijake vysledky o nezavislych mnozinach v ruznych hypergrafech. Velmi podobny vysledek dokazali nezavisle i Saxton a Thomason - je mozne referovat ktrykoliv z techto dvou clanku, jen mi ten od Balogha a spol. prisel mirne pristupnejsi. Dulezite je vysvetlit poradne hlavni vysledek a ukazat nejakou aplikaci. Potom by se dal rict algoritmus, ktery prislusne "kontejnery" najde, a nejspis nebude cas se propocitat celym dukazem (i kdyz dukaz zase tak dlouhy neni).

A relative Szemeredi theorem by D. Conlon, J. Fox, and Y. Zhao (Vojta Tůma)

Podstatne zjednoduseni legendarniho vysledku Greena a Taa o libovolne dlouhych aritmetickych posloupnostech prvocisel. Clanek je ve skutecnosti o hypergrafech, presneji o "relativni verzi" regularity lemmatu a souvisejicich vecech. Hlavni duraz bych doporucoval klast na objasneni formulace vysledku, ktera je pomerne nezvykla. Specialne zkusenost v teto oblasti ukazala, ze "funkce jsou lepsi nez mnoziny", na coz je potreba si trochu zvyknout.

Convex Equipartitions: The Spicy Chicken Theorem by Roman Karasev, Alfredo Hubard, and Boris Aronov (Zuzana Safernová)

Abychom meli taky aspon jeden topologicky clanek. Velmi prirozeny problem a pekna odpoved (pro mocniny prvocisel). Asi nelze prednest dukaz topologicke vety, tj. sekci 5, ale zbytek by se pri trose snahy mel dat vysvetlit.

On the Caccetta-Haggkvist Conjecture with Forbidden Subgraphs by Alexander A. Razborov (Martin Kupec)

Další použití flag algeber, které už jsme na semináři letos potkali. Zminovaná hypotéza Caccetta-Haggkvist je jeden z nejvýznamnějších současných otevřených problémů teorie grafů.

A Full Derandomization of Sch¨oning's k-SAT Algorithm by Robin Moser and Dominik Scheder (Du\u0161an Knop)

Schoninguv pravdepodobnostni algoritmus resi napriklad 3-SAT v case (4/3)^n, tedy exponencialnim, ale mnohem rychleji, nez prohledavanim vsech moznosti. Zde se autorum podarilo najit celkem jednoduchy algoritmus deterministicky (po rade vysledku jinych autoru, ktere byly mnohem slozitejsi a cas mely horsi).

An approximate version of Sidorenko s conjecture -- David Conlon, Jacob Fox, Benny Sudakov (Jan Kynčl)

Hypotéza Sidorenka (a také Erdöse a Simonovitse) říká, že je-li H bipartitní graf, tak náhodný graf má asymptoticky nejméně kopií H (coby podgrafů) ze všech grafů stejné velikosti a hustoty. V článku se tato hypotéza dokazuje pro speciální bipartitní grafy, a z toho se odvodí její přibližná verze pro všechny grafy. I zde se použije metoda Dependent random choice.

New results for the growth of sets of real numbers by Timothy G. F. Jones (Zuzana Safernová)

Jedno z důležitých témat v aditivní kombinatorice, kombinatorické geometrii a jiných oblastech je "expanze" různých přirozených funkcí více proměnných. Základním výsledkem je věta o součtech a součinech: pro konečnou množinu A reálných čísel musí být aspoň jedna z množin A+A a A.A podstatně větší než A. Tento poměrně jednoduchý a určitě krátký článek zkoumá podobné otázky pro jiné funkce, než součet a součin.

Tight Lower Bounds for Halfspace Range Searching by Sunil Arya, David M. Mount, and Jian Xia (Josef Cibulka)

Geometrický článek o problému vyhledávání v oblastech (range searching), podává dolní odhad pro jistý typ datových struktur, zesiluje starší výsledky.

A bound for the number of vertices of a polytope with applications by Alexander Barvinok (Marek Krčál)

Nedávno Esperet, Kardoš, King, Kráĺ a Norine dokázali hypotézu Lovásze a Plummera o exponenciálním počtu párování v 3-regulárních grafech bez mostů. Tento článek dokazuje slabší výsledek (exponenciální počet párování pro menší třídu 3-regulárních grafů) jednoduše a geometricky, použitím obecné věty na mnohostěn párování.

Two extensions of Ramsey s theorem -- David Conlon, Jacob Fox, Benny Sudakov (Martin Balko)

Dvě přirozená zesílení klasické Ramseyovy věty pro grafy. Další příležitost přiučit se, jak používat Dependent random choice.

2-Cancellative Hypergraphs and Codes -- Zoltán Füredi (Michaela Seifertova)

Článek o různých systémech množin inspirovaný teorií samoopravných kódů. Hlavní pojem, který se zkoumá, je 2-zkratitelný systém množin, tj. takový systém, že pro žádné čtyři množiny v systému, A, B, C a D, neplatí, že sjednocení A, B a C je stejné, jako sjednocení A, B a D. Rozmanité výsledky i metody, není třeba říkat všechno, ale určitě vysvětlit metodu v kapitole 10 -- vtipné využití polynomů.

On sunflowers and matrix multiplication by N. Alon, A. Shpilka, and C. Umans (Marek Eliáš)

Překvapivá a celkem jednoduchá souvislost kombinatorických domněnek, motivovaných maticovým násobením, se starou domněnkou o Delta-systémech neboli slunečnicích. Krátké důkazy, přečíst celé, ale není nutné vše odříkat.

The disjoint paths problem in quadratic time by Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Bruce Reed (Michal Voner)

Úloha: je dáno k dvojic vrcholů grafu, nalezněte pro každou dvojici cestu z jednoho vrcholu do druhého tak, aby vzniklých k cest bylo disjunktních (nebo řekněte, že to nejde). Tato úloha se uměla řešit v čase kubickém, článek to vylepšuje na kvadratický algoritmus. Používají se teorie minorů, tree-width, atd. Je potřeba citlivě podat, aby se tyto pojmy osvětlili i těm, kdo na ně ještě nejsou navyklí.

Nearly Complete Graphs Decomposable into Large Induced Matchings and their Applications by Noga Alon, A. Moitra and Benny Sudakov (Martin Kupec)

Dvě krásné konstrukce grafů s téměř neuvěřitelnou vlastností (plus aplikace, které stačí naznačit). Vynikající ilustrace toho, že v dnešní teorii grafů se nevystačí s kreslením malých obrázků.

Making polynomials robust to noise by A. A. Sherstov (V. Tůma)

Elegantne resi matematickou otazku o mnohoclenech, motivovanou komunikacni slozitosti. Trocha pravdepodobnosti a Fourierovy analyzy, vypada peclive a ciste napsane.

Complexity measures of sign matrices by N. Linial, S. Mendelson, G. Schechtman and A. Shraibman (Tereza Klimošová)

Jak "slozita" je dana matice nul a jednicek? To se da merit ruzne, napriklad hodnosti, a je to zakladni otazka napriklad v teorii komunikacni slozitosti a dalsich oblastech. Tento jiz trochu starsi clanek (N. Linial o nem dokonce mluvil na kolokviu KAM, jestli me pamet neklame) do teto oblasti prenasi pojem z teorie Banachovych prostoru, takzvanou faktorizacni normu. V souvisejicim clanku Lower Bounds in Communication Complexity Based on Factorization Norms se najdou nektere konkretni aplikace a dalsi poznatky. Velmi pekne a pomerne pristupne cteni o maticich.

A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem by Per Austrin and Subhash Khot (Pavel Rytíř)

Opravdu pomerne jednoducha redukce, ale mazana (staci vypravet o pripadu q=2). Pripomenuti teorie samoopravnych kodu.

Counting Stars and Other Small Subgraphs in Sublinear Time by Mira Gonen, Dana Ron, and Yuval Shavitt (Marek Tesař)

Hleda se pocet kopii pevneho grafu H v danem vstupnim grafu. Pro nektere H se to da (priblizne a pravdepodobnostne) udelat dokonce v sublinearnim case. V tomoto clanku se napriklad pro hvezdy najde algoritmus i dolni odhad temer stejneho radu. Delsi clanek, staci vybrat cast ilustrujici hlavni myslenky na jednoduchem pripade. (Doporuceno prof. Kratochvilem.)

3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General by Timon Hertli (Marek Krčál)

Přesný algoritmus na splnitelnost logických formulí, v čase exponenciálním ale lepším než triviální 2^n. Vlastně chytré pozorování, že dříve známý algoritmus funguje lépe, než ukazovala předchozí analýza. Autor je magisterský student.

Towards dimension expanders over finite fields by Zeev Dvir and Amir Shpilka (Zuzana Safernová)

Varianta na téma explicitní konstrukce objektů, které je snadné spočítat -- podobně jako jsou třeba grafové expandery s omezeným stupněm. Tentokrát chceme omezený počet lineárních transformací vektorového prostoru takových, že každému malému lineárnímu prostoru dostatečně "nafouknou" dimenzi.

A Center Transversal Theorem for Hyperplanes and Applications to Graph Drawing by Vida Dujmovic and Stefan Langerman (Jaroslav Hančl)

Geometrický článek s celkem pěknou větou Ramseyova typu o přímkách, důkaz používá několik zajímavých nástrojů. Vyřešený problém o kreslení grafů asi zas tak zásadní není, ale proč ne. Já osobně bych asi nezaváděl geologický formalismus s magmatem a řekl bych důkaz přímo, ale to je věc vkusu. Každopádně není nutné říkat všechna tvrzení.

The condensation transition in random hypergraph 2-coloring by Amin Coja-Oghlan and Lenka Zdeborová (Lukáš Mach)

Pokročilejší techniky z pravděpodobnostních metod v rigorózním důkazu existence podivuhodného fázového přechodu (samozřejmě známého fyzikům). Není třeba propočítávat a dokazovat vše.

An Upper bound on the number of Steiner triple systems by Nathan Linial and Zur Luria (Josef Cibulka)

Pěkné aplikace entropie v asymptotickém počítání. Navazuje na předchozí článek stejných autorů o počítání vícedimenzionálních permutací, ten by přicházel také v úvahu jako alternativa.

An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance by Amit Chakrabarti and Oded Regev (Tomáš Gavenčiak)

Clanek o zakladnim problemu v komunikacni slozitosti. Pouziva netrivialni pojmy a metody z pravdepodobnosti, ale myslim, ze vsechno je tam definovano a vysvetleno pomerne pristupnym zpusobem. Pro prezentaci na jeden seminar by asi stacilo vysvetlit dukladne zneni prislusnych vysledku z pravdepodobnosti a objasnit, jak z nich vyplyva reseni slozitostniho problemu. Kdyz se povede rict i neco ze sekci 3.2 a 3.3, tim lepe, nebo je mozne o tom navazat dalsi seminar nebo jeho kus.

Long cycles in subgraphs of (pseudo)random directed graphs by Ido Ben-Eliezer, Michael Krivelevich, and Benny Sudakov (Tomáš Valla)

Regularity lemma (ve verzi pro řídké orientované grafy) se použije na řešení následující otázky: kolik procent hran je třeba smazat z orientovaného grafu, aby neměl žádné orientované kružnice?

Transitive Sets in Euclidean Ramsey Theory by Imre Leader, Paul A. Russell, and Mark Walters (Jan Kynčl)

Zajimavy pokrok v patrani po euklidovsky ramseyovskych mnozinach. Krasna matematika, hezke otevrene problemy. Jeden z problemu vyresili pozdeji autori v clanku Transitive Sets and Cyclic Quadrilaterals.

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity by Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak (Milan Straka)

Znamenity algoritmicky vysledek - rychla aproximace editacni vzdalenosti, metody hlavne pravdepodobnostni. Doporucuji soustredit se na vetu 1.1 (horni odhad, tj. sekce 2.1 a 3), dolni odhad jen zminit. Zrejme budou potreba 2 seminare.

Jason P. Bell and Stanley N. Burris: Partition Identities I: Sandwich Theorems and Logical 0-1 Laws (Jaroslav Hančl)

Algebraic Independence and Blackbox Identity Testing by Malte Beecken, Johannes Mittmann, and Nitin Saxena (Zuzana Safernová)

Na tomto článku si člověk může zdravě provětrat a doplnit znalosti z algebry (polynomy a takové věci). Potřebné nástroje nejsou až tak vysoká věda, jak autoři naznačují (myslím, že všechny jsou nejpozději z 19. století), ale jejich použití je hezké. Řešený problém je motivovaný složitostí aritmetických obvodů hloubky 4 a týká se testování polynomiálních identit. Není potřeba dokazovat všechno, méně zajímavé věci se dají nechat jako černá skříňka.

Holographic algorithms by Leslie Valianti (Pavel Rytíř)

Popisuje pozoruhodnou metodu, jak vyrábět polynomiální algoritmy. Vychází se z neméně pozoruhodného algoritmu Fishera, Kasteleyna a Temperleyho, který vyjadřuje počet perfektních párování v rovinném grafu jako determinant a tudíž ho počítá v polynomiálním čase. (Tenhle algoritmus bychom zřejmě použili jako černou skříňku, ledaže by někdo měl chuť ho vysvětlit ve zvláštní přednášce.) Vlastní náplň Valiantova článku je, jak jiné problémy převádět na perfektní párování v rovinných grafech. Z dlouhého článku by se měl udělat hlavně aspoň jeden konkrétní příklad pořádně, aby bylo konkrétně vidět, jak metoda funguje, o zbytku jen stručné zmínky. Trochu pomoct s prezentací můžou třeba Caiovy slajdy. Téma se od té doby dále rozvinulo; pro informaci o novějších výsledcích a přístupech viz třeba články Valiant, Landsberg, Morton a Norine a Cai.

Finitely forcible graphons by L. LovĂĄsz and B. Szegedy (Tereza KlimoĹĄovĂĄ)

Dalťí pojednåní o grafonech -- limitåch grafových posloupností.

Quick Approximation to Matrices and Applications by A. Frieze and R. Kannan (Marek Krčál)

Starsi, ale pekny clanek o aproximacnich algoritmech pro huste grafy. Z aplikaci staci udelat treba jen MAXCUT, zato poradne (nebo samozrejme i vic, pokud cas dovoli). Na aproximaci tzv. rezove normy matice (cut-norm) existuji uz lepsi algoritmy (viz Alon a Naor), tato cast se muze rict i jako cerna skrinka.

Entropy-based Bounds on Dimension Reduction in L_1 by Oded Regev (Tomáš Gavenčiak)

Krátký článek (rychle si ho zamluvte!!!), ale o to pečlivěji by se měl přečíst a vysvětlit. Dává jednoduché řešení problému redukce dimenze v prostoru L_1, který byl svého času velmi populární (pro ty, kdo slyšeli o Johnsonově-Lindenstraussově zplošťovacím lemmatu: tohle ukazuje, že narozdíl od euklidovského prostoru se v L_1 zplošťovat prakticky nedá). Spojit s úvodem do entropie v rozsahu potřebném pro důkaz. Na druhé straně stačí říct podrobně případ k=2, a pro obecné k pouze formulovat výsledek a naznačit potřebné změny.

Dependent random choice by J. Fox and B. Sudakov (Jan Volec)

Prehledovy clanek o jednom peknem triku v pravdepodobnostni metode. Vybrat nekolik vhodnych kousku.

Approximate Center Points with Proofs by Gary L. Miller and Donald R. Sheehy (Jaroslav Horacek)

Pomerne jednoduchy clanek. Geometricke algoritmy, hledani priblizneho centra bodove mnoziny v prostoru velke dimenze pomoci Radonovy vety a Tverbergovy vety.

Resilient pancyclicity of random and pseudo-random graphs by Michael Krivelevich, Choongbum Lee, Benny Sudakov (Bernard Lidický)

Graf je pancyklický, pokud obsahuje cykly všech délek (od 3, 4, ... po počet vrcholů grafu). Ukazuje se, že náhodný graf je velice odolně pancyklický: je možno u každého vrcholú smazat skoro polovinu hran, a graf zůstane pancyklický.

An O(log n/log ln) approximation algorithm for the asymmetric traveling salesman problem by A. Asadpour, M. Goemans, A. Madry, S. Oveis Gharan, and A. Saberi (Tomáš Valla)

Vyhodnoceno jako nejlepsi clanek ze SODA 2010. Pro obycejneho obchodniho cestujiciho je znama aproximace az na konstantu, ale v orientovanem grafu je to tezsi. Tento clanek aproximaci vylepsuje elegantnim zpusobem a kombinaci rady nastroju, takze se z nej da pochytit rada uzitecnych veci.

OPTIMAL BOUNDS FOR SIGN-REPRESENTING THE INTERSECTION OF TWO HALFSPACES BY POLYNOMIALS by ALEXANDER A. SHERSTOV (Zuzana Safernová)

Clanek o problemu z teorie uceni, ale ve skutecnosti o velmi prirozenem problemu s polynomy. Mame mnozinu M danout jako prunik klinu (pruniku dvou poloprostoru) s diskretni krychli {0,1}^n, a chteli bychom ji reprezentovat mnohoclenem, v tom smyslu, aby mnohoclen byl kladny v bodech M a zaporny v bodech {0,1}^n mimo M. V clanku se dokazuje, ze to obecne nejde mnohoclenem stupne radove mensiho nez n.

Subexponential Algorithms for Unique Games and Related Problems by Sanjeev Arora, Boaz Barak, and David Steurer (Ivan Dovica)

Unique games zde neznamenaji opravdove hry, nybrz jednu z nejdulezitejsich znamych vypocetnich uloh, ktere se zatim vznaseji v prostoru "mezi P a NP". Takzvana Unique Games Conjecture pravi, ze zminena vypocetni uloha by mela byt NP-uplna, a z toho by plynula spousta uzasnych vysledku o neaproximovatelnosti vselijakych jinych uloh (napriklad maximalniho rezu). V tomto clanku se autori dostavaji mozna dost blizko v vyvraceni Unique Games Conjecture, konstruuji totiz algoritmus, bezici v case mensim nez exponencialnim. Metoda je velmi zajimava, je zalozena na vlastnich cislech grafu a zobecnuje takzvanou Cheegerovu nerovnost (vztah mezi druhym vlastnim cislem a expanzi). Na seminari doporucuji udelat podrobne algoritmus pro expanzi malych mnozin (vpodstate sekce 2 a 3 plus zdrave vybrana cast z dodatku) a u Unique Games jen formulovat vysledek a naznacit, jak se to dela. Stejne asi lepe na 2 seminare, mozne i pro 2 lidi.

Triangle Detection Versus Matrix Multiplication: A Study of Truly Subcubic Reducibility by Virginia Vassilevska Williams and Ryan Williams (Milan Straka)

Prekvapiva redukce: kdyby nekdo umel najit v grafu s vazenymi hranami trojuhelnik se zapornou vahou (pokud existuje) v subkubickem case, pak by sly nasobit boolovske matice (s operacemi OR a AND misto obvykleho scitani a nasobeni) v subkubickem case. A nekolik dalsich. Doporucuji rict jeden konkretni pripad, treba ten booleovsky nebo (min,+), jejich obecny ramec asi neni nutne zavadet.

The chance that a convex body is lattice-point free: A relative of Buffon's needle problem by Imre Bárány (Josef Cibulka)

Pro dané konvexní těleso, jaká je pravděpodobnost, že jeho náhodné posunutí neobsahuje žádný mřížový bod? Tato přirozená otázka souvisí s celočíselným programováním.

Triangle-intersecting Families of Graphs by by David Ellis, Yuval Filmus, and Ehud Friedgut (Jan Hladký)

Velmi prirozena otazka, kazde dva grafy z daneho souboru grafu na danych n vrcholech maji spolecny aspon 1 trojuhelnik, kolik grafu muze soubor maximalne mit? Ale pozoruhodne tezka, tento clanek ji resi pomoci harmonicke analyzy. Dlouhy, ale urcite se staci omezit na pripad p=1/2, ktery konci na strane 23.

Approximate kernel clustering by Subash Khot and Assaf Naor (Marek Krčál)

Aproximacni algoritmus pro jisty velmi obecny model shlukove analyzy. Pouziva semidefinitni programovani a pravdepodobnostni zaokrouhlovani. Prednest mozno pouze prvni cast, rekneme vetu 2.1 pro nejaky konkretni pripad, tj. algoritmus a jeho analyzu. Dalsi, patrne narocnejsi cast se tyka optimality aproximacnich faktoru za predpokladu takzvane Unique Games Conjecture - samozrejme se lze pokusit i o tu. Je potreba neopisovat na tabuli ci na slajdy vsechny vzorecky, ale rozlustit, co rikaji.

Random Formulas have Frozen Variables by Dimitris Achlioptas and Federico Ricci-Tersenghi (Pavel Rytíř)

V teoreticke fyzice i v jinych oborech je velky zajem o reseni problemu splnitelnosti (SAT) nahodne generovanych formuli. Pokud ma takova formule "hodne" klauzuli (nad jistym pomerne presne znamym prahem), je skoro jiste nesplnitelna a pokud ma "malo" klauzuli, pak splnujici ohodnoceni promennych se skoro jiste da najit pomerne jednoduchym a rychlym algoritmem. Ale v urcitem rozmezi poctu klauzuli se sice vi, ze nahodna formule bude skoro jiste splnitelna, ale pres velke usili se nikomu nepodarilo najit algoritmus, ktery by takove formule resil. Fyzici uz dlouho "vedeli", proc to tak je - nerigoroznimi metodami odvodili, ze splnujici ohodnoceni tvori male izolovane "dulky" v rozsahlem terenu vsech moznych ohodnoceni, a zname algoritmy nemaji sanci dulky objevit. V tomto clanku se takove veci matematicky formuluji a dokazuji. Pozor, neutopit prednasku ve vzoreccich, snazit se rikat hlavne myslenky.

On the size of Kakeya sets in finite fields by Zeev Dvir a navazujici clanky (Martin Tancer)

Kakeyova mnozina je mnozina v R^d, ktera obsahuje usecku jednotkove delky v kazdem smeru. Jeden z hodne prekvapivych matematickych vysledku je existence Kakeyovych mnozin miry nula (to dokazal Bezikovic zhruba pred 90 lety). S Kakeyovymi mnozinami je spojena rada zasadnich vysledku i problemu v analyze. Analogie Kakeyovych mnozin pro konecna telesa jsou zase dulezite napriklad v konstrukcich ruznych zarizenicek pro vylepsovani nahodnosti (mergers, extractors). V roce 2008 vyresil Zeev Dvir krasnym kratickym argumentem takzvanou Kakeyovu domnenku pro konecna telesa, ktera ukazuje, ze analogie Kakayovy mnoziny nad konecnym telesem mala byt nemuze. Mozno pouzit na 2-3 seminare pro dva lidi, zacit zacit uvodem o Kakeyovych mnozinach, rict Dviruv dukaz (ten je ale samotny prilis kratky na samostatny referat) a prejit k navazujicim clankum: Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers by Z. Dvir, S. Kopparty, S. Saraf, M. Sudan (z toho asi jen cast vylepsujici Dviruv dolni odhad), On lines and Joints by H. Kaplan, M. Sharir, E. Shustin.

Saving Space by Algebraization by Daniel Lokshtanov and Jesper Nederlof (Milan Straka)

Algoritmy na principu rychle Fourierovy ci Mobiovy transformace resi NP-uplne problemy, jako napriklad problem tlumoku (knapsack) v pseudopolynomialnim case a polynomialnim prostoru. Ten polynomialni prostor je to zasadni vylepseni. Vybrat samozrejme jen nektere z algoritmu.

A weaker version of Lovász' path removal conjecture by Ken-ichi Kawarabayashi, Orlando Lee, Bruce Reed, Paul Wollan (Rudolf Stolař)

Existuje funkce f(k) taková, že pro každý f(k)-souvislý graf a každou hranu v něm, existuje cyklus, který touto hranou prochází a po jehož odebrání zbyde k-souvislý graf. Klasická teorie grafů, příležitost doučit se věty, které se neprobírají ve standardních přednáškách z grafů (třeba Maderova věta a vlastnosti k-linked grafů). Vlastní důkaz je ale poměrně krátký.

Asymptotically optimal frugal colouring by Michael Molloy, Bruce Reed (Tomáš Valla)

Grafy s maximálním stupněm $\Delta$ se barví pomocí $\Delta+1$ barev, aby žádný vrchol nesousedil s více než $\beta$ vrcholy stejné barvy. Tento pojem autoři zavedli už před časem, teď dosáhnou asymptoticky optimálního $\beta = \Theta(\log \Delta/\log\log \Delta)$.

A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning by Daniel A. Spielman, Shang-Hua Teng (T. Gavenčiak)

Název říká vše -- cílem je lokálně zpracovat obrovský graf (třeba webu) a najít v něm "clustery", skupiny vrcholů, které jsou spolu propojeny více než jinam. Na článek navazují další dva, konečným výsledkem je extrémně rychlé řešení (některých) soustav lineárních rovnic.

Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations by Gabriel Nivasch (Josef Cibulka)

Davenportovy-Schinzelovy posloupnosti maji na KAM znamenitou tradici (Klazar, Valtr), a uz proto bychom meli trochu sledovat, co se kolem nich deje. Tento clanek vypada dlouhy a slozity, ale je zalozen vpodstate na jedinem novem triku, inovovane rekurenci (z predchoziho clanku). Vysvetlit problem a formulovat nove vysledky (neni treba zachazet prilis do detailu vsech vzorecku, ty si stejne nikdo nezapamatuje), a potom objasnit novou techniku na jednom prikladu, treba pro lambda_3(n) (novy dukaz Klazarova vysledku). Pripadne rict i konstrukci dolniho odhadu.

Sorting under Partial Information (without the Ellipsoid Algorithm) by Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Raphaël Jungers, J. Ian Munro (Marek Tesař)

Klasicka uloha o trideni s castecnou informaci, navazuje na clanek Kahna a Kima, vylepsuje algoritmus. Zajimave pojmy, hezky problem, hezka matematika. Delsi, potreba citlive vybrat vhodne casti.

Point configurations that are asymmetric yet balanced by Henry Cohn, Noam D. Elkies, Abhinav Kumar, and Achill Sch\"urmann (Josef Cibulka)

Zkoumaji se "hodne pravidelne" konfigurace bodu na sferach. Zajimava oblast, o niz jsme v minulych letech moc nemluvili.

Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs by Ashish Goel, Michael Kapralov, Sanjeev Khanna (Bernard Lidický)

Klasicke algoritmy na perfektni parovani v bipartitnim grafu jsou mnohem pomalejsi; pro n vrcholu a radove n^2 hran (husty graf) potrebuji n^{2.5}. Tady, za predpokladu regularity, se to dela v radove n log n - kouzlo s vhodnym Markovovym retezcem. Nevypada prilis slozite.

A bipartite strengthening of the Crossing Lemma by Jacob Fox, János Pach, Csaba D. Tóth (Marek Tesař)

Známé Crossing lemma dává odhad na počet průsečíků v rovinném nakreslení nerovinného grafu. V tomto článku se (za jistých předpokladů) tento výsledek zlepšuje, nejenom číselně (lepší odhad), ale také strukturálně: ukáže se, že každé rovinné nakreslení grafu obsahuje "l-mřížku" (dvě l-prvkové množiny hran, E_1 a E_2, kde každá hrana z E_1 protíná každou hranu z E_2). Velikost l závisí na počtu hran a vrcholů daného grafu, jak se dočtete v článku. V článku se využívá následucící výsledek stejných autorů.

Intersection patterns of curves by Jacob Fox, Janos Pach, and Csaba D. Toth (Jan Kyncl)

Klasická Ramseyova teorie říká, že každý graf s n vrcholy obsahuje úplný podgraf nebo nezávislou množinu velikosti řádově log n, ale nemusí obsahovat větší. Obdobně pro bipartitní grafy. V tomto článku se ukazuje, že pro průsečíkové grafy křivek v rovině je situace jiná, za jistých předpokladů je velikost úplného (bipartitního) podgrafu lineární v n! (Vykřičník není faktoriál, ale údiv.)

Solving MAX-r-SAT above a Tight Lower Bound by Noga Alon, Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo (Ondra Suchý)

V problemu Max-r-SAT chceme pro logickou formuli v konjunktivnim tvaru s r literaly v klauzuli najit prirazeni promennym, splnujici co nejvic klauzuli. Jednoduchy pravdepodobnostni argument ukazuje, ze z m klauzuli se vzdycky dat splnit aspon (1-2^{-r})m. Zde se ukazuje, ze rozhodnout, zda lze splnit tento pocet plus jeste k klauzuli navic, lze v case zavisejicim polynomialne na n a exponencialne na k (tj. fixed-parameter tractability). Metoda je velmi zajimava, vyuziva lemmatu z harmonicke analyzy od Bourgaina (to by bylo dobre najit a aspon naznacit, jak se dokazuje - mozna v dalsim seminari). (Doporuceno prof. Kratochvilem.)

On the measure of intersecting families, uniqueness and stability by Ehud Friedgut (Martin Tancer)

Klasická Erdös-Ko-Radoova věta říká, kolik nejvíc může být k-prvkových podmnožin n-prvkové množiny, pokud se každé dvě protínají. Různá její vylepšení hovoří o situaci, kdy se každé dvě množiny protínají alespoň ve dvou (třech, ...) prvcích. V tomto článku autor používá Fourierovu analýzu (v níž je přeborník) na množině {0,1}^n aby ukázal, že maximální systémy v Erdös-Ko-Radoově větě (a jejích vylepšeních) jsou robustní. Nejenom, že je jediné maximum (systém všech k-prvkových množin obsahujících jeden zvolený prvek), ale každá množina, která má "skoro maximální počet prvků", je tomuto maximu blízká. Velice pěkně napsaný a poučný článek. Pro zájemce existuje pokračování a vylepšení (autoří Dinur a Friedgut). Na Friedgutově stránce je k článku pěkná prezentace.

Ramsey games with giants by Tom Bohman, Alan Frieze, Michael Krivelevich, Po-Shen Loh, Benny Sudakov (Tomáš Valla)

Jeden z nejdůležitějších výsledků teorie náhodných grafů popisuje vznik obří komponenty: přidáváme-li do prázdného grafu (s n vrcholy) hrany v náhodném pořadí, napřed jsou všechny souvislé komponenty malé (řádově log n), a po přidání nemnoha hran vznikne právě jedna obří komponenta (velikosti lineární v n). V článku se zkoumá, jak se situace změní, když hrany grafu obarvíme a budeme zkoumat vznik obřích komponent v jednotlivých barvách.

On the possibility of faster SAT algorithms by Mihai Patrascu and Ryan Williams (Tomáš Gavenčiak)

Algoritmicky problem SAT (splnitelnost CNF formuli) s n promennymi neumi nikdo resit podstatne rychleji nez v case zhruba 2^n. Zde se redukcemi ukazuje, ze kdyz predpokladame takovouto tezkost pro SAT, i rada jinych problemu bude tezkych. Neni potreba rikat vsechny priklady. (Doporuceno prof. Kratochvilem.)

The lonely runner with seven runners by J. Barajas and O. Serra (Tomas Vyskocil)

Pozoruhodny ciselne-teoreticky problem osameleho bezce, zde se resi pripad sedmi bezcu. Nedelat rozbor vsech pripadu do detailu, vysvetlit jen myslenky a udelat treba nejake pripady pro ilustraci.

Anti-Ramsey Properties of Random Graphs by Tom Bohman, Alan Frieze, Oleg Pikhurko (David Hartman)

Autoři zkoumají, kdy má náhodný graf následující "anti-Ramseyovskou" vlastnost A(b,H): pro každé obarvení hran, kde se žádná barva neužívá více než b-krát, existuje podgraf isomorfní s H, v němž všechny hrany mají různou barvu.

Poly-logarithmic independence fools AC0 circuits by Mark Braverman (Milan Straka)

Kratky a velice chytry clanek, jeden z hitu sezony ve vypocetni slozitosti, od autora, o nemz nepochybne bude slyset cim dal vic. Dokazuje se, ze pseudonahodne generatory z velice siroke tridy osali vsechny booleovske obvody omezene hloubky. Nejlip pro nekoho, kdo nejakou slozitost vychodil, nicmene clanek vypada velice jasne napsany a vse potrebne v nem zda se je uvedeno nebo citovano. Kalkulace neni treba podrobne reprodukovat - soustredit se na podstatu veci.

A Short Proof of the Hajnal-Szemeredi Theorem on Equitable Coloring by H. A. Kierstead and A. V. Kostochka (Ondrej Suchy)

Hanjalova-Szemerediho veta pravi, ze kazdy graf maximalniho stupne r ma obarveni r+1 barvami, kde kazda barva se pouzije na skoro stejny pocet vrcholu (pocty se lisi nejvys o jednicku). Vskutku kratke a navic algoritmicke.

Message passing algorithms and improved LP decoding by Sanjeev Arora, Constantinos Daskalakis , and David Steurer

Tema patri do teorie samoopravnych kodu. Konkretne se pojednava o dekodovani takzvanych LDPC kodu (Low-Density Parity Check), jejichz zakladni myslenka je pres 40 let stara a velmi elegantni. Zde se dekodovaci problem pres linearni programovani (dekodovaci trik ze starsiho clanku Feldmana a spol) modeluje jako pravdepodobnostni otazka o stromech. Pravdepodobnostni cast (sekce 6) je pomerne nezavisla na zbytku a slo by ji rict zvlast, pripadne i vynechat. Mozno i pro dva recniky.

A constructive proof of the general Lovasz Local Lemma by Robin A. Moser and Gabor Tardos (Marek Krcal)

Puvodni dukaz LLL je nekonstruktivni: ukazuje, ze nejaky jev ma nenulovou pravdepodobnost, ale pravdepodobnost je nepatrna. Pocinaje clankem Becka se postupne dokazovaly silnejsi a silnejsi algoritmicke verze. Tahle je velmi obecna, proti puvodni Lovaszove verzi se v hodnote parametru nic neztraci a prislusny algoritmus je naprosto prirozeny.

Max Cut and the Smallest Eigenvalue by Luca Trevisan (Pavel Rytir)

Aproximacni algoritmus pro maximalni rez v grafu pomoci vlastniho cisla. Dava slabsi vysledek nez znamy Goemansuv-Williamsonuv algoritmus, ale nepouziva semidefinitni programovani. Staci prednest vetu 1.

Lion and Man: Can Both Win? by B. Bollobás, I. Leader, M. Walters (Tomas Valla)

Lev honí člověka v metrickém prostoru: kdo vyhraje? V článku se zkoumají "hry na honěnou" v metrických prostorech probíhající ve spojitém čase. Situace ohledně existence vyhrávajících (neprohrávajících) strategií přínášejí nečekaná překvapení.

A separator theorem for string graphs and its applications by Jacob Fox and Janos Pach (Josef Cibulka)

Pekna veta o prunikovych grafech krivek (tzv. nitacich) s radou aplikaci. Jasne napsane, neprilis komplikovane.

Large almost monochromatic subsets in hypergraphs by David Conlon, Jacob Fox, Benny Sudakov (Bernard Lidický)

Opět trocha Ramseyovy teorie. Pokud obarvíme hrany úplného grafu, tak největší jednobarevná klika je zhruba stejně velká jako největší "skoro jednobarevná" klika. Autoři ukazují, že když barvíme trojúhelníky v úplném grafu (čili trojice místo dvojic), situace se velice změní: "skoro jednobarevný" podgraf existuje mnohem větší. Tím se vyřeší problém Erdöse a Hajnala o diskrepanci v hypergrafech. Krátky a jednoduchý článek.

Epsilon-nets and union complexity by Kasturi Varadarajan (Jan Kynčl)

Epsilon-sit napriklad pro nejakou konecnou mnozinu X v rovine vzhledem k trojuhelnikum je mnozina N takova, ze kazdy trojuhelnik obsahujici vic nez epsilon.|X| bodu z X obsahuje take nejaky bod z N. To je dulezity pojem (napr. ve vypocetni geometrii nebo v teorii uceni). Vi se, ze pro zminene trojuhelniky vzdy existuje epsilon-sit velikosti radu (1/epsilon)log(1/epsilon). Tezka a dlouho otevrena otazka je, zda je potreba ten logaritmus (to ma vyznam napr. pro aproximacni algoritmy na minimalni pokryti, kde se tenhle logaritmus objevuje primo jako aproximacni faktor). V tomto clanku se log vylepsuje v nekterych pripadech na log log. Pokud by byli 2 zajemci, bylo by pekne porovnat metodu s clankem Small-size epsilon nets for axis-parallel rectangles and boxes (B. Aronov, E. Ezra, M. Sharir), kde se podobnych, v necem silnejsich vysledku dosahuje jinou metodou. Prirozene neni potreba probirat vsechny aplikace, jde o objasneni metody na 1-2 prikladech.

On the power of linear dependencies by Imre Bárány (Marek Tesař)

Máme několik jednotkových vektorů s nulovým součtem, chceme je přerovnat tak, aby všechny částečné součty byly malé. Autor zkoumá různé varianty tohoto klasického problému a ukazuje hezký způsob řešení. Hezká a jednoduchá lineární algebra, jednoduchý článek, který jde přečíst snadno a rychle.

Economical elimination of cycles in the torus by Noga Alon (Marek Sterzik)

Kratky Alonuv clanek, vylepsuje predchozi odhady na pocet vrcholu, ktere je potreba vymazat z d-dimenzionalniho toru (soucinu d kruznic), aby se presekaly vsechny topologicky netrivialni kruznice.

New approximation guarantee for chromatic number by Sanjeev Arora, Eden Chlamtac and Moses Charikar (Martin Pergel)

Kolika barvami se da v polynomialnim case obarvit kazdy 3-barevny graf? Dalsi pokrok v algoritmech na tento problem, pouzivajici modernich geometrickych nastroju. Asi v jedne prednasce vysvetlit veci z dodatku A (Blumuv algoritmus) a KPMS algoritmus a jeho analyzu a v dalsi prednasce nove veci.

Quasirandom Groups by Timothy Gowers (J. Bystron)

V kazde n-prvkove abelovske grupe existuje mnozina X aspon n/3 prvku, v niz rovnice xy=z nema reseni (operaci piseme multiplikativne kvuli dalsimu). Otazka byla, jestli se takova mnozina, s aspon cn prvky pro nejake pevne kladne c, najde tez v obecne konecne grupe. Zde se dokazuje zaporna odpoved. Velice pekna matematika a znamenite napsana. Navrhoval bych referovat pouze prvni 3 sekce, zato dukladne (2 seminare, jeden o kvazinahodnosti a jeden s vlastnim dukazem, vcetne kratkeho pripomenuti potrebnych veci o reprezentacich - ty se na matematice vetsinou berou ale na informatice pokud vim ne). Jedna vec je v clanku bez dukazu (ze PSGL_2(q) nema netrivialni reprezentace male dimenze); to se da v pripade zajmu najit v knize Davidoff-Sarnak-Valette a prislusny kus muzu poskytnout.

Censorship Resistant Peer-to-Peer Networks by Amos Fiat and Jared Saia (Rudolf Stolar)

Clanek o efektivnim sdileni dat mezi pocitaci v siti takovym zpusobem, aby ani vyrazeni urciteho procenta uzlu data nenarusilo. Nekolik triku a pravdepodobnostni metoda, ale pekna webova aplikace, abychom sli s dobou.

Finding small balanced separators by Uriel Feige and Mohammad Mahdian (Ondrej Suchy)

Cilem je najit v danem grafu maly rez, ktery graf rozdeli na priblizne stejne velke casti (stejne az na konstantni faktor). To je zakladem rady algoritmu typu rozdel a panuj. V tomto clanku pozoruhodny aproximacni algoritmus. Prezentaci smerovat k dukazu vety 4.1.

Induced Ramsey-type theorems by Jacob Fox and Benny Sudakov (Tomas Valla)

Podle Ramseyovy vety obsahuje kazdy graf G na n vrcholech nezavislou mnozinu nebo kliku velikosti zhruba log n, a tento odhad nelze obecne zlepsit. Ale kdyz predpokladame, ze G neobsahuje nejaky pevny (maly) graf H jako indukovany podgraf, odhad na velikost kliky nebo nezavisle mnoziny podstatne vzroste. V tomto clanku se vylepsuji kvantitativni vysledky ve vetach takovehoto typu. Staci dokazat jednu z nekolika hlavnich vet.

Linear time algorithms for finding a dominating set of fixed size in degenerated graphs by Noga Alon and Shai Gutner (Eva Jelinkova)

Nadpis je dlouhatansky, ale zato popisuje, co se v clanku dela. Doporuceno J. Kratochvilem.

A combinatorial algorithm minimizing submodular functions in strongly polynomial time by Lex Schrijver (Ondrej Rucky)

Dnes uz skoro "klasika" v kombinatoricke optimalizaci. Submodularni funkce jsou diskretni zalezitost, ale drive se umely minimalizovat jen pres spojite rozsireni a elipsoidovou metodu. Tohle je jeden ze dvou nezavisle objevenych kombinatorickych algoritmu. Pomerne kratke.

Simple deterministic approximation algorithms for counting matchings by M.Bayati, D.Gamarnik, D.Katz, C.Nair and P.Tetali (Bernard Lidicky)

Oblibena #P-tezka vypocetni uloha, zjistit kolik ma dany graf parovani, se da priblizne resit v polynomialnim case pravdepodobnostnimi algoritmy. Zde se pro grafy omezeneho stupne poda polynomialni aproximacni algoritmus deterministicky, zalozenych na celkem jednoduche myslence ze statisticke fyziky.

Bijective counting of plane bipolar orientations by Eric Fusy, Dominique Poulalhon and Gilles Schaeffer (Hossein Teimoori Faal)

Pocitani jistych rovinnych objektu pomoci bijekce, soucast sirsiho trendu nedavnych uspechu v enumeraci. Vysvetlit (pripomenout?) tez Gesselovo-Viennotovo lemma, ktere se v clanku pouzije.

Extremal problems on triangle areas in the plane and three-space by Adrian Dumitrescu and Csaba D. Tóth (Martin Tancer)

Mnozina n bodu v rovine v obecne poloze urcuje n nad 3 trojuhelniku. Kolik z nich muze mit jednotkovou plochu? V clanku se dokazuje novy hodni odhad a nekolik dalsich drobnych vysledku. Uvod do nekterych triku a technik diskretni geometrie.

How neighborly can a centrally symmetric polytope be? by Nathan Linial and Isabella Novik(Pavel Rytir)

Jake je nejvetsi k takove, ze existuje d-dimenzionalni stredove symetricky konvexni mnohosten s n vrcholy takovy, ze kazda k-tice vrcholu neobsahujici dva protilehle vrcholy tvori stenu? Tato otazka ma pozoruhodnou motivaci (analyza signalu a samoopravne kody) a v posledni dobe na ni pracovala rada lidi. Tento clanek dava asymptoticky odhad presny az na multiplikativni konstantu, pomerne jednoduse.

Additive approximation for edge-deletion problems by Noga Alon, Asaf Shapira, and Benny Sudakov (Martin Balek)

Kolik nejmene hran musime vymazat z daneho grafu, aby se stal tribarevny? Studuji se priblizne algoritmy pro problemy tohoto typu. Rozsahly clanek ma nekolik casti, patrne se stihne vysvetlit jen cast. Pripadne mozno i rozdelit mezi dva referujici. Rada dulezitych nastroju z teorie grafu, hlavne extremalni.

FOURIER MEETS MOBIUS: FAST SUBSET CONVOLUTION by ANDREAS BJORKLUND, THORE HUSFELDT, PETTERI KASKI, AND MIKKO KOIVISTO (Tomas Bily)

Neco jako rychla Fourierova transformace, ale pro funkce definovane na mnozine vsech podmnozin n-prvkove mnoziny. Jednoduchy napad, ktery urychli nekolik algoritmu.

Lower bounds on locality sensitive hashing by Rajeev Motwani, Assaf Naor, and Rina Panigrahy (Ales Privetivy)

Hasovani (hashing) je zakladni technika v datovych strukturach. "Locality sensitive hashing" proti normalnimu hasovani navic umistuje blizke klice do blizkych pozic tabulky, coz je dulezite napriklad pri vyhledavani nejblizsiho souseda. V tomto clanku se dokazuje pomerne jednoduse dolni odhad na nejlepsi mozne parametry takoveho hasovaciho algoritmu. Pouziva se jedna vec z harmonicke analyzy, a clanek je tedy zvlast vhodny pro nekoho, kdo vychodil kurs Nati Liniala a Gila Kalaie v unoru 2006.

Szemeredi's lemma for the analyst by Laszlo Lovasz and Balazs Szegedy (Jakub Bystron)

Zname Szemerediho regularity lemma, bez nejz se v moderni teorii grafu obejde uz malokdo, se v tomto clanku prenasi do rise spojitych funkci. Clanek je take soucasti sirsiho usili o porozumeni limitam nekonecnych posloupnosti grafu a podobnym vecem.

An exact Turan result for the generalized triangle by Oleg Pikhurko (Jan Hubicka)

Vety Turanova typu pro systemy trojic ci k-tic jsou obtiznym tematem, a proto i znacne specialni vysledky jsou pozoruhodne. V tomto clanku je videt nekolik uzitecnych technik, zejmena pristup pres tzv. stabilitu (vysledky typu "je-li pocet hran blizky extremalnimu, musi i cely hypergraf byt blizky extremalnimu hypergrafu").

Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: Sharper bounds, simpler proofs, and algorithmic applications by Leonid Gurvits (Petr Skovron)

Pozoruhodny pristup ke starym otazkam, jako napriklad Van der Waerdenove domnence o permanentu, pomoci nerovnosti pro specialni tridy polynomu.

Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1 by Piotr Indyk (Tomas Vyskocil)

Je dobre znamo, ze n-dimenzionalni prostor s euklidovskou metrikou se da vnorit do Cn-dimenzionalniho prostoru s L1-metrikou temer isometricky, rekneme s distorzi nejvys 2, pricemz C je vhodna konstanta. To se dokazuje pravdepodobnostne, a zapeklita otazka je, jak takove vnoreni zkonstruovat. V tomto prulomovem clanku se pomoci modernich nastroju (jako extraktoru nahodnosti) konstruuje vnoreni do ponekud horsi, ale temer linearni dimenze.

Near-optimal algorithms for unique games by Moses Charikar, Konstantin Makarychev, and Yury Makarychev (Pavel Nejedly)

Novy prispevek tohoto clanku je mozna zajimavy spis pro znalce, ale pojmy a techniky, se kterymi se tam pracuje, jsou velice dulezite. Algoritmus je zalozen na semidefinitnim programovani, a tyka se takzvane "Unique Games Conjecture", zajimave otazky v teorii aproximacnich algoritmu.

An elementary construction of constant-degree expanders by Noga Alon, Oded Schwartz, and Asaf Shapira (David Hartman)

Opravdu jednodussi nez predchozi konstrukce. Elegantni a pomerne kratky clanek.

Sparse universal graphs for bounded-degree graphs by Noga Alon and Michael Capalbo (Tomas Valla)

Graf je univerzalni pro danou mnozinu grafu, jestlize kazdy z nich obsahuje jako podgraf. Problem je sestrojit pokud mozno ridke univerzalni grafy. Kombinatoricke remeslo na mistrovske urovni.

Counting independent sets up to the tree threshold by Dror Weitz (Martin Pergel)

Nezavisle mnoziny v grafu maleho maximalniho stupne se daji nahodne generovat ci priblizne pocitat pomoci Markovovych retezcu. V tomto peknem clanku se dale posunuji hranice parametru, pro ktere to jeste funguje.

A Doubling Dimension Threshold Theta(loglog n) for Augmented Graph Navigability by P. Fraigniaud, E. Lebhar, and Z. Lotker (Ivan Dovica)

"Navigable" (splavny?) graf je takovy graf na n vrcholech, ze kdyz se vyrazi z nejakeho vrcholu a jde se "smerem" k jinemu, tj. v kazdem kroku se jde do takoveho souseda, ktery je cilovemu vrcholu nejbliz, pak se do cile dorazi v polylogaritmickem poctu kroku. Problem (motivovany pocitacovymi sitemi) je k danemu grafu pridat maly pocet hran "zkratek" tak, ze zacne byt splavny. V tomto clanku se dela hlavne dolni odhad.

Revisiting two theorems of Curto and Fialkow on moment matrices by Monique Laurent (Jan Foniok)

Pekny kratky a poucny clanek s algebraickym nadechem, staci rict dukaz vety 1.2. Problem momentu se pta, jake posloupnosti (m_j)_j mohou byt momenty nejake miry, kde j-ty moment miry mi je intergal x^j podle mi. V clanku se uvazuji miry mi na R^n koncentrovane v konecne mnoha bodech.

Measure and conquer: a simple O(2^{0.288n}) independent set algorithm by Fedor V. Fomin, Fabrizio Grandoni and Dieter Kratch (Ondrej Suchy)

Nova analyza stareho algoritmu, pomerne jednoducha zakladni myslenka.

Covering the n-space by convex bodies and its chromatic number by Zoltan Furedi and Jeong-Hyun Kang (Vit Jelinek)

Novy dukaz klasickeho Erdosova-Rogersova vysledku o minimalni hustote pokrytiR^n kopiemi daneho konvexniho telesa. Pekny kratky clanek.

Generating all vertices of a polyhedron is hard by Leonid Khachyian, Endre Boros, Konrad Borys, Khaled Elbassioni, and Vladimir Gurvitch (Jiri Fink)

Dokazuje se obtiznost jisteho enumeracniho problemu pro grafy a jako dusledek se dostane, ze je algoritmicky tezke vyrobit seznam vsech vrcholu mnohostenu daneho jako prunik poloprostoru. To byla vyznacna otazka v teorii linearniho programovani.

Graph powers, Delsarte, Hoffman, Ramsey and Shannon by Noga Alon and Eyal Lubetzky (Diana Piguet)

Nezavisle mnoziny v grafovych soucinech, Ramseyovske konstrukce, prevazne algebraicke metody. Mnoho poucnych metod a triku.

Group-theoretic algorithms for matrix multiplication by Henry Cohn, Robert Kleinberg, Balazs Szegedy, and Christopher Umans (Zdenek Dvorak)

Od dob Strassenova objevu, ze matice lze nasobit rychleji nez v case radu n^3, je otazka, jak rychle je tedy lze nasobit, jednim z nejzajimavejsich problemu teoreticke informatiky. Ale od clanku Coppersmithe a Winograda z roku 1990 nenastal skoro zadny pokrok. Az nyni prinasi tenhle krasny clanek novy pohled na vec v ramci teorie grup a dava novou nadeji na reseni problemu. Pro lidi, kteri se nevyhybaji opravdove matematice a specialne algebre. Pro pripravu referatu doporucuji postup shora dolu: Rozhodnout se, ktere vysledky rict (nabizi se jeden nebo dva konkretni algoritmy z clanku, plus souvislost s jednoznacne resitelnymi skladankami), a zjistit, co vsechno je na to potreba. Cast bude treba nastudovat v predchozim clanku Cohna a Umanse.

Generating Randomized Roundings with Cardinality Constraints and Derandomizations by Benjamin Doerr (Eva Ondrackova)

Mnoho kombinatorickych optimalizacnich problemu se da vyjadrit jako maximalizace linearni funkce pres vsechna celociselna reseni soustavy Ax=b. Optimalni realne reseni se da spocitat linearnim programovani. Pravdepodobnostni zaokrouhlovani je trik, jimz se nekdy z optimalniho realneho reseni da ziskat dobre celociselne reseni, pricemz ale soustava Ax=b uz nemusi byt splnena presne. Tento clanek pojednava o situaci, kdy na presnem splneni nekolika vyznacnych rovnic trvame. Konferencni verze clanku, plnou verzi dodam zajemci na vyzadani.

Constructions of Non-Principal Families in Extremal Hypergraph Theory by Dhuruv Mubayi and Oleg Pikhurko (Kamila Bumbova)

Kratky clanek o utrapach, ktere cekaji kazdeho zobecnovatele Turanovy vety na systemy k-tic.

O(\sqrt{log n}) approximation to SPARSEST CUT can be found in \tilde O(n^2) time by Sanjeev Arora, Elad Hazan and Satyen Kale (Jakub Cerny)

Hledani nejridsiho rezu v grafu, tj. rozdeleni vrcholu na dve neprazdne casti A a B tak, ze pocet hran mezi A a B deleny min(|A|,|B|) je minimalni, je urcite jednim z algoritmickych problemu, ktere inspirovaly vyvoj nejzajimavejsich metod a vysledku. Dlouho byl nejlepsi polynomialni algoritmus s aproximacnim faktorem log n. Vloni to Arora a spol zlepsili na odmocninu z log n, a tento clanek se stara o "rychly" vypocet (z polynomialniho casu s velkym exponentem ke skoro kvadratickemu). Je potreba rict a radne objasnit vetu Arory, Raa a Vaziraniho o existenci expanderovych toku (jeji dukaz by se ted nerikal, ledaze by ho nekdo chtel nastudovat jako nezavisly referat - je to pozoruhodna veta a nepochybne se na ni bude dal pracovat, tedy na vylepseni odhadu a zjednoduseni dukazu). A potom vysvetlit, jak se expanderovy tok pocita (zajimavym algoritmem z teorie her!) a jak se pouzije na hledani priblizne nejridsiho rezu, a rict spis strucny prehled dalsich nastroju, ktere se v clanku pouzivaji.

Integrals, partitions, and cellular automata by Alexander E. Holroyd, Thomas M. Liggett, and Dan Romik (Tomas Bily)

Bavila vas v prvnim rocniku cviceni z analyzy? Zde se na ne muzete rozpomenout a propocitat s autory pekne intergaly. Samozrejme s kombinatorickymi aplikacemi, na asymptotiku postu rozkladu na k scitancu a take na bunecne automaty. Navrzeno Martinem Klazarem, ktery k tomu pise: "Pro nekoho, kdo se neboji integralu. Vybrat podstatne a neztratit cas a neutopit to v technickych detailech."

Undirected ST-connectivity in Log-space by Omer Reingold (Martin Mares)

Rozhodne jeden z clanku roku ve vypocetni slozitosti: ukazuje, ze rozhodnout souvislost neorientovaneho grafu s n vrcholy lze s pouzitim pameti jen O(log n). To byl dlouhou dobu otevreny problem a z vysledku plynou obecne vztahy mezi tridami vypocetni slozitosti. Clanek pouziva cikcak expandery, o nichz se na seminari pred casem mluvilo, vicemene jako cernou skrinku, a nezda se byt technicky nijak narocny.

Proc nejdou nektere integraly vyjadrit elementarnimi funkcemi (Petr Skovron)

Kdyz jsem pocital integraly na zapocet z analyzy i pri jinych prilezitostech me zajimalo, jak se dokazuje, ze nektere pekne funkce, treba exp(-x^2), integral "nemaji", tj. primitivni funkce se neda vyjadrit pomoci obvyklych elementarnich funkci. Behem studia nam to celkem prirozene nikdo nerekl. Koho by to take zajimalo a chtelo by se mu to rict na seminari (nemusime mit porad jen kombinatoriku...), strucny ale pomerne srozumitelny popis je zde. Detailnejsi je napriklad zde, nebo si vyhledejte nektery z clanku, na nez se prvni spis odkazuje.

A short proof of the Harris-Kesten theorem by Bela Bollobas and Oliver Riordan ( Robert Babilon)

Kdyz spojime kazdou dvojici sousednich mrizovych bodu v rovine (vedle sebe v radku nebo vedle sebe ve sloupci) hranou s pravdepodobnosti p, pro jake nejmensi p dostaneme skoro jiste nekonecnou komponentu? To je jeden ze zakladnich problemu statisticke fyziky, a v tomto clanku je novy dukaz vysledku, ze kriticka hodnota je p=0.5. Doporuceno Martinem Klazarem.

On weighted graph homomorphisms by David Galvin and Prasad Tetali (Jan Hubicka)

Kratky clanek, neco vzorecku, pocitani homomorfismu, elegantni metoda s entropii (rozviji pristup Jeffa Kahna).

A simple linear-time (1+epsilon)-approximation for k-means clustering in any dimension by Amit Kumar, Yogish Sabharwal, and Sandeep Sen (Radek Sykora)

Aproximacni algoritmy ve vypocetni geometrii. K obsirnemu nazvu clanku staci snad jen dorict, ze k-means clustering je uloha rozdelit danou mnozinu n bodu v euklidovskem prostoru na k casti, zvanych shluky, tak aby se minimalizoval soucet ctvercu vsech vzdalenosti mezi dvojicemi bodu, nalezejicich do stejneho shluku.

Dynamic optimality - almost by Eric Demaine, Dion Harmon, John Iacono, and Mihai Pătraşcu (Petr Kucera)

Kdo delal statnice z informatiky, setkal se nutne s tzv. splay-stromy Sleatora a Tarjana, jednoduchou dynamickou datovou strukturou, na niz se vyucuje napriklad pojem amortizovane slozitosti. Zmineni autori vyslovili domnenku, ze tato datova struktura je ve vhodne definovanem smyslu optimalni. Dlouho se kolem toho nic nedelo, a nyni v tomto clanku z FOCS 2004 se podarilo dokazat, ze splay-stromy jsou optimalni az mozna na maly faktor log log n.

A Permutation Regularity Lemma by Joshua Cooper (Diaga Piguet)

On the Turan Number of the Hexagon by Zoltan Furedi, Assaf Naor, and Jacques Verstraete (Vit Jelinek)

Zlepsuje se konstanta u konstrukce grafu bez sesticyklu s co nejvetsim poctem hran, s pouzitim pozoruhodnych algebraickych prostredku. Dokazuji se i dalsi veci, napriklad vylepseny horni odhad, ale prednaska na seminari by mela asi byt hlavne o te konstrukci.

Problems and results in extremal combinatorics, Part II by Noga Alon (Martin Pergel)

Dalsi prilezitost sledovat mistra pri praci na drobnejsich dilech. Nekolik na sobe nezavislych vysledku, referovat na kolik bude cas.

Graph Products, Fourier Analysis and Spectral Techniques by Noga Alon , Irit Dinur, Ehud Friedgut and Benny Sudakov (Martin Balek)

Zkouma barevnost ctvereckovych soucinu pomoci Fourierovy analyzy, velmi uzitecne techniky a elegantni vysledky. Na strance Ehuda Friedguta je k tomu i prezentace v Powerpointu.

Approximating the cut-norm via Grothendieck's inequality by Noga Alon and Assaf Naor (Ales Privetivy)

Z matice se ma vybrat podmatice s co nejvetsim souctem prvku. Nekolik aproximacnich algoritmu s pouzitim peknych myslenek moderni analyzy.

Reflection positivity, rank connectivity, and homomorphism of graph by Michael Freedman, Laszlo Lovasz and Alexander Schrijveri (Zdenek Dvorak)

Charakterizuji funkce grafu G, ktere se daji vyjadrit jako pocet homomorfismu G do nejakeho pevneho grafu H (presneji receno, homomorfismy mohou mit vahy, indukovane vahami na hranach a na vrcholech H, a pak se bere soucet vah vsech homomorfismu). Algebraicke metody, souvislosti se statistickou fyzikou; clanek neni jednoduchy ale je to krasna matematika, jak se ostatne od autoru da cekat. Staci rict vhodne vybrane casti. Pro studenty homomorfismu temer povinne.

A lower bound on the density of sphere packings via graph theory by Michael Krivelevich, Simon Litsyn, and Alexander Vardy (Jan Stola)

Jak napovidal titulek, v tomto kratkem clanku se metodou z teorie grafu znovu dokazuje klasicky vysledek z geometrie cisel, o existenci husteho pakovani kouli ve velke dimenzi.

Sublinear geometric algorithms by Bernard Chazelle, Ding Liu, and Avner Magen (Jakub Cerny)

Testovat, zda se dva dane konvexni n-uhelniky protinaji, se da v case umernem odmocnine z n. Tento pomerne jednoduchy clanek rika jak, a nekolik dalsich prekvapivych algoritmu.

On levels in arrangements of curves, II: a simple inequality and its consequence by Timothy Chan (Petr Skovron)

Hladiny v arrangementech jsou jednim z evergreenu kombinatoricke geometrie, a presto autor zcela jednoduchym napadem dokazuje nove pekne veci (o krivkach).

Testing subgraphs in directed graphs by N. Alon and A. Shapira (Martin Balek)

Navrzeno prof. Nesetrilem. Vyzkum v ramci sirsiho problemu pravdepodobnostniho testovani vlastnosti objektu. V tomto pripade chceme tim, ze se podivame na konstantne mnoho sikovne vybranych dvojic vrcholu, rozlisit grafy neobsahujici dany (pevny) podgraf H od grafu, ktere obsahuji H i po odebrani libovolnych epsilon.n^2 hran. Delsi clanek, treba vhodne vybrat pekne myslenky k referovani.

Flow metrics by Claudson Bornstein and Santosh Vempala (Jan Kara)

Podstatna cast aproximacnich algoritmu pouziva linearni programovani: vyresi se vhodna linearni relaxace problemu a ta se potom nejak zaokrouhli na celociselne reseni problemu. Tento clanek je krasny a znacne netrivialni priklad. Jednotnym zpusobem resi nekolik pribuznych problemu, spocivajicich v hledani vhodneho poradi vrcholu grafu podle ruznych kriterii, napriklad minimalni prumerna "delka" hrany.

Proving integrality gaps without knowing the linear program by Sanjeev Arora, Bela Bollobas and Laszlo Lovas (Petr Kucera)

FOCS 2002. Krasny dukaz toho, ze problem vrcholoveho pokryti nelze aproximovat s faktorem o moc lepsim nez 2 pomoci linearnich relaxaci "lokalniho" typu. Pouziva trochu nahodnych grafu a dalsich veci, ale minimalne prvni cast neni prilis slozita.

Lattice Walks in Zd and Permutations with No Long Ascending Subsequences by Ira Gessel, Jonathan Weinstein, and Herbert S. Wilf (David Kronus)

Krasne pocitani: kolik je permutaci neobsahujicich zadnou rostouci podposloupnost delsi nez d, a pozoruhodne souvislosti s vselicim. Ostatne, abstrakt je tady:

We identify a set of d! signed points, called Toeplitz points, in Z^d, with the following property: for every n>0, the excess of the number of lattice walks of n steps, from the origin to all positive Toeplitz points, over the number to all negative Toeplitz points, is equal to n\choose n/2 times the number of permutations of {1,2,...,n} that contain no ascending subsequence of length >d. We prove this first by generating functions, using a determinantal theorem of Gessel. We give a second proof by direct construction of an appropriate involution. The latter provides a purely combinatorial proof of Gessel's theorem by interpreting it in terms of lattice walks. Finally we give a proof that uses the Schensted algorithm.

Graph Homomorphisms and Long Range Action by Graham R. Brightwell and Peter Winkler (D. Ptacnikova)

Pekny, pomerne elementarni clanek. Nejlepe prednest jenom cast z nej.

Abstract. We show that if a graph H is k-colorable, then (k - 1)-branching walks on H exhibit long range action, in the sense that the position of a token at time 0 constrains the configuration of its descendents arbitrarily far into the future. This long range action property is one of several investigated herein; all are similar in some respects to chromatic number but based on viewing H as the range, instead of the domain, of a graph homomorphism. The properties are based on combinatorial forms of probabilistic concepts from statistical physics, although we argue that they are natural even in a purely graph-theoretic setting. They behave well in many respects, but quite a few fundamental questions remain open.

Ramsey-type theorems for Metric Spaces with applications to Online Problems by Y. Bartal, B. Bollobas, and M. Mendel (D. Piguetova)

Clanek je o online algoritmech, ale mam na mysli predneseni jen jedne pekne vety Ramseyova typu pro konecne metricke prostory: Vpodstate, ze kazdy dost velky metricky prostor obsahuje pribliznou kopii metriky nejakeho stromu dane velikosti (a jeste specialniho typu).

Symmetric groups as products of Abelian subgroups by M. Abert (O. Pangrac)

Pomoci mazane zkombinovanych svislych a vodorovnych posunu v rovine se dokazuje, ze symetricka grupa na nekonecne mnozine se da vyjadrit jako soucin nejvys 289 abelovskych podgrup. Trochu neco jineho nez obvykle.

Tighter lower bounds for nearest neighbor search and related problems in the cell probe model by Omer Barkol and Yuval Rabani (P. Kucera)

Informaticke tema - patrani po nejblizsim sousedu v Hammingove krychli. Dolni odhady v Yaove "cell-probe" modelu. V clanku je hodne pocitani, ale myslenky jsou ve skutecnosti jednoduche. Staci rict jenom cast.

Fast Monte-Carlo algorithms for approximate matrix multiplication by Petros Drineas and Ravi Kannan (V. Franek)

Myslenka aproximovat soucin dvou matic pravdepodobnostne, vybranim nejakych nahodnych vzorku, neni v dnesni dobe nijak prekvapiva. Ale udelat to "spravne", tak aby to fungovalo, neni jen tak. V tomhle clanku se popisuje pomerne jednoducha fungujici metoda.

Problems and results in extremal combinatorics, Part I by Noga Alon (M. Balek)

Ve skutecnosti sbirecka alonovskych perlicek v extremalni kombinatorice. Nekolik na sobe nezavislych kousku, referovat na kolik bude cas.

Asymptotically tight bounds for some multicolored Ramsey numbers by Noga Alon and Vojtech Rodl (Robert Samal)

Kouzla s vlastnimi cisly a explicitnimi konstrukcemi expanderu. Staci prednest vhodne vybranou cast.

Generating a Random Sink-free Orientation in Quadratic Time by Henry Cohn, Robin Pemantle and James Propp (P. Skovron)

Nahodne generovani pomoci Markovova retezce, velmi pekne a elementarni. Abstrakt zde.

Fractional planks by Ron Aharoni, Ron Holzman, Michael Krivelevich, and Roy Meshulam (H. Nyklova)

Chytry clanek o jedne variante stareho geometrickeho problemu (pokryvani konvexniho telesa destickami minimalni celkove sirky).

Low-dimensional liner programming with violations by T. Chan (J. Hubicka)

Pekny napad dava pomerne jednoduchy a nejspis optimalni algoritmus pro jednoduse formulovany rovinny problem, ktery odolal nekolika predchozim pokusum o efektivni reseni. Staci pohovorit o rovinnem pripadu.

Chordal embeddings of planar graphs by V. Bouchitte, F. Mazoit, and I. Todinca (M. Mares)

Kratky dukaz hypotezy Robertsona a Seymoura: stromovy zdvih rovinneho grafu a jeho dualu se lisi nanejvys o 1.

The intrinsic dimensionality of graphs by Robert Krauthgamer and James R. Lee ( Jan Stola)

STOC 2003. Grafy a jejich vnorovani do mrizek. Presneji receno, minimalni d takove, ze G je podgrafem d-dimensionalni mrizky Z^d, se srovnava s "rustem kouli v G", tj. minimalnim q takovym, ze kazda koule o polomeru r obsahuje nejvys r^q vrcholu. Rada peknych triku, souvisi s vnorovanim konecnych metrickych prostoru. Staci vysvetlit vhodne vybrane casti (navrh: uvod, sekce 6,2, a ze sekce 3 prehled, pripadne s vynechanim nejakych detailu).

Infinite antichains of matroids with characteristic set p by James Oxley, Charles Semple, Dirk Vertigan, and Geoff Whittle

Three moves on signed surface triangulations by Shalom Eliahou, Sylvian Gravier and Charles Payan

Optimal probabilistic fingerprint codes by Gabor Tardos (Petr Skovron)

Obrana proti softwarovym piratum pravdepodobnostnimi metodami. Bude nevinny uzivatel obvinen? Unikne koalice c piratu spravedlivemu trestu? To vse, jakoz i pekne pravdepodobnostni triky, se doctete v tomto clanku.

On a question of Erdos and Sze meredi by Jozsef Solymosi (Diana Piguetova)

Zabyva se otazkou, jaka je minimalni hodnota max(|A+A|,|A.A|) pro n-prvkovou mnozinu A realnych cisel (A+A jsou vsechny soucty dvojic cisel z A, a A.A jsou vsechny souciny). Jako uvod slouzi drivejsi kratky clanecek Elekese o tomtez. Nejdriv prerikat ten, a potom Solymosiho dabelske vylepseni. (Solymosiho clanek je zatim jen predbezna verze, ale vse potrebne se z ni myslim da vycist.)

A tight bound for approximating arbitrary metrics by tree metrics by Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar (Ales Privetivy)

Zrejme posledni krucek v problemu rozpracovanem drive Alonem a spol a Bartalem, a zaroven podstatne zjednoduseni predchozich konstrukci. Dava skvely nastroj pro tvorbu pribliznych algoritmu: Zhruba receno, umime-li nejakou ulohu metricke povahy resit pro stromy, muzeme ji pomoci tohoto vysledku (prevdepodobnostne) resit i pro libovolne grafy s aproximacnim faktorem radu log n. Zvlastni premie pro toho, kdo se nauci spravne psat prijmeni prvniho autora.

New counterexamples to Knaster's conjecture by Aicke Hinrichs and Christian Richter (Veronika Douchova)

Knaster se v roce 1947 ptal, jestli pro kazde spojite zobrazeni f sfery v R^n do R^m a kazdou konfiguraci K sestavajici z n-m+1 bodu na te sfere existuje otoceni r sfery takove, ze f(r(K)) je jediny bod. Ukazalo se, ze obecne to neplati. Tento clanek sam o some asi neni ten nejzajimavejsi o Knasterove domnence, spis vylepsuje predchozi napady, nicmene ta domnenka zajimava je, i metoda na jeji vyvraceni.

Homomorphism and dimension by Patrice Ossona de Mendez and Pierre Rosenstiehl (Petr Hanus)

Jedna z moznych dimenzi grafu je Dushnik-Millerova dimenze mnoziny jeho vrcholu a hran usporadane inkluzi. Zde se zavadi varianta teto dimenze, kdy se bere maximum z dimenzi grafu majicich homomorfismus do uvazovaneho grafu. Pak se vyvraci domnenky Felsnera a Trottera pomoci Krize a Nesetrila... ostatne tento clanek byl navrzen prof. Nesetrilem.

Long monotone paths in line arrangements by Jozsef Balogh, Oded Regev, Clifford Smyth, William Steiger, and Mario Szegedy (Kamila Bumbova)

O tomhle problemu uz se urcite mluvilo na nektere z polednich prednasek: Je dano n primek v obecne poloze. Uvazme cesticku udelanou z kousku tech primek, ktera jde zleva doprava a nikdy se nevraci. Kolikrat nanejvys muze takova cesticka zahnout? V tomhle clanku se peknou konstrukci ukazuje, ze lze zahnout temer n^2-krat.

Sandwiching random graphs by J.-H. Kim and V. H. Vu (Robert Samal)

Dva mistri pravdepodobnostni metody z dalneho vychodu ukazuji, ze nahodny d-regularni graf se v jistem smyslu velmi podoba nahodnemu grafu v Erdosove modelu G(n,p) pro p=d/n. Zatimco s nahodnym d-regularnim grafem se pocita tezko, s Erdosovym modelem to jde zpravidla mnohem lepe. Krasny ale dlouhy clanek s hodne myslenkami a jeste vice formulkami, ale nenechte se odstrasit! Vysvetlit hlavne formulaci vysledku a pristup k dukazu (algoritmus generovani), z dukazu pak rict jen vhodne vybrane casti a hlavni myslenky (napriklad asi vynechat sekci 3). Pro fajnsmekry.

Finding maximum flows in undirected graphs seems easier than bipartite matching by David R. Karger and Matthew S. Levine (Jan Hubicka)

Dumyslny algoritmus pro maximalni toky, doporuceno Petrem Kolmanem. Clanek je trochu starsi, ale zda se, ze od te doby zadna podstatna zlepseni nenastala. Staci rict vhodne vybrane casti. Studium je mozno doplnit prehledovym clankem A. Goldberga zde.

A tight bound for the number of different directions in three dimensions by Janos Pach, Rom Pinchasi, and Micha Sharir (Jan Stola)

Pekna elementarni kombinatoricka geometrie na klasicke tema.

Equilateral sets in l^n_p by Noga Alon and Pavel Pudlak (Vojtech Franek)

Metody extremalni kombinatoriky zari ve starem geometrickem problemu. Neni treba referovat vse.

Abstract. We show that for every odd integer p\geq 1$ there is an absolute positive constant c_p, so that the maximum cardinality of a set of vectors in R^n such that the l_p distance between any pair is precisely 1, is at most c_p n\log n. We prove some upper bounds for other l_p norms as well.

Clifford algebras and approximating the permanent by Steve Chien, Lars Rasmussen, and Alistair Sinclair (Martin Mares)

Rozvinuti jednoducheho triku na priblizne pocitani permanentu 0/1 matice pomoci determinantu. V puvodnim triku se misto kazde jednicky dosazovalo nahodne +1 nebo -1, v mazanejsi verzi +1, -1, +i, nebo -i, a v tomto clanku se dosazuje nahodne z baze jistych Cliffordovych algeber. Krome toho, ze se clovek docte, co takova Cliffordova algebra zhruba je, je v clanku i rada jinych zajimavych veci. K referovani je nutne s citem neco vybrat, vse se nestihne.

An improvement of a lemma of Tardos by Nets Hawk Katz (Veronika Douchova)

Vylepsuje nejlepsi znamy odhad pro jeden z upornych problemu kombinatoricke geometrie, minimalni pocet ruznych vzdalenosti v n-bodove mnozine v rovine. Ale o vzdalenostech se tam skoro nehovori, protoze se vylepsi jiste kombinatoricke lemma, a z toho automaticky plyne vylepseni pro ty ruzne vzdalenosti jiz znamymi metodami (ktere asi neni treba referovat, nebo kdyz tak strucne). Chytry a velmi elementarni dukaz, neco jako kombinatoricka teorie cisel. Patrne studentsky clanek, je treba se jim trochu prokousat a pak ho s citem prevypravet.

Maximum matchings via Gaussian elimination by Marcin Mucha and Piotr Sankowski (David Hartman)

Uz delsi dobu byl znam Lovaszuv uzasny algebraicky trik dovolujici testovat existenci perfektniho parovani v grafu na n vrcholech v case umernem dobe potrebne k vynasobeni dvou ctvercovych n x n matic. Tento clanek (studentsky!) ukazuje, ze v temze case se da perfektni parovani (nebo dokonce maximalni parovani) i najit, coz byl dlouho otevreny problem. Zajemci o uvod do problematiky muzu dodat kapitolu skript, ktera o zminenem Lovaszove algoritmu pojednava.

Extracting randomness using few independent sources by B. Barak, R. Impagliazzo, and A. Wigderson (Robert Samal, Ales Privetivy)

Tenhle clanek je na dva vicemene nezavisle referaty. Jeden je o vete Bourgaina, Katznelsona a Taa o souctech a soucinech v konecnych telesech. To je nedavny vysledek, ktery se ukazuje byt mimoradne dulezity (s jeho pomoci se vyresilo nejen nekolik zasadnich problemu v teorii slozitosti, o nichz je tento clanek a jeho nasledovnici, ale i problemy v teorii grup a v teorii cisel!). Dukaz uvedeny zde (v dodatku A) by mel byt pristupneji napsany nez puvodni dukaz Bourgaina a spol. Druhy referat by potom byl o vyluhovani nahodnosti, coz je vlastni tema clanku. Doporucuji prohlednout tez Wigdersonovu stranku, jestli by se tam nenasly nejake inspirativni materialy k prednasce.

Proofs without syntax by Dominic J.D. Hughes (Jan Fonoik)

Ukazuje se, ze klasicke dukazy ve vyrokove logice jsou ekvivalentni jistym grafovym homomorfismum. Jednoduche, ale je treba dat trochu pozor, aby prednaska objasnovala myslenku a nebyla jen dlouhym sledem formalnich definic a dukazu. Doporuceno Martinem Klazarem.

Lifts, discrepancy and nearly optimal spectral gaps by Nathan Linial and Yonatan Bilu (Zdenek Dvorak)

Ukazuji, ze jistou operaci "nahodneho 2-zdvihu" vznikne z kazdeho d-regularniho grafu dobry expander. Zajimave hlavne technikami, procvici se expandery, druhe vlastni cislo, a takove veci.

The PCP Theorem by gap amplification by Irit Dinur (Martin Mares, Jan Kara, Petr Skovron)

PCP veta je bezpochyby jednim z nejvetsich intelektualnich vykonu informatiky. Jeji dosavadni dukazy, zalozene na pravdepodobnostnim overovani dukazu, zabiraji prinejmensim tenkou knizku. Tento dvacetistrankovy clanek podava novy dukaz, zalozeny na "zesilovani nesplnitelnosti" logickych formuli. Dukaz je pekne modularni, udelany z nekolika pomerne jasne oddelenych casti, z nichz kazda se muze prohovorit zvlast. Jako uvod do PCP vety muzu nabidnout kousek svych virtualnich skripticek (na vyzadani poslu, nebo pripadne sam odprednesu). Tohle myslim stoji za to udelat poradne a do detailu a venovat tomu treba pul semestru, kdyz bude potreba. Referat pro tym 2-3 lidi.

Gaber-Galilova explicitni konstrukce expanderu (Martin Pergel)

The Kissing Problem in Three Dimensions by Oleg R. Musin (Tomas Bily)

Velmi poucny clanek: silne metody daji znamy vysledek pro (pomerne tezky) problem elementarni geometrie. Abstrakt: The kissing number k(3) is the maximal number of equal size nonoverlapping spheres in three dimensions that can touch another sphere of the same size. This number was the subject of a famous discussion between Isaac Newton and David Gregory in 1694. The first proof that k(3) = 12 was given by Schutte and van der Waerden only in 1953. In this paper we present a new solution of the Newton-Gregory problem that uses our extension of the Delsarte method. This proof relies on basic calculus and simple spherical geometry.

Faster core-set constructions data stream algorithms in fixed dimensions by Timothy Chan (Jan Hubicka)

Elegantni vylepseni aproximacnich algoritmu, momentalne asi jeden z nejzajimavejsich trendu ve vypocetni geometrii, a take neco o "data stream" algoritmech, coz je dalsi modni pojem. (Mnoho aplikaci zakladnich konstrukci, neni treba rikat vse.)

Homological connectivity of random 2-complexes by Nathan Linial and Roy Meshulam (Diana Piguet)

Jak znamo, nahodny graf G(n,p) zacne byt skoro jiste souvisly kolem p= (log n)/2. V tomto clanku se misto nahodnych grafu studuji nahodne 2-dimenzionalni simplicialni komplexy: vezme se uplny graf K_n, a kazdy trojuhelnik v nem se "zalepi" (topologickym trojuhelnikem) s pravdepodobnosti p. Pro jake p prestane takto definovany objekt mit "1-dimezionalni diry"? Celkem standardni pravdepodobnostni pocitani je treba zkombinovat s nekolika definicemi z topologie. Ty si zde clovek zopakuje, nebo se je nauci, ve velmi konkretnich podminkach - napriklad se nahledne, ze 1-kohranice je presne mnozina hran minimalniho rezu v K_n, a tak. Nova oblast vyzkumu, ve ktere by se mozna dalo pekne pokracovat.

Approximating edit distance efficiently by Ziv Bar-Yossef, T.S. Jayram, Robert Krauthgamer, and Ravi Kumar (Martin Balek)

Rychle algoritmy na odhad editacni vzdalenosti znakovych retezcu, vhodne pro ukoly jako napriklad objeveni nekolika skoro stejnych verzi jednoho zaznamu v nejake databazi. Nerikat vsechny uvedene algoritmy, a pred referovanim zkusit sehnat uplnou verzi, pokud uz bude k dispozici.

Extractors and pseudorandom generators by Luca Trevisan (Vit Jelinek)

Jiz ne uplne nejnovejsi, ale zasadni clanek z vypocetni slozitosti. Technicky jednoduchy (tedy kdyz se vstrebaji vsechny definice), odhalujici souvislost mezi statistickou nahodnosti (neco se chova skoro jako rovnomerne rozdelena nahodna velicina) a vypocetni nahodnosti (zadny polynomialni algoritmus to nedokaze odlisit od skutecne nahodne veliciny), kterou vsichni predtim prehledli. Doporucuji poradne a pomalu vysvetlit zakladni defnice, mozna i pomoci slajdu, a potom probrat sekce 2 a 3. Rict neco o pozadi a souvislostech, ale moc se tim nerozptylovat, mnoho poznamek v clanku oceni pouze znalci; soustredit se na hlavni vetu. Ponekud modernejsi pohled na totez a obecny uvod viz prehledovy clanek Ronen Shaltiel: Recent developments in extractors, mozno vyjit tez z nej jako zakladu prednasky.

Integer cells in convex sets by Roman Vershynin (Vojtech Franek)

Dokazuje zajimave zobecneni znameho Sauerova-Shelahova-Vapnikova-Cervonenkisova lemmatu (maximalni pocet mnozin v systemu, ktery neindukuje zadny "uplny podsystem" velikosti d+1) a souvislosti s konvexni geometrii. Zaklad je vysvetlit vetu 1.1 a jeji dukaz, a trosku neco rict o souvislosti s konvexni geometrii, napr. zformulovat "volume ratio" vetu neco malo kolem.

On random +-1 matrices: singularity and determinant by Terrence Tao and Van Ha Vu (Robert Babilon)

Novy jednodussi dukaz toho, ze determinant nahodne matice typu n krat n, jejiz prvky jsou nezavisle +1/-1 s pravdepodobnosti 1/2, je skoro jiste nenulovy. A nekolik dalsich peknych vysledku - z nich vybrat. Doporuceno (take) Martinem Klazarem.

Removing even crossings by Michael Pelsmajer, Marcus Schaefer, and Daniel Stefankovic (Petr Kucera)

O kresleni grafu, a obzvlast velice jednoduchy dukaz vety Hananiho a Tuttea. Zatim je k dispozici jen petistrankovy abstrakt - nez budete referovat, zajimejte se prosim, jestli uz existuje uplna verze, je prislibena.

Towards 3-Query Locally Decodable Codes of Subexponential Length by Sergej Jechanin (Sergey Yekhanin) (Vit Jelinek)

K cemu jsou Mersennova prvocisla? Donedavna se zdalo, ze prisne vzato k nicemu, ale v tomto clanku se ukazuje, ze se z nich daji zkonstruovat podivuhodne ucinne lokalne dekodovatelne kody. Konkretne to znamena, ze n-bitovy retezec x zakodujeme kodem C(x), a kdyz nam nekdo da slovo w, coz je C(x) zpotvorene na rekneme 10% mist, pro kazde i=1,2,..,n se staci podivat na jiste 3 bity w (vhodne nahodne vybrane), a se slusnou pravdepodobnosti zjistime, co bylo x_i. Takove kody se umely i predtim, ale delka C(x) byla exponencialni v n, kdezto tady se udela delke podstatne mensi. Jeden z nejlepsich clanku STOC 2007.

Marriage, Honesty, and Stability by Nicole Immorlica and Mohammad Mahdian (Jan Stola)

Technicky neco elementarni teorie pravdepodobnosti aplikovane na analyzu algoritmu. Zajimave aspekty (algoritmickeho) problemu stabilniho manzelstvi a zminky o jeho pozoruhodnych aplikacich v praxi.

Measurable sets with excluded distances by Boris Bukh (Josef Cibulka, Jan Kyncl)

Jakou maximalni hustotu muze mit meritelna mnozina A v rovine, kdyz zadne dva z jejich bodu nemaji vzdalenost z dane konecne mnoziny D? Pokrok v pozoruhodne a tezke oblasti. Neleknete se integralu a Fourierovy transformace.

The number of cliques in a graph of given order and size by V. Nikiforov (Jose Zamora)

Zesileni Turanovy vety: kolik nejmene musi graf na n vrcholech s m hranami obsahovat r-klik, kdyz je m vetsi nez Turanovo cislo (zarucujici aspon 1 kliku). Analyza, Lagrangeovy multiplikatory, hodne vzorecku, treba prednest s citem, vzorecku jen trochu na ukazku a vysvetlit myslenky. Doporuceno Martinem Klazarem.

Non-backtracking random walks mix faster by Noga Alon, Itai Benjamini, Eyal Lubetzky, and Sasha Sodin (Jiri Fink)

Obycejna nahodna prochazka v grafu pokracuje vzdy do nahodne vybraneho souseda vrcholu, v nemz prave je, kdezto nevracejici se nahodna prochazka nejde nikdy zpatky do souseda, z nehoz prave prisla. V clanku se dokazuje, ze na vhodnych grafech (regularnich expanderech) nevracejici se nahodna prochazka konverguje k rovnomernemu rozdeleni rychleji, nez prochazka obycejna, a dalsi vysledky. Vhodne jako lekce nekterych technik, jimiz se otazky o nahodnych prochazkach resi.

Perturbed identity matrices have hig rank: proof and applications by Noga Alon (Marek Tesar)

Pripomina drive publikovanou vetu na tema v titulku a uvadi radu aplikaci, nektere tez publikovane jinde a nektere nove. Sestava z kratsich povetsinou nezavislych kousku.

Stable Kneser hypergraphs and ideals in N with the Nikodym property by Noga Alon, Lech Drewnowski and Tomasz Luczak (Martin Tancer)

Pouziti kombinatoriky, konkretne Kneserovych (a Schrijverovych) hypergrafu v problemu na pomezi analyzy a teorie mnozin. Hlavne pro ty, kdo maji radi nekonecne mnoziny.

Words Maps and Spectra of Random Graph Lifts by Nati Linial and Doron Puder (Vit Jelinek)

Krasna kombinatorika slov a permutaci a souvislost s vlastnimi cisly jistych nahodnych grafu. Dlouhy (ale dobre citelny!) clanek. Na prednasku je potreba vybrat nejpeknejsi casti. Napriklad se da vzit jako zaklad novy dukaz Nicovy vety a potom vysvetlit vysledky o nahodnych nakrytich (random lifts), pripadne neco z dukazu, pokud cas dovoli.

Shuffling by semirandom transpositions by Elchanan Mossel, Yuval Peres, and Alistair Sinclair (Milan Straka)

Z balicku n karet vytahneme nahodnou kartu a polozime ji navrch balicku. Kolikrat to musime udelat, abychom dostali "dobre zamichany" balicek? Odpoved je radove n log n a souvisi s peknou teorii kolem Markovovych retezcu. Referovat by se mel dolni odhad podle tohoto clanku, ktery vyuziva druheho vlastniho cisla a kouzel s vhodnou komplexni funkci.

Coloring K_k-free intersection graphs of geometric objects in the plane by Jacob Fox and Janos Pach (Louis Esperet)

Vlastnosti nitovych grafu a topologickych grafu, jedno z tradicne silnych temat na KAM. V tomto clanku je vysledku mnoho, je treba vybrat. Jeden mozny navrh je soustredit se na vetu 11 a vystopovati, co vsechno je na ni potreba.

Linear equations modulo 2 and the L_1 diameter of convex bodies by Subash Khot and Assaf Naor (Eva Jelinkova)

Tento clanek neni povetsinou technicky prilis narocny, ale lze se z nej naucit rade uzitecnych pojmu. Prezentace by se mela soustredit hlavne na pekne vysvetleni uvodu a vysledku a na sekci 2. Vetu 3.1 staci jen formulovat nebo si najit dukaz ponekud slabsi verze z clanku [10] (nebo samozrejme lze naznacit i dukaz ze sekce 3). Vetu 4.1 je mozne uvest jako zajimavou souvislost, pokud cas dovoli.

Graph Sparsification by Effective Resistances by Daniel A. Spielman and Nikhil Srivastava (Josef Cibulka)

Graf G s mnoha hranami chceme nahradit pokud mozno ridkym (vazenym) grafem H na stejne mnozine vrcholu tak, aby cena vsech rezu zustala priblizne zachovana. Tento clanek problem elegantne resi pouzitim nekolika zajimavych nastroju.

Fourier analysis, linear programming, and densities of distance avoiding sets in R^n by Fernando Mario de Oliveira Filho and Frank Vallentin (Marek Sterzik)

Jaka je barevonst R^n? Tj chceme priradit kazdemu bodu z R^n barvu tak, aby body ve vzdalenosti 1 nikdy nemely stejnou barvu - s jakym nejmensim poctem barev vystacime? V tomto kratkem clanku se analytickou metodou (pres Fouriorovu transformaci a linearni programovani) dokazuji vylepsene dolni odhady. Metoda pripomina Delsartuv pristup v teorii kodu.

Can a Graph Have Distinct Regular Partitions? by Noga Alon, Asaf Shapira, and Uri Stav (David Hartman)

Jista zjemneni Szemerediho regularity lemmatu, vhodne hlavne pro nekoho, kdo samotne regularity lemma uz zna. Doporuceno J. Kratochvilem.

The Density of Iterated Plane Intersection Graphs and a Gap Result for Triangulations by Rolf Klein and Martin Kutz (Jan Stola)

Zacneme s konecnou mnozinou bodu, spojime vsechny dvojice useckami, vezmeme vsechny jejich pruseciky, zase spojime kazde dva useckou, a tak porad dal - co se bude dit?

A (De)constructive Approach to Program Checking by Shafi Goldwasser and Dan Gutfreund and Alex Healy and Tali Kaufman and Guy Rothblum (Tomas Vyskocil)

A well-known example of program checking is the Freivalds tester for matrix multiplication, which checks whether a matrix C is equal to the product of matrices A and B in roughly quadratic time, although nobody can multiply the matrices that fast. The present paper provides a rather general (and simple) idea of constructing fast checkers for various computational problems from programs that actually solve the problems. A long paper, but shouldn't be too hard (after you look up the few definitions of complexity classes); only a suitably selected part(s) should be presented - probably start with a concrete example.

Making a K_4-free graph bipartite by Benny Sudakov (Hossein Teimori Faal)

Problem klasicke extremalni teorie grafu vicemene formulovany v titulku. Pomerne kratke.

Economical toric spines via Cheeger's Inequality by Noga Alon and Boaz Klartag (Jan Kyncl)

d-dimenzionalni toroidalni graf se dostane jako soucin cyklu (v clanku se uvazuji dva mozne souciny a tudiz dve verze toroidalniho grafu). Chceme najit co nejmensi mnozinu hran, pripadne vrcholu, jejiz odstraneni pretne vsechny cykly v toroidalnim grafu. Zde se dokazuji horni odhady jednoduchym a krasnym trikem (nenechte se zastrasit nekolika vzorecky). Staci vysvetlit dukaz jen pro jednu z vet. Docela zajimave by bylo (vyhledat a) rict, na co vysledek takoveho typu potrebovat Ran Raz (odkaz [7]).

The Complexity of Computing a Nash Equilibrium by Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou (Marek Krcal; Tomas Valla)

Jeden z nekolika pomerne nedavnych zasadnich clanku o vypocetni slozitosti Nashovych rovnovaznych strategii v teorii her. Zajimavy jednak tim, ze se uvedou (ci zopakuji) pojmy z teorie her, ale hlavne asi uvedenim slozitostnich trid jako PPAD, ktera zachycuje vypocetni problemy, v nichz je zarucena existence reseni existencnim dukazem urciteho typu (zalozenem na parite). Uz je jeden zajemce o referovani - v pripade, ze by byli i dalsi, mohli bychom se vic o takovych slozitostnich tridach naucit ze starsiho clanku C. Papadimitriou: The Complexity of the Parity Argument and Other Inefficient proofs of Existence a dale sledovat novejsi vyvoj, tykajici se mnohokrat opakovanych her, v clanku C. Borgs, J. Chayes, N. Immorlica, A. Kalai, V. Mirrokni and C. Papadimitriou: The Myth of the Folk Theorem.

Improved upper bounds on the crossing number by Vida Dujmovic, Ken-ichi Kawarabayashi, Bojan Mohar and David R. Wood (Rudolf Stolar)

Prusecikova cisla a grafy bez zakazanych minoru, zajimave asi hlavne pouzitymi nastroji.

On maximizing welfare when utility functions are subadditive by Uriel Feige (Bernard Lidicky)

Priblizny algoritmus pro maximalizaci funkci z jiste dulezite tridy (motivace: kombinatoricke aukce). Pri prezentaci usilovat o dukaz vety 5, ostatni veci staci zminit strucne nebo vynechat.

Multiplicative weights method: a meta-algorithm and its applications by Sanjeev Arora, Elad Hazan, and Satyen Kale (Marek Tesar)

Prehledovy clanek o jednom peknem a zakladnim triku, ktery je uzitecny v algoritmech i v matematickych dukazech. Vysvetlit algoritmus s dukazem (nejdriv na jednoduchem prikladu) a pak zminit nektere z aplikaci, jak to casove vyjde.

On the Complexity of Lattice Problems with Polynomial Approximation Factors by Oded Regev (Pavel Rytir)

Prehledovy clanek o mrizkach, konkretne o algorithmickem problemu hledani nejblizsiho mrizoveho vektoru k danemu bodu. Vysvetlit zakladni definice a vybrat cast vhodnou pro prezentaci. Hlavni motivace je vyuziti mrizek v kryptografii, o cemz pojednava tento Regevuv prehledovy clanek, z nehoz by take slo neco vybrat a referovat.

A Generalized Carpenter's Rule Theorem for Self-Touching Linkages by Timothy G. Abbott, Erik D. Demaine, and Blaise Gassend (Onderj Suchy)

Narovnavani metru v rovine. Trocha elementarni topologie. Doporuceno Pavlem Valtrem.

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.

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.