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., kcolorings, there is a very big gap between the largest average degree for which known polynomialtime 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 solutionspace geometry. Roughly speaking, at some problemspecific critical density, the set of solutions shatters and goes from being a single giant ball to exponentially many, wellseparated, tiny pieces. All known polynomialtime 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 oneway 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) fixedparameter algorithms, kernelizations, and approximation algorithms (often PTASs), for a wide variety of NPhard 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 smalltreewidth 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
