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
> JAN 28: Theory CS Seminar
About
Undergraduate
Graduate
Research
People
News & Events
JAN 28: Theory CS Seminar
Event date: Thursday, January 28, 2010, at 1:00 PM
Location: Pratt Building Rm. 266
Speaker: Dimitris Achlioptas
University of California at Santa Cruz and University of Athens
Title: Algorithmic Phase Transitions in Constraint Satisfaction Problems
Abstract: For many Constraint Satisfaction Problems by now we have a good understanding of the largest constraint density for which solutions exist. At the same time, though, all known polynomial-time algorithms for these problems stop finding solutions at much smaller densities. We study this phenomenon by examining how the different sets of solutions evolve as constraints are added. We prove in a precise mathematical sense that, for each problem studied, the barrier faced by algorithms corresponds to a phase transition in that problem's solution-space geometry. Roughly speaking, at some problem-specific critical density, the set of solutions shatters and goes from being a single giant ball to exponentially many, well-separated, tiny pieces. All known polynomial-time algorithms work in the ball regime, but stop as soon as the shattering occurs. Besides giving a geometric view of the solution space of random CSPs our results provide novel constructions of one-way functions.
Joint work with Amin Coja-Oghlan.