Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
Why Study CS at U of T
Career Options
History of DCS
Giving to DCS
Computer Science at UofT Mississauga
Computer Science at UofT Scarborough
Contact
Employment Opportunities for Faculty/Lecturers
How to Find Us
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate students
Current Graduate students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
Newsletter: @DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
>
FEB 9: Theory CS Seminar
> FEB 25: Theory CS Seminar
About
Undergraduate
Graduate
Research
People
News & Events
FEB 25: Theory CS Seminar
Event date: Thursday, February 25, 2010, at 2:00 PM
Location: Pratt Building Rm. 266
Speaker: Yi Wu
Carnegie Mellon University
Title: Approximability of NP hard problems in Learning and CSP
Abstract: An α-approximation algorithm is an algorithm guaranteed to output a solution that is within an α ratio of the optimal solution. We are interested in the following question: Given an NP-hard optimization problem, what is the best approximation guarantee that any polynomial time algorithm could achieve?
We mostly focus on studying the approximability of two classes of NP-hard problems: Constraint Satisfaction Problems (CSPs) and Computational Learning Problems. Our research in the field of CSPs is to show that certain Semidefinite Programming (SDP) algorithms are the optimal polynomial time approximation algorithm; our work in the learning area is to prove that tasks are inherently hard; i.e., there is no better-than-trivial algorithm for the problems.
We will describe results on the approximability of several problems from these two classes such as Max-Cut, Satisfiable 3-CSPs and agnostic learning of monomials and low degree PTFs.