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.
Schedule:
| Thursday 6/27 Part 1: 8:30-9:15am Part 2: 9:20am-10am | 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 10:00-11am | Sepehr Assadi University of Waterloo | Title/Abstract TBA |
| Friday 6/28 8:30-9:30am | Sorrachai Yingchareonthawornchai Hebrew University of Jerusalem | Title/Abstract TBA |
| Friday 6/28 9:30-10:30am | Jiapeng Zhang USC | Title/Abstract TBA |
| Friday 6/28 10:30-11 | All Speakers | Open Problem Session Speakers from the workshop will present open problems related to their talks. |