Computer Science Thesis Proposal

Friday, September 16, 2016 - 11:00am to 12:00pm

Location:

Traffic21 Classroom 6501 Gates & Hillman Centers

Speaker:

EUIWOONG LEE, Ph.D. Student http://www.cs.cmu.edu/~euiwoonl/

For More Information, Contact:

deb@cs.cmu.edu

This thesis tries to expand the frontiers of approximation algorithms, with respect to the range of optimization problems as well as mathematical tools for algorithms and hardness. We show tight approximabilities for various fundamental problems in combinatorial optimization. We organize these problems into three categories — new and applied constraint satisfaction problems (CSP), hypergraph coloring under promise, and graph covering/cut problems. Conceptually extending the traditional problems like CSP, coloring, and covering, they include important open problems in approximation algorithms. Some problems are inspired by other areas of theory of computing including coding theory and computational economics. We also try to present new techniques to prove tight approximabilities. For coloring and cut problems, we provide a unified framework to show strong hardness results, encompassing many previous techniques for related problems and yielding new results. For CSPs, our new techniques often stem from a combination of ideas from multiple traditional techniques that have been developed separately. Thesis Committee:Venkatesan Guruswami (Chair)Anupam GuptaRyan O'DonnellR. RaviOla Svensson (EPFL) Copy of Thesis Summary

Keywords:

Thesis Proposal