N&O Seminars 2005-2008

See below for an overview of all N&O seminars from 2005 to 2008.


Speaker: Nicole Immorlica (Northwestern Univ.) 
Title: Approximating Matches Made in Heaven 
Date/Location: Thursday December 18, 14h00, room M280, CWI-Amsterdam

Speaker: Janina Brenner (TU Berlin) 
Title: Cooperative cost sharing via singleton mechanisms 
Date/Location: Thursday December 11, 13h00, room M280, CWI-Amsterdam

Speaker: Florian Horn (CWI) 
Title: The complexity of Muller games 
Date/Location: Friday November 28, 13h00, room M279, CWI-Amsterdam

Event: PhD defense of Jarek Byrka 
Title: Randomized Approximation Algorithms: Facility Location, Phylogenetic Networks, Nash Equilibria 
Date/Location: Monday October 13, 16h00, TU Eindhoven. 
as part of the Diamant Algorithms Day.

speaker: Philipp Rostalski (ETH, Zurich) 
Title: Quasi-Hankel matrices and the real radical ideal 
Date/Location: Thursday September 25, 13h00, room M280, CWI-Amsterdam.

speaker: Maurits de Graaf (Thales) 
Title: The network lifetime problem in ad-hoc networks: results and problems 
Date/Location: Friday September 12, 13h00, room M279, CWI-Amsterdam.

speaker: Renato Gomes, CWI intern and Northwestern graduate student 
Title: Externalities in Keyword Auctions: an Empirical Assessment and a Model of Scoring Rules 
Date/Location: Thursday September 4, 15h00, room M280, CWI-Amsterdam.

speaker: Achill Schuermann (Univ. Magdeburg) 
Title: Computational Geometry of Positive Definite Quadratic Forms 
Date/Location: Thursday September 4, 13h00, room M280, CWI-Amsterdam.

speaker: Jason Hartline (Northwestern University) 
Title: Optimal Mechanism Design - from the 2007 Nobel Prize in Economics to the Foundations of Internet Algorithms 
Date/Location: Thursday August 28, 13h00, room M280, CWI-Amsterdam.

speaker: Elena Grigorescu, MIT and CWI Intern 
Title: 2-transitivity is insufficient for local testability 
Date/Location: Thursday August 14, 13h00, room M279, CWI-Amsterdam.

speaker: Mohammad Mahdian, Yahoo! Research 
Title: Externalities in Online Advertising 
Date/Location: Thursday July 24, 13h00, room M279, CWI-Amsterdam.

speaker: Aravind Srinivasan (Univ. Maryland) 
Title: Dependent rounding and its applications to approximation algorithms 
Date/Location: Thursday July 3, 10h00, room M279, CWI-Amsterdam.

speaker: Fernando de Oliveira Filho (CWI) 
Title: Fourier analysis, linear programming, and densities of distance avoiding sets in R^n 
Date/Location: Friday June 6, 13h00, room M280, CWI-Amsterdam.

speaker: Seffi Naor (Technion) 
Title: A Primal-Dual Approach to Online Optimization Problems 
Date/Location: Thursday 15 May, 13h00, room M280, CWI-Amsterdam.

speaker: Guido Schaeffer (Technical University Berlin) 
Title: Cost Sharing Mechanisms for Combinatorial Optimization Problems 
Date/Location: Wednesday 23 April, 13h00, CWI-Amsterdam, M279.

speaker: Martin Gairing (International Computer Science Institute, Berkeley) 
Title: Selfish Routing in Networks 
Date/Location: Monday 21 April, 10h00, CWI-Amsterdam, M279.

Celebrating Lex' birthday
13h30: Cor Hurkens, Franklin Magic Squares 
14h30: Hein van der Holst, On $\mu(G)$ and other Colin de Verdiere-type parameters 
16h15: Rudi Pendavingh, Lifting of matroid representations over partial fields 
Date/Location: Friday 18 April, 13h15, CWI-Amsterdam, M280.

speaker: Xinhui Wang (Univ. Twente) 
Title: Exact algorithms for the Steiner tree problem 
Date/Location: Wednesday 16 April, 10h30, CWI-Amsterdam, M279.

speaker: Vahab Mirrokni (Microsoft Research, Redmond) 
Title: Submodular optimization and online advertisement 
Date/Location: Monday 14 April, 10h00, CWI-Amsterdam, M279.

Event: PhD defense of Nebojsa Gvozdenovic 
Title: Approximating the stability number and the chromatic number of a graph via semidefinite programming 
Date/Location: Thursday 10 April, 12h00, Agnietenkapel, University of Amsterdam.

speaker: Benny Mounits (CWI) 
Title: Upper Bounds for Codes Over Finite Rings via Semidefinite Programming 
Date/Location: Thursday 3 April, 13h00, CWI-Amsterdam, M280.

speaker: Monique Laurent (CWI) 
Title: Comparing some linear algebra methods for (real) solving polynomial equations 
Date/Location: Friday February 22, 10h00, CWI-Amsterdam, M280.

speaker: Fernando Oliveira de Filho (CWI) 
Title: How to destroy all group Steiner trees in a graph? 
Date/Location: Friday February 15, 10h00, CWI-Amsterdam, M280.

speaker: Anupam Gupta (CMU) 
Title: Oblivious Network Design 
Date/Location: Monday January 14, 10h30, CWI-Amsterdam, M280.


speaker: Piotr Indyk (MIT) 
Title: Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1 
Date/Location: Tuesday December 18, 10h30, CWI-Amsterdam, M279.

speaker: Dion Gijswijt (UvA) 
Title: Fractional matroid matchings: finding a maximum weight fractional matching 
Date/Location: Friday December 7, 13h00, CWI-Amsterdam, M279.

speaker: Tobias Mueller (Eurandom) 
Title: Circular choosability 
Date/Location: Friday November 23, 13h00, CWI-Amsterdam, M279.

speaker: Kamal Jain (Microsoft Research) 
Title: Atomic Economics 
Date/Location: Friday November 16, 13h00, CWI-Amsterdam, M280.

speaker: Edith Elkind (University of Southampton) 
Title: Frugality in set system auctions: an overview 
Date/Location: Monday November 12, 11h00, CWI-Amsterdam, M280.

speaker: Lars Schewe (CWI) 
Title: Realizability of oriented matroids 
Date/Location: Friday November 2, 13h00, CWI-Amsterdam, M280.

speaker: Nicole Immorlica (CWI) 
Title: Revenue maximization in digital goods auctions 
Date/Location: Friday October 12, 13h00, CWI-Amsterdam, M280.

speaker: Frank McSherry (Microsoft Research) 
Title: Mechanism Design via Differential Privacy 
Date/Location: Monday October 1st, 16h00, CWI-Amsterdam, M279.

speaker: Jarek Byrka and Steven Kelk 
Title: Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks 
Date/Location: Monday October 1st, 10h00, CWI-Amsterdam, M279.

speaker: Erik Jan van Leeuwen 
Title: Domination in Geometric Intersection Graphs 
Date/Location: Friday September 7, 10h00, CWI-Amsterdam, M280.

speaker: Gyula Pap 
Title: Packing A-paths subject to node-capacities 
Date/Location: Friday August 24, 13h00, CWI-Amsterdam, M279.

speaker: Gyula Karolyi 
Title: The Combinatorial Nullstellensatz and the Polynomial Method 
Date/Location: Friday August 24, 10h00, CWI-Amsterdam, M279.

speaker: Amin Saberi 
Title: Approximation Algorithms for Fair Allocation of Indivisible Goods 
Date/Location: Tuesday July 3, 10h00, CWI-Amsterdam, M280.

speaker: Vangelis Markakis 
Title: Algorithms for Approximate Nash Equilibria 
Date/Location: Friday June 22, 13h00, CWI-Amsterdam, M280.

speaker: Benny Mounits 
Title: Lower bounds on the minimum average distance of binary codes 
Date/Location: Thursday June 7, 10h00, CWI-Amsterdam, H320 (Nikhef).

speaker: Arantza Estevez-Fernandez 
Title: Sequencing games: an introduction to OR games 
Date/Location: Friday May 25, 13h00, CWI-Amsterdam, M280

speaker: Nicole Immorlica 
Title: Secretary Problems and Online Auction Design 
Date/Location: Tuesday May 15, 13h30, CWI-Amsterdam, M279

speaker: Serguei Norin 
Title: Pfaffian orientations of graphs 
Date/Location: Tuesday April 17, 10h00, CWI-Amsterdam, M279

speaker: Markus Schweighofer 
Title: Sums of hermitian squares of polynomials, the BMV conjecture and Connes' embedding problem 
Date/Location: Tuesday April 17, 13h00, CWI-Amsterdam, M279

speaker: Hein van der Holst 
Title: Minimum rank of graphs and 2-separations 
Date/Location: Tuesday April 17, 15h30, CWI-Amsterdam, M279

speaker: Frank Vallentin 
Title: Packing problems in compact metric spaces 
Date/Location: Wednesday April 11, 15h00, CWI-Amsterdam, M279

speaker: Frank Vallentin 
Title: Voronoi cells of lattices, regular matroids, and a bit of complexity theory 
Date/Location: Tuesday March 6, 13h00, CWI-Amsterdam, M280

speaker: Dion Gijswijt 
Title: Fractional matroid matching (follow-up) 
Date/Location: Thursday Februari 22, 10h00, CWI-Amsterdam, Room M280

speaker: Dion Gijswijt 
Title: Fractional matroid matching 
Date/Location: Thursday Februari 15, 10h00, CWI-Amsterdam, Room M280

speaker: Katharina Huber (School of Computing Sciences, University of East Anglia) 
Title: Median graphs and beyond 
Date/Location: Monday January 29, 15h00-17h00, CWI-Amsterdam, Room M280

speaker: Fernando de Oliveira Filho (CWI) 
Title: A conjecture of Lovasz concerning bi-critical graphs 
Date/Location: Friday January 26, 10h00, CWI-Amsterdam, Room M279


speaker: Steven Kelk (CWI) 
Title: Beaches of islands of tractability: Algorithms for parsimony and minimum perfect phylogeny haplotyping problems 
Date/Location: 08-12-2006, 13h00, CWI-Amsterdam, Room M280

speaker: Lex Schrijver (CWI) 
Title: Shortest disjoint paths in planar graphs 
Date/Location: 24-11-2006, 13h00, CWI-Amsterdam, Room M280

DIAMANT Intercity Event: Lattice Day
Date: Friday November 10, 2006 
Place: University of Leiden.

speaker: Jarek Byrka (CWI) 
Title: A 1.5-approximation algorithm for the metric uncapacitated facility location problem 
Date/Location: 20-10-2006, 13h00, CWI-Amsterdam, Room M280 

speaker: Erik Jan van Leeuwen (CWI) 
Title: Algorithmic aspects of graph minor theory 
Date/Location: 06-10-2006, 13h00, CWI-Amsterdam, Room M280 

speaker: Hartwig Bosse (CWI) 
Title: Symmetries and sums of squares of polynomials 
Date/Location: 15-09-2006, 13h00, CWI-Amsterdam, Room M280 

DIAMANT/Spinoza Intercity Seminar on Algebra and Symmetries in Combinatorics and Optimization
Date: Friday June 30, 2006. 
Location: University of Amsterdam 
See here for the list of talks.

speaker: Vangelis Markakis (University of Toronto) 
Title: Computational Aspects of Game Theory and Microeconomics 
Date/Location: 28-06-2006, 10h00, CWI-Amsterdam, Room M280 

speaker: Jules van Kempen (Utrecht University) 
Title: Online capacity planning of repairs at Rüttchen car dealers 
Date/Location: 23-06-2006, 13h00, CWI-Amsterdam, Room M279 

speaker: Mike Steel, Director for Biomathematics Research Centre, University of Canterbury (New Zealand) 
Title: Combinatorial approaches in phylogenetics 
Date/Location: Wednesday 14-06-2006, 10h15, CWI-Amsterdam, Room N328 (NIKHEF building) 

speaker: Beniamin Mounits (CWI) 
Title: Joint weight enumerators and semidefinite programminng bound for binary codes 
Date/Location: 09-06-2006, 13h00, CWI-Amsterdam, Room M279 

speaker: Frank Vallentin (CWI) 
Title: Semidefinite programming bounds for spherical codes 
Date/Location: 15-05-2006, 13h00, CWI-Amsterdam, Room M279 

speaker: Stefan van Zwam (TUE) 
Title: A semidefinite programming relaxation of the space of Korkin--Zolotarev reduced lattice bases 
Date/Location: 28-4-2006, 10h30, CWI-Amsterdam, Room M280 

speaker: Monique Laurent (CWI) 
Title: Solving systems of polynomial equations via linear algebra 
Date/Location: 07-04-2006, 13h00, CWI-Amsterdam, Room M280 

speakers: Steven Kelk (CWI) and Leen Stougie (CWI/TUE) 
Title: Prefix reversals on strings over finite alphabets 
Date/Location: 24-03-2006, 13h00, CWI-Amsterdam, Room M280 

speaker: Lex Schrijver, CWI 
Title: Tensor algebras and invariant theory 
Date/Location: 10-03-2006, 13h00, CWI-Amsterdam, Room M280 

Speaker: Vangelis Markakis, University of Toronto, Toronto 
Title: Inapproximability Results for Maximizing the Social Welfare in Combinatorial Auctions 
Date/Location: Tuesday 14-02-2006, 11h00, CWI-Amsterdam, Room M280 

Speaker: Thomas Erlebach, University of Leicester, Leicester 
Title: Minimum weight dominating sets in unit disk graphs 
Date/Location: Thursday 02-02-2006, 13h00, CWI-Amsterdam, Room M280 

DIAMANT Intercity Event: Integer Programming Day
Date: Friday January 27, 2006 
Place: Technical University Eindhoven. See here for details.

Speaker: Fernando de Oliveira Filho, CWI 
Title: Fast matrix multiplication (II) 
Date/Location: 20-01-2006, 11h00, CWI-Amsterdam, Room M280 


Speaker: Fernando de Oliveira Filho, CWI 
Title: Fast matrix multiplication (I) 
Date/Location: 16-12-2005, 13h00, CWI-Amsterdam, Room M279 

Speaker: Benny Mounits, Technion, Haifa 
Title: Upper bounds on sizes of codes via association schemes and linear programming 
Date/Location: 02-12-2005, 10h00, CWI-Amsterdam, Room M279 

No seminar on 18-11-2005 
DIAMANT/EIDMA symposium 2005, Mierlo, November 16-18, 2005.

Speaker: Erik Jan van Leeuwen, CWI 
Title: Better approximation schemes on disk graphs 
Date/Location: 04-11-2005, 13h00, CWI-Amsterdam, Room M279 

Speaker: Frank Vallentin, CWI 
Title: Computing the minimum distortion for embedding distance-transitive graphs in the Euclidean space 
Date/Location: 21-10-2005, 13h00, CWI-Amsterdam, Room H220 (NIKHEF building) 

Speaker: Nebojsa Gvozdenovic, CWI 
Title: Approximating the chromatic number of a graph by semidefinite programming 
Date/Location: 07-10-2005, 13h00, CWI-Amsterdam, Room M279