TCSA Day 2013
We are happy to invite you to the fourth annual

Theoretical Computer Science Amsterdam (TCSA) Day
which will take place on

Friday November 1, 2013,
14:0017:00
in room L017 of CWI, Science Park 123, 1098 XG Amsterdam.
Directions to CWI
The TCSA Day is intended to be an annual event, taking place in the Fall, to alternate with
the national NVTI Theory Day that takes place in Spring.
The event is organized jointly by CWI, UvA, and VU, and its aim is to foster cooperation among the various TCSreseachers in and around Amsterdam.
Its Steering Committee consists of Jan Bergstra (UvA), Harry Buhrman (CWI, UvA), and Wan Fokkink (VU).
The Organizing Committee are
Alban Ponse (UvA),
Femke van Raamsdonk (VU),
Leen Torenvliet (UvA),
and Ronald de Wolf (CWI, UvA).
The 2009 edition took place at the VU, the 2010 edition at CWI, and the 2011 edition at UvA.
The programme consists of three talks by researchers from CWI, UvA, and VU.
There is no need to register. Tea and coffee will be provided.
Schedule
 14:0014:45 Ronald de Wolf (CWI, UvA): Exponential Lower Bounds for Polytopes in Combinatorial Optimization
 14:4515:00 coffee/tea break
 15:0015:45 Andrew Polonsky (VU): An Overview of Type Theory
 15:4516:00 coffee/tea break
 16:0016:45 Gunnar Klau (CWI, VU): Three Combinatorial Problems in Bioinformatics
Abstracts
 14:0014: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 NPhard 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 20year open problem by Yannakakis, who already proved such a result for symmetric linear programs. We prove similar lower bounds for polytopes assocated with other NPhard problems such as MaxCut and Independent Set.
Joint work with Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, at STOC'12
 15:0015: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 CurryHoward isomorphism, the core idea behind the deep integration between logical and computational levels unique to type theory.
 16:0016: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 socalled 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 NPhard, and I will present our solution approaches as well as a few open problems and future research directions.
This page is maintained by Ronald de Wolf. Last update: Oct 8, 2013