Georgia Institute of Technology College of Sciences

We generalize the existing reduction mechanism due to Braun, Pokutta and Zink (2014)for linear programming problems and semidefinite programming problems in two ways 1) relaxing the requirement of affineness2) extending to fractional optimization problems As applications we prove several new LP-hardness and SDP-hardnessresults, e.g., for the (non-uniform) Sparsest Cut problem with bounded treewidth on the supply graph, the Balanced Separator problem with bounded treewidth onthe demand graph, the Max Cut problem and the Matching problem on 3-regular graphs.We also provide a new, very strong Lasserre integrality gapfor the Independent Set problem, which is strictly greater than thebest known LP approximation, showing that the Lasserre hierarchydoes not always provide the tightest SDP relaxation.Joint work with Gabor Braun and Sebastian Pokutta.