Invited Speakers



   Dimitris Achlioptas (Department of Computer Science UC Santa Cruz)  


Erik Demaine  (MIT Computer Science and Artificial Intelligence Laboratory)


Abstracts of Invited Talks:

Dimitris Achlioptas (Invited Talk). Algorithmic Barriers from Phase Transitions in Graphs

Abstract: For a number of optimization problems on random graphs and hypergraphs, e.g., k-colorings, there is a very big gap between the largest average degree for which known polynomial-time algorithms can find solutions, and the largest average degree for which solutions provably exist. We study this phenomenon by examining how sets of solutions evolve as edges are added. We prove in a precise mathematical sense that, for each problem studied, the barrier faced by algorithms corresponds to a phase transition in the problem’s solution-space geometry. Roughly speaking, at some problem-specific critical density, the set of solutions shatters and goes from being a single giant ball to exponentially many, well-separated, tiny pieces. All known polynomial-time algorithms work in the ball regime, but stop as soon as the shattering occurs. Besides giving a geometric view of the solution space of random instances our results provide novel constructions of one-way functions.

Erik Demaine (Invited Talk). Algorithmic Graph Minors and Bidimensionality

Abstract: Graph Minor Theory, developed by Robertson and Seymour over two decades, provides powerful structural results about a wide family of graph classes (anything closed under deletion and contraction). In recent years, this theory has been extended and generalized to apply to many algorithmic problems.  Bidimensionality theory is one approach to algorithmic graph minor theory.  This theory provides general tools for designing fast (constructive, often subexponential) fixed-parameter algorithms, kernelizations, and approximation algorithms (often PTASs), for a wide variety of NP-hard graph problems for graphs excluding a fixed minor.  For example, some of the most general algorithms for feedback vertex set and connected dominating set are based on bidimensionality.  Another approach is ``deletion and contraction decompositions'', which split any graph excluding a fixed minor into a bounded number of small-treewidth graphs.  For example, this approach has led to some of the most general algorithms for graph coloring and the Traveling Salesman Problem on graphs.  I will describe these and other approaches to efficient algorithms through graph minors.

Videos of Invited talks

Dimitris Achlioptas