Computing approximate solutions to NP-hard optimization problems is an idea that is attractive both in theory and practice. Semidefinite programming (SDP) has become an indispensable tool in this area. It has led to new and better algorithms, and recently, thanks in part to the PI's prior work, more combinatorial algorithms that actually avoid SDP. The connections of SDP to high-dimensional geometry, metric embeddings, fourier transforms, and probabilistically checkable proofs are also at the center of some of the exciting work in theoretical computer science in recent years.
The project will work on ideas to (a) apply SDP to design new approximation algorithms for a host of problems, such as graph coloring, metric traveling salesman, graph partitioning, vertex cover; (b) use insights from SDP to design efficient combinatorial algorithms; (c) apply SDP insights (and a ``constructive'' version of SDP duality discovered recently by the PI and his student) to new settings such as decoding error-correcting codes, compressed sensing, and analysing network algorithms and swarm algorithms; (d) explore connections between SDPs, high-dimensional geometry, fourier transforms, and probabilistically checkable proofs.
SDP-inspired primal-dual approaches are an important new extension of traditional approaches based upon linear-programming duality, and developing their uses promises to have transformative impact. Development of new approximation algorithms for central problems like graph partitioning and metric TSP may also transform the field.
During this project new courses will be designed at the undergraduate and graduate level to teach these new ideas in an accessible way.
