# List of articles to refer at Doctoral seminar

## Available articles

Planar point sets determine many pairwise crossing segments [PDF]

It is well-known that every set of $n$ points in the plane in general position determines at least $\Omega(\sqrt{n})$ pairwise crossing line segments. It is widely conjectured that one should be always able to find linearly many such line segments, but the $\Omega(\sqrt{n})$-bound remained the best known bound for decades. In this paper, the authors almost solve this problem by showing that we always have at least $\Omega(n^{1-o(1)})$ pairwise crossing segments. The method they use is not very complicated, so this should be fairly simple to present.

An improved bound for weak epsilon-nets in the plane [PDF]

The author proves a first improvement on the bound for the weak $\epsilon$-nets in the plane, which addresses one of the truly improtant problems in combinaotrial geometry and gives a first improvement for this problem since 1992. More specifically, for a positive $\varepsilon$, let $f_2(\varepsilon)$ be the smallest positive number $f$ such that, for any finite underlying set $P$ of points in the plane, one can pierce any convex set containing at least $\varepsilon |P|$ points from $P$ using only $f$ points from the plane. The main result in this paper shows that $f_2(\varepsilon) = O(1/\varepsilon^{3/2+\gamma})$ for any positive $\gamma$.

Short proofs of some extremal results III [PDF]

This paper is a collection of results from extremal combinatorics, for which the authors give short and elegant proofs. The topics considered include independent arithmetic progressions, concentration for Ramsey numbers of random graphs, and Ramsey multiplicity. Some of the proofs yield full or partial solutions to open problems. It would be nice to present in detail a selection of the problems from the paper.

Polynomial to exponential transition in Ramsey theory [PDF]

The authors study a parameter $r_k(s,t;n)$, which generalizes Ramsey numbers $r_k(s,n)$ of coplete $k$-uniform hypergraphs $K^k_s$ and $K^k_n$ and which was introduced by Erdos to shed more light on the growth rate of Ramsey numbers. The authors almost prove a old conjecture by Erdos and Hajnal, for which Erdos offered 500 dollars, about the growth rate of $r_k(s,t;n)$.

Asymptotically optimal induced universal graphs [PDF]

A graph is k-universal if it contains every graph on k vertices as an induced subgraph. The problems that have received the most interest in this area are to find a k-universal graph with as few vertices as possible and to understand for which n a typical n-vertex graph is k-universal. In this paper both of these problems are effectively resolved, which essentially closes the book on the study of k-universal graphs.

Consistent sets of lines with no colorful incidence [PDF]

Call a collection of photographs consistent' if there is a same scene that these are photographs of (from different points of view). For the case when the scene' is just a set of points, we construct a collection of 101 photographs such that every 100 of them are consistent, but all of them together are inconsistent. Preliminary version appeared in SoCG'18.

Finding Cliques in Social Networks: A New Distribution-Free Model [PDF] Michal Opler

The authors propose an algorithm to find maximum cliques in $c$-closed graphs: graphs where if two vertices have at least $c$ common neighbors, then they are adjacent. Such property tends to be true for graphs of social networks.

Asymptotically good edge correspondence colouring [PDF]

An interesting graph coloring problem is solved by probabilistic tools well worth the study. Working knowledge of probabilistic method required.

The hat guessing number of graphs [PDF]

A variant of a well-known hat guessing game. And a collection of great techniques used to analyze it: probabilistic method, Lovász Local Lemma and the Combinatorial Nullstellensatz. Great place to learn the technique from one of the grand masters.

Lovász, vectors, graphs and codes [PDF]

An interesting algebraic construction of triangle-free graphs that tends to appear in many different contexts (extremal graph theory, coding theory, geometry).

The Reverse Kakeya Problem [PDF]

The original Kakeya problem asks for a minimum area shape which allows for a unit segment to be rotated within itself by 360 degrees. This classical problem has some surprising answers which deserves a short discussion of its own. This paper discusses the "inverse" problem. Given convex shapes $P$ and $Q$, how large can $P$ be made so that it can be rotated by 360 degrees inside $Q$ and prove an old conjecture for this problem.

Faster Algorithms for some Optimization Problems on Collinear Points [PDF]

This paper discusses three basic geometric optimization problems over $n$ points related to covering things by disks. Two of these problems are known to be NP-hard. The interesting thing is that they consider what some might dismiss as trivial case: the input set of points are collinear. They present fast algorithms for this case.

Dynamic Planar Orthogonal Point Location in Sublogarithmic Time [PDF]

Planar point location is one of the classic problems in Computational Geometry that one studies in introductory courses on CG/Algorithms. This paper presents improved algorithms for orthogonal case of the problem. A nice paper for data-structures enthusiasts!

Average-Case Fine-Grained Hardness [PDF] Pavel Dvoøák

This paper presents examples of some problems that can be solved in polynomial time in the worst case and are hard even in average case for slightly smaller polynomial times. A nice paper related to fine-grained complexity that has been becoming very popular recently and which roughly aims to prove lower bounds for polynomial-time solvable problems assuming that some famous problems have no better solutions than what is known.

Finding forbidden minors in sublinear time: a $n^{1/2+o(1)}$-query one-sided tester for minor closed properties on bounded degree graphs [PDF]

This paper discusses a fast way to find a minor H in bounded degree graphs assuming that a linear number of edges must be removed from the input graph to make it H-minor-free. Sublinear times appear surprising since one apparently doesn't even need to read the whole input, but that is the usual deal in results dealing with things such as property testing. A good choice of a paper if you have never seen sublinear algorithms.

Bootstrapping Results for Threshold Circuits Just Beyond Known Lower Bounds [PDF]

Lower bounds in complexity theory look abysmal and various explanatory results exist as to why we don't have better lower bounds. This paper falls in this regime and proves that even some very weak improvements in lower bounds for a certain complexity class ($TC^0$ to be precise) can give very strong separation from other classes.

The list chromatic number of graphs with small clique number [PDF] 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.

Uniform sampling through the Lovász local lemma [PDF] 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.

Fully-Dynamic Minimum Spanning Forest with Improved Worst-Case Update Time [PDF]

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})$.

Geodesic Walks in Polytopes [PDF]

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.

Approximate Counting, the Lovász Local Lemma and Inference in Graphical Models [PDF] 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.

How Well Do Local Algorithms Solve Semidefinite Programs? [PDF]

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.

Linear embeddings of graphs and graph limits [PDF] Jakub Pekárek

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 [PDF]

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.

On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing [PDF]

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.

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.

Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus [PDF]

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

Expanders via Local Edge Flips [PDF]

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

Improved Deterministic Algorithms for Linear Programming in Low Dimensions [PDF] Michael Skotnica

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

Undirected Graph Exploration with $\Theta(\log\log n)$ Pebbles [PDF] 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.

Characterisation of Strongly Stable Matchings [PDF]

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

Online Lower Bounds via Duality [PDF] Jakub Pekárek

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

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.).