Institute for Mathematical Sciences                                        Programs & Activities

 

   
 

Online registration form
    Register

 

Enquiries

      General

      Scientific aspects


   

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

 

 

 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


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

- 8 - 9 Feb 2016, Chinese New Year


 

 Venue

 

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

top
Best viewed with IE 7 and above