Applications of Turán-type Problems in Theoretical Computer Science
Organizer: Greg Bodwin, University of Michigan
When: June 27 (Thursday) and June 28 (Friday), both days 8:30-11am
Where: Sheraton Vancouver Wall Centre, Vancouver (STOC venue). Room TBA.
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 streaming algorithms, derandomization, complexity theory, sorting, network design, and much more. This workshop will consist of four survey talks, covering four of the major successes of this method, in addition to a starting tutorial explaining the area. No prior knowledge is assumed: talks will survey Turán-type problems from scratch.
Thursday, June 27, 8:30-10am: Greg Bodwin (University of Michigan) - Workshop Tutorial
We will give an introduction to the basic definitions, history, techniques, and applications of Turán-type problems in theoretical computer science, with a focus specifically on applications in network design. The first part of the tutorial will be a gentle introduction to the definitions, history, and techniques in Turán-type problems, including a survey of the objects that will be discussed later in the workshop. The second part will show some sample applications in network design.
________________________________________________________________________
Thursday, June 27, 10-11am: Sepehr Assadi (University of Waterloo) - TBA
________________________________________________________________________
Friday, June 28, 8:30-9:30am: Sorrachai Yingchareonthawornchai (Hebrew University of Jerusalem) - TBA
________________________________________________________________________
Friday, June 28, 9:30-10:30am: Jiapeng Zhang (USC) - TBA
________________________________________________________________________
Friday, June 28, 10:30-11am: Open Problem Session
Speakers from the workshop will present open problems related to their talks.