Sepehr Assadi, Yu Chen, and Sanjeev Khanna: Sublinear Algorithms for (Δ + 1) Vertex Coloring
This paper shows a "palette-sparsification" theorem for graph coloring that is useful for designing efficient sublinear algorithms for Delta+1 coloring (recall that every graph with max. degree Delta has a Delta+1 coloring). Most of the talk should focus on the proof of the "palette-sparsification" theorem (about 7 pages of the paper), with only a brief description of how to use it in sublinear algorithms. No need to present details of the lower bounds proven. Suitable for a PhD student or a master student (an experience with the probabilistic method is an advantage). For more background, you can contact P. Vesely.

J. Gubeladze: Normal polytopes and ellipsoids
This a paper which relates combinatorics, polytope theory and algebra. It is suitable for a PhD student or an experienced Master's student. If you need any help with this paper, contact Martin Tancer.

S. M. Cioabă, S. Dewar, X. Gu: Spectral conditions for graph rigidity in the Euclidean plane
This paper relates rigidity theory of a graph with its spectral properties. Rigidity, roughly speaking, describes how flexible the graph is during a continuous motion. Spectral properties are properties of eigenvalues of the adjacency matrix of the graph and some related matrices. The paper contains a small bit of technical computations. It would be desirable to sketch only the main ideas in this part while possibly skipping some computations. The paper is suitable for a PhD student or an experienced Master's student. If you need any help with this paper, contact Martin Tancer.

D. Ellis: Union-closed families with small average overlap densities
The paper is on combinatorics of families of subsets of certain set and the title describes the contents quite well. The paper is relatively short and it is most sutable for a Bachelor's student or a Master's student. If you need any help with this paper, contact Martin Tancer.

J. Nelson, H. Yu: Optimal bounds for approximate counting
We can maintain a counter incremented N times using O(log N) bits, however, what if we only need an approximation of N in return for even a smaller number of bits? This paper gives an optimal space upper and lower bounds for the approximate counting problem. It is suitable for a PhD or master student (some experience with randomized algorithms is an advantage). For more background, see reference [CY20] or ask P. Vesely.

S. Assadi, A. Dudeja: A Simple Semi-Streaming Algorithm for Global Minimum Cuts
Presents an O(n log n)-space algorithm that makes two passes over a sequence of edges of a (possibly dense) graph and then outputs a global minimum cut with high constant probability. Also proves a nearly tight lower bound. Suitable for a PhD student or a master student (some experience with randomized algorithms is an advantage). For more background, you can contact P. Vesely.

G. Pineda-Villavicencio: A new proof of Balinski’s theorem on the connectivity of polytopes
Balinski's theorem says that the graph of a d-dimensional convex polytope is d-connected. The author of this paper gives a new proof of this theorem. The contents of this paper seems to be very easily accessible even to Bachelor's students. Thus this paper is suitable for Bachelor's students or possibly for Master's students. If you need any help with this paper, you may contact Martin Tancer.

X. Chen, S. Fu: Two bijections on weakly increasing trees
This is a paper (essentially) in enumerative combinatorics and it provides some bijections for counting certain labelled trees. The paper is perhaps best suited for a Master's student. But it may also be suitable for an experienced Bachelor's student or a PhD student. If you need any help with this paper, contact Martin Tancer.

A. Karlin, N. Klein, S. Oveis Gharan, X. Zhang: An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-Subgraph Problem
A short paper improving the approximation ratio for finding cheapest multi-subgraphs with desired edge connectivity. If time allows, it'd be good to explain the previously best 3/2 approximation algorithm or lemmas from previous work used in the paper. If you need help with the paper, you can contact Pavel Vesely.

Michael Luby: LOCAL: Maximal Independent Set (Mohsen Ghaffari)
An exposition of the Maximal Independent Set (MIS) problem which is a central problem in the area of distributed algorithms for local graph problems. If you need any help with this paper, you may contact Michal Koucký.

Linial, Kuhn-Wattenhofer: LOCAL: Deterministic Coloring of General Graphs (Mohsen Ghaffari)
An exposition of coloring algorithms for general graphs in the LOCAL model. If you need any help with this paper, you may contact Michal Koucký.

Laurinharju and Suomela: LOCAL: Linial’s Lower Bound Made Easy
Linial’s seminal result shows that any deterministic distributed algorithm that finds a 3-colouring of an n-cycle requires at least log ∗ (n)/2 − 1 communication rounds. We give a new simpler proof of this theorem. If you need any help with this paper, you may contact Michal Koucký.

Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie: LOCAL: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge-coloring. For most problems the best randomized algorithm is at least exponentially faster than the best deterministic algorithm. In this paper we prove that these exponential gaps are necessary and establish numerous connections between the deterministic and randomized complexities in the LOCAL model (Sections 3 and 5). If you need any help with this paper, you may contact Michal Koucký.

Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie, Jukka Suomela: LOCAL: The distributed complexity of locally checkable problems on paths is decidable
Consider a computer network that consists of a path with n nodes. The nodes are labeled with inputs from a constant-sized set, and the task is to find output labels from a constant-sized set subject to some local constraints—more formally, we have an LCL (locally checkable labeling) problem. How many communication rounds are needed (in the standard LOCAL model of computing) to solve this problem? It is well known that the answer is always either O(1) rounds, or Θ(log ∗ n) rounds, or Θ(n) rounds. This paper shows that this question is decidable (albeit PSPACE- hard): it presents an algorithm that, given any LCL problem defined on a path, outputs the distributed computational complexity of this problem and the corresponding asymptotically optimal algorithm. If you need any help with this paper, you may contact Michal Koucký.

Robert Kleinberg, Daniel Mitropolsky, Christos Papadimitriou: Total Functions in the Polynomial Hierarchy
We identify several genres of search problems beyond NP for which existence of solutions is guaranteed. One class that seems especially rich in such problems is PEPP (for "polynomial empty pigeonhole principle"), which includes problems related to existence theorems proved through the union bound, such as finding a bit string that is far from all codewords, finding an explicit rigid matrix, as well as a problem we call Complexity, capturing Complexity Theory's quest. When the union bound is generous, in that solutions constitute at least a polynomial fraction of the domain, we have a family of seemingly weaker classes -PEPP, which are inside FP^NP|poly. Higher in the hierarchy, we identify the constructive version of the Sauer-Shelah lemma and the appropriate generalization of PPP that contains it. The resulting total function hierarchy turns out to be more stable than the polynomial hierarchy: it is known that, under oracles, total functions within FNP may be easy, but total functions a level higher may still be harder than FP^NP. If you need any help with this paper, contact Pavel Hubáček.

Nir Bitansky and Idan Gerichter: On the Cryptographic Hardness of Local Search
We show new hardness results for the class of Polynomial Local Search problems (PLS): * Hardness of PLS based on a falsifiable assumption on bilinear groups introduced by Kalai, Paneth, and Yang (STOC 2019), and the Exponential Time Hypothesis for randomized algorithms. Previous standard model constructions relied on non-falsifiable and non-standard assumptions. * Hardness of PLS relative to random oracles. The construction is essentially different than previous constructions, and in particular is unconditionally secure. The construction also demonstrates the hardness of parallelizing local search. The core observation behind the results is that the unique proofs property of incrementally- verifiable computations previously used to demonstrate hardness in PLS can be traded with a simple incremental completeness property. If you need help with this paper, contact Pavel Hubáček.

NOTE ON THE TURÁN NUMBER OF THE LINEAR 3-GRAPH C13: CHAOLIANG TANG, HEHUI WU, SHENGTONG ZHANG, AND ZEYU ZHENG
Extremal graph theory -- how many edges in a graph one needs to get a certain tree as a subgraph. Proofs are nice and paper is short :-).

Order-isomorphic twins in permutations: Boris Bukh, Oleksandr Rudenko
Two subpermutations in a permutation are called twins, if they have the same order-type (for instance, 1562 has the same order-type as 1342). The authors prove that each permutations contains twins of length roughly $n^{3/5}$. The proof is short but interesting. It uses, among else, a Poisson random process in a square.