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 for "Semidefinite Programming and Graph Algorithms"
Image courtesy of Philipp Rostalski

Confirmed Speakers & Participants

  • Speaker
  • Poster Presenter
  • Attendee
  • Virtual Attendee

Workshop Schedule

Monday, February 10, 2014
TimeEventLocationMaterials
8:30 - 8:55am ESTRegistration: Semidefinite Programming and Graph Algorithms Workshop11th Floor Collaborative Space 
8:55 - 9:00am ESTWelcome - ICERM Director11th Floor Lecture Hall 
9:00 - 9:45am ESTThe 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:30am ESTCoffee Break11th Floor Collaborative Space 
10:30 - 11:15am ESTRounding Sum of Squares Relaxations - Boaz Barak, Microsoft Research11th Floor Lecture Hall
11:30 - 12:15pm ESTTBA - Jonathan Kelner, Massachusetts Institute of Technology11th Floor Lecture Hall 
12:30 - 2:30pm ESTBreak for Lunch  
2:30 - 3:15pm ESTConvergence of SDP hierarchies using kernel based methods - Stephanie Wehner, National University of Singapore11th Floor Lecture Hall
3:30 - 4:00pm ESTCoffee Break10th Floor Collaborative Space 
4:00 - 4:45pm ESTVertical versus horizontal Poincare inequalities - Assaf Naor, New York University11th Floor Lecture Hall
5:00 - 6:30pm ESTWelcome Reception11th Floor Collaborative Space 
Tuesday, February 11, 2014
TimeEventLocationMaterials
9:00 - 9:45am ESTExpander flows, Geometric embeddings and Graph Partitioning - Claire Mathieu, Ecole Normale Superieure11th Floor Lecture Hall
10:00 - 10:30am ESTCoffee Break11th Floor Collaborative Space 
10:30 - 11:15am ESTTowards a Better Approximation of Sparsest Cut? - Sanjeev Arora, Princeton University11th Floor Lecture Hall 
11:30 - 12:15pm ESTGoing off the grid - Benjamin Recht, University of California, Berkeley11th Floor Lecture Hall
12:30 - 2:30pm ESTBreak for Lunch  
2:30 - 3:15pm ESTOn the existence of 0/1 polytopes with high semidefinite extension complexity - Sebastian Pokutta, Georgia Institute of Technology11th Floor Lecture Hall 
3:30 - 4:00pm ESTCoffee Break11th Floor Collaborative Space 
4:00 - 4:45pm ESTSemidefinite programming and discrepancy- Recent developments - Nikhil Bansal, Technische Universiteit Eindhoven11th Floor Lecture Hall
Wednesday, February 12, 2014
TimeEventLocationMaterials
9:00 - 9:45am ESTTBA - Michel Goemans, Massachusetts Institute of Technology11th Floor Lecture Hall 
10:00 - 10:30am ESTCoffee Break11th Floor Collaborative Space 
10:30 - 11:15am ESTSemidefinite programming bounds for codes and anticodes in Cayley graphs - Frank Vallentin, Universitat zu Koln11th Floor Lecture Hall
11:30 - 12:15pm ESTNear optimal deterministic volume estimation via M-ellipsoids - Daniel Dadush, New York University11th Floor Lecture Hall
12:30 - 12:40pm ESTGroup Photo11th Floor Lecture Hall 
12:40 - 2:30pm ESTBreak for Lunch  
2:30 - 3:15pm ESTA 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:20pm ESTOptimization Algorithms for Planar Graphs (ongoing semester course) - Phil Klein, Brown University and Claire Mathieu, Brown University10th Floor Classroom 
3:30 - 4:00pm ESTCoffee Break11th Floor Collaborative Space 
4:00 - 4:45pm ESTGraph parameters from entangled games and quantum zero-error communication. - Jop Briet, New York University11th Floor Lecture Hall 
7:00 - 8:30pm ESTPoster Session and Dessert Reception11th Floor Lecture Hall and Collaborative Space 
Thursday, February 13, 2014
TimeEventLocationMaterials
9:00 - 9:45am ESTThree-dimensional Structure Determination of Molecules without Crystallization- from Electron Microscopy to Semidefinite Programming - Amit Singer, Princeton University11th Floor Lecture Hall
10:00 - 10:30am ESTCoffee Break11th Floor Collaborative Space 
10:30 - 11:15am ESTOn the power of Symmetric SDP relaxations - Prasad Raghavendra, University of California, Berkeley11th Floor Lecture Hall
11:30 - 12:15pm ESTHardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs - Yuan Zhou, Carnegie Mellon University11th Floor Lecture Hall 
12:30 - 2:30pm ESTBreak for Lunch  
2:30 - 3:15pm ESTSDP and eigenvalue bounds for the graph partition problem - Renata Sotirov, Tilburg University, Netherlands11th Floor Lecture Hall
3:25 - 3:25pm ESTPlease take a moment to complete the survey that was distributed by email.  
3:30 - 4:00pm ESTCoffee Break11th Floor Collaborative Space 
4:00 - 4:45pm ESTTBA - Pablo Parrilo, Massachusetts Institute of Technology11th Floor Lecture Hall 
Friday, February 14, 2014
TimeEventLocationMaterials
9:00 - 9:45am ESTFaster SDP hierarchy solvers for local rounding algorithms - Ali Kemal Sinop, IAS11th Floor Lecture Hall
10:00 - 10:30am ESTCoffee Break11th Floor Collaborative Space 
10:30 - 11:15am ESTLatent Variable Graphical Model Selection via Convex Optimization - Venkat Chandrasekaran, California Institute of Technology11th Floor Lecture Hall 
11:30 - 12:15pm ESTA Combinatorial, Primal-Duel approach to Semidefinite Programs - Satyen Kale, Yahoo!11th Floor Lecture Hall 
12:30 - 2:30pm ESTBreak for Lunch  
1:00 - 2:15pm ESTTheory Seminar -ongoing semester seminar- Improving Christofides' Algorithm for the s-t Path Traveling Salesman Problem - David Shmoys, Cornell University11th Floor Classroom 
2:30 - 3:30pm ESTLearning how to rank via forbidden patterns - semirankings and the Erdos-Hajnal Conjecture - Krzysztof Choromanski, Google Inc.11th Floor Lecture Hall
3:30 - 4:00pm ESTCoffee Break11th Floor Collaborative Space 

Associated Semester Workshops

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

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