RFG on Applications of Convex Geometry, Winter Session.
Here is the schedule of lectures and talks given :
Jan 10 - 12 : Speaker - Jesus.
Introduction to Linear Programming
Jan 17 : Martin Luther King Day - off.
Jan 19 : Speaker - Amitabh.
Applications of LP - Max Flow-Min Cut, Von Neumann's Minimax, TUM matrices for exact IP, Approximation Algorithms for Vertex Cover
Jan 24-26-31 : Speaker - Jesus.
Recent hot topics in LP
Feb 2 : Break.
Feb 7-9 : Speaker - Amitabh.
Paper on NulLA and polynomial optimization by DeLoera, Malkin and Parillo
. The paper is available here :
Computations with Polynomial Equations and Inequalities Arising in Combinatorial Optimization
Feb 14-16 : Speaker - Amitabh.
Short Introduction to SDP. Lovasz's Theta Bodies for approximating Stable Set, Max-Cut Goemans-Williamson Algorithm
. Here are the papers related to this :
On the Shannon Capacity of a Graph
Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems using Semidefinite Programming
Feb 23 : Speaker - Amitabh.
Preliminaries for Amirali's talk : Basic notions of convexity, Sum of Squares and Nonnegativity of polyniomials. Starting NP-Completeness
Here are the two papers related to this :
NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems
.
A convex polynomial that is not sos-convex
.
Feb 28 : Speaker - Amitabh.
Finish NP-Completeness. Start with
Theta bodies on Polynomial Ideals
by Gouveia, Parillo, Thomas
March 2-7 : Speaker - Amitabh.
Continue with
Theta bodies on polynomial ideals
March 9 : Elchanan Mossel's talk on Social Choice Theory
March 14 : Speaker - Mohamed.
Finishing up
Theta bodies on polynomial ideals
March 15 : Speaker - Amirali Ahmadi.
Talk on "Deciding Polynomial Convexity is NP-hard". Here is a link to the
abstract
March 16 : Amirali Ahmadi.
Talk on "SOS-Convexity: an algebraic relaxation for convexity of polynomials". Here is a link to the
abstract