Home

Semidefinite Programming and Graph Algorithms (February 10-14, 2014)


Organizing Committee
  • Monique Laurent
    (CWI and Tilburg University, Netherlands)
  • David Phillips
    (United States Naval Academy)
  • David Steurer
    (Cornell University)
  • Kilian Weinberger
    (Washington University, St Louis)


[Image courtesy of Philipp Rostalski]
Description

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.

  • Amir Ali Ahmadi
    (Massachusetts Institute of Technology)
  • Ian Alevy
    (Brown University)
  • Sanjeev Arora *
    (Princeton University)
  • Chen Avin
    (Ben Gurion University of the Negev)
  • Nikhil Bansal *
    (Technische Universiteit Eindhoven)
  • Boaz Barak *
    (Microsoft Research)
  • Emanuel Ben-David
    (Columbia University)
  • Ioana Bercea
    (University of Maryland)
  • Tejal Bhamre
    (Princeton University)
  • Milan Bradonjic
    (Lucent Technologies Bell Laboratories)
  • Xavier Bresson
    (Université de Lausanne)
  • Jop Briët*
    (New York University)
  • Venkat Chandrasekeran*
    (California Institute of Technology)
  • Krzysztof Choromanski *
    (Google Inc.)
  • Mihai Cucuringu
    (University of California, Los Angeles)
  • Daniel Dadush*
    (New York University)
  • Lorenzo De Stefani
    (Università di Padova)
  • Thomas Dickerson
    (Brown University)
  • Hamza Fawzi
    (Massachusetts Institute of Technology)
  • Arjuna Flenner
    (Naval Air Warfare Center)
  • Kyle Fox
    (University of Illinois at Urbana-Champaign)
  • Eli Fox-Epstein
    (Brown University)
  • Nathanaël François
    (Université de Paris VII (Denis Diderot))
  • Cristina Garcia
    (Claremont Graduate University)
  • Nicolas Garcia
    (Carnegie Mellon University)
  • Michel Goemans *
    (Massachusetts Institute of Technology)
  • Sebastian Gruler
    (Universität Konstanz)
  • Steven Heilman
    (Courant Institute of Mathematical Sciences)
  • Huiyi Hu
    (University of California, Los Angeles)
  • Blake Hunter
    (University of California, Los Angeles)
  • Sameer Iyer
    (Brown University)
  • Satyen Kale *
    (Yahoo! Inc.)
MondayFebruary 10, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
8:30 - 8:55Registration: Semidefinite Programming and Graph Algorithms Workshop11th Floor Collaborative Space
8:55 - 9:00WelcomeICERM Director11th Floor Lecture Hall
9:00 - 9:45The Moment-LP and Moment-SOS approaches in polynomial optimizationJean Lasserre, Centre National de la Recherche Scientifique (CNRS)11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee Break11th Floor Collaborative Space
10:30 - 11:15Rounding Sum of Squares RelaxationsBoaz Barak, Microsoft Research11th Floor Lecture Hall
PDF
PDF
11:30 - 12:15TBAJonathan Kelner, Massachusetts Institute of Technology11th Floor Lecture Hall
12:30 - 2:30Break for Lunch
2:30 - 3:15Convergence of SDP hierarchies using kernel based methodsStephanie Wehner, National University of Singapore11th Floor Lecture Hall
PDF
3:30 - 4:00Coffee Break10th Floor Collaborative Space
4:00 - 4:45Vertical versus horizontal Poincare inequalitiesAssaf Naor, New York University11th Floor Lecture Hall
PDF
PDF
5:00 - 6:30Welcome Reception11th Floor Collaborative Space

TuesdayFebruary 11, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45Expander flows, Geometric embeddings and Graph PartitioningClaire Mathieu, Ecole Normale Superieure11th Floor Lecture Hall
PDF
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
PDF
11:30 - 12:15Going off the gridBenjamin Recht, University of California, Berkeley11th Floor Lecture Hall
PDF
PDF
12:30 - 2:30Break for Lunch
2:30 - 3:15On the existence of 0/1 polytopes with high semidefinite extension complexitySebastian Pokutta, Georgia Institute of Technology11th Floor Lecture Hall
3:30 - 4:00Coffee Break11th Floor Collaborative Space
4:00 - 4:45Semidefinite programming and discrepancy- Recent developmentsNikhil Bansal, Technische Universiteit Eindhoven11th Floor Lecture Hall
PDF
PDF

WednesdayFebruary 12, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45TBAMichel 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 graphsFrank Vallentin, Universitat zu Koln11th Floor Lecture Hall
PDF
PDF
11:30 - 12:15Near optimal deterministic volume estimation via M-ellipsoidsDaniel Dadush, New York University11th Floor Lecture Hall
PDF
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 ImplicationsAnthony Man-Cho So, Chinese University of Hong Kong11th Floor Lecture Hall
PDF
PDF
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

ThursdayFebruary 13, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45Three-dimensional Structure Determination of Molecules without Crystallization- from Electron Microscopy to Semidefinite ProgrammingAmit Singer, Princeton University11th Floor Lecture Hall
PDF
PDF
10:00 - 10:30Coffee Break11th Floor Collaborative Space
10:30 - 11:15On the power of Symmetric SDP relaxationsPrasad Raghavendra, University of California, Berkeley11th Floor Lecture Hall
PDF
11:30 - 12:15Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphsYuan Zhou, Carnegie Mellon University11th Floor Lecture Hall
12:30 - 2:30Break for Lunch
2:30 - 3:15SDP and eigenvalue bounds for the graph partition problemRenata Sotirov, Tilburg University, Netherlands11th Floor Lecture Hall
PDF
PDF
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:45TBAPablo Parrilo, Massachusetts Institute of Technology11th Floor Lecture Hall

FridayFebruary 14, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45Faster SDP hierarchy solvers for local rounding algorithmsAli Kemal Sinop, IAS11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee Break11th Floor Collaborative Space
10:30 - 11:15Latent Variable Graphical Model Selection via Convex OptimizationVenkat Chandrasekaran, California Institute of Technology11th Floor Lecture Hall
11:30 - 12:15The Matrix Multiplicative Weights Algorithm- Applications to SDP and Online Matrix PredictionSatyen Kale, Yahoo!11th Floor Lecture Hall
PDF
PDF
12:30 - 2:30Break for Lunch
1:00 - 2:15Theory Seminar -ongoing semester seminar- Improving Christofides' Algorithm for the s-t Path Traveling Salesman ProblemDavid Shmoys, Cornell University11th Floor Classroom
PDF
2:30 - 3:30Learning how to rank via forbidden patterns - semirankings and the Erdos-Hajnal ConjectureKrzysztof Choromanski, Google Inc.11th Floor Lecture Hall
PDF
3:30 - 4:00Coffee Break11th Floor Collaborative Space