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

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.

Aysel Erey: On the average order of a dominating set of a forest
The title essential is self-explanatory: The aim of the paper is to provide a lower bound on the average order of a dominating set in a forest. There is a bit of computation in the paper; however, otherwise it is elementary. Therefore it should be accessible for Bc and Ms students. For any inquiries on this paper contact Martin Tancer.

Ce Jin, Virginia Vassilevska Williams, and Renfei Zhou: Listing 6-Cycles
The authors present a simple algorithm, based on color coding, that lists t (non-induced) 6-cycles in an n-node undirected graph in time O((n^2 + # of 6-cycles)*log(n)). For inquiries about this paper, feel free to contact Pavel Vesely.

Alexander Golovnev, Tom Gur, Igor Shinkar: Derandomization of Cell Sampling
This paper improves lower bounds on static data structures. The proof is using graph theory, in particular showing that every dense-enough hypergraph contains a small dense subgraph. For inquiries about this paper, feel free to contact Pavel Vesely.

Bill Jackson, Shin-ichi Tanigawa: Maximal matroids in weak order posets
Given a family of sets, can this family be a set of circuits of matroid? Is there the maximal matroid with these circuits? The aim of the paper is to provide partial answers for the question above. The paper is long thus it would be desired to select a small subset of the results of the paper to be presented. The paper is suitable for a PhD student or an enthusiastic Master student. If you need any help regarding this paper (including the choice of topics), please contact Martin Tancer. If desired, it could be also shared by more students. It has enough content for two talks.

Jialei Song Baogang Xu: Divisibility and coloring of some $P_5$-free graphs
The authors study graph classes where they forbid $P_5$ and some other graphs. For graphs in these classes, they for example show that it is possible to split such into a perfect part and a part with a smaller clique number. They also obtain results on the chromatic number of a slightly more restricted class. For inquiries on this paper, please contact Irena Penev.

Simón Piga, Marcelo Sales and Bjarne Schülke: The codegree Turán density of tight cycles minus one edge
This is a variant of a Turán density problem: If we have many edges in a hypergraph, then it contains a certain subhypergraph (in this case so called tight cycle minus an edge). Here the condition on many edges is given via codegree condition: every pair of vertices is contained in alpha n edges and the target is to optimize alpha. The paper is the most suitable for Bc students, or possibly Ms students. For inquiries, contact Martin Tancer

Gryphon Patlin, Jan van den Brand: Sublinear-Time Algorithm for MST-Weight Revisited
The usual sublinear-time algorithm for minimum spanning tree builds on Kruskal's algorithm. Here, the authors build on Jarník's (also known as Prim's) algorithm. For inquiries, you may contact Pavel Veselý.

William Kuszmaul: A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations
Chernoff bounds are widely used in theoretical computer science, yet their standard proofs may not give much intuition. Here, the author gives a proof that offers some intuition, has matching lower bounds and is user-friendly. Ideally, the standard proof of Chernoff bounds should be quickly presented as well. For inquiries, you may contact Pavel Veselý.

Dingyu Wang: Multi-dimensional Approximate Counting
In the classical problem of approximate counting, we want to approximate a number n using only loglog(n) bits (only +1 operations are allowed). The Morris counter can indeed do so for given relative error (with a small additive term depending on the relative error) and is optimal with respect to space. However, if we want to approximate more numbers than just one, using more Morris counters might not be the right move for some error metrics. Here, the author gives an optimal approximate counting algorithm for the Euclidean mean square error. For inquiries, you may contact Pavel Veselý.

Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann: Simpler Optimal Sorting from a Directed Acyclic Graph
In this paper, the authors give a simpler algorithm for the problem of sorting with partial information: you are given a partial order P described as an directed acyclic graph and you are given access to a comparison oracle that describes a linear extension L of P (so, you give two elements x,y to the oracle and it tells you whether x < y or y < x). The worst-case optimal algorithm (for both the running time and the number of oracle queries) has been known before, yet its analysis was quite sophisticated. Here, the authors give the worst-case optimal algorithm with a simple proof. For inquiries, you may contact Pavel Veselý.

Hsien-Chih Chang, Vincent Cohen-Addad, Jonathan Conroy, Hung Le, Marcin Pilipczuk, Michał Pilipczuk: Embedding Planar Graphs into Graphs of Treewidth O(log^3 n)
For approximation algorithms, it may be useful to build a metric embedding of a graph G into a structurally simpler edge-weighted graph H with small distortion of distances. Solving a problem on H may then give a reasonable approximation for G. Here, the authors construct a metric embedding of a planar graph on n vertices into a graph with treewidth O(log^3 n). This paper is quite long, so the presentation could only cover the explanation of the significance of the result, and a sketch of the construction. For inquiries, you may contact Pavel Veselý.

Aditya Anand, Thatchaphol Saranurak, Yunfan Wang: Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
Recently, a model for graph algorithms called the cut model attracted significant attention. Here, instead of knowing the edges of the graph, we get access to a cut oracle: given a subset S of the graph's vertices, the oracle returns the number of edges between the set S and the set V-S. We can learn the whole graph structure using O(n^2) queries and then use any standard algorithm. The authors improve this by presenting an algorithm that requires subquadratic number of queries for computing the min-cut on the whole graph and s-t max-flow. For inquiries, you may contact Pavel Veselý.

Ce Jin, Yael Kirkpatrick, Virginia Vassilevska Williams, Nicole Wein: Beyond 2-Approximation for k-Center in Graphs
The problem of k-Center is as follows: you have n points and a metric. You want to design k of the points as centers such that you minimize the largest distance from any point to its closest center. A 2-approximation algorithm is known, and this is tight as (2-epsilon)-approximation is NP-hard, when k is part of the input. The authors then give an algorithm that gives a (2-epsilon)-approximation with the caveat of an additional constant additive error. Additionally, the authors also give fine-grained lower bounds for the problem, though in the presentation, the main focus should be on the algorithm. For inquiries, you may contact Pavel Veselý.

Jean-Christophe Filliâtre: Verifying Two Lines of C with Why3: An Exercise in Program Verification
This article details the formal verification of a 2-line C program that computes the number of solutions to the n-queens problem. The formal proof of (an abstraction of) the C code is performed using the Why3 tool to generate the verification conditions and several provers (Alt-Ergo, CVC3, Coq) to discharge them. The main purpose of this article is to illustrate the use of Why3 in verifying an algorithmically complex program. For inquiries, you may contact Robert Šámal.

Andrei Asinowski, Gill Barequet, Gil Ben-Shachar, Martha Carolina Osegueda, Günter Rote: On the Number of Compositions of Two Polycubes
The paper presents a construction of two polyominos of size n that can be composed together without overlap in at least (n^2)/(2^{8\sqrt{\log_2 n}}) different ways (Theorem 4). This in particular disproves a previous erroneous claim by Barequet and Barequet that the maximum number of compositions of two polyominos is only linear in their size. For inquiries, you may contact Jan Kynčl.

Jineon Baek, Seewoo Lee: An Equilateral Triangle of Side > n Cannot be Covered by n^2 + 1 Unit Equilateral Triangles Homothetic to it
The title describes the paper very well. The paper is quite elementary and is suitable for (not so experienced) Bachelor students. For inquiries contact Martin Tancer.

Y. Li, M. Fu, Y. Zhang: Lower Bound on Translative Covering Density of Tetrahedra
A paper from combinatorial geometry on covering density when covering the Euclidean space by tetrahedra. When presenting the paper, it is important to explain the high level ideas rather than just the technical computations. Recommended for Master students or experienced Bachelor students. For inquiries, contact Martin Tancer.

N. Alon, O. Bousquet, K. Green Larsen, S. Moran, and S. Moran: Diagonalization Games
The paper studies a game for two players inspired by Cantor's diagonalization. One player maintains a list of binary vectors, the second player may ask queries: what is jth bit of ith vector. The goal of the second player is either to produce a vector different from all vectors for the first player (or to prove that no such vector exists). The paper studies how many queries are needed for this task. The paper is suitable for both Bachelor or Master students. For inquiries, contact Martin Tancer