Institute for Mathematical Sciences                                        Programs & Activities

 

   
 

Online registration form
    Register

 

Enquiries

      General

      Scientific aspects


   

Workshop 3 on Approximation Algorithms

(15 - 19 Feb 2016)

Venue: IMS Auditorium
Venue: Centre for Quantum Technologies, Seminar Room, S15-03-15 (18 Feb 2016, 4pm-5pm)


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

 

Monday, 15 Feb 2016

09:45am - 10:00am

Registration

10:00am - 11:00am

Hypercontractivity and sum of squares (PDF)
Ryan O'Donnell, Carnegie Mellon University, USA

11:00am - 11:30am

--- Group Photo & Coffee Break ---

11:30am - 12:30pm

Beyond worst case analysis of graph partitioning algorithms (PDF)
Konstantin Makarychev, Microsoft Research, USA

12.30pm - 02:30pm

--- Lunch Reception at IMS ---

02:30pm - 03:30pm

Factor-11/8 NP-inapproximability for 2-variable linear equations (PDF)
Sangxia Huang, École Polytechnique Fédérale de Lausanne, Switzerland

03:30pm - 04:00pm

--- Coffee Break ---

04:00pm - 05:00pm

Free Discussion

Tuesday, 16 Feb 2016

09:45am - 10:00am

Registration

10:00am - 11:00am

Almost optimal sum of squares lower bounds for planted clique I (PDF)
Pravesh Kothari, The University of Texas at Austin, USA

11:00am - 11:30am

--- Coffee Break ---

11:30am - 12:30pm

Almost optimal sum of squares lower bounds for planted clique II (PDF)
Pravesh Kothari, The University of Texas at Austin, USA

12.30pm - 02:30pm

--- Lunch Break ---

02:30pm - 03:30pm

Limitations of monogamy, Tsirelson-type bounds, and other semidefinite programs in quantum information (PDF)
Anand Natarajan, Massachusetts Institute of Technology, USA

03:30pm - 04:00pm

--- Coffee Break ---

04:00pm - 05:00pm

Free Discussion

Wednesday, 17 Feb 2016

09:45am - 10:00am

Registration

10:00am - 11:00am

Fast algorithms for optimising over unentangled states: SDP hierarchies vs eps-nets I
Fernando Brandao, Microsoft Research, USA

11:00am - 11:30am

--- Coffee Break ---

11:30am - 12:30pm

Fast algorithms for optimising over unentangled states: SDP hierarchies vs eps-nets II
Fernando Brandao, Microsoft Research, USA

12.30pm - 02:30pm

--- Lunch Break ---

02:30pm - 05:00pm

Free Discussion

06:30pm - 07:30pm

Public Lecture: Evolution and Computation

Speaker: Nisheeth Vishnoi, École Polytechnique Fédérale de Lausanne, Switzerland

Venue: NUS University Hall Auditorium, Lee Kong Chian Wing, Level 2
           21 Lower Kent Ridge Road, Singapore 119077

Thursday, 18 Feb 2016

09:45am - 10:00am

Registration

10:00am - 11:00am

Towards the sliding scale conjecture: old and new PCP constructions (PDF)
Prahladh Harsha, Tata Institute of Fundamental Research, India

11:00am - 11:30am

--- Coffee Break ---

11:30am - 12:30pm

Classical approximation algorithms for quantum constraint satisfaction problems (PDF)
Sevag Gharibian, Virginia Commonwealth University, USA

12.30pm - 02:30pm

--- Lunch Break ---

02:30pm - 03:30pm

Free Discussion

03:30pm - 04:00pm

--- Coffee Break ---

04:00pm - 05:00pm

Random words, longest increasing subsequences, and quantum PCA
Ryan O'Donnell, Carnegie Mellon University, USA
Venue: Centre for Quantum Technologies, Seminar Room, S15-03-15
           Block S15, Faculty of Science, 3 Science Drive 2, Singapore 117543

Friday, 19 Feb 2016

09:45am - 10:00am

Registration

10:00am - 11:00am

Nonuniform graph partitioning with unrelated weights
Yury Makarychev, Toyota Technological Institute at Chicago, USA

11:00am - 11:30am

--- Coffee Break ---

11:30am - 12:30pm

Rounding the sparsest cut SDP on low threshold-rank graphs (PDF)
Rakesh Venkat, Tata Institute of Fundamental Research, India

12.30pm - 02:30pm

--- Lunch Break ---

02:30pm - 05:00pm

Free Discussion


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

top
Best viewed with IE 7 and above