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) - Ruzsa-Szemerédi Graphs and a (biased) Sample of Their Applications
Talk delivered by Sanjeev Khanna and Janani Sundaresan
Ruzsa-Szemeredi Graphs (RS graphs henceforth) are a family of extremal graphs with a magical property: they are "locally sparse" and yet "globally dense". More accurately, an (r,t)-RS graph is an edge-disjoint union of t induced matchings, each of size r. Over the years, various constructions of these graphs, with different parameters r,t, have found numerous applications to different areas of TCS. In this talk, we discuss a biased sample of these applications to some graph problems in areas such as streaming, sparsification, and dynamic algorithms.
________________________________________________________________________
Friday, June 28, 8:30-9:30am: Sorrachai Yingchareonthawornchai (Hebrew University of Jerusalem) - How to Search and Sort using Forbidden 0-1 Matrix Theory
We will present a survey on recent progress in pattern-avoiding access in binary search trees and its application to sorting pattern-avoiding permutations. We will explore the key techniques in the area that allow us to achieve nearly tight amortized analysis through the lens of forbidden 0-1 matrix theory, including the new matrix decomposition method. We will also present new tight extremal bounds on 0-1 matrices forbidding product patterns, which bound the time required to sort a pattern-avoiding permutation. Prior familiarity with forbidden 0-1 matrix theory is not required.
________________________________________________________________________
Friday, June 28, 9:30-10:30am: Jiapeng Zhang (USC) - Structure-vs-Pseudorandomness Approach and Its Applications
The structure-vs-pseudorandomness approach is a powerful tool in mathematics and theoretical computer sciences with numerous important applications. In this talk, I will discuss its connections to study sets. Several applications will be covered, such as the improved sunflower lemma, lifting theorems, and recent developments in gadgetless liftings.
________________________________________________________________________
Friday, June 28, 10:30-11am: Open Problem Session
Speakers from the workshop will present open problems related to their talks.