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