Organizing Committee
Abstract

Semidefinite programming is playing an ever increasing role in many areas of computer science and mathematics, including complexity theory, approximation algorithms for hard graph problems, discrete geometry, machine learning, and extremal combinatorics.

This workshop will bring together researchers from these different fields. The goal is to explore connections, learn and share techniques, and build bridges.

Image courtesy of Philipp Rostalski

Confirmed Speakers & Participants

  • Speaker
  • Poster Presenter
  • Attendee

Workshop Schedule

Monday, February 10, 2014
TimeEventLocationMaterials
8:30 - 8:55Registration: Semidefinite Programming and Graph Algorithms Workshop11th Floor Collaborative Space 
8:55 - 9:00Welcome - ICERM Director11th Floor Lecture Hall 
9:00 - 9:45The Moment-LP and Moment-SOS approaches in polynomial optimization - Jean Lasserre, Centre National de la Recherche Scientifique (CNRS)11th Floor Lecture Hall
10:00 - 10:30Coffee Break11th Floor Collaborative Space 
10:30 - 11:15Rounding Sum of Squares Relaxations - Boaz Barak, Microsoft Research11th Floor Lecture Hall
11:30 - 12:15TBA - Jonathan Kelner, Massachusetts Institute of Technology11th Floor Lecture Hall 
12:30 - 2:30Break for Lunch  
2:30 - 3:15Convergence of SDP hierarchies using kernel based methods - Stephanie Wehner, National University of Singapore11th Floor Lecture Hall
3:30 - 4:00Coffee Break10th Floor Collaborative Space 
4:00 - 4:45Vertical versus horizontal Poincare inequalities - Assaf Naor, New York University11th Floor Lecture Hall
5:00 - 6:30Welcome Reception11th Floor Collaborative Space 
Tuesday, February 11, 2014
TimeEventLocationMaterials
9:00 - 9:45Expander flows, Geometric embeddings and Graph Partitioning - Claire Mathieu, Ecole Normale Superieure11th Floor Lecture Hall
10:00 - 10:30Coffee Break11th Floor Collaborative Space 
10:30 - 11:15Towards a Better Approximation of Sparsest Cut? - Sanjeev Arora, Princeton University11th Floor Lecture Hall 
11:30 - 12:15Going off the grid - Benjamin Recht, University of California, Berkeley11th Floor Lecture Hall
12:30 - 2:30Break for Lunch  
2:30 - 3:15On the existence of 0/1 polytopes with high semidefinite extension complexity - Sebastian Pokutta, Georgia Institute of Technology11th Floor Lecture Hall 
3:30 - 4:00Coffee Break11th Floor Collaborative Space 
4:00 - 4:45Semidefinite programming and discrepancy- Recent developments - Nikhil Bansal, Technische Universiteit Eindhoven11th Floor Lecture Hall
Wednesday, February 12, 2014
TimeEventLocationMaterials
9:00 - 9:45TBA - Michel Goemans, Massachusetts Institute of Technology11th Floor Lecture Hall 
10:00 - 10:30Coffee Break11th Floor Collaborative Space 
10:30 - 11:15Semidefinite programming bounds for codes and anticodes in Cayley graphs - Frank Vallentin, Universitat zu Koln11th Floor Lecture Hall
11:30 - 12:15Near optimal deterministic volume estimation via M-ellipsoids - Daniel Dadush, New York University11th Floor Lecture Hall
12:30 - 12:40Group Photo11th Floor Lecture Hall 
12:40 - 2:30Break for Lunch  
2:30 - 3:15A Non-Convex Optimization Approach to Network Localization- Polynomial-Time Computability and Rigidity-Theoretic Implications - Anthony Man-Cho So, Chinese University of Hong Kong11th Floor Lecture Hall
3:00 - 5:20Optimization Algorithms for Planar Graphs (ongoing semester course) - Phil Klein, Brown University and Claire Mathieu, Brown University10th Floor Classroom 
3:30 - 4:00Coffee Break11th Floor Collaborative Space 
4:00 - 4:45Graph parameters from entangled games and quantum zero-error communication. - Jop Briet, New York University11th Floor Lecture Hall 
7:00 - 8:30Poster Session and Dessert Reception11th Floor Lecture Hall and Collaborative Space 
Thursday, February 13, 2014
TimeEventLocationMaterials
9:00 - 9:45Three-dimensional Structure Determination of Molecules without Crystallization- from Electron Microscopy to Semidefinite Programming - Amit Singer, Princeton University11th Floor Lecture Hall
10:00 - 10:30Coffee Break11th Floor Collaborative Space 
10:30 - 11:15On the power of Symmetric SDP relaxations - Prasad Raghavendra, University of California, Berkeley11th Floor Lecture Hall
11:30 - 12:15Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs - Yuan Zhou, Carnegie Mellon University11th Floor Lecture Hall 
12:30 - 2:30Break for Lunch  
2:30 - 3:15SDP and eigenvalue bounds for the graph partition problem - Renata Sotirov, Tilburg University, Netherlands11th Floor Lecture Hall
3:25 - 3:25Please take a moment to complete the survey that was distributed by email.  
3:30 - 4:00Coffee Break11th Floor Collaborative Space 
4:00 - 4:45TBA - Pablo Parrilo, Massachusetts Institute of Technology11th Floor Lecture Hall 
Friday, February 14, 2014
TimeEventLocationMaterials
9:00 - 9:45Faster SDP hierarchy solvers for local rounding algorithms - Ali Kemal Sinop, IAS11th Floor Lecture Hall
10:00 - 10:30Coffee Break11th Floor Collaborative Space 
10:30 - 11:15Latent Variable Graphical Model Selection via Convex Optimization - Venkat Chandrasekaran, California Institute of Technology11th Floor Lecture Hall 
11:30 - 12:15A Combinatorial, Primal-Duel approach to Semidefinite Programs - Satyen Kale, Yahoo!11th Floor Lecture Hall 
12:30 - 2:30Break for Lunch  
1:00 - 2:15Theory Seminar -ongoing semester seminar- Improving Christofides' Algorithm for the s-t Path Traveling Salesman Problem - David Shmoys, Cornell University11th Floor Classroom 
2:30 - 3:30Learning how to rank via forbidden patterns - semirankings and the Erdos-Hajnal Conjecture - Krzysztof Choromanski, Google Inc.11th Floor Lecture Hall
3:30 - 4:00Coffee Break11th Floor Collaborative Space 

Associated Semester Workshops

Network Science and Graph Algorithms
Network Science and Graph Algorithms Image
Stochastic Graph Models
Stochastic Graph Models Image

Research Clusters

Lecture Videos

Going off the grid

Benjamin Recht
University of California, Berkeley
February 11, 2014

The Moment-LP and Moment-SOS approaches in polynomial optimization

Jean Lasserre
Centre National de la Recherche Scientifique (CNRS)
February 10, 2014