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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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

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

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

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

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.

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.

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

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.

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.

M. Schaefer: A New Algorithm for Embedding Plane Graphs at Fixed Vertex Locations

The title describes the contents quite well; an additional aim of the algorithm is to achieve a small number of bends. The paper is elementary but all its contents will probably not fit into the duration of a standard talk. Thus the speaker has to select carefully what to emphasize. The paper is most suitable for Master's students. But it is also suitable for an experienced Bachelor's student, or possibly for a PhD student. If you need any help with this paper, contact Martin Tancer.

The title describes the contents quite well; an additional aim of the algorithm is to achieve a small number of bends. The paper is elementary but all its contents will probably not fit into the duration of a standard talk. Thus the speaker has to select carefully what to emphasize. The paper is most suitable for Master's students. But it is also suitable for an experienced Bachelor's student, or possibly for a PhD student. If you need any help with this paper, contact Martin Tancer.

R. Jayaram, J. Kallaugher: An Optimal Algorithm for Triangle Counting in the Stream

This short paper presents an algorithm for approximating the number of triangles in a graph, whose edges arrive in a sequence and the algorithm cannot store all of them. For more background, you can contact P. Vesely.

This short paper presents an algorithm for approximating the number of triangles in a graph, whose edges arrive in a sequence and the algorithm cannot store all of them. For more background, you can contact P. Vesely.

T. Korhonen: A Single-Exponential Time 2-Approximation Algorithm for Treewidth

This short paper presents a new approximation algorithm for treewidth, a fundamental graph parameter that is NP-hard to compute in general.

This short paper presents a new approximation algorithm for treewidth, a fundamental graph parameter that is NP-hard to compute in general.

Mohsen Ghaffari: LOCAL: An Improved Distributed Algorithm for Maximal Independent Set

The Maximal Independent Set (MIS) problem is one of the basics in the study of locality in distributed graph algorithms. This paper presents an extremely simple randomized algorithm providing a near-optimal local complexity for this problem, which incidentally, when combined with some known techniques, also leads to a near-optimal global complexity. If you need any help with this paper, you may contact Michal Koucký.

The Maximal Independent Set (MIS) problem is one of the basics in the study of locality in distributed graph algorithms. This paper presents an extremely simple randomized algorithm providing a near-optimal local complexity for this problem, which incidentally, when combined with some known techniques, also leads to a near-optimal global complexity. If you need any help with this paper, you may contact Michal Koucký.

A. P. Bharathi, S. A. Choudum: Colouring of (P3 ∪ P2)-free graphs

One of the results of the paper is that the graph as in the title have chromatic number bounded from above by a cubic function of the clique number.

One of the results of the paper is that the graph as in the title have chromatic number bounded from above by a cubic function of the clique number.

M. Bonamy, C. Groenland, C. Muller, J. Narboni, J. Pekárek d,3, Alexandra Wesolek: A note on connected greedy edge colouring

The authors compare greedy edge coloring with the version where the edges are additionally ordered in a "connected fashion". The show NP-hardness of distinction of this two cases, while they mention some case when the distinction is easy.

The authors compare greedy edge coloring with the version where the edges are additionally ordered in a "connected fashion". The show NP-hardness of distinction of this two cases, while they mention some case when the distinction is easy.

Paul W. Goldberg, Alexandros Hollender: The Hairy Ball Problem is PPAD-Complete

The Hairy Ball Theorem states that every continuous tangent vector field on an even-dimensional sphere must have a zero. We prove that the associated computational problem of computing an approximate zero is PPAD-complete. We also give a FIXP-hardness result for the general exact computation problem. In order to show that this problem lies in PPAD, we provide new results on multiple-source variants of End-of-Line, the canonical PPAD-complete problem. In particular, finding an approximate zero of a Hairy Ball vector field on an even-dimensional sphere reduces to a 2-source End-of-Line problem. If the domain is changed to be the torus of genus g ≥ 2 instead (where the Hairy Ball Theorem also holds), then the problem reduces to a 2(g − 1)-source End-of-Line problem. These multiple-source End-of-Line results are of independent interest and provide new tools for showing membership in PPAD. In particular, we use them to provide the first full proof of PPAD-completeness for the Imbalance problem defined by Beame et al. in 1998. If you need any help with this paper, you may contact Pavel Hubáček.

The Hairy Ball Theorem states that every continuous tangent vector field on an even-dimensional sphere must have a zero. We prove that the associated computational problem of computing an approximate zero is PPAD-complete. We also give a FIXP-hardness result for the general exact computation problem. In order to show that this problem lies in PPAD, we provide new results on multiple-source variants of End-of-Line, the canonical PPAD-complete problem. In particular, finding an approximate zero of a Hairy Ball vector field on an even-dimensional sphere reduces to a 2-source End-of-Line problem. If the domain is changed to be the torus of genus g ≥ 2 instead (where the Hairy Ball Theorem also holds), then the problem reduces to a 2(g − 1)-source End-of-Line problem. These multiple-source End-of-Line results are of independent interest and provide new tools for showing membership in PPAD. In particular, we use them to provide the first full proof of PPAD-completeness for the Imbalance problem defined by Beame et al. in 1998. If you need any help with this paper, you may contact Pavel Hubáček.

Ore’s Conjecture for $k = 4$ and Grötzsch Theorem: Alexandr Kostochka, Matthew Yancey

A graph is $k$-critical, if it has chromatic number $k$, but all subgraphs are $(k-1)$-colorable. The authors give a lower bound for the number of edges in a 4-critical graph. As a consequence, they give a simple short proof of the Grötzsch Theorem that every triangle-free planar graph is 3-colorable.

A graph is $k$-critical, if it has chromatic number $k$, but all subgraphs are $(k-1)$-colorable. The authors give a lower bound for the number of edges in a 4-critical graph. As a consequence, they give a simple short proof of the Grötzsch Theorem that every triangle-free planar graph is 3-colorable.