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: Mar 20
About
Undergraduate
Graduate
Research
People
News & Events
Theory Seminar: Mar 20
Event date: Friday, March 20, 2015, at 11:10 AM
Location: GB221
Speaker: Jan Pich, University of Toronto
Title: Complexity Theory in Bounded Arithmetic
Abstract:
We will discuss the provability of complexity theoretic conjectures in weakfragments of arithmetic like Cook's theory PV. These theories are actuallyquite powerful in the sense that they can formalize a lot of computationalcomplexity, e.g. PV proves the PCP theorem. However, to prove a statement in such a theory one typically needs to provide an efficient algorithm witnessing its existential quantifiers. In some cases this might lead to acontradiction. Notably, the question whether such a witnessing exists isoften of independent interest.In this talk we will focus on circuit lower bounds. It is not known how toshow that polynomial circuit lower bounds for SAT are unprovable in PV butunder certain hardness assumptions we can obtain the unprovability essentially for any theory weaker than PV (in terms of provably total functions). Unconditionally quasipolynomial circuit lower bounds for SAT are unprovablein the theory V0.