STOC 2024 Workshop: Applications of Turán-type Problems in Theoretical Computer Science

Header image of a spider weaving a graph as its web

When: Thursday June 27 and Friday June 28, 8:30-11am

Where: Sheraton Vancouver Wall Centre, Vancouver (STOC venue; room TBA)

What: In extremal combinatorics, a Turán-type problem is one that asks for the maximum possible size of a combinatorial system – such as a graph, hypergraph, or matrix – that avoids one or more forbidden patterns. These are named after Turán’s Theorem, which settles the maximum possible number of edges in a graph that does not contain any k-cliques as subgraphs.

Recently, Theoretical Computer Scientists have discovered powerful applications of classical results on Turán-type problems in the areas of algorithms, complexity theory, network design, and more. This workshop will cover some of the major successes of this method. No prior knowledge is assumed: talks will survey Turán-type problems, the combinatorial methods used to solve them, and their applications in computer science from scratch.


Thursday 6/27

Part 1:

Part 2:
Greg Bodwin
University of Michigan
Workshop Tutorial

Abstract: We will give an introduction to the basic definitions, history, techniques, and applications of Turán-type problems in theoretical computer science. We will introduce the problems that will be covered in greater depth in later talks in this workshop, and we will explore reductions and connections between them. We will also show some some sample applications of Turán-type problems in network design.

No previous knowledge of extremal combinatorics or theoretical computer science will be assumed.
Thursday 6/27

Sepehr Assadi
University of Waterloo
Title/Abstract TBA
Friday 6/28


Sorrachai Yingchareonthawornchai
Hebrew University of Jerusalem
Title/Abstract TBA
Friday 6/28

Jiapeng Zhang
Title/Abstract TBA
Friday 6/28

All SpeakersOpen Problem Session

Speakers from the workshop will present open problems related to their talks.