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
> NOV 27: Theory CS Seminar
About
Undergraduate
Graduate
Research
People
News & Events
NOV 27: Theory CS Seminar
Event date: Friday, November 27, 2009, at 11:00 AM
Location: Galbraith Bldg, Rm. 244
Speaker: Irenee Briquel
Laboratoire de l Informatique du Parallelisme - ENS
Lyon and Fields Institure
Title: Lower bounds on the tree-width of boolean formulas
Abstract: To a boolean formula can be associated the clause graph, where the
vertices are the variables, and where two variables are linked in the
graph when they belong to the same clause.
In a previous work, Pascal Koiran and Klaus Meer studied the link
between the complexity of the formula and the tree-width of the clause
graph - for short, the tree-width of the formula. They found an algorithm to compute efficiently polynomials associated with boolean formulas of bounded tree-width.
To estimate the limits of this method, it is interesting to look for lower bounds on the tree-width of boolean formulas, establishing that the previously mentioned algorithm is not efficient for the associated polynomials.
To find lower bounds on the tree-width, we show a link between this notion and the communication complexity of the boolean formula. We show that lower bounds on the communication complexity can transpose to the tree-width, and explore the possibilities of this method. This is based on joint work with Pascal Koiran and Klaus Meer.