Workshops

Fall 2017

Hierarchies, Extended Formulations and Matrix-Analytic Techniques

Nov 6, 2017 to Nov 9, 2017

Return to event »

All events take place in the Calvin Lab auditorium

Monday, November 6th, 2017
9:30 am–9:50 am		Coffee and Check-In
9:50 am–10:00 am		Opening Remarks
10:00 am–11:00 am		Constructing Extended Formulations Volker Kaibel, Otto-von-Guericke-Universität Magdeburg
11:00 am–11:30 am		Break
11:30 am–12:00 pm		Small (Explicit) Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits Sam Fiorini, Université Libre de Bruxelles
12:00 pm–12:30 pm		Computing the Nucleolus of Weighted Cooperative Matching Games in Polynomial Time Kanstantin Pashkovich, University of Waterloo
12:30 pm–2:30 pm		Lunch
2:30 pm–3:00 pm		A Lower Bound on the Positive Semidefinite Rank of Convex Bodies Hamza Fawzi, University of Cambridge
3:00 pm–3:30 pm		Bounds for Matrix Factorization Ranks via Semidefinite Programming and Tracial Polynomial Optimization Monique Laurent, CWI Amsterdam
3:30 pm–4:00 pm		Break
4:00 pm–4:30 pm		Symmetric Sums of Square Annie Raymond, University of Washington
4:30 pm–5:00 pm		Sparse Polynomial Interpolation: Compressed Sensing, Super-resolution, or Prony? Jean-Bernard Lasserre, CNRS

Tuesday, November 7th, 2017
9:30 am–10:00 am		Coffee and Check-In
10:00 am–11:00 am		Pseudocalibration and SoS Lower Bounds Sam Hopkins, Cornell University and Aaron Potechin, Institute for Advanced Study
11:00 am–11:30 am		Break
11:30 am–12:00 pm		Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere Vijay Bhattiprolu, Carnegie Mellon University
12:00 pm–12:30 pm		Spectral Aspects of Symmetric Matrix Signings Alexandra Kolla, University of Illinois at Urbana-Champaign
12:30 pm–2:30 pm		Lunch
2:30 pm–3:00 pm		From Weak to Strong LP Gaps for all CSPs Madhur Tulsiani, Toyota Technological Institute at Chicago
3:00 pm–3:30 pm		Break
3:30 pm–4:00 pm		LP, SOCP, and Optimization-Free Approaches to Polynomial Optimization Amir Ali Ahmadi, Princeton University
4:00 pm–4:30 pm		Matrix Completion and Sums of Squares Greg Blekherman , Georgia Institute of Technology
4:30 pm–5:00 pm		SOS and the Dreaded Bit-complexity Ryan O'Donnell, Carnegie Mellon University
5:00 pm–6:00 pm		Reception

Wednesday, November 8th, 2017
9:30 am–10:00 am		Coffee and Check-In
10:00 am–10:30 pm		Maximizing Sub-determinants and Connections to Permanents and Inequalities on Stable Polynomials Mohit Singh, Georgia Institute of Technology
10:30 am–11:00 am		Spectrahedra and Directional Derivatives of Determinants James Saunderson, Monash University
11:00 am–11:30 am		Break
11:30 am–12:30 pm		Counting and Optimization Using Stable Polynomials Nima Anari, Stanford University
12:30 pm–2:30 pm		Lunch
2:30 pm–3:30 pm		Independent Set Polytopes: Query vs. Communication Perspective Mika Göös, University of Toronto
3:30 pm–4:00 pm		Break
4:00 pm–4:30 pm		Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs Raghu Meka, UCLA
4:30 pm–5:30 pm		Short Announcements and Open Problems

Thursday, November 9th, 2017
9:30 am–10:00 am		Coffee and Check-In
10:00 am–11:00 am		From Proofs to Algorithms for Machine Learning Problems David Steurer, Cornell University
11:00 am–11:30 am		Break
11:30 am–12:00 pm		Nonnegative Polynomials, Nonconvex Polynomial Optimization, and Applications to Learning Georgina Hall, Princeton University
12:00 pm–12:30 pm		Fast Spectral Algorithms from Sum-of-Squares Analyses Tselil Schramm, UC Berkeley
12:30 pm–2:30 pm		Lunch
2:30 pm–3:00 pm		Computing the Independence Polynomial in Shearer's Region for the LLL Nick Harvey, University of British Columbia
3:00 pm–3:30 pm		Quantum Entanglement, Sum of Squares, and the Log Rank Conjecture Pravesh Kothari, Princeton University