Seminars 2011-2015

N&O seminars and the speakers from 2011 to 2015.


Speaker: Malwina Duda (Alpen-Adria Universität Klagenfurt)
Title: Exact Subgraph relaxations for MAX-CUT
Date/location: Tuesday 24 November, 11h00, room L016

Speaker: Daniel Dadush (CWI)
Title: On the Geometry of Linear Programming
Date/location: Friday 13 November, 10h00, room L016

Speaker: Maria Dostert (Koln)
Title: New upper bounds for the density of translative packings of superballs
Date/location: Wednesday 04 November, 11h00, room L016

Speaker: Thijs Laarhoven (TU/E)
Title: Sieving for shortest lattice vectors using nearest neighbor search techniques
Date/Location: Wednesday 07 October, 11h00, L016

Speaker: Viresh Patel (UvA)
Title: Hamilton cycles in Robust Expanders
Date/Location: Wednesday 30 September, 11h00, L016

Speaker: Roxana Hess (LAAS-CNRS, Toulouse)
Title: Semidefinite approximations of the polynomial abscissa
Date/Location: Wednesday 23 September, 11h00, L016

Speaker: David Roberson (NTU & CQT)
Title: Unique Vector Colorings: Theory and Applications
Date/Location: Wednesday 09 September, 11h00, L016

Speaker: George Rabanca (CUNY)
Title: Improved Approximation Algorithms for Weighted 2-Path Partitions
Date/Location: Tuesday 01 September, 16h00, L016

Speaker: Divesh Aggarwal (EPFL)
Title: Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling
Date/Location: Wednesday 26 August, 11h00, L016

Speaker: Seeun Umboh (UW Madison)
Title: Online Network Design Algorithms via Hierarchical Decomposition
Date/Location: Friday 03 July, 15h00, L016

Speaker: Teresa Piovesan (CWI)
Title: Round elimination in exact communication complexity
Date/Location: Wednesday 24 June, 11h00, L016

Speaker: David de Laat (TU Delft)
Title: Moment methods in energy minimization
Date/Location: Wednesday 22 April, 11h00, room L16

Speaker: Dan Garber (Technion - Israel Institute of Technology)
Title: Projection-free Learning and Optimization
Date/location:Wednesday 25 March, 11h00, room L16

Speaker: Sangxia Huang (Stockholm KTH)
Title: Finding Good Assignments for Satisfiable Instances of Boolean CSPs
Date/location: Friday, February 13, 11h00, room L16

Speaker: Shinichi Tanigawa (RIMS Kyoto University)
Title: Characterizations of the rigidity of graphs
Date/location: Wednesday, February 4, 11h00, room L16

Speaker: Daniel Dadush (CWI Amsterdam)
Title: On the Shadow Simplex Method for Curved Polyhedra
Date/location: Wednesday, January 21, 11h00, room L16

Speaker: Vasilis Gkatzelis (Stanford University)
Title: Mechanism Design For Fair Division
Date/location: Monday, January 12, 11h00, room L016 


Speaker: Rene Sitters (VU Amsterdam)
Title: Polynomial time approximation schemes for the traveling repairman and other minimum latency problems
Date/location: Tuesday December 9, 16h00, room L120.

Speaker: Arne Reimers (CWI Amsterdam)
Title: TBA
Date/location: Tuesday November 25, 16h00, room L16.

Speaker: Emmanouil Pountourakis (Northwestern University)
Title: Mechanisms for Hiring a Matroid Base without Money
Date/location: Thursday, October 9, 16h00, room L016.

Speaker: Tillman Weisser (University Konstanz)
Title: Certificates for nonnegativity
Date/location: Wednesday 1 October, 11h00, room L016.

Speaker: Matteo Seminarotti
Title: QAP and recognition of Robinsonian matrices
Date/location: Tuesday 30 September, 11h00, room TBA.

Speaker: Andreas Feldmann  (University of Waterloo, Canada)

Title: A (1+ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
Date/location: Tuesday, September 16, 16h00, room L016.

Speaker: Antonios Varvitsiotis (Centre for Quantum Technologies, NUS Singapore)
Title: Two Characterizations of Nonlocal Games with Perfect Maximally Entangled Strategies
Date/location: Friday, September 5, 11h00, room L016.

Speaker: Siddharth Barman (California Institute of Technology)
Title: Approximating Caratheodory’s Theorem and Nash Equilibria
Date/location: Thursday, September 4, 16h00, room L016.

Speaker: Angelina Vidali (Duke University, USA)
Title: Mechanism desing for crowdsourcing in networks
Date/location: Wednesday, July 9, 14h00, room L016.

Speaker: Christopher Pütz (FU Berlin, Germany)
Title: Price of Anarchy under Uncertainty
Date/location: Tuesday, July 8, 14h00, room L016.

Speaker: Anke van Zuylen (College of William & Mary, USA)
Title: On some recent MAX SAT approximation algorithms
Date/location: Wednesday, July 2, 16h00, room L016.

Event: Algorithmic Game Theory Mini-Symposium

Speakers: Krzysztof Apt (CWI & UvA), Edith Elkind (Universirty of Oxford, UK), Stefano Leonardi (Sapienza University Rome, Italy)
Date/location: Monday, June 16, 10:30-14:15, room L016.
A detailed program can be found here

After the mini-symposium, Bart de Keijzer will defend his PhD thesis at the VU University Amsterdam, De Boelelaan 1105, Aula, 15:45-16:45

Speaker: Neil Walton (University of Amsterdam)
Title: Incentivized Optimal Advert Assignment via Utility Decomposition
Date/location: Tuesday, May 27, 16h00, room L016.

Speaker: Seth Pettie (University of Michigan, USA)
Title: 3SUM is Subquadratic
Date/location: Tuesday, April 22, 16h00, room L016.

Speaker: Marcus Klaas (UvA)
Title: Computing Optimal Tolls with Arc Restrictions and Heterogeneous Players
Date/location: Thursday, February 20, 11h00, room L016.

Speaker: Sabine Burgdorf (EPFL Lausanne)
Title: Tracial polynomial optimization and its relation to the embedding conjecture of Connes
Date/location: Tuesday, February 18, 16h00, room L016.

Speaker: Marcello Pelillo Ca’ (Foscari University, Venice, Italy)
Title: Grouping Games: Finding Clusters in Graphs, Digraphs and Hypergraphs
Date/location: Wednesday, February 5, 11h00, room L016.

Speaker: Marcin Dziubinski (Institute of Informatics, Warsaw University)
Title: Decentralized defence in networks
Date/location: Wednesday, January 29, 11h00, room L016.


Speaker: Mona Rahn (CWI)
Title: Bounding the inefficiency of altruism through social contribution games
Date/location: Tuesday, November 26, 16h00, room L016.

Speaker: Teun Janssen (TU Delft)
Title: Noise minimization on houses around airports
Date/location: Tuesday, November 5, 16h00, room L016.

Speaker: Irving van Heuven van Staereling (VU Amsterdam)
Title: Optimizing Bid Strategies in Sponsored Search Auctions
Date/location: Tuesday, October 1, 16h00, room L016.

Speaker: Martin van der Schans (Ortec-Finance)
Title: A Heuristic for Completing Covariance And Correlation Matrices
Date/location: Tuesday, September 10, 11h00, room TBA.

Speaker: Matteo Seminaroti (University La Sapienza, Roma)
Title: A Lot-Sizing based algorithm for demand side management and optimal electric vehicle charging
Date/location: Monday, July 15, 16h00, room L016

Speaker: Huyen Phong (University of Limoges)
Title: Some inexact proximal regularization algorithm for unconstrained optimization
Date/location: Monday, July 15, 11h00, room L016

Speaker: Carles Padro (NTU Singapore, on leave from UPC, Barcelona)
Title: Secret Sharing, Rank Inequalities and Information Inequalities
Date/location: Wednesday 19 June, 16h00, room L016

Speaker: Katherine Edwards (Princeton University, USA)
Title: Bounding the fractional chromatic number of K_Delta-free graphs
Date/location: Tuesday, June 11, 11h00, L016

Speaker: Vijay Vazirani (Georgia Institute of Technology, USA)
Title: New (Practical) Complementary Pivot Algorithms for Market Equilibria
Date/location: Wednesday, May 29, 11h00, L016

Speaker: Vijay Vazirani (Georgia Institute of Technology, USA)
Title: Matching - A New Proof for an Ancient Algorithm
Date/location: Tuesday, May 28, 15h00, L017

Speaker: Francesco Mambelli (University of Bologna)
Title: Heuristic Algorithms for Max-Cut problems
Date/location: Tuesday, April 23, 15h00, L016

Speaker: Philip Brinkmann (Freie Universität Berlin)
Title: Minkowski Sums of Triangles - The Burton Conjecture
Date/location: Tuesday, April 9, 11h00, L016

Speaker: Maria Polukarova (University of Southampton)
Title: Considerate Equilibrium
Date/location: Monday, March 25, 16h00, L120

Workshop: 4th SDP days
Date/Location: March 21, 22, room L120

Speaker: Peter Dickinson (University Groningen)
Title: Applications and Approximations for Set-semidefinite Optimisation
Date/Location: Tuesday 5 March, 11h00, room L120

Speaker: Nikhil Devanur (Microsoft Research, Redmond)
Title: Tatonnement Beyond Gross Substitutes? Gradient Descent to the Rescue
Date/location: Tuesday 26 February, 15h00, L016

Speaker: Nicole Immorlica (Northwestern University)
Title: The Degree of Segregation in Social Networks
Date/location: Tuesday 26 February, 13h30, L016

Speaker: Louis Esperet (Grenoble)
Title: Relaxed coloring of graphs of bounded genus
Date/Location: Tuesday 5 February, 11h00, room L016

Speaker: Ross Kang (CWI)
Title: The distance-t chromatic index
Date/location: Tuesday 22 January, 11h00, room L016


Speaker: Onno Zoeter (Xerox Research Centre Europe, France)
Title: Optimal Learning While Selling and A Large Scale Demand Based Pricing Experiment
Date/location: Wednesday 13 December, 11h00, L016

Speaker: Peter Csikvari (Alfred Renyi Institute of Mathematics & Eotvos Lorand University, Budapest)
Title: Benjamini-Schramm Continuity Of Root Moments Of Graph Polynomials
Date/location: Tuesday 30 October, 13h30, L016

Speaker: Kostas Kollias (MPI Saarbruecken, Germany)
Title: Restoring Pure Equilibria to Weighted Congestion Games
Date/location: Friday 26 October, 11h30, L016

Speaker: Marieke Musegaas (Tilburg University, The Netherlands)
Title: Sequencing Situations and Personnel Scheduling Problems 
Date/location: Wednesday 17 October, 14h00, L016

Speaker: Mona Rahn (University of Bonn, Germany)
Title: Truthful randomized mechanisms for combinatorial auctions
Date/location: Monday 15 October, 14h00, L016

Speaker: Andrea Simonetto (TU Delft)
Title: Distributed Optimization for Robotic Networks
Date/Location: Tuesday 9 October, 11h00, L016

Speaker: Xavier Perez-Gimenez (MPI Saarbrucken)
Title: Asymptotic enumeration of sparse strongly connected digraphs by vertices and edges
Date/Location: Friday 7 September, 16h00, L120

Speaker: Erik Jan van Leeuwen (Sapienza University of Rome, Italy)
Title: An Algorithmic Decomposition Theorem for Claw-Free Graphs and its Applications 
Date/location: Tuesday 28 August, 16h00, L016

Speaker: Carla Michini (University La Sapienza, Rome)
Title: The Hirsch Conjecture for the Fractional Stable Set Polytope
Date/location: Tuesday 12 June, 16h00, L016

Speaker: Teresa Piovesan (University of Maastricht)
Title: Rooted phylogenetic networks: computing hybridization number via softwired clusters
Date/location: Wednesday 6 June, 14h00, room L016

Speaker: Piotr Krysta (University of Liverpool)
Title: Online Mechanism Design (Randomized Rounding on the Fly)
Date/location: Tuesday, 17 April, 16h00, room L120

Speaker: Neil Walton (University of Amsterdam)
Title: Utility optimization in queueing networks
Date/location: Monday 26 March, 16h00, room L120

Speaker: Samuel Fiorini (Universite Libre de Bruxelles)
Title: Linear vs. Semidefinite Extended Formulations: Exponential  Separation and Strong Lower Bounds                                    
Date/location: Wednesday 7 March, 11h00, room L016

Speaker: Gauthier van den Hove (CWI)                                 
Title: Recursive Programming: A Clarification
Date/location: Tuesday 6 March, 16h00, room L016

Speaker: Vangelis Markakis (Athens University of Economics and Business)    
Title: On Worst-Case Allocations in the Presence of Indivisible Goods              
Date/location: Tuesday 7 February, 16h00, room L017

Speaker: Jan Voss (University of Cologne, Germany)
Title: A systemtheoretic model for cooperative games (and more) 
Date/location: Thursday 26 January, 11h00, room L016

Speaker: Amir Jabbari (Norwegian University of Science and Technology, Norway)
Title: Application of Data Processing for Autonomous Control in Communication and Nano-Communication Networks 
Date/location: Tuesday 24 January, 11h00, room L016


Event: Dutch Network on Computational Game Theory Day
Date/location: Friday 2 December, 11:00-17:00, room L017

Speaker: Stefan Canzar (CWI)
Title: On Tree-Constrained Matchings
Date/location: Tuesday 29 November, 11h00, room L016

Speaker: Venkatesan Guruswami (Carnegie Mellon University, Pittsburgh)
Title: Lasserre hierarchy, higher eigenvalues, and graph partitioning
Date/location: Friday 25 November, 11h00, room L017

Speaker: Riccardo Colini Baldeschi (Sapienza University of Rome)
Title: Auctions with Budgets
Date/location: Tuesday 22 November, 11h00, room L016

Speaker: Anke van Zuylen (MPI for Informatics, Germany)
Title: The Subtour LP for the Traveling Salesman Problem I: A Proof of the Boyd-Carr Conjecture
Date/location: Tuesday 4 October, 11h00, room L016

Speaker: Felix Rodrigues (Universidade Federal do Rio Grande do Sul, Brazil)
Title: On the Smoothed Price of Anarchy of the Traffic Assignment Problem
Date/location: Wednesday 28 September, 11h00, room L017

Speaker: Ross Kang (Durham University)
Title: Glauber dynamics mixes rapidly on graphs of bounded tree-width
Date/location: Tuesday 6 September, 13h30, room L016

Speaker: Willem-Jan van Hoeve (Carnegie Mellon University, Pittsburgh)
Title: Decision Diagrams for Discrete Optimization
Date/location: Tuesday 6 September, 11h00, room L016

Speaker: Morteza Zadimoghaddam (MIT)
Title: Submodular Secretary Problem and Extensions
Date/location: Thursday 11 August, 13h30, room L016

Speaker: Caroline Jagtenberg (Utrecht University)
Title: Lower bounds for Smith’s rule in stochastic machine scheduling
Date/location: Thursday 14 July, 13h30, room L016

Event: Applications of Semidefinite Programming Date/location: Friday July 1st, room L120, CWI-Amsterdam
Additional lectures: Thursday June 30, room L120

Speaker: Leslie Lamport (Microsoft Corporation, CA, USA)
Title: The PlusCal Algorithm Language
Date/location:  Thursday June 16, 16h00, Turing room, CWI-Amsterdam

Speaker: Marianne Nagy (Tilburg University)
Title: On semidefinite programming bounds for graph bandwidth
Date/location:  Wednesday June 8, 13h30, room L016, CWI-Amsterdam

Speaker: Rene Sitters (VU Amsterdam)
Title: TSP on Cubic and Subcubic Graphs
Date/location:  Wednesday June 8, 11h00, room L016, CWI-Amsterdam

Speaker: Peter Rossmanith (RTWH Aachen, Germany)
Title:  A Practical Approach to Solve Hard Optimization Problems of Graphs with Small Treewidth
Date/location:  Thursday 28 April, 15h30, room L016, CWI-Amsterdam

Speaker: Troels Bjerre Sørensen (University of Warwick, UK)
Title:  Risk when playing for chips
Date/location:  Thursday 28 April, 14h00, room L016, CWI-Amsterdam

Speaker:  Suzanne van der Ster (VU University Amsterdam)
Title: Mixed-criticality scheduling
Date/location: Thursday 21 April, 16h00, room L017, CWI-Amsterdam 

Speaker: Guido Schäfer (CWI and VU University Amsterdam)
Title: On the Inefficiency of Altruistic Games
Date/location: Monday 18 April, 14h00, room L017, CWI-Amsterdam 

Speaker: Amy Greenwald (Brown University and CWI) 
Title: Autonomous Bidding Agent Strategies for Ad Auctions
Date/location: Monday 11 April, 12h30, room L017, CWI-Amsterdam 

Speaker: Sunil Simon (CWI) 
Title: Algorithmic issues in imperfect information games of infinite
Date/location: Monday 4 April, 14h00, room L017, CWI-Amsterdam 

Speaker: Vincent Conitzer (Duke University and CWI) 
Title: Computational Methods for Acting Strategically
Date/location: Monday 14 March, 14h00, room L120, CWI-Amsterdam 

Speaker: Bart de Keijzer (CWI) 
Title: The Strong Price of Anarchy in Bottleneck Congestion Games
Date/location: Monday 28 February, 14h00, room L016, CWI-Amsterdam 

Speaker: Victor Naroditskiy (University of Southampton, UK) and Mingyu Guo (Liverpool University, UK) 
Title: Better Redistribution with Inefficient Allocation in Multi-Unit Auctions (M. Guo) and Optimal Payments in Strategy-Proof Mechanisms (V. Naroditskiy)
Date/location: Tuesday 15 February, 10:30-12:00, room L016, CWI-Amsterdam 

Speaker: Miguel Navascues (Universidad Complutense de Madrid) 
Title: Noncommutative polynomial optimization 
Date/location: Monday 14 February, 16h00, room L016, CWI-Amsterdam 

Speaker: Eva Tardos (Cornell University)
Title:  Price of Anarchy for Adword Auctions
Date/location: Friday 11 February, 14:00, room L017, CWI-Amsterdam 

Speaker: Mohit Singh (McGill University, Canada) 
Title: Online Submodular function maximization subject to matroid constraints 
Date/location: Friday 21 January, 14:00, room L016, CWI-Amsterdam

Speaker: Nikhil Bansal (IBM TJ Watson) 
Title: Algorithms for Discrepancy Minimization 
Date/location: Friday 21 January, 11:00, room L017, CWI-Amsterdam