List of articles to refer at Doctoral seminar

Main page of Doctoral seminar

This page is administrated by Robert Šámal. If you want to refer some unreserved article, write me an e-mail.

Available articles

Michael Molloy The list chromatic number of graphs with small clique number [arXiv] Pavel Dvořák

A graph without a triangle and with maximal degree D has chromatic number at most $(1+o(1)) \frac{D}{\log D}$. This was proved by Johansson but never published. Reed and Molloy basically wrote a book about this proof. Here this result is proved in a few pages by a beautiful probabilistic argument (called entropy compression). It is possible to just present Section 2, if time allows we can see generalization for graphs with bounded clique size.

Oliver Riordan, Lutz Warnke Achlioptas process phase transitions are continuous [arXiv]

Pravdepodobnostni clanek, ne zas tak slozity, pozoruhodny tim, ze vyvraci "empiricky" i "heuristicky" overenou domnenku o nespojitosti fazoveho prechodu, ktera byla i publikovana v Science.

Terence Tao The Erdös Discrepancy problem [PDF] Karel Král

Solution of a problem that was open for a long time -- for every infinite sequence of $\pm 1$ the sum of elements at positions d, 2d, ..., nd can be arbitrary large. The paper uses Fourier analysis and several other interesting techniques to provide a solution. Not for the faint of heart!

Cristian S. Claude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Frank Stephan Deciding Parity Games in Quasipolynomial Time [Link]

Parity games are played on finite graphs by two players who take turns. It is a longstanding open problem whether these games are decidable in polynomial time. The authors prove that the games can be solved in Quasipolynomial time. This is a breakthrough similar to Babai's result on graph isomorphism.

Heng Guo, Mark Jerrum, Jingcheng Liu Uniform sampling through the Lovász local lemma [arXiv] Jan Voborník

This paper proposes a new algorithmic framework called "partial rejection sampling" to draw samples exactly from a product distribution conditioned on none of a number of bad events occurring. This is due to a new connection with the Lovász local lemma.

Christian Wulff-Nilsen Fully-Dynamic Minimum Spanning Forest with Improved Worst-Case Update Time [arXiv]

This paper provides a randomized data structure maintaining minimum spanning forest in a dynamic graph. Updates take expected worst-case time of $O(n^{1/2-\varepsilon})$. This bound is first improvement over a 25 year old bound of $O(\sqrt{n})$.

Yin Tat Lee, Santosh S. Vempala Geodesic Walks in Polytopes [arXiv]

This rather long paper describes the geodesic walk for sampling Riemannian manifolds and application to generating random points from the interior of polytopes specified by m inequalities. The problem of generating random samples from polytopes is an important problem with applications to volume estimation among others.

Ankur Moitra Approximate Counting, the Lovász Local Lemma and Inference in Graphical Models [arXiv] Jakub Pekárek

The main result is an algorithm to approximately count the number of solutions to a CNF formula under some restrictions closing an exponential gap between the upper and lower bounds. They also show that under Lovász Local Lemma-like conditions one can also generate approximately uniformly at random from the set of all satisfying assigments. The length of the paper should be ideal for the PhD seminar.

Zhou Fan, Andreaa Montanari How Well Do Local Algorithms Solve Semidefinite Programs? [arXiv]

The authors discuss local algorithms - algorithms that at each step take into account only a bounded neighborhood of the input graph - and discuss their power to solve Semidefinite programs. A nice paper.

Béla Bollobás, Oliver Riordan An old approach to the giant component problem [PDF]

Given a random graph (with a given degree sequence), how big is the largest connected component? This paper improves earlier results and, being written by the masters of the area, allows one to witness many interesting and important techniques. (Approximation of the generation of random graph by a branching process, to name just one.) Working knowledge of probabilistic method required.

Huda Chuangpishit, Mahya Ghandehari, Matthew Hurshman, Jeannette Janssen, Nauzer Kalyaniwalla Linear embeddings of graphs and graph limits [PDF]

Graph limit approach to a new version of random graphs: we first choose random vertices from an interval [0,1] and then assign the edges at random -- but with probability depending on the distance of the vertices. An opportunity to study a recent technique (graphons, etc.) in a new setting.

The Computational Power of Optimization in Online Learning [arXiv]

Again, a paper in learning theory about minimizing regret in prediction based on expert advised when experts can be chosen in some optimal way at any point.

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

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

Eric Fusy Quadratic exact-size and linear approximate-size random sampling of planar graphs [PDF]

Jak generovat nahodny rovinny graf, a to rychle. Kombinuje zname vysledky o vytvorujicich funkcich pro rovinne grafy s nedavnou myslenkou Boltzmannovych nahodnych generatoru (Duchon, Flajolet, Louchard, Schaeffer). Oboji je potreba pekne objasnit, asi i s pouzitim puvodnich clanku. Tezsi clanek, mozna vhodny i pro 2 lidi.

Lionel Levine, Wesley Pegden, Charles K. Smart Apollonian structure in the abelian sandpile [arXiv]

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

Radu Curticapean, Dániel Marx Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus [web]

Shows parameterized hardness results for counting perfect matchings under a counting variant of Strong Exponential Time Hypothesis.

Zeyuan Allen-Zhu, Aditya Bhaskara, Silvio Lattanzi, Vahab Mirrokni, Lorenzo Orecchia Expanders via Local Edge Flips [arXiv]

Improved bounds for a decentralized, local algorithm to transform any regular graph (with degree \(\Omega(\log{n}))\) into an expander.

Timothy M. Chan Improved Deterministic Algorithms for Linear Programming in Low Dimensions [web]

A better derandomization of Clark's LP algorithm to give improved runtime dependence on the dimension.

Yann Disser, Jan Hackfeld, Max Klimm Undirected Graph Exploration with \(\Theta(\log\log n)\) Pebbles [web] Veronika Slívová

Exploring a graph with memory less than \(O(\log{n})\) when the memory units can be dropped off and picked up by agents like pebbles used to mark nodes.

Pratik Ghosal, Adam Kunysz, Katarzyna Paluch Characterisation of Strongly Stable Matchings [arXiv]

Shows that there exists a "small" partial order representing strongly stable matchings of a graph. Also gives algorithms to compute such a representation.

Daniel Průša, Tomáš Werner LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP [web] 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.

Yossi Azar, Ilan Reuven Cohen, Alan Roytman Online Lower Bounds via Duality [arXiv]

Uses LP duality to give lower bound on the competitiveness of online algorithms.

Noga Alon, Nicolo Cesa-Bianchi, Claudio Gentile, Shie Mannor, Yishay Mansour, Ohad Shamir Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback [PDF]

Multiarmed bandit is a well-studied subject where we need to make decisions with uncertain outcomes (unknown probabilities), we want to (eventually) learn what decisions are good, but not to pay too much for making bad decisions along the way. In this paper theorems about the situation are proved using tools from information theory (relative entropy, etc.).

Reserved articles

Jacob Fox, Janos Pach, Andrew Suk Approximating the rectilinear crossing number [arXiv] 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.

Presented articles

Ran Raz Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning [web] 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 [arXiv] 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 [web] 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 [arXiv] 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 [arXiv] 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? [arXiv] 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 [arXiv] 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 [arXiv] 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 [arXiv] 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 [arXiv] 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 [arXiv] 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 [arXiv] 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 [arXiv] 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 [arXiv] 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[arXiv] 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 [arXiv] 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 [arXiv] 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 [arXiv] 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 [arXiv] 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).

Archiv už drive přednesených článků