TCSA Day 2013

• Theoretical Computer Science Amsterdam (TCSA) Day

• Friday November 1, 2013, 14:00-17:00
  in room L017 of CWI, Science Park 123, 1098 XG Amsterdam. Directions to CWI

Schedule

• 14:00-14:45 Ronald de Wolf (CWI, UvA): Exponential Lower Bounds for Polytopes in Combinatorial Optimization
• 14:45-15:00 coffee/tea break
• 15:00-15:45 Andrew Polonsky (VU): An Overview of Type Theory
• 15:45-16:00 coffee/tea break
• 16:00-16:45 Gunnar Klau (CWI, VU): Three Combinatorial Problems in Bioinformatics

Abstracts

• 14:00-14:45 Ronald de Wolf (CWI, UvA): Exponential Lower Bounds for Polytopes in Combinatorial Optimization
  
  Abstract: In the 1980s there were attempts to show that P=NP by means of efficient linear programs for NP-hard problems such as the Traveling Salesman problem (TSP). We show that such attempts cannot work: "reasonable" linear programs for solving TSP require exponential size. More precisely, every linear program whose associated polytope projects to the traveling salesman polytope needs to have an exponential number of linear constraints. This solves a 20-year open problem by Yannakakis, who already proved such a result for symmetric linear programs. We prove similar lower bounds for polytopes assocated with other NP-hard problems such as Max-Cut and Independent Set.
  Joint work with Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, at STOC'12



• 15:00-15:45 Andrew Polonsky (VU): An Overview of Type Theory
  
  Abstract: This talk will be a basic introduction to type theory. Type theory is a language for constructive mathematics in which logic and computation are integrated in a natural way at the most fundamental level. The goal of type theory is to be for constructive mathematics what set theory is for classical mathematics: an informal language for communicating concepts and statements. The realization of this goal has historically been impeded by the problem of extensionality, but recent ideas falling under the generic name of "Homotopy Type Theory" give promise for the resolution of this challenge. As a result, type theory has seen increasing attention from mathematicians as of late. This talk will focus on the Curry-Howard isomorphism, the core idea behind the deep integration between logical and computational levels unique to type theory.



• 16:00-16:45 Gunnar Klau (CWI, VU): Three Combinatorial Problems in Bioinformatics
  
  Abstract: In this talk I will give an overview of three topics in bioinformatics and how to approach them with combinatorial models. The topics are (i) partitioning molecule graphs into so-called charge groups, a problem that has to be solved before running molecular dynamics simulations, (ii) comparing phylogenetic trees and (iii) comparing biological networks. All these problems are NP-hard, and I will present our solution approaches as well as a few open problems and future research directions.