Skip to main navigation
Skip to Content
Computer Science
University of Toronto
Quercus
Student Support
Contact
About
History of U of T Computer Science
Computer Science at U of T Mississauga
Computer Science at U of T Scarborough
Employment Opportunities for Faculty/Lecturers
How to Find Us
Contact
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
@DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> Theory Seminar - Jan 10
About
Undergraduate
Graduate
Research
People
News & Events
Theory Seminar - Jan 10
Event date: Friday, January 10, 2014, at 11:10 AM
Location: GB248
Speaker: Per Austrin, KTH Royal Institute of Technology, Stockholm
Title: (2+eps)-SAT is NP-hard
Abstract:
We prove the following hardness result for a natural promise variant of the classical CNF-satisfiability problem: given a CNF-formula where each clause has width w and the guarantee that there exists an assignment satisfying at least g = w/2-1 literals in each clause, it is NP-hard to find a satisfying assignment to the formula (that sets at least one literal to true in each clause). On the other hand, when g = w/2, it is easy to find a satisfying assignment via simple generalizations of the
algorithms for 2-SAT.
We also prove that given a (2k+1)-uniform hypergraph that can be 2-colored such that each edge has perfect balance (at most k+1 vertices of either color), it is NP-hard to find a 2-coloring that avoids a monochromatic edge. In other words, a set system with discrepancy 1 is hard to distinguish from a set system with worst possible discrepancy.
(Joint work with Venkatesan Guruswami and Johan HÃ¥stad)