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
> Theory Seminar - April 27
About
Undergraduate
Graduate
Research
People
News & Events
Theory Seminar - April 27
Event date: Friday, April 27, 2012, at 11:10 AM
Location: BA5256
Speaker: Dieter van Melkebeek
University of Wisconsin-Madison
Title: Locality from Circuit Lower Bounds
Abstract:
Expressibility and inexpressibility in logics over finite structures plays an important role in various areas of computer science, such as databases, automated verification, and descriptive complexity theory. One potent tool for proving inexpressibility results is the notion of locality. Informally, a logical query is local if it can be answered by only looking at small, localized parts of the input. Once a class of queries is known to be local it is often simple to prove a particular query cannot be expressed in this class by showing that the query is not local. For example, each first-order query over graphs only depends on the neighborhoods of the arguments up to some constant distance. On the other hand, the query checking whether two vertices are connected cannot be answered by considering only the neighborhoods of those two vertices up to a constant distance. These two facts imply that connectivity is not expressible in first-order logic.
In this presentation we show how to use circuit lower bounds to establish upper bounds on the locality of logics. In particular, we consider a logic closely related to the complexity class AC0 of all languages that can be decided by nonuniform families of polynomial-size constant-depth circuits. We exploit the known lower bounds for parity on constant-depth circuits to obtain a tight upper bound for the locality of queries expressible in that logic.
As the topic bridges between ``theory A'' and ``theory B'', I will try to provide enough background so as to make the presentation accessible to both communities.
Joint work with Matthew Anderson, Nicole Schweikardt, and Luc Segoufin.