Clanky prednesene na doktorandskem seminari
Jacob Fox, Janos Pach, Andrew Suk
Approximating the rectilinear crossing number
[PDF]
Jarda Hančl
Provides a deterministic algorithm for approximating the rectilinear crossing
number upto a "small" additive error. This shows constant approximation for
dense graphs.
Daniel Průša, Tomáš Werner
LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP
[PDF]
Peter Korcsok
Shows that LP relaxations of some hard problems cannot be solved faster than
general LPs by exploiting some hidden structure due to being a special case.
Ran Raz
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning
[PDF]
Martin Böhm
The paper proves lower bound on learning the parity function. Learning
theory is an area that is becoming more and more important and I think this
paper can offer students a good opportunity to familiarize with the area.
Max Bannach, Christoph Stockhusen, Till Tantau
Fast Parallel Fixed-Parameter Algorithms via Color Coding
[PDF]
Radek Hušek
Fixed-parameter complexity is well established way to measure efficiency of
algorithms. This is one of the first attempts to use this approach for parallel
algorithms, often yielding contant-time algorithms! The key (and simple) idea
is to use certain "color coding": to encode the sought-for object by certain
vertex coloring, that we may effectively choose at random.
Charalampos Mavroforakis, Michael Mathioudakis, Aristides Gionis
Absorbing random-walk centrality: Theory and algorithms
[PDF]
Peter Korcsok
We want to define what vertices of a graph are most "central" (so that the
notion makes sense and also we can easily compute them). A natural notion uses
random walks: among all sets of $k$ vertices we choose such that minimizes
time, in which we hit the set by a random walk. This has direct connections to
web searching and PageRank. Analysis uses some random walks and basic linear
algebra.
F. Foucaud, M. Krivelevich, G. Perarnau
Large subgraphs without short cycles
[PDF]
Vojtěch Kaluža
Graphs with many edges but no short cycle, a mainstay of extremal
combinatorics. Used tools are covered in the probabilistic method (techniques)
class -- the main proof is basically a somewhat complex application of the
Lovász Local Lemma.
Tomáš Kaiser, Matěj Stehlík
Colouring quadrangulations of projective spaces
[PDF]
Martin Balko
Topological method (using simplicial complexes, their homologies etc.) is
used to find another proof of the chromatic number of Kneser graphs.
Generalizations of quadrangulations (graphs where all faces are 4-cycles) to
high-dimensional spaces is used. Good for someone who already know something
about the topological method.
Ayush Choure and Sundar Vishwanathan:
Random Walks, Electric Networks and The Transience Class problem of Sandpiles
[PDF]
Jana Syrovátková
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ů.
Brendan Murphy, Oliver Roche-Newton, Ilya Shkredov
Variations on the sum-product problem
[PDF]
Jaroslav Hančl
Important number-theory problem with applications in computer science
revolves around the fact that no set $A$ can resemble both an arithmetic and a
geometric sequence. This seems to imply, that either $A+A$ (the set of all
sums) or $A.A$ (the set of all products) is large. Some number theory,
Szemerédi-Trotter theorem and a bit of calculation.
Jon Kleinberg, Sigal Oren
Mechanisms for (Mis)allocating Scientific Credit
[PDF]
Jan Musílek
A scientific take on the problems of academia/research where credit may not
be assigned in the "most fair way". This (relatively old) paper seems to
apply that lack of perfection may actually be good.
Massimo Lauria, Pavel Pudlák, Vojtěch Rödl, Neil Thapen
The complexity of proving that a graph is Ramsey
[PDF]
Pavel Veselý
A graph on n vertices is c-Ramsey if it contains neither clique nor
independent set with c log(n) vertices. How hard is it to prove that a graph is
c-Ramsey? The paper gives superpolynomial lower bounds on the length of a
shortest proof.
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Tight Bounds for Subgraph Isomorphism and Graph Homomorphism
[PDF]
Tomáš Masařík
How fast can we test whether there is a graph homomorphism from $G$ to $H$?
Obvious brute-force algorithm runs in time $|V(H)|^|V(G)|$. It is shown that we
cannot do much better, unless Exponential Time Hypothesis fails. Not too hard
and no heavy machinery is used.
Allan Gronlund, Seth Pettie
Threesomes, Degenerates, and Love Triangles
[PDF]
Debarati Das
Kolik porovnani realnych cisel se potrebuje na vyreseni tzv. 3-SUM problemu,
kde se ma zjistit, jestli
$X+Y$ ma nejaky spolecny prvek se $Z$, kde $X,Y,Z$ jsou $n$-prvkove mnoziny
realnych cisel, a $X+Y=\{x+y:x\in X, y\in Y\}$? Vseobecne se verilo,
ze skoro kvadraticky mnoho, a pro jisty slaby vypocetni model (kde
se smeji zjistovat jen znamenka linearnich forem ve trech vstupnich
promennych) to je dokonce dokazano. U spousty dalsich problemu
mela redukce z 3-SUM ukazovat take neco jako kvadratickou slozitost.
A tady najednou prichazi algoritmus, ktery potrebuje jen zhruba
$n^{3/2}$ porovnani (ktery pracuje s linearnimi formami ve 4 promennych).
Neni to subkvadraticky algoritmus, protoze kvadraricky cas potrebuje
na jine operace, ale ty se prinejmensim neobjevuji v obvyklych
modelech pro dolni odhady (algebraicke rozhodovaci stromy a podobne).
S vyjimkou zrejme zertovneho nazvu inspirovaneho internetovymi
vyhledavaci neni na clanku ani nic mravnostne zavadneho.
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, and Luca Trevisan:
Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap
[PDF]
Michaela Seifrtova
Cheegerova nerovnost je zakladni vztah ve spektralni teorii grafu, ktery
odhaduje expanzi grafu pomoci druheho vlastniho cisla. Tady se dokazuje
nova nerovnost, v niz vystupuji i vyssi vlastni cisla a v nekterych pripadech
davaji odhady lepsi. Tim se i zcasti zduvodnuje, proc v praxi dobre funguje
hledani separatoru grafu pomoci druheho vlastniho vektoru. Dlouhy clanek -
ale doporucuju ignorovat vsechno s vyjimkou vety 1.1 a jejiho dukazu
(a vybrat jen jeden z dukazu, je jich tam vic).
Dukaz se asi taky mirne zjednodusi, pokud budeme predpokladat, ze graf je
regularni.
Eran Nevo, Stedman Wilson
How many n-vertex triangulations does the 3-sphere have?
[PDF]
Michaela Seifertová
Zkonstruuji jich hodne. Pomerne kratky clanek, ale je potreba
poradne vysvetlit topologicke pojmy i celou konstrukci.
Mirjam Friesen, Aya Hamed, Troy Lee, Dirk Oliver Theis
Fooling sets and rank
[PDF]
Zuzka Safernová
Pomerne jednoduche algebraicke konstrukce s cetnymi zajimavymi souvislostmi v informatice. Viz abstrakt.
László Lovász:
Subgraph Densities in Signed Graphons and the Local Simonovits-Sidorenko Conjecture
[PDF]
Martin Kupec
Č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.
Ryan Williams
Faster all-pairs shortest paths via circuit complexity
[PDF]
Ondra Bilka
Krasny objev: novy algoritmus na nejkratsi cesty ve vazenem grafu mezi vsemi
dvojicemi vrcholu. Ve skole se uci Floyduv-Warshalluv algoritmus kubicky,
dosud byla znama vylepseni o logaritmicke faktory pomoci triku s tabulkami
a hle - tady se dosahne zlepseni o mnohem vetsi faktor zhruba
exp((log n)^{1/2}), coz otrasa virou, ze lip nez kubicky to nepujde.
Pomerne kratke.
Micha Sharir, Adam Sheffer, and Emo Welzl:
Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn's Technique
[PDF]
Marek Elias
V rovine mame 2n-bodovou mnozinu a ptame se, kolika zpusoby na ni muzeme
nakreslit perfektni parovani, jehoz hrany jsou nekrizici se usecky - tedy
zajima nas maximum pres vsechny $2n$-bodove mnoziny. Podobne otazky
se studovaly v rade clanku a specialne tenhle jednak dosahuje pro
nektere z otazek zatim nejlepsich znamych vysledku, a jednak pouziva
zvlast pekne techniky, specialne Kasteleynuv (a Temperleyuv-Fisheruv) trik
pocitani parovani pomoci determinantu, se kterym se urcite stoji za to
seznamit. Casopisovou verzi na pozadani poskytne J. Matousek, zde na webu neni,
protoze na tento ucel pripadne hadky s koncernem Reed-Elsevier asi nestoji
za to.
János Pach, Gábor Tardos
Tight lower bounds for the size of epsilon-nets
[PDF]
Jaroslav Hančl
Dlouho známý výsledek Hausslera a Welzla (1987) říkal, že prostor s omezenou VC dimenzí má
$\varepsilon$-síť velikosti $\frac 1\varepsilon \log(\frac 1\varepsilon)$. Po několika částečných výsledcích se v tomto
článku konečně podařilo ukázat, že tento výsledek je těsný.
M. Laurent, A. Varvitsiotis
Positive Semidefinite Matrix Completion, Universal Rigidity and the Strong Arnold Property
[PDF]
Vojta Tůma
V článku se zkoumají oblasti příbuzné tzv. Connellyho podmínce na globální rigiditu: když máme pro množinu
bodů dané podmínky na vzájemné vzdálenosti (tyče dané délky), jak lze zajistit, že existuje jediné řešení?
Tato věta je stará, ale v článku se předvádí nový a jednodušší důkaz pomocí semidefinitních matic. Motivací ostatně je otázka,
kdy lze částečně vyplněnou matici doplnit tak, aby byl positivně semidefinitní.
Michel X. Goemans, Thomas Rothvoss
Polynomiality for Bin Packing with a Constant Number of Item Types
[PDF]
Martin Böhm
Nedavny zasadni pokrok v algoritmech na pakovani (bin packing), pouziva
poleydralni metody. Jeden ze dvou clanku na SODA 2014 z vyznamenanim pro
nejlepsi clanek.
Timothy M. Chan
Klee's Measure Problem Made Easy
[PDF]
Tomáš Gavenčiak
I v dobe, kdy dulezite nove algoritmy jsou spletitejsi a spletitejsi, se prece jen obcas povede neco jednoducheho, jako napriklad tento algoritmus na vypocet objemu sjednoceni kvadru. Bude-li dost casu, muze se neco
rict i o casti s vylepsenim pro RAM model.
Charilaos Efthymiou:
A simple algorithm for random colouring $G(n, d/n)$ using $(2+\epsilon)d$ colours
[PDF]
Vojtěch Kaluža
Vtipný algoritmus na generování (skoro uniformně) náhodných obarvení v polynomiálním čase.
Nicolas Bousquet, Aurélie Lagoutte, Stéphan Thomassé:
Clique versus Independent Set
[PDF]
Dusan Knop
Pěkný článek o různých souvislostech nenápadného problému: najít co nejméně řezů v grafu, které by od sebe oddělovaly každou
dvojici klika -- nezávislá množina.
Erdal Arikan:
Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels
e
[PDF]
Tomáš Gavenčiak
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.
Guillaume Moroz and Boris Aronov:
Computing the Distance between Piecewise-Linear Bivariate Functions
[PDF]
Michaela Seifrtová
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.
Adam Marcus, Daniel A. Spielman, and Nikhil Srivastava
Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees
[PDF]
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.
Shachar Lovett and Raghu Meka:
Constructive Discrepancy Minimization by Walking on The Edges
[PDF]
Martin Balko
Novy konstruktivni dukaz pro obarveni s malou diskrepanci.
Kratke a ne moc tezke.
Siu On Chan, James R. Lee, Prasad Raghavendra, and David Steurer:
Approximate Constraint Satisfaction Requires Large LP Relaxations
[PDF]
Marek Elias
Ukazuje se zde, ze rozumne velke linearni programy z urcite siroke tridy
nemuzou moc dobre aproximovat MAXCUT, MAX3SAT, a jine ulohy o splnitelnosti
omezujicich podminek. Centralnim pojmem je Sheraliho-Adamsova hierarchie
linearnich relaxaci, s niz stoji za to se seznamit. Dale se pouziva
neco booleovske Fourierovy analyzy a dalsi nastroje. Pritom clanek
neni prilis dlouhy (staci dojit do sekce 3).
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.
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).
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.
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.
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ů.
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).
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.
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.
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.
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í.
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.
Č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ů.
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.
Ú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í.
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ů.
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.
Opravdu pomerne jednoducha redukce, ale mazana (staci vypravet o pripadu q=2).
Pripomenuti teorie samoopravnych kodu.
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.)
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.
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.
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í.
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.
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.
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.
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?
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.
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)
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.
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.
DalĹĄĂ pojednĂĄnĂ o grafonech -- limitĂĄch grafovĂ˝ch posloupnostĂ.
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.
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.
Prehledovy clanek o jednom peknem triku v pravdepodobnostni metode.
Vybrat nekolik vhodnych kousku.
Pomerne jednoduchy clanek. Geometricke algoritmy, hledani
priblizneho centra bodove mnoziny v prostoru velke dimenze
pomoci Radonovy vety a Tverbergovy vety.
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ý.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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ý.
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)$.
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.
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.
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.
Zkoumaji se "hodne pravidelne" konfigurace bodu na sferach.
Zajimava oblast, o niz jsme v minulych letech moc nemluvili.
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.
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ů.
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.)
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.
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.)
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.
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.
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.
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.
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.
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.
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.
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í.
Pekna veta o prunikovych grafech krivek (tzv. nitacich)
s radou aplikaci. Jasne napsane, neprilis komplikovane.
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-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.
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.
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.
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.
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.
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.
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.
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.
Nadpis je dlouhatansky, ale zato popisuje, co se v clanku dela.
Doporuceno J. Kratochvilem.
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.
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.
Pocitani jistych rovinnych objektu pomoci bijekce,
soucast sirsiho trendu nedavnych uspechu v enumeraci.
Vysvetlit (pripomenout?)
tez Gesselovo-Viennotovo lemma, ktere se
v clanku pouzije.
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.
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.
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.
Neco jako rychla Fourierova transformace, ale
pro funkce definovane na mnozine vsech podmnozin
n-prvkove mnoziny. Jednoduchy napad, ktery urychli
nekolik algoritmu.
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.
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.
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").
Pozoruhodny pristup ke starym otazkam, jako napriklad Van der Waerdenove
domnence o permanentu, pomoci nerovnosti pro specialni tridy polynomu.
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.
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.
Opravdu jednodussi nez predchozi konstrukce. Elegantni a pomerne kratky clanek.
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.
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.
"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.
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.
Nova analyza stareho algoritmu, pomerne jednoducha zakladni myslenka.
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.
Nezavisle mnoziny v grafovych soucinech, Ramseyovske konstrukce,
prevazne algebraicke metody. Mnoho poucnych metod a triku.
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.
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.
Kratky clanek o utrapach, ktere cekaji kazdeho zobecnovatele Turanovy vety na systemy k-tic.
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.
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."
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.
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.
Kratky clanek, neco vzorecku,
pocitani homomorfismu, elegantni metoda s entropii (rozviji pristup Jeffa Kahna).
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.
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.
Dalsi prilezitost sledovat mistra pri praci na drobnejsich dilech.
Nekolik na sobe nezavislych vysledku, referovat na kolik bude cas.
Zkouma barevnost ctvereckovych soucinu pomoci Fourierovy analyzy,
velmi uzitecne techniky a elegantni vysledky. Na
strance Ehuda Friedguta je k tomu i prezentace v Powerpointu.
Z matice se ma vybrat podmatice s co nejvetsim souctem prvku.
Nekolik aproximacnich algoritmu s pouzitim peknych myslenek
moderni analyzy.
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.
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.
Hladiny v arrangementech jsou jednim z evergreenu kombinatoricke geometrie, a presto
autor zcela jednoduchym napadem dokazuje nove pekne veci (o krivkach).
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.
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.
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.
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).
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.
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.
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.
Ve skutecnosti sbirecka alonovskych perlicek v extremalni kombinatorice.
Nekolik na sobe nezavislych kousku, referovat na kolik bude cas.
Kouzla s vlastnimi cisly a explicitnimi konstrukcemi expanderu.
Staci prednest vhodne vybranou cast.
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).
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.
Kratky dukaz hypotezy Robertsona a Seymoura: stromovy zdvih rovinneho grafu
a jeho dualu se lisi nanejvys o 1.
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).
Three moves on signed surface triangulations by Shalom Eliahou,
Sylvian Gravier and Charles Payan
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.
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.)
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.
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.
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.
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.
Pekna elementarni kombinatoricka geometrie na klasicke tema.
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.
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.
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.
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.
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.
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.
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.
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)
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.
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.)
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.
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.
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.
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.
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.
Technicky neco elementarni teorie pravdepodobnosti aplikovane na
analyzu algoritmu. Zajimave aspekty (algoritmickeho) problemu
stabilniho manzelstvi a zminky o jeho pozoruhodnych aplikacich v praxi.
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.
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.
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.
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.
Pouziti kombinatoriky, konkretne Kneserovych (a Schrijverovych)
hypergrafu v problemu na pomezi analyzy a teorie mnozin.
Hlavne pro ty, kdo maji radi nekonecne mnoziny.
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.
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.
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.
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.
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.
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.
Jista zjemneni Szemerediho regularity lemmatu, vhodne hlavne pro nekoho,
kdo samotne regularity lemma uz zna. Doporuceno J. Kratochvilem.
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.
Problem klasicke extremalni teorie grafu vicemene formulovany v titulku.
Pomerne kratke.
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.
Prusecikova cisla a grafy bez zakazanych minoru,
zajimave asi hlavne pouzitymi nastroji.
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.
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.
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.
Narovnavani metru v rovine. Trocha elementarni topologie.
Doporuceno Pavlem Valtrem.
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.
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.
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.
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.