Semidefinite and Matrix Methods for Optimization and Communication
(18 January - 28 February 2016)

 

Organizing Committee · Visitors and Participants · Overview · Activities · Venue

 

Organizing Committee

 

• Rahul Jain (National University of Singapore)
• Hartmut Klauck (Nanyang Technological University and National University of Singapore)
• Troy Lee (Nanyang Technological University and National University of Singapore)
• Miklos Santha (Université Paris Diderot - Paris 7 and National University of Singapore)
  
  

Visitors and Participants

 

• Overseas visitors
• Local visitors
• Graduate students
• Registered local participants

 

Overview

The program will cover topics in combinatorial optimization, approximation algorithms, and communication complexity and links connecting these areas.  A common approach to hard combinatorial optimizations is to look at relaxations of these problems as linear or semidefinite programs.  On the algorithmic side, one hopes to show that these relaxations can provide good approximations to the optimal value.  On the hardness side, one hopes to show that (ever more complicated) relaxations are still far from the true value.

The program will look at both sides of this coin.  On the algorithmic side, we will look at approaches using hierarchies of linear/semidefinite programming relaxations and also approaches using epsilon nets.  This workshop will also explore the intriguing use of quantum information in approximation algorithms.

On the hardness side, we will look at lower bounds on extended formulation size.  There has been exciting recent progress showing lower bounds on both linear and positive semidefinite extended formulation size, but many open problems remain.  This area has close connections to communication complexity, both classical and quantum.

Finally, we will look at communication complexity itself and recent progress on the log rank conjecture.

Activities

• Workshop 1 on Log Rank Conjecture: 18 - 22 Jan 2016
• Workshop 2 on Positive Semidefinite Rank: 1 - 5 Feb 2016
• Workshop 3 on Approximation Algorithms: 15 - 19 Feb 2016
• Public Lecture

  Date:	Wednesday, 17 February 2016
  Venue:	NUS University Hall Auditorium Lee Kong Chian Wing, Level 2 21 Lower Kent Ridge Road, Singapore 119077
  06:30pm - 07:30pm	Evolution and Computation Nisheeth Vishnoi, École Polytechnique Fédérale de Lausanne, Switzerland

  
  
  

Please note that our office will be closed on the following public holiday.

- 8 - 9 Feb 2016, Chinese New Year

 

Venue

 

• IMS Auditorium
   

Organizing Committee · Visitors and Participants · Overview · Activities · Venue